c++的std::set和std::unordered_set性能对比 红黑树与哈希表【STL深入】

std::set 基于红黑树，稳定有序但插入/查找是 O(log n)

std::set 内部用红黑树实现，自动维护元素升序（按 operator 或自定义比较器），所有操作时间复杂度都是 O(log n)。适合需要频繁遍历有序数据、或依赖顺序语义（比如 lower_bound、upper_bound、范围查询）的场景。内存开销相对小，每个节点只存 key 和少量指针（通常 3 指针 + 颜色位），但树结构带来常数因子略高。

std::unordered_set 基于哈希表，平均 O(1) 但最坏 O(n)，无序

std::unordered_set 使用开放寻址或链地址法（标准未强制，libc++ 和 libstdc++ 多用桶+链表），平均查找/插入/删除为 O(1)，但依赖哈希函数质量和负载因子。当哈希冲突严重或 rehash 频繁时，性能可能退化到 O(n)。不保证顺序，迭代器遍历无逻辑规律。内存占用通常更高：需额外空间存桶数组、空闲槽位或链表指针，且默认最大负载因子为 1.0（可调）。

关键性能影响因素对比

• 数据规模小（n ：std::set 可能更快——哈希计算和桶跳转的开销抵消了 O(1) 优势，红黑树常数更可控。
• key 类型哈希成本高（如 std::string 长串）：std::unordered_set 的哈希计算本身成瓶颈，而 std::set 只做 log n 次比较，反而更稳。
• 存在大量重复插入/查找，且 key 分布不均：差的哈希函数（如对指针地址直接 cast）易导致聚集，unordered_set 性能骤降；set 则不受影响。
• 需要范围操作（如 [a,b) 内所有元素）：只有 set 支持高效 lower_bound + upper_bound 遍历；unordered_set 必须全表扫描。

实际选型建议

• 要有序、要范围查询、key 比较便宜（如 int、enum）→ 选 std::set。
• 纯成员存在性判断、插入后不关心顺序、key 有高质量哈希（如内置类型、短 string）、数据量大 → 优先考虑 std::unordered_set。
• 不确定时，先用 unordered_set；若实测发现哈希冲突多（bucket_count() 小但 load_factor() 接近 1）、或出现偶发长延迟，切换为 set 或自定义哈希/调整 max_load_factor()。
• 注意：unordered_set 的迭代器无效化规则更宽松（仅 rehash 时全部失效），而 set 插入不使已有迭代器失效——这对某些算法设计有影响。