一、set容器的背景及优势

1.引入

set容器时c++标准库中的一个关联容器，存储了一组唯一的元素，并按照一定的顺序排列。它提供了高效的元素查找、插入和删除操作。同map容器一样也是基于红黑树实现的，所以对于查找、插入和删除有对数级的时间复杂度。

set容器存储的元素必须满足以下条件：

• 元素类型必须可以比较大小。
• 元素类型必须可以赋值和复制。
• 存储到 set 容器中的元素，元素值无法修改；

例如，有下面两组键值对数据，第一组中各键值对的键和值不相等，第二组中各键值对的键和值相等：

• 第一组键值对：{<‘s1’, 1>, <‘s2’, 2>, <‘s3’, 3>}
• 第二组键值对：{<‘a’, ‘a’>, <‘b’, ‘b’>, <‘c’, ‘c’>}

常见操作：

2.set性质

和 map 容器不同的是，C++ STL中的 set 容器类模板中未提供 at() 成员函数，也未对 [] 运算符 进行重载。因此，要想访问 set 容器中存储的元素，只能借助 set 容器的迭代器。

下面给出set容器使用示例：

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<char> cSet;          // 创建字符类型的集合
    // 插入元素
    cSet.insert('B');
    cSet.insert('C');
    cSet.insert('D');
    cSet.insert('A');
    cSet.insert('F');
    cout << "old set:" << endl;
    set<char>::iterator it;
    // 循环显示集合中的元素
    for (it = cSet.begin(); it != cSet.end(); ++it)
        cout << *it << endl;
    char cTmp;
    /* 第一次查找 */
    cTmp = 'D';
    it = cSet.find(cTmp);                    // 在集合中查找指定的元素
    cout << "start find: " << cTmp << endl;
    if (it == cSet.end())                    // 没找到元素
        cout << "not found" << endl;
    else                                     // 找到元素
        cout << "found" << endl;
    /* 第二次查找 */
    cTmp = 'G';
    it = cSet.find(cTmp);                    // 查找指定的元素
    cout << "start find: " << cTmp << endl;
    if (it == cSet.end())                    // 没找到元素
        cout << "not found" << endl;
    else                                     // 找到元素
        cout << "found" << endl;
    return 0;
}

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> iSet;      // 创建一个整型集合 iSet
    // 依次向集合中插入 5 个元素
    iSet.insert(1);
    iSet.insert(3);
    iSet.insert(5);
    iSet.insert(7);
    iSet.insert(9);
    cout << "old set:" << endl;
    set<int>::iterator it;
    for (it = iSet.begin(); it != iSet.end(); ++it)   // 输出集合中的元素
        cout << *it << endl;
    it = iSet.begin();
    iSet.erase(++it);   // 删除集合的第 2 个元素（即 3）
    cout << "new set:" << endl;
    for (it = iSet.begin(); it != iSet.end(); ++it)   // 输出集合中的元素
        cout << *it << endl;
    return 0;
}

二、经典例题