【C++】—— set 与 multiset
【C++】—— map 与 set
- 1 序列式容器和关联式容器
- 2 set 系列的使用
- 2.1 set 和 multiset 参考文档
- 2.2 set 类的介绍
- 2.3 set 的迭代器和构造
- 2.4 set的增删查
- 2.4.1 insert
- 2.4.2 find 与 erase
- 2.4.3 count
- 2.5 lower_bound 与 upper_bound
- 2.6 multiset 与 set 的差异
- 2.6.1 不再去重
- 2.6.2 find 返回中序的第一个
- 2.6.3 erase 删除所有的 x
- 2.6.4 count 个数
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 class set;
• 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 主要构造方式如下：
- 无参构造
explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());- 迭代器区间构造
template 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 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 insert(const value_type& val); // 列表插⼊，已经在容器中存在的值不会插⼊ void insert(initializer_list il); // 迭代器区间插⼊，已经在容器中存在的值不会插⼊ template void insert(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 这里还不需要用到它，暂不解释，在后面的 m a p map map 部分会详细介绍。
举个栗子：
int main() { // 去重+升序排序 set s; // 去重+降序排序（给⼀个⼤于的仿函数） //set s; s.insert(5); s.insert(2); s.insert(7); s.insert(5); set::iterator it = s.begin(); while (it != s.end()) { // error C3892: “it”: 不能给常量赋值 // *it = 1; cout set 2,8,3,9,2 }); for (auto e : s) { cout // void insert(initializer_list "sort", "insert", "add" }; // 遍历string⽐较ascll码⼤⼩顺序遍历的 for (auto& e : strset) { cout set 4,2,7,2,8,5,9 }; for (auto e : s) { cout cout cout cout s.erase(pos); } else { cout cout set 4,2,7,2,8,5,9 }; // 利⽤count间接实现快速查找 int x; cin x; if (s.count(x)) { cout cout std::set cout cout multiset 4,2,7,2,4,8,4,5,4,9 }; auto it = s.begin(); while (it != s.end()) { cout multiset 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 multiset 4,2,7,2,4,8,4,5,4,9 }; for (auto e : s) { cout cout multiset 4,2,7,2,4,8,4,5,4,9 }; for (auto e : s) { cout
- 列表构造
- 拷贝构造
- 迭代器区间构造
- 无参构造
