C++ STL 容器完全指南（四）：set 与 unordered_set 深度详解

引言在前面的文章中我们学习了vector、deque、list三大顺序容器和map关联容器。本文将继续深入讲解另一个重要的关联容器——set。set的核心特点是元素唯一且自动排序。它和map的底层一样采用红黑树实现但set只存键值而不存映射值可以理解为一个没有 value 的 map。C11 还引入了基于哈希表的unordered_set提供 O(1) 平均查找速度。第一部分set 的基本概念一、底层结构set的底层是一棵红黑树保证了元素唯一不允许重复元素自动排序默认升序查找、插入、删除都是O(log n)二、set 与 map 的关系对比项setmap存储内容只存key存key-value键值对元素类型setint存 intmapint, string存 pair去重方式key 唯一key 唯一排序方式按 key 排序按 key 排序修改值❌ 不允许破坏排序✅ 可修改 value底层红黑树红黑树一句话理解set就是只有 key 没有 value 的 map。第二部分set 的创建与初始化#include iostream #include set #include functional // greater using namespace std; int main() { // 1. 默认构造升序 setint s1; // 2. 初始化列表 setint s2 {3, 1, 4, 1, 5, 9, 2, 6, 5}; // 实际存储1, 2, 3, 4, 5, 6, 9去重 升序 // 3. 指定排序规则降序 setint, greater s3 {3, 1, 4, 1, 5, 9}; // 实际存储9, 5, 4, 3, 1 // 4. 从其他容器构造 vectorint v {7, 3, 9, 1, 5}; setint s4(v.begin(), v.end()); // 5. 从数组构造 int arr[] {8, 2, 6, 4}; setint s5(arr, arr 4); // 6. 拷贝构造 setint s6(s2); return 0; }第三部分元素操作一、插入setint s {1, 3, 5}; // 1. insert(val) — 返回 pairiterator, bool auto ret s.insert(4); // ret.first → 指向插入元素的迭代器 // ret.second → true插入成功 ret s.insert(3); // ret.second → falsekey 已存在插入失败 // 2. insert(迭代器, val) — 带提示位置的插入 s.insert(s.begin(), 2); // 3. 批量插入 s.insert({6, 7, 8}); vectorint v {9, 10}; s.insert(v.begin(), v.end()); // 4. emplace() — 原地构造C11效率最高 s.emplace(11);insert 返回值的含义auto ret s.insert(5); if (ret.second) { cout 插入成功 *(ret.first) endl; } else { cout 插入失败元素已存在 endl; }情况ret.firstret.second插入成功指向新元素的迭代器true元素已存在指向已存在元素的迭代器false二、删除setint s {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 1. 按值删除返回删除的个数 size_t n s.erase(5); // n 1set 中只删了一个 // 2. 按迭代器删除 auto it s.find(3); if (it ! s.end()) { s.erase(it); // 删除迭代器指向的元素 } // 3. 按范围删除 [first, last) it s.find(7); s.erase(s.begin(), it); // 删除 [1, 7) 即 1,2,4,6 // 4. 清空 s.clear();三、查找setint s {1, 3, 5, 7, 9}; // 1. find() — 返回迭代器未找到返回 end() auto it s.find(5); if (it ! s.end()) { cout 找到 *it endl; } // 2. count() — 返回匹配的数量set 中只有 0 或 1 if (s.count(3)) { cout 存在 endl; } // 3. lower_bound(x) — 返回第一个 x 的位置 it s.lower_bound(4); // 指向 5第一个 4 cout *it endl; // 输出 5 // 4. upper_bound(x) — 返回第一个 x 的位置 it s.upper_bound(5); // 指向 7第一个 5 cout *it endl; // 输出 7 // 5. equal_range(x) — 返回 [lower_bound, upper_bound) 的 pair auto range s.equal_range(5); // range.first → lower_bound(5) 指向 5 // range.second → upper_bound(5) 指向 7lower_bound vs upper_bound 图解四、遍历setint s {3, 1, 4, 1, 5, 9, 2}; // 方式1范围 for最简洁 for (int val : s) { cout val ; // 1 2 3 4 5 9 } // 方式2迭代器只能 const_iterator for (auto it s.cbegin(); it ! s.cend(); it) { cout *it ; } // 方式3反向遍历 for (auto it s.crbegin(); it ! s.crend(); it) { cout *it ; // 9 5 4 3 2 1 }第四部分自定义排序规则一、使用仿函数// 自定义降序仿函数 struct Descending { bool operator()(int a, int b) const { return a b; // 大的排前面 } }; setint, Descending s {1, 3, 5, 2, 4}; // 遍历5 4 3 2 1二、存储自定义类型class Student { public: int id; string name; int score; Student(int id, string name, int score) : id(id), name(name), score(score) {} }; // 按分数降序排序的仿函数 struct CompareByScore { bool operator()(const Student a, const Student b) const { return a.score b.score; // 分数高的在前 } }; int main() { setStudent, CompareByScore students; students.emplace(1001, Alice, 92); students.emplace(1002, Bob, 88); students.emplace(1003, Carol, 95); for (const auto s : students) { cout s.name : s.score endl; } // Carol: 95 // Alice: 92 // Bob: 88 return 0; }三、使用 LambdaC11auto cmp [](int a, int b) { return a b; }; setint, decltype(cmp) s(cmp); s {1, 3, 5, 2, 4};第五部分multiset 可重复集合multiset与set的唯一区别是允许存储重复元素。#include set multisetint ms {1, 2, 2, 3, 3, 3}; cout ms.size() endl; // 6包含重复元素 cout ms.count(2) endl; // 22 出现了两次 cout ms.count(3) endl; // 33 出现了三次 // insert 总是成功不会返回 pair只返回迭代器 auto it ms.insert(2); // 第二个 2 不会被拒绝 // erase 按值删除会删除所有匹配元素 ms.erase(3); // 删除所有 3 // erase 按迭代器删除只删一个 it ms.find(2); ms.erase(it); // 只删第一个 2第六部分unordered_set一、底层结构unordered_set基于哈希表实现C11 引入。对比项setunordered_set底层红黑树哈希表元素顺序自动排序无序查找O(log n)O(1) 平均O(n) 最坏插入O(log n)O(1) 平均内存占用较小较大哈希表开销迭代器双向单向前向自定义类型需提供比较函数需提供哈希函数 相等比较二、基本使用#include iostream #include unordered_set using namespace std; int main() { unordered_setint us {3, 1, 4, 1, 5, 9}; // 插入 us.insert(2); us.emplace(7); // 查找O(1) 平均 if (us.find(5) ! us.end()) { cout 找到 5 endl; } // 遍历无序 for (int val : us) { cout val ; // 顺序不可预测 } // 删除 us.erase(3); // 哈希表相关信息 cout size: us.size() endl; cout bucket_count: us.bucket_count() endl; cout load_factor: us.load_factor() endl; return 0; }三、自定义哈希函数struct Point { int x, y; bool operator(const Point other) const { return x other.x y other.y; } }; // 自定义哈希 struct PointHash { size_t operator()(const Point p) const { return hashint()(p.x) ^ (hashint()(p.y) 1); } }; int main() { unordered_setPoint, PointHash points; points.insert({1, 2}); points.insert({3, 4}); if (points.find({1, 2}) ! points.end()) { cout 存在 (1,2) endl; } return 0; }四、set vs unordered_set 选择建议场景推荐原因需要有序遍历set自动排序需要范围查询set支持 lower_bound只需快速查找unordered_setO(1) 平均内存敏感set内存占用小自定义类型较复杂unordered_set只需实现哈希函数第七部分完整示例#include iostream #include set #include unordered_set #include string #include functional using namespace std; void printSet(const setint s) { for (int val : s) cout val ; cout endl; } int main() { cout set 基本操作 \n; setint s {5, 2, 8, 1, 9, 2, 8}; cout 初始化后; printSet(s); cout 元素个数 s.size() endl; // 插入测试 auto ret s.insert(4); cout 插入 4 (ret.second ? 成功 : 失败) endl; ret s.insert(5); cout 插入 5 (ret.second ? 成功 : 失败) endl; cout 插入后; printSet(s); // 查找测试 cout \n 查找操作 \n; for (int x : {3, 5, 10}) { auto it s.find(x); cout 查找 x : (it ! s.end() ? 找到 : 不存在) endl; } // 范围查找 auto lb s.lower_bound(4); auto ub s.upper_bound(8); cout 区间 [4, 8]; for (auto it lb; it ! ub; it) cout *it ; cout endl; // 删除测试 cout \n 删除操作 \n; s.erase(2); cout 删除 2 后; printSet(s); // 降序 set cout \n 降序 set \n; setint, greater s2 {5, 2, 8, 1, 9}; cout 降序; for (int val : s2) cout val ; cout endl; // unordered_set cout \n unordered_set \n; unordered_setint us {5, 2, 8, 1, 9, 2, 8}; cout 元素个数 us.size() endl; cout 遍历无序; for (int val : us) cout val ; cout endl; return 0; }运行结果总结一、set 核心操作速查操作方法复杂度插入insert(val)/emplace(val)O(log n)删除erase(val)/erase(it)O(log n)查找find(val)O(log n)计数count(val)O(log n)下界lower_bound(val)O(log n)上界upper_bound(val)O(log n)遍历for(:)/ 迭代器O(n)二、各容器对比容器底层元素唯一自动排序随机访问查找set红黑树✅✅ 升序❌O(log n)multiset红黑树❌✅ 升序❌O(log n)unordered_set哈希表✅❌❌O(1)vector数组❌❌✅O(n)三、一句话记忆set用红黑树实现元素自动升序排列且唯一插入失败返回 false支持lower_bound/upper_bound范围查询unordered_set用哈希表实现无序但查找 O(1)需要自定义哈希函数。