C++ 第四阶段 STL 容器 - 第五讲：详解 std::set 与 std::unordered_set
目录
📌 一、std::set 与 std::unordered_set 概述
📌 二、std::set 详解
1. 核心特性
2. 常用函数解析
3. 自定义比较函数
📌 三、std::unordered_set 详解
1. 核心特性
2. 常用函数解析
3. 自定义哈希与比较函数
📌 四、性能对比与优化建议
1. 性能对比表
2. 优化建议
📌 五、常见陷阱与解决方案
1. 修改 std::set 中的元素
2. std::unordered_set 的 rehash
3. 自定义类型的哈希冲突
📌 六、典型应用场景
1. 去重场景
2. 快速查找
3. 有序集合操作
🧠 总结
C++从入门到入土学习导航_c++学习进程-CSDN博客
📌 一、std::set 与 std::unordered_set 概述
std::set 和 std::unordered_set 是 C++ STL 中的 集合容器，用于存储唯一的元素集合。它们的核心区别在于：
| 特性 | std::set | std::unordered_set |
|---|---|---|
| 底层实现 | 红黑树（自动排序） | 哈希表（无序） |
| 元素顺序 | 升序排列 | 无序 |
| 查找复杂度 | O(log n) | 平均 O(1)（最坏 O(n)） |
| 内存占用 | 较高（红黑树节点指针） | 较低（哈希桶） |
| 适用场景 | 需要有序集合 | 快速查找/插入/删除 |
📌 二、std::set 详解
1. 核心特性
- 唯一性：所有元素唯一。
- 自动排序：元素按升序排列（默认使用
<运算符）。 - 双向迭代器：支持顺序遍历。
- 动态内存管理：自动调整红黑树结构。
2. 常用函数解析
#include <set>
#include <iostream>int main() {// 1. 初始化std::set<int> s1;std::set<int> s2 = {1, 3, 2};std::set<int> s3(s2.begin(), s2.end());// 2. 插入与删除s1.insert(5); // 插入单个元素s1.insert({6, 7, 8}); // 插入多个元素s1.erase(5); // 删除指定值s1.erase(s1.begin()); // 删除指定迭代器位置// 3. 查找与访问auto it = s1.find(3);if (it != s1.end()) {std::cout << "Found: " << *it << "\n";}// 4. 遍历for (const auto& val : s1) {std::cout << val << " "; // 输出有序元素}// 5. 特殊操作（仅 set 支持）auto lb = s1.lower_bound(4); // >=4 的第一个元素auto ub = s1.upper_bound(4); // >4 的第一个元素return 0;
}3. 自定义比较函数
struct CompareDesc {bool operator()(int a, int b) const {return a > b; // 降序排列}
};std::set<int, CompareDesc> s = {3, 1, 2};
for (const auto& val : s) {std::cout << val << " "; // 输出 3 2 1
}📌 三、std::unordered_set 详解
1. 核心特性
- 唯一性：所有元素唯一。
- 无序性：元素存储顺序由哈希值决定。
- 快速查找：平均时间复杂度为 O(1)。
- 哈希冲突：通过链表或开放寻址法解决。
2. 常用函数解析
#include <unordered_set>
#include <iostream>int main() {// 1. 初始化std::unordered_set<int> us1;std::unordered_set<int> us2 = {1, 3, 2};std::unordered_set<int> us3(us2.begin(), us2.end());// 2. 插入与删除us1.insert(5);us1.insert({6, 7, 8});us1.erase(5);us1.erase(us1.begin()); // 删除指定迭代器位置// 3. 查找与访问if (us1.find(3) != us1.end()) {std::cout << "Found\n";}// 4. 遍历for (const auto& val : us1) {std::cout << val << " "; // 输出无序元素}// 5. 性能优化us1.reserve(100); // 预分配桶空间us1.max_load_factor(0.75); // 设置最大负载因子return 0;
}3. 自定义哈希与比较函数
struct Key {int a, b;bool operator==(const Key& other) const {return a == other.a && b == other.b;}
};struct KeyHash {std::size_t operator()(const Key& k) const {return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);}
};std::unordered_set<Key, KeyHash> mySet;
mySet.insert({1, 2});📌 四、性能对比与优化建议
1. 性能对比表
| 操作 | std::set | std::unordered_set |
|---|---|---|
| 查找 | O(log n) | O(1)（平均） |
| 插入 | O(log n) | O(1)（平均） |
| 删除 | O(log n) | O(1)（平均） |
| 遍历 | O(n) | O(n) |
| 内存占用 | 高 | 低 |
2. 优化建议
std::set：- 适用于需要有序集合的场景。
- 避免频繁插入/删除导致的树结构调整。
- 使用
lower_bound/upper_bound提高性能。
std::unordered_set：- 适用于快速查找/插入/删除的场景。
- 预分配桶空间（
reserve()）减少 rehash 次数。 - 调整负载因子（
max_load_factor()）优化内存使用。 - 自定义高效的哈希函数和比较器。
📌 五、常见陷阱与解决方案
1. 修改 std::set 中的元素
- 问题：
std::set中的元素不可直接修改，否则会破坏排序。 - 解决方案：删除旧元素并插入新元素。
std::set<int> s = {1, 2, 3};
s.erase(2);
s.insert(4);2. std::unordered_set 的 rehash
- 问题：插入元素可能导致 rehash，迭代器失效。
- 解决方案：避免在遍历时直接修改容器，或使用临时容器。
for (auto it = us.begin(); it != us.end(); ) {if (*it % 2 == 0) {it = us.erase(it); // 安全删除} else {++it;}
}3. 自定义类型的哈希冲突
- 问题：自定义类型未定义哈希函数或比较器。
- 解决方案：重载
operator==和自定义哈希函数。
struct Key {int a, b;bool operator==(const Key& other) const {return a == other.a && b == other.b;}
};struct KeyHash {std::size_t operator()(const Key& k) const {return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);}
};std::unordered_set<Key, KeyHash> mySet;📌 六、典型应用场景
1. 去重场景
- 适用场景：统计唯一元素数量。
std::unordered_set<std::string> uniqueWords;
std::string text = "hello world hello";
std::istringstream iss(text);
std::string word;
while (iss >> word) {uniqueWords.insert(word);
}
std::cout << "Unique words: " << uniqueWords.size() << "\n";2. 快速查找
- 适用场景：验证元素是否存在。
std::set<int> blacklist = {1001, 1002, 1003};
if (blacklist.find(1001) != blacklist.end()) {std::cout << "Blocked!\n";
}3. 有序集合操作
- 适用场景：需要按顺序处理元素。
std::set<int> sortedData = {5, 1, 3};
for (int val : sortedData) {std::cout << val << " "; // 输出 1 3 5
}🧠 总结
| 容器 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
std::set | 有序、稳定迭代器 | 插入/删除较慢 | 需要排序、范围查询 |
std::unordered_set | 查找/插入快 | 无序、迭代器可能失效 | 快速查找、去重 |