std::unordered_map 和 std::map 是 C++ 标准库中两种不同的关联容器，它们都用于存储键值对，但在实现方式、性能特点和使用场景上存在显著区别。以下是它们的主要区别：
1. 数据结构
std::map：- 基于 红黑树（一种自平衡二叉搜索树）实现。
- 键值对按照键的顺序存储，支持有序遍历。
std::unordered_map：- 基于 哈希表 实现。
- 键值对存储在哈希表中，不保证顺序。
2. 性能特点
- 查找操作：
std::map：平均时间复杂度为 O(log n)，因为需要在红黑树中进行二分查找。std::unordered_map：平均时间复杂度为 O(1)，但在最坏情况下（大量冲突）可能退化到 O(n)。
- 插入操作：
std::map：平均时间复杂度为 O(log n)，因为需要在红黑树中插入节点并保持平衡。std::unordered_map：平均时间复杂度为 O(1)，但在最坏情况下可能退化到 O(n)。
- 删除操作：
std::map：平均时间复杂度为 O(log n)，因为需要在红黑树中删除节点并保持平衡。std::unordered_map：平均时间复杂度为 O(1)，但在最坏情况下可能退化到 O(n)。
3. 内存使用
std::map：- 内存使用较为紧凑，因为红黑树的节点结构相对简单。
std::unordered_map：- 通常需要预留一定的空间来减少冲突，因此可能占用更多的内存。
4. 顺序
std::map：- 键值对按照键的顺序存储，支持有序遍历。
- 可以通过迭代器按顺序访问所有元素。
std::unordered_map：- 不保证键值对的顺序，遍历时的顺序是不确定的。
5. 适用场景
std::map：- 适用于需要按键的顺序访问元素的场景。
- 适用于需要频繁进行范围查询的场景。
std::unordered_map：- 适用于需要快速查找、插入和删除操作的场景。
- 适用于键的顺序不重要的场景。
示例代码
std::map
#include <iostream>
#include <map>int main() {std::map<int, std::string> m;m[1] = "one";m[3] = "three";m[2] = "two";// 遍历 map，按键的顺序输出for (const auto& pair : m) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}
std::unordered_map
#include <iostream>
#include <unordered_map>int main() {std::unordered_map<int, std::string> um;um[1] = "one";um[3] = "three";um[2] = "two";// 遍历 unordered_map，顺序不确定for (const auto& pair : um) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}
总结
std::map：- 基于红黑树实现，支持有序遍历。
- 查找、插入和删除操作的平均时间复杂度为 O(log n)。
- 适用于需要按键的顺序访问元素或进行范围查询的场景。
std::unordered_map：- 基于哈希表实现，不保证顺序。
- 查找、插入和删除操作的平均时间复杂度为 O(1)。
- 适用于需要快速查找、插入和删除操作的场景。
选择哪种容器取决于你的具体需求，例如是否需要有序遍历、是否需要高效查找等。
