C++中set与unordered_set对比指南

C++ 中 set 和 unordered_set 使用指南

一、核心概念

1. set特点

   • 基于红黑树实现，元素自动排序（默认升序）
   • 操作时间复杂度：$O(\log n)$
   • 需要头文件：#include <set>

2. unordered_set特点

   • 基于哈希表实现，元素无序存储
   • 平均时间复杂度：$O(1)$（最坏情况 $O(n)$）
   • 需要头文件：#include <unordered_set>

二、基本操作对比

三、代码示例

#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; }

四、选择建议

1. 优先使用unordered_set当：

   • 需要极速查找（$O(1)$ 平均复杂度）
   • 元素顺序无关紧要
   • 自定义哈希函数（对自定义类型）

2. 选择set当：

   • 需要有序遍历元素
   • 需要范围查询（如lower_bound()）
   • 元素比较操作简单（对自定义类型需重载<）

五、进阶技巧

1. 自定义排序规则（set）

struct CustomCompare { bool operator()(const int& a, const int& b) const { return a > b; // 改为降序 } }; std::set<int, CustomCompare> customSet;

1. 自定义哈希函数（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()监控负载因子。