C++ set与unordered_set使用详解

set基于红黑树实现，元素有序，操作复杂度O(log n)；unordered_set基于哈希表，元素无序，平均操作复杂度O(1)，适用于存在性查询。

在C++中，set 和 unordered_set 是两种常用的关联式容器，用于存储唯一的元素。它们都定义在 <set> 和 <unordered_set> 头文件中，但底层实现和性能特性不同，适用于不同的场景。

set 的使用方法

set 基于红黑树实现，元素自动排序（默认升序），插入、删除、查找的时间复杂度为 O(log n)。适合需要有序遍历或范围查询的场景。

基本操作示例：

• 包含头文件：#include <set>
• 创建 set 并插入元素：

此时 set 中元素为 {5, 10, 15}，已自动排序。

• 遍历输出：

• 查找元素：

• 删除元素：
s.erase(10); // 删除值为10的元素
• 自定义排序（例如降序）：
set<int, greater<int>> s_desc;
s_desc.insert(5);
s_desc.insert(10);
// 元素顺序：10, 5

unordered_set 的使用方法

unordered_set 基于哈希表实现，元素无序，插入、删除、查找平均时间复杂度为 O(1)，最坏情况 O(n)。适合只关心存在性而不关心顺序的场景。

基本操作示例：

• 包含头文件：#include <unordered_set>
• 创建 unordered_set 并插入：
unordered_set<int> us;
us.insert(10);
us.insert(5);
us.insert(15);

元素顺序不确定，可能是任意排列。

• 查找元素：
if (us.find(5) != us.end()) {
   cout << "5 exists";
}
• 删除元素：
us.erase(10);
• 遍历输出（顺序不固定）：
for (const auto& x : us) {
   cout << x << " ";
}
• 可以指定桶数或自定义哈希函数（高级用法）：
// 自定义哈希结构（例如对 pair）
struct HashPair {
   size_t operator()(const pair<int, int>& p) const {
      return hash<int>{}(p.first) ^ hash<int>{}(p.second);
   }
};

unordered_set<pair<int, int>, HashPair> custom_us;

set 与 unordered_set 的选择建议

根据实际需求选择：

• 需要元素有序或进行范围操作（如找前驱后继）→ 使用 set
• 只关心元素是否存在、插入/查找效率优先 → 使用 unordered_set
• 数据量大且哈希分布均匀时，unordered_set 更快
• 注意：unordered_set 可能因哈希冲突导致性能下降，set 性能更稳定
基本上就这些，掌握 insert、find、erase 和遍历就能应对大多数情况。