map

存储 key-value，==key唯一==

底层：红黑树。红黑树参考：RBTree

是否有序：有序（key升序）

unordered_map

存储key-value，==key唯一==

底层：哈希表。

是否有序：无序

multimap

存储key-value，==key不唯一==（一个key对应多个value）

底层：红黑树。

是否有序：有序（key升序）

unordered_multimap

存储key-vlaue，==key不唯一==（一个key对应多个value）

底层：哈希表。

总结：

  • 带有unordered就是哈希表，没有unordered就是红黑树
  • 带有multi就是可重复key

横向对比

有序用树，高速用哈希，重复用multi，唯一用map

特性 map multimap unordered_map unordered_multimap
底层结构 红黑树（平衡二叉搜索树） 红黑树 哈希表（Hash Table） 哈希表
元素顺序 有序（默认升序） 有序 无序 无序
键唯一性 唯一 可重复 唯一 可重复
插入/查找时间复杂度 O(log n) O(log n) O(1)（平均），O(n)（最坏） O(1)（平均），O(n)（最坏）
内存占用 较高（树节点额外信息） 较高 较低（但需预留哈希桶空间） 较低
operator[]支持 ✅ ❌ ✅ ❌
适用场景 需有序遍历或范围查询 需有序且允许键重复 高频查找且无需顺序 高频插入/删除且允许键重复