C++ 中 set 和 unordered_set 使用指南
一、核心概念
set特点- 基于红黑树实现，元素自动排序（默认升序）
- 操作时间复杂度：$O(\log n)$
- 需要头文件：
#include <set>
unordered_set特点- 基于哈希表实现，元素无序存储
- 平均时间复杂度：$O(1)$（最坏情况 $O(n)$）
- 需要头文件：
#include <unordered_set>
二、基本操作对比
| 操作 | set | unordered_set |
|---|---|---|
| 插入元素 | .insert(value) | .insert(value) |
| 删除元素 | .erase(value) | .erase(value) |
| 查找元素 | .find(value) | .find(value) |
| 检查存在性 | .count(value) > 0 | .count(value) > 0 |
| 元素数量 | .size() | .size() |
三、代码示例
#include <iostream> #include <set> #include <unordered_set> int main() { // 1. set 使用示例（自动排序） std::set<int> orderedSet; orderedSet.insert({3, 1, 4, 2}); // 插入元素 std::cout << "Set 内容（已排序）: "; for (int num : orderedSet) std::cout << num << " "; // 输出: 1 2 3 4 // 2. unordered_set 使用示例（无序存储） std::unordered_set<int> unorderedSet; unorderedSet.insert({3, 1, 4, 2}); std::cout << "\nUnordered_set 内容: "; for (int num : unorderedSet) std::cout << num << " "; // 输出可能: 2 4 1 3（顺序不确定） // 3. 查找操作对比 std::cout << "\n\n查找结果: "; std::cout << "Set 查找4: " << (orderedSet.find(4) != orderedSet.end()); std::cout << " | Unordered_set 查找4: " << (unorderedSet.find(4) != unorderedSet.end()); // 4. 删除操作 orderedSet.erase(2); unorderedSet.erase(2); return 0; }四、选择建议
优先使用
unordered_set当：- 需要极速查找（$O(1)$ 平均复杂度）
- 元素顺序无关紧要
- 自定义哈希函数（对自定义类型）
选择
set当：- 需要有序遍历元素
- 需要范围查询（如
lower_bound()） - 元素比较操作简单（对自定义类型需重载
<）
五、进阶技巧
- 自定义排序规则（set）
struct CustomCompare { bool operator()(const int& a, const int& b) const { return a > b; // 改为降序 } }; std::set<int, CustomCompare> customSet;- 自定义哈希函数（unordered_set）
struct MyHash { size_t operator()(const std::string& s) const { return s.length(); // 按字符串长度哈希 } }; std::unordered_set<std::string, MyHash> customUnorderedSet;关键提示：
unordered_set的性能取决于哈希函数质量，劣质哈希可能导致 $O(n)$ 复杂度。当元素数量超过桶数量时，会自动重新哈希（rehash），可通过.load_factor()监控负载因子。
