map

  • 基于红黑树实现,红黑树的每个节点存储一个pair对象。
  • 键值对按照键的顺序排列。
  • 插入、删除、查找操作的平均时间复杂度为O(log n)

unordered_map

  • 基于哈希表实现。键值对在容器中的位置是由键的哈希值决定。
  • 插入、删除、查找的平均时间复杂度为O(1)

如何解决哈希冲突

multimap

  • key值可以重复出现