c++的std::set和std::unordered_set该如何取舍？ (有序与哈希)

需顺序遍历时必须用std::set，因其红黑树实现保证升序；仅查存在性时优先unordered_set，平均O(1)查找但依赖哈希质量；key不可比较则选unordered_set，不可哈希则只能用set。

需要按顺序遍历或取范围时，必须用 std::set

如果你要频繁做 lower_bound、upper_bound、equal_range，或者需要迭代器保证升序（比如打印所有元素、做归并操作），std::set 是唯一选择。它底层是红黑树，天然有序，begin() 到 end() 就是从小到大。

而 std::unordered_set 的迭代器顺序完全不确定，每次插入/删除后都可能变，不能依赖遍历顺序。

• std::set 支持 key_comp() 自定义比较逻辑，能轻松实现字典序、长度优先等复合排序
• std::unordered_set 即使你重载了 operator== 和哈希函数，也无法提供任何顺序保证
• 若误把 unordered_set 当作有序容器用（比如想“取前 5 个最小值”），结果会随机且不可重现

只关心存在性判断和单点查找时，优先选 std::unordered_set

查一个元素在不在集合里，find() 或 count() 操作，std::unordered_set 平均是 O(1)，std::set 是 O(log n)。数据量大时差距明显——比如百万级元素，前者平均几次哈希+比较，后者要 20 层树跳转。

但要注意：这个“平均 O(1)”依赖哈希函数质量。如果大量键映射到同一桶（哈希冲突严重），性能会退化成 O(n)。

立即学习“C++免费学习笔记（深入）”；

• 内置类型（int、std::String）的默认哈希通常够用；自定义结构体必须显式提供好哈希特化（std::hash）
• 插入顺序不影响查找效率，但极端情况下（如全哈希到同一个桶），unordered_set 可能比 set 还慢
• 内存占用通常更高：unordered_set 要预留空桶、维护指针链表；set 每节点只存 key + 3 个指针

元素类型不支持严格弱序比较时，不能用 std::set

std::set 要求 key 类型可比较（满足 Strict Weak Ordering），比如必须能用 比较两个对象，并满足自反性、传递性等。很多类型默认没定义 operator，比如 std::vector、自定义结构体、std::shared_ptr 等。

这时要么手动写比较器（Lambda 或 functor），要么改用 unordered_set —— 它只要求可哈希（std::hash）和可相等（operator==），门槛更低。

• 例如：用 std::vector 当 key，set 需要传入 lambda：

  std::set, std::less<>> s;

  （c++14 起 std::less 支持泛型调用）

• 而 unordered_set 必须特化 std::hash<:vector>>，否则编译失败
• 没有比较器也不打算写？那 set 直接不可用，别硬扛

内存受限或对最坏性能敏感时，std::set 更可控

std::unordered_set 的 rehash 行为是隐式的：当负载因子超过 max_load_factor()（默认 1.0），它会重新分配更大 bucket 数组，并把所有元素 rehash 过去。这是一次 O(n) 操作，可能卡住实时逻辑。

std::set 插入始终是 O(log n)，无突发开销，内存增长也平滑（每个节点单独 new）。

• 可用 reserve(n) 预分配 bucket，但无法完全避免 rehash；rehash(n) 可强制扩容，但需预估容量
• set 的内存局部性差（指针跳转多），unordered_set 的 bucket 数组连续，缓存友好——但前提是哈希分布均匀
• 调试时，unordered_set 的内部结构（桶数组+链表）比红黑树更难 inspect，GDB / ide 显示也不直观

实际选型往往不是非此即彼：先问自己三个问题—— 是否需要顺序？是否只查存在性？key 类型能否方便地比较或哈希？ 多数时候答案会自然指向一个。但别忽略 rehash 的毛刺、哈希碰撞的陷阱、以及调试时多花的那半小时。