各容器对比

容器名称 类型 底层结构 元素顺序 键唯一性 时间复杂度（查找） 头文件
set 有序集合 红黑树 升序排列 唯一 O(log n) <set>
multiset 有序多重集合 红黑树 升序排列 可重复 O(log n) <set>
unordered_set 无序集合 哈希表 无顺序 唯一 平均 O(1) <unordered_set>
unordered_multiset 无序多重集合 哈希表 无顺序 可重复 平均 O(1) <unordered_set>
map 有序映射 红黑树 按键升序 唯一 O(log n) <map>
multimap 有序多重映射 红黑树 按键升序 可重复 O(log n) <map>
unordered_map 无序映射 哈希表 无顺序 唯一 平均 O(1) <unordered_map>
unordered_multimap 无序多重映射 哈希表 无顺序 可重复 平均 O(1) <unordered_map>

详细特性对比

1. 有序容器（基于红黑树）

特性 set/multiset map/multimap
存储内容 单一值（Key） 键值对（Key-Value）
键唯一性 set：唯一；multiset：可重复 map：唯一；multimap：可重复
排序方式 按 Key 升序排列 按 Key 升序排列
插入/删除/查找性能 O(log n) O(log n)
内存占用 较高（树节点开销） 较高（树节点开销）
适用场景 需要有序遍历或范围查询 需要按键有序遍历或范围查询
自定义排序 支持（通过比较器） 支持（通过比较器）

2. 无序容器（基于哈希表）

特性 unordered_set/unordered_multiset unordered_map/unordered_multimap
存储内容 单一值（Key） 键值对（Key-Value）
键唯一性 unordered_set：唯一；unordered_multiset：可重复 unordered_map：唯一；unordered_multimap：可重复
排序方式 无特定顺序 无特定顺序
插入/删除/查找性能 平均 O(1)，最坏 O(n)（哈希冲突时） 平均 O(1)，最坏 O(n)
内存占用 较低（哈希表可能稀疏） 较低（哈希表可能稀疏）
适用场景 快速查找，无需顺序 快速按键查找，无需顺序
哈希函数要求 需要为 Key 定义哈希函数 需要为 Key 定义哈希函数

核心区别总结

1. 性能对比

  • 红黑树容器：
    • 所有操作（插入、删除、查找）的时间复杂度稳定为 O(log n)。
    • 内存占用较高（每个节点需存储父/子节点指针和颜色标记）。
  • 哈希表容器：
    • 平均时间复杂度为 O(1)，但哈希冲突时可能退化为 O(n)。
    • 内存占用较低，但哈希表扩容时会发生 rehash，可能导致性能抖动。

2. 哈希函数要求

  • 无序容器需要为 Key 类型提供哈希函数：
    • 内置类型（如 int、string）已默认支持。
    • 自定义类型需手动实现哈希函数（例如特化 std::hash 或传递哈希函数对象）。

选择容器的决策树

  1. 需要键值对吗？
    • ✔️ 是 → 选择 map、multimap、unordered_map 或 unordered_multimap。
    • ❌ 否 → 选择 set、multiset、unordered_set 或 unordered_multiset。
  2. 允许重复键吗？
    • ✔️ 是 → 选择 multiset、multimap、unordered_multiset 或 unordered_multimap。
    • ❌ 否 → 选择 set、map、unordered_set 或 unordered_map。
  3. 需要元素有序吗？
    • ✔️ 是 → 选择红黑树容器（set、map、multiset、multimap）。
    • ❌ 否 → 选择哈希表容器（unordered_*）。