一、性能对比

unordered_map

• 基于哈希表实现，平均时间复杂度为 O(1)（插入、删除、查找）。
• 最坏情况下（哈希冲突严重）时间复杂度退化到 O(n)。
• 不保证元素顺序，遍历结果与插入顺序无关。

map

• 基于红黑树实现，时间复杂度稳定为 O(log n)（插入、删除、查找）。
• 元素按键值自动排序（默认升序），遍历结果为有序序列。

二、内存占用

• unordered_map：哈希表需要维护桶和链表/开放寻址结构，内存开销通常更高。
• map：红黑树节点存储父子指针和颜色标记，内存占用相对更低。

三、适用场景

优先使用 unordered_map 的情况

• 需要高频插入、删除、查找，且不关心元素顺序。
• 键类型支持高效的哈希函数（如基本类型、标准库字符串）。

优先使用 map 的情况

• 需要按键顺序遍历或范围查询（如输出有序结果）。
• 键类型无良好哈希函数（需自定义哈希时可能引入性能问题）。

四、代码示例

unordered_map 示例

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> word_count;
word_count["apple"] = 5;  // O(1) 插入
word_count["banana"] = 3;
if (word_count.find("apple") != word_count.end()) {  // O(1) 查找
    // 存在键 "apple"
}

map 示例

#include <map>
#include <string>

std::map<std::string, int> sorted_word_count;
sorted_word_count["banana"] = 3;  // O(log n) 插入
sorted_word_count["apple"] = 5;
for (const auto& pair : sorted_word_count) {  // 有序遍历
    // 输出顺序: apple -> banana
}

五、特殊注意事项

• 键类型要求：

  • map 要求键类型支持 < 操作符或自定义比较器。
  • unordered_map 要求键类型支持哈希函数和 == 操作符。

• 自定义哈希函数（仅 unordered_map 需要）：

  struct CustomKey {
      int id;
      std::string name;
  };
  
  struct CustomHash {
      size_t operator()(const CustomKey& k) const {
          return std::hash<int>()(k.id) ^ std::hash<std::string>()(k.name);
      }
  };
  
  std::unordered_map<CustomKey, int, CustomHash> custom_map;