目录
📌 一、std::set 与 std::unordered_set 概述
2. std::unordered_set 的 rehash
📌 一、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 |
查找/插入快 | 无序、迭代器可能失效 | 快速查找、去重 |