std::map 和 std::unordered_map

std::map 和 std::unordered_map 是 C++ STL 中的两种关联容器，它们在存储元素和查找元素的方式上有一些重大的区别。

1. 区别：

• std::map：

  • std::map 是有序关联容器，按照键值进行自动排序，默认按照键的升序排列。
  • 内部实现使用红黑树（Red-Black Tree），因此查找、插入和删除操作的平均时间复杂度为 O(log n)。
  • 需要额外的空间来存储树节点的指针，因此相对于 std::unordered_map 占用更多的内存。

• std::unordered_map：

  • std::unordered_map 是无序关联容器，不对元素进行排序，元素的存储位置由哈希函数决定。
  • 内部实现使用哈希表（Hash Table），因此查找、插入和删除操作的平均时间复杂度为 O(1)，但最坏情况下可能达到 O(n)。
  • 不需要维护元素的排序，因此在插入和删除元素时性能可能比 std::map 更好，但对于查找元素，std::map 在有序状态下的性能可能更好。

2. 适用场景：

• std::map 适用场景：

  • 当需要按照键值对进行自动排序时，可以选择使用 std::map。它适用于那些需要在遍历元素时按照键的顺序进行的场景。
  • 在需要在必定范围内查找键值时，std::map 的查找性能是稳定的，不会像 std::unordered_map 在最坏情况下出现线性查找时间。

• std::unordered_map 适用场景：

  • 当不需要元素有序，而更关心插入和删除的性能时，可以选择 std::unordered_map。它适用于大量插入和删除操作的场景。
  • 当查找频率较低，而插入和删除频率较高时，std::unordered_map 的性能一般优于 std::map。

总结：

• 如果需要有序的关联容器，或者对元素的顺序有严格要求，选择 std::map。
• 如果对元素的顺序无要求，更关心插入和删除操作的性能，选择 std::unordered_map。

在实际应用中，根据具体的需求和数据特点来选择合适的关联容器是很重大的，有时候也可以根据场景的不同在程序中灵活地使用这两种容器。