C++ map 和 unordered_map 的区别和联系

C++ map 和 unordered_map 的区别和联系

map 和 unordered_map 都是 C++ 标准库中关联容器，用于存储键值对。它们的主要区别在于底层实现和性能特性，联系在于它们都提供了键值对的存储和访问功能。

区别：

详细解释：

• 底层实现：

  • map 使用红黑树作为底层数据结构。红黑树是一种自平衡的二叉搜索树，保证了在插入、删除和查找操作时，树的高度始终保持在 O(log n) 级别。
  • unordered_map 使用哈希表作为底层数据结构。哈希表通过哈希函数将键映射到桶 (bucket) 中，从而实现快速的查找。

• 排序：

  • map 中的键是有序的，默认情况下按照键的 < 运算符进行排序。这意味着你可以按顺序遍历 map 中的元素。
  • unordered_map 中的键是无序的。元素的存储顺序取决于哈希函数和插入顺序。

• 查找复杂度：

  • map 的查找复杂度为 O(log n)，因为需要在红黑树中进行搜索。
  • unordered_map 的平均查找复杂度为 O(1)，因为哈希表可以根据键直接定位到对应的桶。但是，在最坏情况下 (例如，所有键都哈希到同一个桶)，查找复杂度会退化为 O(n)。

• 插入和删除复杂度：

  • map 的插入和删除复杂度为 O(log n)，因为需要在红黑树中进行调整。
  • unordered_map 的平均插入和删除复杂度为 O(1)。但是，在最坏情况下，插入和删除复杂度会退化为 O(n)，并且可能需要重新哈希 (rehash) 以保持性能。

• 内存占用：

  • map 的内存占用通常比 unordered_map 略小，因为它不需要额外的空间用于哈希表。
  • unordered_map 的内存占用通常比 map 略大，因为它需要额外的空间用于哈希表，并且可能需要预留一些空桶以减少冲突。

• 迭代器：

  • map 的迭代器按键的顺序遍历元素。
  • unordered_map 的迭代器遍历元素的顺序是不确定的，取决于哈希函数和插入顺序。

• 适用场景：

  • 如果你需要键的有序性，例如范围查询或按顺序输出，那么 map 是一个更好的选择。
  • 如果你追求快速查找、插入和删除，并且不关心键的顺序，那么 unordered_map 是一个更好的选择。

• 哈希函数：

  • map 不需要提供哈希函数，因为它使用 < 运算符进行比较。
  • unordered_map 需要提供哈希函数，用于将键映射到桶中。你可以使用默认的 std::hash，也可以自定义哈希函数。

联系：

• 都是关联容器： 它们都用于存储键值对，并提供基于键的访问功能。
• 提供类似的操作： 它们都提供了 insert、erase、find、count 等操作，用于插入、删除、查找和统计元素。
• 都是模板类： 它们都是模板类，可以存储任意类型的键和值。

示例代码：

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>

int main() {
  // map
  std::map<std::string, int> myMap;
  myMap["apple"] = 1;
  myMap["banana"] = 2;
  myMap["orange"] = 3;

  std::cout << "map elements (ordered):" << std::endl;
  for (auto const& [key, val] : myMap) {
    std::cout << key << ": " << val << std::endl;
  }

  // unordered_map
  std::unordered_map<std::string, int> myUnorderedMap;
  myUnorderedMap["apple"] = 1;
  myUnorderedMap["banana"] = 2;
  myUnorderedMap["orange"] = 3;

  std::cout << "\nunordered_map elements (unordered):" << std::endl;
  for (auto const& [key, val] : myUnorderedMap) {
    std::cout << key << ": " << val << std::endl;
  }

  return 0;
}

总结：

选择 map 还是 unordered_map 取决于你的具体需求。如果你需要键的有序性，或者需要进行范围查询，那么 map 是一个更好的选择。如果你追求快速查找、插入和删除，并且不关心键的顺序，那么 unordered_map 是一个更好的选择。 在实际应用中，通常需要根据具体情况进行性能测试，以确定哪种容器更适合你的需求。