深入解剖STL set/multiset：接口使用与核心特性详解
❤️@燃于AC之乐 来自重庆 计算机专业的一枚大学生
✨专注 C/C++ Linux 数据结构 算法竞赛 AI
🏞️志同道合的人会看见同一片风景！
👇点击进入作者专栏：
《算法画解》 ✅
《C++》 ✅
🌟《算法画解》算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！
文章目录
前言（关联式容器概述）
容器，置物之所也。根据“数据在容器中的排列特性”，容器可分为序列式容器和关联式容器两种。
序列式容器：如string、vector、list、deque等，逻辑结构为线性序列，元素按在容器中的存储位置顺序保存和访问，元素之间没有紧密的关联关系。
关联式容器：每个元素都有一个键值（key）和一个实值（value）。容器内部结构（通常是平衡二叉树）依照键值大小，以特定规则将元素放置于适当位置。关联式容器没有头尾概念（只有最大元素和最小元素），因此不支持push_back()、push_front()、pop_back()、pop_front()等操作。
本章讲解的set和multiset底层是红黑树——一棵平衡二叉搜索树。set是key搜索场景的结构，multiset是支持键值冗余的key搜索场景结构。
一、set类介绍
1.1 set的类模板声明
template<classT,// set::key_type/value_typeclassCompare= less<T>,// set::key_compare/value_compareclassAlloc= allocator<T>// set::allocator_type>classset;要点说明：
T：set底层存储的关键字类型Compare：比较方式，默认less<T>（升序），可传greater<T>实现降序Alloc：空间配置器，一般使用默认- 底层结构：红黑树，平衡二叉搜索树
- 增删查效率：O(logN)
- 迭代器遍历：按中序遍历，有序输出
- const特性：set的iterator和const_iterator均不支持修改元素（修改key会破坏二叉搜索树结构）
二、set的构造与迭代器
2.1 构造接口
set提供了多种构造方式，以适应不同的初始化需求：
// 1. 无参默认构造explicitset(const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());// 2. 迭代器区间构造template<classInputIterator>set(InputIterator first, InputIterator last,const key_compare& comp =key_compare(),const allocator_type&=allocator_type());// 3. 拷贝构造set(const set& x);// 4. initializer_list构造set(initializer_list<value_type> il,const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());2.2 迭代器接口
set的迭代器是双向迭代器，遍历走中序，默认升序：
// 正向迭代器 iterator begin();// 返回指向最小元素的迭代器 iterator end();// 返回尾后迭代器// 反向迭代器 reverse_iterator rbegin();// 返回指向最大元素的迭代器 reverse_iterator rend();// 返回反向尾后迭代器// const迭代器 const_iterator cbegin()const; const_iterator cend()const; const_reverse_iterator crbegin()const; const_reverse_iterator crend()const;三、set的核心操作接口
3.1 插入操作
// 单个数据插入，返回pair<迭代器, 是否成功> pair<iterator,bool>insert(const value_type& val);// 列表插入，已存在的值不会插入voidinsert(initializer_list<value_type> il);// 迭代器区间插入，已存在的值不会插入template<classInputIterator>voidinsert(InputIterator first, InputIterator last);接口说明：
insert(const value_type& val)：单元素插入。返回值的second为true表示插入成功，false表示值已存在insert(initializer_list)：批量插入，已存在的元素自动跳过insert(iterator, iterator)：插入另一容器中的一段区间
3.2 查找操作
// 查找val，返回迭代器，未找到返回end() iterator find(const value_type& val);// 查找val的个数（set中只能是0或1） size_type count(const value_type& val)const;接口说明：
find()：O(logN)效率，远快于全局find()算法的O(N)count()：set中值唯一，因此返回值只能是0或1，常用于判断存在性
3.3 删除操作
// 删除迭代器位置的值 iterator erase(const_iterator position);// 删除val，返回删除个数（0或1） size_type erase(const value_type& val);// 删除迭代器区间 iterator erase(const_iterator first, const_iterator last);接口说明：
erase(position)：删除指定位置的元素，返回下一个元素的迭代器erase(val)：按值删除，返回删除的元素个数（0或1）erase(first, last)：删除区间内的所有元素，左闭右开[first, last)
3.4 边界查找操作
// 返回 >= val 的第一个元素的迭代器 iterator lower_bound(const value_type& val)const;// 返回 > val 的第一个元素的迭代器 iterator upper_bound(const value_type& val)const;// 返回pair<lower_bound, upper_bound> pair<iterator,iterator>equal_range(const value_type& val)const;接口说明：
lower_bound()：二分查找下界，第一个不小于val的位置upper_bound()：二分查找上界，第一个大于val的位置equal_range()：同时获取下界和上界，常用于区间操作
四、set使用详解
4.1 插入与遍历
接口讲解：
本示例演示set最基础的插入和遍历操作。insert()用于添加元素，set会自动去重并排序；迭代器和范围for均可用于遍历，遍历结果为升序序列。注意：set的迭代器是常量迭代器，不允许通过迭代器修改元素值。
#include<iostream>#include<set>usingnamespace std;intmain(){// 1. 默认构造：升序排序 + 去重 set<int> s;// 2. 降序构造（注释示例）// set<int, greater<int>> s;// 3. 插入元素，重复值自动忽略 s.insert(5); s.insert(2); s.insert(7); s.insert(5);// 已存在，插入失败// 4. 迭代器遍历（中序升序）auto it = s.begin();while(it != s.end()){// *it = 1; // 错误！不允许通过迭代器修改 cout <<*it <<" ";++it;} cout << endl;// 输出：2 5 7// 5. initializer_list批量插入 s.insert({2,8,3,9});// 2已存在，插入失败for(auto e : s)// 范围for遍历{ cout << e <<" ";} cout << endl;// 输出：2 3 5 7 8 9// 6. string类型set：按字典序（ASCII码）排序 set<string> strset ={"sort","insert","add"};for(auto& e : strset){ cout << e <<" ";} cout << endl;// 输出：add insert sortreturn0;}输出结果：
2 5 7 2 3 5 7 8 9 add insert sort 4.2 查找与删除
接口讲解：
本示例演示set的查找和删除操作。find()用于定位元素位置，erase()支持按迭代器删除和按值删除两种方式。按值删除时，返回值表示删除的元素个数（0或1）。count()可用于快速判断元素是否存在，代码更简洁。
#include<iostream>#include<set>usingnamespace std;intmain(){// 1. initializer_list构造 set<int> s ={4,2,7,2,8,5,9};for(auto e : s){ cout << e <<" ";} cout << endl;// 输出：2 4 5 7 8 9// 2. 删除最小值（begin指向最小元素） s.erase(s.begin());for(auto e : s){ cout << e <<" ";} cout << endl;// 输出：4 5 7 8 9// 3. 按值删除int x; cin >> x;int num = s.erase(x);// 返回删除的元素个数if(num ==0){ cout << x <<"不存在！"<< endl;}for(auto e : s){ cout << e <<" ";} cout << endl;// 4. 查找后删除（推荐方式） cin >> x;auto pos = s.find(x);// O(logN)查找if(pos != s.end()){ s.erase(pos);// 迭代器删除}else{ cout << x <<"不存在！"<< endl;}for(auto e : s){ cout << e <<" ";} cout << endl;// 5. 算法库find vs set::find 效率对比auto pos1 =find(s.begin(), s.end(), x);// O(N)，全局算法auto pos2 = s.find(x);// O(logN)，利用红黑树特性// 6. 利用count快速判断存在性 cin >> x;if(s.count(x))// count返回0或1{ cout << x <<"在！"<< endl;}else{ cout << x <<"不存在！"<< endl;}return0;}4.3 区间操作：lower_bound与upper_bound
接口讲解：lower_bound()和upper_bound()是set提供的二分查找边界接口，专门用于区间操作。lower_bound(val)返回第一个≥val的元素位置，upper_bound(val)返回第一个**>val**的元素位置。二者配合可以精确定位出一个值区间[lower_bound, upper_bound)，常用于批量删除或区间遍历。
#include<iostream>#include<set>usingnamespace std;intmain(){// 1. 构造有序序列 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;// 2. 删除区间 [30, 60] 内的所有元素// lower_bound(30)：返回第一个 >=30 的元素迭代器（指向30）auto itlow = myset.lower_bound(30);// upper_bound(60)：返回第一个 >60 的元素迭代器（指向70）auto itup = myset.upper_bound(60);// 3. 删除 [itlow, itup) 区间元素 myset.erase(itlow, itup);for(auto e : myset){ cout << e <<" ";} cout << endl;// 输出：10 20 70 80 90return0;}区间图解：
原集合：10 20 30 40 50 60 70 80 90 ↑ ↑ itlow(30) itup(70) 删除区间：[30,60] 被全部删除 结果：10 20 70 80 90 五、multiset的使用
5.1 multiset与set的差异对比
| 特性 | set | multiset |
|---|---|---|
| 键值冗余 | ❌ 不支持（去重） | ✅ 支持（可重复） |
| insert | 已存在则插入失败 | 总是成功 |
| find | 返回任意位置 | 返回中序第一个 |
| count | 返回0或1 | 返回实际个数 |
| erase(val) | 删除0或1个 | 删除所有等于val的元素 |
5.2 multiset插入与遍历
接口讲解：
multiset的接口与set完全一致，但行为不同。multiset允许插入重复值，insert()总是成功；遍历时重复值会连续出现（因为有序）。这是multiset最核心的特性。
#include<iostream>#include<set>usingnamespace std;intmain(){// 1. multiset：排序 + 不去重 multiset<int> s ={4,2,7,2,4,8,4,5,4,9};// 2. 遍历：有序输出，重复值保留auto it = s.begin();while(it != s.end()){ cout <<*it <<" ";++it;} cout << endl;// 输出：2 2 4 4 4 4 5 7 8 9return0;}5.3 multiset的find操作
接口讲解：
multiset的find()与set不同：当存在多个相同值的元素时，find()返回中序遍历的第一个。这一特性使得我们可以从第一个重复元素开始，顺序遍历所有相等元素。
#include<iostream>#include<set>usingnamespace std;intmain(){ multiset<int> s ={4,2,7,2,4,8,4,5,4,9};// 1. find返回中序第一个int x; cin >> x;auto pos = s.find(x);// 找到第一个x// 2. 遍历所有等于x的元素while(pos != s.end()&&*pos == x){ cout <<*pos <<" ";++pos;} cout << endl;return0;}输入/输出示例：
输入：4 输出：4 4 4 4 5.4 multiset的count与erase操作
接口讲解：
multiset的count()返回实际重复个数，而不仅仅是0或1；erase(val)会删除所有等于val的元素，并返回删除的总个数。这是与set最显著的行为差异。
#include<iostream>#include<set>usingnamespace std;intmain(){ multiset<int> s ={4,2,7,2,4,8,4,5,4,9};// 1. count返回实际个数int x; cin >> x; cout << s.count(x)<< endl;// 输出4（有4个4）// 2. erase(val)删除所有匹配元素 s.erase(x);// 一次性删除所有xfor(auto e : s){ cout << e <<" ";} cout << endl;// 输出：2 2 5 7 8 9return0;}完整示例：
#include<iostream>#include<set>usingnamespace std;intmain(){// 1. 构造multiset multiset<int> s ={4,2,7,2,4,8,4,5,4,9};// 2. 遍历（有序，含重复值）auto it = s.begin();while(it != s.end()){ cout <<*it <<" ";++it;} cout << endl;// 输出：2 2 4 4 4 4 5 7 8 9// 3. find返回中序第一个int x; cin >> x;auto pos = s.find(x);while(pos != s.end()&&*pos == x){ cout <<*pos <<" ";++pos;} cout << endl;// 4. count返回实际个数 cout << s.count(x)<< endl;// 5. erase(val)删除所有 s.erase(x);for(auto e : s){ cout << e <<" ";} cout << endl;return0;}输入/输出示例：
输入：4 输出： 2 2 4 4 4 4 5 7 8 9 4 4 4 4 4 2 2 5 7 8 9 六、set的应用场景
6.1 场景一：去重 + 排序
接口讲解：
set天然具备“插入时自动去重、遍历时自动排序”的特性。将数据插入set后，重复值被自动过滤，且可以直接获得有序序列，无需额外调用sort()和unique()。
#include<iostream>#include<set>#include<vector>usingnamespace std;intmain(){ vector<int> v ={5,2,7,2,8,5,9,3,3,1};// 1. vector -> set：自动去重 + 排序 set<int>s(v.begin(), v.end());// 2. 直接获得有序无重复序列for(auto e : s){ cout << e <<" ";// 输出：1 2 3 5 7 8 9} cout << endl;return0;}6.2 场景二：快速查找与存在性判断
接口讲解：
set基于红黑树实现，find()和count()都是O(logN)效率，远快于线性结构（如vector、list）的O(N)查找。适合需要频繁查询某元素是否存在的场景。
#include<iostream>#include<set>#include<string>usingnamespace std;intmain(){// 小区车牌号白名单 set<string> whiteList ={"京A12345","京B67890","粤C33445","沪D55667"}; string car; cin >> car;// O(logN)快速判断if(whiteList.count(car)){ cout <<"欢迎回家！"<< endl;}else{ cout <<"非本小区车辆，禁止入内！"<< endl;}return0;}6.3 场景三：两个数组的交集（LeetCode）
接口讲解：
利用set的有序性，可以像合并有序序列一样求交集。将两个数组分别放入set后，它们都是有序序列，用双指针法遍历比较即可得到交集，时间复杂度O(N)。
classSolution{public: vector<int>intersection(vector<int>& nums1, vector<int>& nums2){// 1. 利用set去重 + 排序 set<int>s1(nums1.begin(), nums1.end()); set<int>s2(nums2.begin(), nums2.end());// 2. 双指针法求交集（利用有序特性） vector<int> ret;auto it1 = s1.begin();auto it2 = s2.begin();while(it1 != s1.end()&& it2 != s2.end()){if(*it1 <*it2){ it1++;}elseif(*it1 >*it2){ it2++;}else{ ret.push_back(*it1); it1++; it2++;}}return ret;}};6.4 场景四：环形链表的入口检测（LeetCode）
接口讲解：
set可以用来存储已访问过的节点指针。遍历链表时，尝试将当前节点插入set，若插入失败（节点已存在），说明链表有环，且该节点就是环的入口。这种方法无需复杂数学证明，是set的经典应用。
classSolution{public: ListNode *detectCycle(ListNode *head){ set<ListNode*> s; ListNode* cur = head;while(cur){// 尝试插入，若second == false，说明节点已存在（环入口）auto ret = s.insert(cur);if(ret.second ==false)return cur; cur = cur->next;}returnnullptr;// 无环}};七、总结
| 容器 | 底层结构 | 元素唯一性 | 有序性 | 查找效率 | 修改限制 |
|---|---|---|---|---|---|
| set | 红黑树 | ✅ 唯一 | ✅ 升序 | O(logN) | ❌ 不可修改 |
| multiset | 红黑树 | ❌ 可重复 | ✅ 升序 | O(logN) | ❌ 不可修改 |
核心要点：
- set是去重+有序的集合，multiset是有序的多重集合
- 增删查都是**O(logN)**效率，基于红黑树实现
- 迭代器遍历按中序升序，不支持修改元素
find()比全局算法快，count()可用于存在性判断lower_bound()/upper_bound()专为区间操作设计- multiset的
find()返回中序第一个，erase(val)删除所有匹配项
加油！志同道合的人会看到同一片风景。
看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！
