【C++】—— set 与 multiset
【C++】—— map 与 set
1 序列式容器和关联式容器
前面我们已经接触过 STL 中的部分容器如：string、vector、list、deque、array等，这些容器统称为序列式容器，因为他们是逻辑结构为线性序列的数据结构（物理结构不一定为线性），两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，它依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。关联式容器中的元素是按关键字来保存和访问的。关联式容器有 map / set 系列和 unordered_map / unordered_set 系列
本文讲解的 m a p map map 和 s e t set set 底层是红黑树，红黑树是一颗平衡二叉搜索树。 s e t set set 是 k e y key key 搜索场景的结构， m a p map map 是 k e y key key / v a l u e value value 搜索场景的结构
2 set 系列的使用
2.1 set 和 multiset 参考文档
https://legacy.cplusplus.com/reference/set/
2.2 set 类的介绍
set 的声明如下：
template<classT,// set::key_type/value_typeclassCompare= less<T>,// set::key_compare/value_compareclassAlloc= allocator<T>// set::allocator_type>classset;• s e t set set 的声明如上，T 就是 s e t set set 底层关键字的类型
• s e t set set 默认要求 T 支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第⼆个模版参数
• s e t set set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
• ⼀般情况下，我们都不需要传后两个模版参数。
• s e t set set 底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是⾛的搜索树的中序，所以是有序的。
• 前面部分我们已经学习了 v e c t o r vector vector / l i s t list list 等容器的使用，STL 容器接口设计，高度相似，所以这里我们就不再⼀个接口⼀个接口的介绍，而是直接带着大家看文档，挑比较重要的接口进行介绍。
这里库中的模板参数用的是 T，个人认为这里设计的不够好，既然是搜索，那用 Key 更好，我们可以将其当成是 Key，虽然库中没用这个名字。
2.3 set 的迭代器和构造
s e t set set 的迭代器是一个双向迭代器：
// 正向迭代器 iterator begin(); iterator end();// 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();s e t set set 主要构造方式如下：
- 无参构造
explicitset(const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());- 迭代器区间构造
template<classInputIterator>set(InputIterator first, InputIterator last,const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());- 拷贝构造
set(const set& x);set(const set& x,const allocator_type& alloc);- 列表构造
set(initializer_list<value_type> il,const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());2.4 set的增删查
首先要注意的是： s e t set set 是不支持改的，因为 s e t set set 属于关联式容器，对齐进行数据修改会破坏它的存储结构
2.4.1 insert
// 单个数据插⼊，如果已经存在则插⼊失败 pair<iterator,bool>insert(const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊voidinsert(initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊template<classInputIterator>voidinsert(InputIterator first, InputIterator last);这里 v a l u e value value_ t y p e type type 就是 T，即 Key；此外 k e y key key_ t y p e type type 也是 T。这里这么设计是为了和后面的 m a p map map 保持一致
返回值 pair<iterator, bool> 这里还不需要用到它，暂不解释，在后面的 m a p map map 部分会详细介绍。
举个栗子：
intmain(){// 去重+升序排序 set<int> s;// 去重+降序排序（给⼀个⼤于的仿函数）//set<int, greater<int>> s; s.insert(5); s.insert(2); s.insert(7); s.insert(5); set<int>::iterator it = s.begin();while(it != s.end()){// error C3892: “it”: 不能给常量赋值// *it = 1; cout <<*it <<" ";++it;} cout << endl;。 return0;}运行结果：
可以看到， s e t set set 是不允许两个相同的值进行插入的，即 s e t set set 有去重功能。并且s e t set set 是不允许修改的，*it = 1 进行修改会报错。
默认 s e t set set 走的是升序，如果想走降序，可以传递一个大于的仿函数。迭代器的底层走的是一个中序遍历
s e t set set 支持列表插入
intmain(){ set<int> s; s.insert({2,8,3,9,2});for(auto e : s){ cout << e <<" ";} cout << endl;return0;}
s e t set set 除了支持整型，其他任意类型都是可以的（如果该类型不支持比较，需自己传递仿函数），我们以 s t r i n g string string 为例
intmain(){// void insert(initializer_list<value_type> il);// 构造出临时对象再拷贝构造，优化成直接构造 set<string> strset ={"sort","insert","add"};// 遍历string⽐较ascll码⼤⼩顺序遍历的for(auto& e : strset){ cout << e <<" ";}return0;}2.4.2 find 与 erase
const_iterator find(const value_type& val)const; iterator find(const value_type& val);f i n d find find返回的是对应位置的迭代器，如果没找到就返回 end()
- 迭代器删除
iterator erase(const_iterator position);- Key删除
size_type erase(const value_type& val);s i z e size size_ t y p e type type 是一个无符号整型，即 u n s i g n e d unsigned unsigned i n t int int，返回的是删除元素的个数。
如果删除成功，表示删除了一个值，返回 1；删除失败，表示没有删除值，返回 0
为什么这里不用 b o o l bool bool 呢？这里是为了兼容 m u l t i s e t multiset multiset。
m u l t i s e t multiset multiset 中允许相同数插入的，可能 e r a s e erase erase 多个相同的值，这时就不能用 b o o l bool bool 了
- 迭代器区间删除
iterator erase(const_iterator first, const_iterator last);栗子：
intmain(){ set<int> s ={4,2,7,2,8,5,9};for(auto e : s){ cout << e <<" ";} cout << endl;// 删除最⼩值 s.erase(s.begin());for(auto e : s){ cout << e <<" ";} cout << endl;// 直接删除xint x; cin >> x;int num = s.erase(x);if(num ==0){ cout << x <<"不存在！"<< endl;}for(auto e : s){ cout << e <<" ";} cout << endl;// 直接查找在利⽤迭代器删除x cin >> x;auto pos = s.find(x);if(pos != s.end()){ s.erase(pos);}else{ cout << x <<"不存在！"<< endl;}for(auto e : s){ cout << e <<" ";} cout << endl;return0;}
s e t set set 进行删除同样会导致迭代器失效
i )
此时删除的是叶子结点 1，删除后迭代器中的指针为野指针，迭代器失效。
ii )
删除 6 节点。它要与 5 或 7 节点进行交换，删除进行删除。虽然此时迭代器中的指针并不是野指针，但它原来的意义已经改变了，我们也认为是迭代器失效。
而且从我们的角度，我们不知道这个节点是直接删除还是替代法删除。
p s ps ps：对二叉搜索树的删除有不理解的小伙伴可移步至：【C++】—— 二叉搜索树
2.4.3 count
c o u n t count count 的功能是返回 v a l u e value value_ t y p e type type 在容器中的个数
size_type count(const value_type& val)const;c o u n t count count 是给 m u l t i s t multist multist 设计的，因为对 s e t set set 而言 c o u n t count count 要么返回 1 要么返回 0，并没有什么意义。但对于 m u l t i s e t multiset multiset 就不一样， m u l t i s e t multiset multiset 是允许多个相同值存在的
我们可以用 c o u n t count count 来判断一个 K e y Key Key 在不在，在的话返回的是 1，不在返回 0。
而且用 c o u n t count count 来判断往往比 f i n d find find 更方便，因为 f i n d find find 返回的是迭代器，迭代器 != end() 才是找到了
intmain(){ set<int> s ={4,2,7,2,8,5,9};// 利⽤count间接实现快速查找int x; cin >> x;if(s.count(x)){ cout << x <<"在！"<< endl;}else{ cout << x <<"不存在！"<< endl;}return0;}2.5 lower_bound 与 upper_bound
// 返回⼤于等于val位置的迭代器 iterator lower_bound(const value_type& val)const;// 返回⼤于val位置的迭代器 iterator upper_bound(const value_type& val)const;l o w e r lower lower_ b o u n d bound bound 与 u p p e r upper upper_ b o u n d bound bound 是为了方便查找一段区间
我们曾经说过，在 STL 里面，只要是迭代器区间必须是左闭右开，这时就可以用到 l o w e r lower lower_ b o u n d bound bound 与 u p p e r upper upper_ b o u n d bound bound
举个栗子：
intmain(){ std::set<int> myset;for(int i =1; i <10; i++) myset.insert(i *10);// 10 20 30 40 50 60 70 80 90for(auto e : myset){ cout << e <<" ";} cout << endl;//// 实现查找到的[itlow,itup)包含[30, 60]区间//// 返回 >= 30（这里即返回30）//auto itlow = myset.lower_bound(30);//// 返回 > 60（这里即返回70）//auto itup = myset.upper_bound(60);// 实现查找到的[itlow,itup)包含[25, 55]区间//对应别人来说，并不知道容器里面是否有 25 和 55，但是查找这段区间的方法与查找30-60的方法一样的// 返回 >= 25（这里即返回30）auto itlow = myset.lower_bound(25);// 返回 > 55（这里即返回60）auto itup = myset.upper_bound(55);// 删除这段区间的值 myset.erase(itlow, itup);for(auto e : myset){ cout << e <<" ";} cout << endl;return0;}2.6 multiset 与 set 的差异
m u l t i s e t multiset multiset 和 s e t set set 的使用基本完全类似，主要区别点在于 m u l t i s e t multiset multiset 支持值冗余，那么 i n s e r t insert insert / f i n d find find / c o u n t count count / e r a s e erase erase 都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。
2.6.1 不再去重
- 相比 s e t set set 不同的是， m u l t i s e t multiset multiset 是排序，但是不去重
intmain(){ multiset<int> s ={4,2,7,2,4,8,4,5,4,9};auto it = s.begin();while(it != s.end()){ cout <<*it <<" ";++it;} cout << endl;return0;}2.6.2 find 返回中序的第一个
- 相比 s e t set set 不同的是， x x x 可能会存在多个， f i n d find find 查找中序遍历的第一个
intmain(){ multiset<int> s ={4,2,7,2,4,8,4,5,4,9};int x; cin >> x;auto pos = s.find(x);while(pos != s.end()&&*pos == x){ cout <<*pos <<" ";++pos;} cout << endl;return0;}简单讲一下他是怎么找到中序的第一个的。
查找依然是 O(logN) 算法的查找，并不是通过中序的方式遍历一遍，这样的话二叉搜索树就失去其意义。
中序的查找规则是：左子树 -> 根 -> 右子树。
假设要找的值是 5 ：如果找到了一个 5 ，就再往其左子树找，因为中序第一个 5 一定是在左树；直到找到了某一个 5 ，并且其左子树没有 5 ，表面当前 5 就是中序的第一个 5。
为什么这里要找中序的第一个呢？ 因为找中序的第一个 x，就可以用迭代器不断++，就可以找到所有的 x
2.6.3 erase 删除所有的 x
- 相比 s e t set set 不同的是， e r a s e erase erase 给值时会
删除所有的 x
intmain(){ multiset<int> s ={4,2,7,2,4,8,4,5,4,9};for(auto e : s){ cout << e <<" ";} cout << endl;int x; cin >> x; s.erase(x);for(auto e : s){ cout << e <<" ";} cout << endl;return0;}2.6.4 count 个数
- 相比 s e t set set 不同的是， c o u n t count count 会返回 x x x 的实际个数
intmain(){ multiset<int> s ={4,2,7,2,4,8,4,5,4,9};for(auto e : s){ cout << e <<" ";} cout << endl;int x; cin >> x; cout << s.count(x)<< endl;return0;}好啦，本期关于 s e t set set 与 m u l t i s e t multiset multiset 的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！
