C++ STL set 系列深度解析：从底层原理、核心接口到实战场景

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一、容器分类序列式容器与关联式容器的本质区别二、set 系列核心原理红黑树赋能的高效特性三、set 核心接口实战基于实操代码详解1、初始化与插入去重 自动排序2、查找与删除精准操作单个元素3、区间操作lower_bound 与 upper_bound四、multiset支持重复 key 的关联式容器五、 set 系列的实战价值解决实际开发问题1、环形链表 II题目链接C算法代码2、两个数组的交集扩展差集思路题目链接C算法代码结束语前言在 C STL 容器中set 系列set 与 multiset是基于红黑树实现的关联式容器核心特性是“自动排序 高效查找”。它既能解决“数据去重 排序”的基础需求也能在复杂场景中如大量数据的查找、区间删除、频率统计提供O(log N)级别的高效操作效率。本文将结合实战测试代码从 set 的核心概念入手讲解其构造、增删查、区间操作等关键接口同时对比 set 与 multiset 的差异帮你彻底掌握这一高频使用容器。一、容器分类序列式容器与关联式容器的本质区别STL 容器的设计围绕 “数据如何存储与访问” 展开序列式与关联式容器的核心差异体现在存储逻辑与访问方式上具体对比如下特性序列式容器如 vector、list关联式容器如 set、map存储逻辑按插入顺序存储元素位置由插入时机决定按键key的内在规则存储如排序规则访问方式通过下标/迭代器位置访问如 vec[2] 通过键值匹配访问如 set.find(3) 底层结构动态数组vector、双向链表list等平衡二叉搜索树红黑树set/map、哈希表unordered_set核心优势插入顺序稳定适合频繁增删尾部元素并且可以对已有结构内的数据进行修改(如 vec[1] 1 )自动排序查找/删除效率高 ( O(log N) 或O(1) 典型使用场景存储连续数据、需要按插入顺序遍历、动态扩容需求去重排序、快速查找、键值映射、区间操作补充说明序列式容器强调“位置”元素的价值在于其存储的内容本身关联式容器强调“关联关系”元素的价值在于通过键值 key 快速定位如 “根据 ID 查找用户信息”set 作为 “key” 型关联式容器仅存储键值核心功能是 “基于 key 的排序与查找”。二、set 系列核心原理红黑树赋能的高效特性set 与 multiset 底层均基于红黑树一种自平衡二叉搜索树实现这一结构赋予它们以下核心特性自动排序红黑树的中序遍历结果为有序序列因此 set 插入元素后会自动按 key 的默认规则less升序排序无需手动调用排序函数如果需要按自己的需求比较可以自行实现仿函数传给第二个模板参数。去重与允许重复set 不允许存储重复 keymultiset 支持重复 key不可修改 keyset 的迭代器为const_iterator无法通过迭代器修改 key修改会破坏红黑树结构高效操作增删查操作的时间复杂度均为O(log N)远优于 vector 的O(N)参考文档set - C Referenceset 的声明template class T, // set::key_type/value_type class Compare lessT, // set::key_compare/value_compare class Alloc allocatorT // set::allocator_type class set; //set的声明如上T就是 set 底层关键字的类型 //set默认要求T支持小于比较如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数 //set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。 //一般情况下我们都不需要传后两个模版参数。 //set底层是用红黑树实现增删查效率是O(logN)迭代器遍历是走的搜索树的中序所以是有序的。set 的构造相关接口// empty (1) ⽆参默认构造 explicit set (const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // range (2) 迭代器区间构造 template class InputIterator set (InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type allocator_type()); // copy (3) 拷⻉构造 set (const set x); // initializer list (5) initializer 列表构造 set (initializer_listvalue_type il, const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // 迭代器是⼀个双向迭代器 iterator - a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();set 的构造我们关注以上几个接口即可。set 的支持正向和反向迭代遍历遍历默认按升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围 forset 不管是 iterator 还是 const_iterator 都不支持迭代器修改数据因为修改关键字数据破坏了底层搜索树的结构这是不允许的。set 的增删查相关接口Member types key_type - The first template parameter (T) value_type - The first template parameter (T) // 单个数据插⼊如果已经存在则插⼊失败 pairiterator,bool insert (const value_type val); // 列表插⼊已经在容器中存在的值不会插⼊ void insert (initializer_listvalue_type il); // 迭代器区间插⼊已经在容器中存在的值不会插⼊ template class InputIterator void insert (InputIterator first, InputIterator last); // 查找val返回val所在的迭代器没有找到返回end() iterator find (const value_type val); // 查找val返回Val的个数 size_type count (const value_type val) const; // 删除⼀个迭代器位置的值返回的是下一个位置的迭代器 iterator erase (const_iterator position); // 删除valval不存在返回0存在返回1 size_type erase (const value_type val); // 删除⼀段迭代器区间的值 iterator erase (const_iterator first, const_iterator last); // 返回第一次出现⼤于等于val位置的迭代器 iterator lower_bound (const value_type val) const; // 返回第一次出现⼤于val位置的迭代器 iterator upper_bound (const value_type val) const;set 的增删查关注以上几个接口即可下面我会为大家一一讲解实现。三、set 核心接口实战基于实操代码详解下面会通过多个测试函数覆盖 set 的核心操作我们结合代码解析其使用方法与注意事项。1、初始化与插入去重 自动排序set 支持多种插入方式插入后自动去重并按默认按升序排列。代码示例注意看注释#include iostream #include set using namespace std; //初始化与插入去重 自动排序 void test_set1() { //测试set的插入与遍历去重 自动排序 setint s1; // 方式1单个元素插入 s1.insert(3); s1.insert(1); s1.insert(2); s1.insert(5); s1.insert(3); s1.insert(5); s1.insert(6); // 遍历方式1迭代器遍历注意*it不可修改 // 遍历结果: 去重有序 auto it s1.begin(); while (it ! s1.end()) { //*it1 1;//不能修改 cout *it ; it; } cout endl; // 方式2初始化列表批量插入 setint s2; s2.insert({ 3,1,2,5,3,5,6 }); // 遍历方式2范围for循环 for (auto e : s2) { cout e ; } cout endl; //若需降序排序可指定排序仿函数setint, greaterint s - 降序排序 setint, greaterint s3({ 3,1,2,5,3,5,6 }); //列表构造 for (auto e : s3) { cout e ; } cout endl; } int main() { test_set1(); }2、查找与删除精准操作单个元素set 提供 find查找、count统计、erase删除接口支持按 key 或迭代器操作// 测试set的查找与删除 void test_set2() { setint s1; s1.insert({ 3,1,2,5,3,5,6 });// 去重后1 2 3 5 6 // 删除最小值 s1.erase(s1.begin());//iterator erase (const_iterator position); for (auto e : s1) { cout e ; } cout endl; // 直接删除x int x; cin x; int num s1.erase(x); //删掉了几个返回值就是几在set里就是1没删掉就是0 //size_type erase(const value_type val); if (num 0) { cout x 不存在 endl; } else { cout x 删除成功 endl; } for (auto e : s1) { cout e ; } cout endl; cout endl; // 直接查找在利用返回值是迭代器删除x setint s2({ 3,1,2,5,3,5,6 }); for (auto e : s2) { cout e ; } cout endl; cin x; auto pos s2.find(x); if (pos ! s2.end()) //如果返回的结果是end()则说明没有找到 { s2.erase(pos); //cout *pos endl; //删除后该位置的迭代器就失效了不能再进行访问 } else { cout x 不存在 endl; } for (auto e : s2) { cout e ; } cout endl; cout endl; // 算法库的查找 O(N) auto pos1 find(s2.begin(), s2.end(), x); // set⾃⾝实现的查找 O(logN) auto pos2 s2.find(x); // 利用count间接实现快速查找 cin x; if (s2.count(x)) { cout x 在 endl; } else { cout x 不在 endl; } } int main() { test_set2(); }关键说明erase 的返回值是删除元素的个数在 set 里要么是0要么是1multiset 删了几个就是几count 在 set 中主要用于判断元素是否存在在 multiset 中返回实际个数。3、区间操作lower_bound 与 upper_boundset 的区间操作依赖 lower_bound 和 upper_bound可用于快速定位边界并且结合 erase 可高效删除区间元素// 测试set的区间操作 void test_set3() { setint s; s.insert({ 3,1,2,5,3,5,6,7,9 }); for (auto e : s) { cout e ; } cout endl; // 需求删除[3, 8]区间的元素即 3 且 8 // lower_bound(val)返回第一个 val 的迭代器此处指向3 auto it1 s.lower_bound(3); // upper_bound(val)返回第一个 val 的迭代器此处指向9 auto it2 s.upper_bound(8); // 按迭代器区间删除删除[it1, it2)内的元素(左闭右开) s.erase(it1, it2); //所以迭代器it2位置不会删除而是删除到左边一个位置结束 for (auto e : s) { cout e ; } cout endl; } int main() { test_set3(); }关键说明lower_bound 与 upper_bound 的时间复杂度均为O(log N)是区间操作的核心区间 [it1, it2) 为 “左闭右开”这样符合 STL 迭代器区间的通用设计如 [begin, end) 。四、multiset支持重复 key 的关联式容器multiset 与 set 接口一致核心差异是允许重复 key适用于需要存储相同元素并统计频率的场景// 测试multiset支持重复key void test_multiset() { multisetint s1; // 插入重复元素不会去重 s1.insert({ 3,1,2,5,3,5,6,3,3 }); // 1. 遍历有序并且保留重复元素 auto it s1.begin(); while (it ! s1.end()) { //*it 1;//不能修改 cout *it ; it; } cout endl; // 相比set不同的是x可能会存在多个find查找中序的第一个 int x; cin x; auto pos s1.find(x); //打印所有的x while (pos ! s1.end() *pos x) { cout *pos ; pos; } cout endl; // 相比set不同的是count会返回x的实际个数 cout x : s1.count(x) 个 endl; //删除按 key 删除所有匹配元素 // 相比set不同的是erase给值时会删除所有的x cout x 删除的个数 s1.erase(x) endl;//删掉所有的3并返回删掉的3的个数 for (auto e : s1) { cout e ; } cout endl; } int main() { test_multiset(); }set 与 multiset 的核心差异总结操作setmultiset插入重复元素自动去重重复元素插入失败不去重保留所有重复元素插入成功find(key)返回唯一匹配元素的迭代器未找到返回end()返回中序遍历中第一个匹配元素的迭代器count(key)返回 0 或 1仅用于判断元素是否存在返回元素在容器中实际出现的次数erase(key)若元素存在则删除 1 个不存在则删除 0 个删除容器中所有与key匹配的元素五、 set 系列的实战价值解决实际开发问题set 系列的“自动排序 高效查找”特性在算法与工程中应用广泛以下是两个典型题目1、环形链表 II题目链接142. 环形链表 II - 力扣LeetCode思路用 set 存储遍历过的节点若插入节点时发现已存在该节点即为入口。C算法代码class Solution { public: ListNode *detectCycle(ListNode *head) { //解法一容器set判断结点地址是否存在过 setListNode* s; while(head) { if(s.count(head) 0) { s.insert(head); } else { return head; } head head-next; } return nullptr; } };2、两个数组的交集扩展差集思路题目链接349. 两个数组的交集 - 力扣LeetCode思路用 set 对两个数组去重 排序再用双指针遍历两个 set找到共同元素。C算法代码class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { // 1. 用set对两个数组去重排序 setint s1(nums1.begin(), nums1.end()); setint s2(nums2.begin(), nums2.end()); vectorint ret; auto it1 s1.begin(); auto it2 s2.begin(); while(it1 ! s1.end() it2 ! s2.end()) { if(*it1 *it2) { it2; } else if(*it1 *it2) { it1; } else { ret.push_back(*it1); it1; it2; } } return ret; } };差集和交集的实战使用多端文件同步的逻辑通过 “差集识别新增 / 缺失文件交集比对时间戳确定更新方向”避免全量传输大幅减少带宽消耗和同步时间是云存储、多端协作工具如网盘、协同办公软件的常见底层逻辑之一。结束语到此C STL 中的 set 容器我们就讲解完了。set 系列作为 STL 关联式容器的核心以红黑树为支撑实现了自动排序、高效查找与去重或允许多重复的能力是处理 “有序数据管理” 场景的利器。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/