深入解剖STL set/multiset：接口使用与核心特性详解

Ne0inhk

— 16 min read
深入解剖STL set/multiset：接口使用与核心特性详解
在这里插入图片描述
在这里插入图片描述

❤️@燃于AC之乐 来自重庆 计算机专业的一枚大学生
✨专注 C/C++ Linux 数据结构 算法竞赛 AI
🏞️志同道合的人会看见同一片风景！

👇点击进入作者专栏：

《算法画解》 ✅

《linux系统编程》✅

《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的差异对比

特性setmultiset
键值冗余❌ 不支持（去重）✅ 支持（可重复）
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)❌ 不可修改

核心要点：

  1. set是去重+有序的集合，multiset是有序的多重集合
  2. 增删查都是**O(logN)**效率，基于红黑树实现
  3. 迭代器遍历按中序升序，不支持修改元素
  4. find()比全局算法快，count()可用于存在性判断
  5. lower_bound()/upper_bound()专为区间操作设计
  6. multiset的find()返回中序第一个，erase(val)删除所有匹配项
在这里插入图片描述


加油！志同道合的人会看到同一片风景。
看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！

Read more

算法王冠上的明珠——动态规划之路径问题(第一篇）

算法王冠上的明珠——动态规划之路径问题(第一篇）

目录 1. 什么叫路径类动态规划 一、核心定义（通俗理解） 二、核心特征（识别这类问题的关键） 2. 动态规划步骤 状态表示 状态转移方程 初始化 填表顺序 返回值 3. 例题讲解 3.1 LeetCode62. 不同路径 3.2 LeetCode63. 不同路径 II 3.3 LeetCodeLCR 166. 珠宝的最高价值 今天我们来聊一聊动态规划的路径类问题。 1. 什么叫路径类动态规划 路径类动态规划是 动态规划的一个重要分支，核心解决 “从起点到终点的路径相关问题”—— 比如 “路径总数”“最短路径长度”“路径上的最大 / 最小和” 等，其本质是通过 “状态递推” 避免重复计算，高效求解多阶段决策的路径问题。 一、

By Ne0inhk
【数据结构】常见时间复杂度以及空间复杂度

【数据结构】常见时间复杂度以及空间复杂度

时间复杂度与空间复杂度 * 一、复杂度的概念 * 二、时间复杂度 * 1、大O的渐进表示法 * 2、函数clock计算运算时间 * 3、常见复杂度对比 * 3.1常数项复杂度 * 3.2线性时间复杂度 * 案例1 * 案例2 * 3.3平方阶复杂度 * 3.4对数复杂度 * 3.5递归函数 * 单递归 * 双递归 * 三、空间复杂度 * 冒泡排序O(1) * 三个反置O(N) 一、复杂度的概念 * 一个算法的好坏，主要是对比两者的时间和空间两个维度，也就是时间和空间复杂度。 * 时间复杂度主要衡量一个算法运行的快慢，空间复杂度主要衡量一个算法运行需要的额外空间 二、时间复杂度 * 算法的时间复杂度是一个函数式T(N)，算法中的基本操作的执行次数，为算法的时间复杂度。 * 注：编译器的不同，编译所需要的时间也不同。越新的编译器，编译的时间往往比旧的编译器快 * 当一个算法函数式为T(

By Ne0inhk
数据结构-单链表

数据结构-单链表

单链表 * 概念与结构 * 结点 * 链表的性质 * 链表的打印 * 实现单链表 * 头文件 * 源文件 * 单链表的打印 * 单链表申请新节点内存 * 尾插 * 头插 * 尾删 * 头删 * 查找 * 在指定位置之前插入数据 * 在指定位置之后插入数据 * 删除pos结点 * 删除pos之后的结点 * 销毁链表 * 链表的分类 * 代码地址 概念与结构 概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 逻辑结构：线性 物理结构（存储结构）：不一定是线性的 链表就类似一个火车，车头是哨兵位（可有可无），车厢是节点 * 将火车里的某节车厢去掉或加上，不会影响其他车厢，每节车厢都是独立存在的。 在链表⾥，每节“车厢”是什么样的呢？ \color{red}{在链表⾥，每节“车厢”是什么样的呢？

By Ne0inhk
【数据结构】排序详解：从快速排序分区逻辑，到携手冒泡排序的算法效率深度评测

【数据结构】排序详解：从快速排序分区逻辑，到携手冒泡排序的算法效率深度评测

🔥@晨非辰Tong： 个人主页 👀专栏：《C语言》、《数据结构与算法入门指南》 💪学习阶段：C语言、数据结构与算法初学者 ⏳“人理解迭代，神理解递归。” 文章目录 * 引言 * 一、介绍交换排序 * 二、高效交换--快速排序“：递归版 * 2.1 介绍：创造背景以及基本思想 * 2.2 基于二叉树结构的主体框架 * 三、找基准值key的三种==递归版==实战方法 * 3.1 快排核心构成：寻找key的算法之"hoare"版本 * 3.3.1 画图理解算法 * 3.3.2 代码实战 * 3.1.3 ==**代码分析**== * 3.2

By Ne0inhk