信息学奥赛
C++标准模板库（STL）
Set

Set

set 简介

Set（集合）是一种数据结构，用于存储唯一且已排序的元素。

以下是关于 set 的关键点：

  • 唯一性： Set 中不允许存在重复的元素。当尝试插入已存在的元素时，通常不会发生任何改变。
  • 已排序： Set 中的元素会根据某种排序准则（例如，使用 < 运算符，或者用户提供的比较函数）进行排序。
  • 基于键的存储： 尽管 set 主要存储元素本身，但其内部实现是基于元素的键（即元素自身）进行排序和组织的，这与 map 类似，map 存储的是 <key, element> 对并基于键排序。

实现方式：

  • 在标准模板库 (STL) 中，set 通常是使用红黑树（red-black tree）实现的。红黑树是一种自平衡的二叉搜索树，能够保证在最坏情况下，插入和删除等操作的时间复杂度为 O(lg n)，其中 n 是 set 中元素的数量。
  • 为什么选择红黑树？
    • 相对于简单的向量实现，红黑树在插入操作上具有更高的效率。在无序向量中插入需要 O(n) 的时间来检查元素是否已存在。在有序向量中，虽然可以使用二分搜索在 O(lg n) 时间内找到插入位置，但移动后续元素以腾出空间需要 O(n) 的时间。
    • 红黑树通过其平衡特性，保证了插入和删除操作的对数时间复杂度，这使得 set 在需要频繁进行这些操作的场景中非常高效.
  • 迭代器： set 的迭代器以**中序遍历（inorder traversal）**的方式访问树中的节点，从而保证按排序顺序访问 set 中的元素。
  • 常量迭代器： 由于修改 set 中节点的信息可能会破坏其键的排序，因此 set 通常只提供常量迭代器，这意味着不能通过迭代器直接修改 set 中的元素的值。如果需要对 set 中的元素进行修改，通常需要先删除该元素，然后插入修改后的新元素。

常用操作：

Set 提供了一系列成员函数来操作集合，包括但不限于：

  • insert(const T& el): 插入元素 el。如果元素已存在，则不会进行插入（对于 set）。
  • erase(const T& el): 删除值为 el 的元素。
  • find(const T& el) const: 查找值为 el 的元素，如果找到则返回指向该元素的迭代器，否则返回指向 end() 的迭代器。
  • count(const T& el) const: 返回 set 中值为 el 的元素的个数（对于 set，结果要么是 0，要么是 1）。
  • empty() const: 检查 set 是否为空。
  • size() const: 返回 set 中元素的个数。
  • clear(): 移除 set 中的所有元素.
  • begin(): 返回指向第一个元素的迭代器.
  • end(): 返回指向 set 尾部（最后一个元素之后）的迭代器.
  • swap(set<T>& s): 与另一个 set s 交换内容.

简单来说，Set 是一种用于存储唯一且已排序元素的高效数据结构。它通常基于红黑树实现，提供了快速的插入、删除和查找操作。 您可以将其想象成一个不允许重复的书架，书本按照某种规则（例如书名）有序地排列在上面。

set 成员函数

成员函数 描述
insert(const T& el) 将元素 el 插入到 set 中。如果元素已存在，则不进行插入。返回一个 pair<iterator, bool>，其中迭代器指向插入的元素（或已存在的元素），bool 值指示是否成功插入。
erase(const T& el) 从 set 中移除所有等于 el 的元素。返回移除的元素个数。
erase(iterator position) 移除迭代器 position 指向的元素。
erase(iterator first, iterator last) 移除范围 [first, last) 内的所有元素。
clear() 移除 set 中的所有元素。
find(const T& el) const 返回一个指向 set 中第一个等于 el 的元素的迭代器。如果未找到，则返回 end()。
count(const T& el) const 返回 set 中等于 el 的元素个数（对于 set 来说，结果要么是 0，要么是 1）。
empty() const 如果 set 为空，则返回 true，否则返回 false。
size() const 返回 set 中元素的个数。
begin() const 返回指向 set 中第一个元素的迭代器。
end() const 返回指向 set 中最后一个元素之后位置的迭代器。
rbegin() const 返回指向 set 中最后一个元素的逆向迭代器。
rend() const 返回指向 set 中第一个元素之前位置的逆向迭代器。
lower_bound(const T& el) const 返回一个指向 set 中第一个不小于 el 的元素的迭代器。
upper_bound(const T& el) const 返回一个指向 set 中第一个大于 el 的元素的迭代器。
equal_range(const T& el) const 返回一个 pair<iterator, iterator>，表示 set 中所有等于 el 的元素的范围。
swap(set& other) 将当前 set 的内容与另一个 set other 的内容进行交换。

set DEMO 程序 

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main() {
    // 创建一个存储整数的 set
    set<int> mySet;

    // 插入元素
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(4);
    mySet.insert(1); // 插入重复元素，不会生效
    mySet.insert(5);
    mySet.insert(9);

    cout << "Set 中的元素 (升序): ";
    for (int element : mySet) {
        cout << element << " ";
    }
    cout << endl;

    // 检查 set 是否为空
    if (mySet.empty()) {
        cout << "Set 是空的" << endl;
    } else {
        cout << "Set 不是空的，包含 " << mySet.size() << " 个元素" << endl;
    }

    // 查找元素
    int searchElement = 4;
    if (mySet.find(searchElement) != mySet.end()) {
        cout << searchElement << " 在 set 中找到" << endl;
    } else {
        cout << searchElement << " 未在 set 中找到" << endl;
    }

    // 统计元素个数
    int countElement = 1;
    cout << countElement << " 在 set 中出现了 " << mySet.count(countElement) << " 次" << endl;

    // 删除元素
    int eraseElement = 3;
    mySet.erase(eraseElement);
    cout << "移除 " << eraseElement << " 后的 Set: ";
    for (int element : mySet) {
        cout << element << " ";
    }
    cout << endl;

    // 使用迭代器删除元素
    set<int>::iterator it = mySet.find(5);
    if (it != mySet.end()) {
        mySet.erase(it);
        cout << "移除 5 后的 Set: ";
        for (int element : mySet) {
            cout << element << " ";
        }
        cout << endl;
    }

    // 使用 lower_bound 和 upper_bound
    cout << "第一个不小于 4 的元素是: " << *mySet.lower_bound(4) << endl;
    cout << "第一个大于 4 的元素是: " << *mySet.upper_bound(4) << endl;

    // 清空 set
    mySet.clear();
    cout << "清空 Set 后的大小: " << mySet.size() << endl;

    return 0;
}
优先队列 (Priority Queue)Map