跳到主要内容C++ set 与 multiset 容器详解 | 极客日志C++算法
C++ set 与 multiset 容器详解
本文介绍了 C++ STL 中关联式容器 set 与 multiset 的使用。两者底层均基于红黑树实现，元素有序且支持快速查找。set 具有去重特性，不支持修改元素；multiset 允许重复值。文章详细讲解了构造方式、迭代器操作、增删查（insert, find, erase, count）以及区间查找（lower_bound, upper_bound）的具体用法和差异。
容器分类与概述
前面我们已经接触过 STL 中的部分容器如：string、vector、list、deque、array等，这些容器统称为序列式容器，因为他们是逻辑结构为线性序列的数据结构（物理结构不一定为线性），两个位置存储的值之间一般没有紧密的关联关系。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系。关联式容器中的元素是按关键字来保存和访问的。关联式容器有 map / set 系列和 unordered_map / unordered_set 系列。
本文讲解的 map 和 set 底层是红黑树，红黑树是一颗平衡二叉搜索树。set 是 key 搜索场景的结构，map 是 key/value 搜索场景的结构。
2 set 系列的使用
2.1 set 和 multiset 参考文档
https://legacy.cplusplus.com/reference/set/
2.2 set 类的介绍
set 的声明如下：
template<class T,
class Compare = less<T>,
class Alloc = allocator<T>>
class set;
- set 的声明如上，T 就是 set 底层关键字的类型。
- set 默认要求 T 支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数。
- set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
- 一般情况下，我们都不需要传后两个模版参数。
- set 底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是走的搜索树的中序，所以是有序的。
- 前面部分我们已经学习了 vector / list 等容器的使用，STL 容器接口设计高度相似，所以这里我们就不再一个接口一个接口的介绍，而是直接带着大家看文档，挑比较重要的接口进行介绍。
这里库中的模板参数用的是 T，个人认为这里设计的不够好，既然是搜索，那用 Key 更好，我们可以将其当成是 Key，虽然库中没用这个名字。
2.3 set 的迭代器和构造
set 的迭代器是一个 双向迭代器：
iterator begin();
iterator end;
;
;
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
()
reverse_iterator rbegin()
reverse_iterator rend()
explicit set(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
template<class InputIterator>
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 的增删查
首先要注意的是：set 是不支持改的，因为 set 属于关联式容器，对其数据进行修改会破坏它的存储结构。
2.4.1 insert
pair<iterator, bool> insert(const value_type& val);
void insert(initializer_list<value_type> il);
template<class InputIterator>
void insert(InputIterator first, InputIterator last);
这里 value_type 就是 T，即 Key；此外 key_type 也是 T。这里这么设计是为了和后面的 map 保持一致。
返回值 pair<iterator, bool> 这里还不需要用到它，暂不解释，在后面的 map 部分会详细介绍。
int main() {
set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(5);
set<int>::iterator it = s.begin();
while(it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
运行结果：
可以看到，set 是不允许两个相同的值进行插入的，即 set 有去重功能。并且 set 是不允许修改的，*it = 1 进行修改会报错。
默认 set 走的是升序，如果想走降序，可以传递一个大于的仿函数。迭代器的底层走的是一个中序遍历。
int main() {
set<int> s;
s.insert({2, 8, 3, 9, 2});
for(auto e : s) {
cout << e << " ";
}
cout << endl;
return 0;
}
set 除了支持整型，其他任意类型都是可以的（如果该类型不支持比较，需自己传递仿函数），我们以 string 为例：
int main() {
set<string> strset = {"sort", "insert", "add"};
for(auto& e : strset) {
cout << e << " ";
}
return 0;
}
2.4.2 find 与 erase
const_iterator find(const value_type& val) const;
iterator find(const value_type& val);
find 返回的是对应位置的 迭代器，如果没找到就返回 end()。
iterator erase(const_iterator position);
size_type erase(const value_type& val);
size_type 是一个无符号整型，即 unsigned int，返回的是删除元素的个数。
如果删除成功，表示删除了一个值，返回 1；删除失败，表示没有删除值，返回 0。
为什么这里不用 bool 呢？这里是为了兼容 multiset。
multiset 中允许相同数插入的，可能 erase 多个相同的值，这时就不能用 bool 了。
iterator erase(const_iterator first, const_iterator last);
int main() {
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;
int x;
cin >> x;
int num = s.erase(x);
if(num == 0) {
cout << x << "不存在！" << endl;
}
for(auto e : s) {
cout << e << " ";
}
cout << endl;
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;
return 0;
}
ps：对二叉搜索树的删除有不理解的小伙伴可查阅相关数据结构资料。
2.4.3 count
count 的功能是返回 value_type 在容器中的个数。
size_type count(const value_type& val) const;
count 是给 multiset 设计的，因为对 set 而言 count 要么返回 1 要么返回 0，并没有什么意义。但对于 multiset 就不一样，multiset 是允许多个相同值存在的。
我们可以用 count 来判断一个 Key 在不在，在的话返回的是 1，不在返回 0。
而且用 count 来判断往往比 find 更方便，因为 find 返回的是迭代器，迭代器 != end() 才是找到了。
int main() {
set<int> s = {4, 2, 7, 2, 8, 5, 9};
int x;
cin >> x;
if(s.count(x)) {
cout << x << "在！" << endl;
} else {
cout << x << "不存在！" << endl;
}
return 0;
}
2.5 lower_bound 与 upper_bound
iterator lower_bound(const value_type& val) const;
iterator upper_bound(const value_type& val) const;
lower_bound 与 upper_bound 是为了方便查找一段区间。
我们曾经说过，在 STL 里面，只要是迭代器区间必须是左闭右开，这时就可以用到 lower_bound 与 upper_bound。
int main() {
std::set<int> myset;
for(int i = 1; i < 10; i++) myset.insert(i * 10);
for(auto e : myset) {
cout << e << " ";
}
cout << endl;
auto itlow = myset.lower_bound(25);
auto itup = myset.upper_bound(55);
myset.erase(itlow, itup);
for(auto e : myset) {
cout << e << " ";
}
cout << endl;
return 0;
}
2.6 multiset 与 set 的差异
multiset 和 set 的使用基本完全类似，主要区别点在于 multiset 支持值冗余，那么 insert / find / count / erase 都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。
2.6.1 不再去重
- 相比 set 不同的是，multiset 是排序，但是不去重。
int main() {
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;
return 0;
}
2.6.2 find 返回中序的第一个
- 相比 set 不同的是，x 可能会存在多个，find 查找中序遍历的第一个。
int main() {
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;
return 0;
}
简单讲一下他是怎么找到中序的第一个的。
查找依然是 O(logN) 算法的查找，并不是通过中序的方式遍历一遍，这样的话二叉搜索树就失去其意义。
中序的查找规则是：左子树 -> 根 -> 右子树。
假设要找的值是 5：如果找到了一个 5，就再往其左子树找，因为中序第一个 5 一定是在左树；直到找到了某一个 5，并且其左子树没有 5，表面当前 5 就是中序的第一个 5。
为什么这里要找中序的第一个呢？因为找中序的第一个 x，就可以用迭代器不断 ++，就可以 找到所有的 x。
2.6.3 erase 删除所有的 x
- 相比 set 不同的是，erase 给值时会
删除所有的 x。
int main() {
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;
return 0;
}
2.6.4 count 个数
- 相比 set 不同的是，count 会返回 x 的实际个数。
int main() {
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;
return 0;
}
