C++ set 的使用

set 的介绍

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行 排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对 子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。

注意：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放 value，但在底层实际存放的是由构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：$lo{g}_{2}n$
7. set中的元素不允许修改(为什么?)
8. set中的底层使用二叉搜索树(红黑树)来实现。

我们来看看为什么 set 中的元素是不能被修改的！

我们先来看看尝试修改 set 中的元素会不会报错吧！

看到这个报错的提示，你可能会认为 set 底层对存储的数据加上了 const 修饰，然而 C++ 库中的实现并不是这个样子呢！我们来看看源码：

我们可以看到，无论是 const 类型的迭代器还是非 const 类型的迭代器，其实都是 const 类型的迭代器！刚那句这个现象，如果你能够不通过迭代器访问 set 中的元素，还是可以修改的！但是并不建议这么做，Effective c++ 中也是这么说的。

构造函数

set 的使用和 map 差不多！set 支持使用一段迭代器区间来初始化，区间的范围是左开右闭！

#include
#include
#include
using namespace std;

int main()
{
    vector<int> a({1,7,6,3,8,5,2,4});

    set<int> s(a.begin(), a.end());
    //输出：1 2 3 4 5 6 7 8
    for(auto e : s)
        cout << (e) << " ";
    cout << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

但是在平时刷算法题的时候，还是比较喜欢使用无参构造。

pair insert (const value_type& val);

向 set 中插入一个元素。如果插入成功，那么返回值 pair 的 first 就是插入元素对应的迭代器，second 就是 true；如果插入失败，返回值 pair 的 first 就是原 set 中 val 值与插入节点的 val 值相等的元素对应的迭代器，second 就是 false。

#include
#include

using namespace std;

int main()
{
    set<int> s;
    
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(3); //第二次插入 3 会失败，返回 set 中与 3 相等的元素对应的迭代器
    s.insert(4);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

size_t erase (const value_type& val)

删除 set 中值为 val 的节点(set 的底层就是红黑树嘛)。返回删除的节点个数，因为 set 中不存在重复的元素，因此返回值不是 0 就是 1。

#include
#include

using namespace std;

int main()
{
    set<int> s;
    
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);

    cout << s.erase(3) << endl; //输出：1
    cout << s.erase(3) << endl; //输出：0

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

size_t count (const value_type& val) const

统计一个 set 中值为 val 的节点的个数。因为 set 中不存在重复的元素，因此返回值不是 1 就是 0。

iterator find (const value_type& val) const

在 set 中查找值为 val 的节点，查找成功返回对应节点的迭代器，查找失败返回 end 迭代器。

bool empty()

返回 set 是否为空，为空返回 true，反之返回 false。

size_t size() const

返回 set 中节点的个数。

void clear()

删除 set 中的所有节点。

#include
#include

using namespace std;

int main()
{
    set<int> s;
    
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);

    cout << s.count(1) << endl; //输出：1
    cout << s.count(0) << endl; //输出：0

    cout << *(s.find(1)) << endl; //输出：1

    cout << s.empty() << endl; //输出：0

    cout << s.size() << endl; //输出：4

    s.clear();
    cout << s.size() << endl; //输出： 0
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28