原理上的差异
std::unordered_map 和 std::map 都是 C++ 标准库中的关联容器，用于存储键值对。但它们之间存在一些关键的差异：
- 内部实现:
std::map: 基于红黑树实现，是一个平衡二叉搜索树。std::unordered_map: 基于哈希表实现。
- 顺序:
std::map: 由于是基于红黑树，键值对总是按键的顺序排序。std::unordered_map: 如其名所示，键值对的顺序是无序的。
- 性能:
std::map: 查找、插入和删除的时间复杂度通常为 O(log n)。std::unordered_map: 在平均情况下，查找、插入和删除的时间复杂度为 O(1)。但在最坏的情况下，这些操作的时间复杂度可能会达到 O(n)。
- 哈希函数:
std::map: 不使用哈希函数。std::unordered_map: 使用哈希函数来确定元素在哈希表中的位置。
- 用途:
std::map: 当你需要有序的键值对或需要频繁地进行范围查询时，使用std::map是更好的选择。std::unordered_map: 当你不需要有序的键值对，并且主要关心查找、插入和删除的速度时，使用std::unordered_map是更好的选择。
- 空间使用:
std::map: 由于红黑树的结构，它可能会使用更多的内存。std::unordered_map: 通常使用较少的内存，但如果哈希表的负载因子过高，可能会导致重新哈希，这可能会暂时增加内存使用。
选择哪一个容器取决于你的具体需求。如果你需要有序的数据或范围查询，std::map 是更好的选择。如果你关心性能并且不需要有序的数据，std::unordered_map 可能是更好的选择。
确实，std::map 和 std::unordered_map 在构造时有一些差异，主要是由于它们的内部实现方式不同。下面我们详细讨论这两者在构造时的差异：
构造之间的差异
1. std::map 的构造：
std::map 的构造相对简单，因为它是基于红黑树实现的。以下是一些常见的构造方法：
- 默认构造：创建一个空的
std::map。
std::map<std::string, int> m1;
- 范围构造：使用另一个容器的元素范围来构造。
std::pair<std::string, int> arr[] = {{"Alice", 90}, {"Bob", 85}}; std::map<std::string, int> m2(arr, arr + 2);
- 拷贝构造：使用另一个
std::map来构造。
std::map<std::string, int> m3(m2);
- 移动构造：使用另一个
std::map的内容来构造，并使原std::map为空。
std::map<std::string, int> m4(std::move(m3));
- 初始化列表构造：
std::map<std::string, int> m5 = {{"Alice", 90}, {"Bob", 85}};
2. std::unordered_map 的构造：
由于 std::unordered_map 是基于哈希表实现的，它在构造时提供了一些额外的选项，主要与哈希函数和等价关系有关。
- 默认构造：创建一个空的
std::unordered_map。
std::unordered_map<std::string, int> um1;
- 范围构造：
std::pair<std::string, int> arr[] = {{"Alice", 90}, {"Bob", 85}}; std::unordered_map<std::string, int> um2(arr, arr + 2);
- 拷贝构造：
std::unordered_map<std::string, int> um3(um2);
- 移动构造：
std::unordered_map<std::string, int> um4(std::move(um3));
- 初始化列表构造：
std::unordered_map<std::string, int> um5 = {{"Alice", 90}, {"Bob", 85}};
- 指定桶数量的构造：可以在构造时指定初始桶数量，这有助于优化性能。
std::unordered_map<std::string, int> um6(50); // 50个桶
- 使用自定义哈希函数和等价关系的构造：
struct MyHash { size_t operator()(const std::string& s) const { // 自定义哈希函数 return std::hash<std::string>()(s); } }; struct MyEqual { bool operator()(const std::string& a, const std::string& b) const { // 自定义等价关系 return a == b; } }; std::unordered_map<std::string, int, MyHash, MyEqual> um7;
总的来说，std::map 和 std::unordered_map 在基本构造方法上都很相似，但 std::unordered_map 提供了一些额外的选项，允许用户更好地控制其哈希表的行为。
需要自定义哈希函数的情况
，std::unordered_map 在某些情况下需要自定义哈希函数，而 std::map 不需要。这主要是因为 std::unordered_map 是基于哈希表的，而 std::map 是基于红黑树的。
以下是一些需要为 std::unordered_map 提供自定义哈希函数的情况：
- 自定义对象作为键：当你使用自定义类型作为键时，C++ 标准库可能不知道如何为这种类型生成哈希值。在这种情况下，你需要提供自定义哈希函数。
struct Student { std::string name; int age; }; struct StudentHash { size_t operator()(const Student& s) const { return std::hash<std::string>()(s.name) ^ std::hash<int>()(s.age); } }; std::unordered_map<Student, int, StudentHash> scores;
- 优化性能：即使对于标准库知道如何哈希的类型，你仍然可能想要提供自定义哈希函数，以优化特定数据集的性能。例如，如果你知道键的某些属性，你可以设计一个更有效的哈希函数。
- 避免冲突：如果默认的哈希函数导致太多的冲突，你可能希望提供一个自定义的哈希函数，以减少冲突并提高性能。
对于 std::map，你不需要提供哈希函数，因为它不是基于哈希的。但是，如果你使用自定义类型作为键，你需要确保该类型支持 < 运算符，或者你可以提供自定义的比较函数。这是因为 std::map 需要能够比较键来在红黑树中正确地放置它们。
总之，当使用 std::unordered_map 时，你可能需要提供自定义哈希函数，特别是当使用自定义类型作为键时。而对于 std::map，你只需要确保键类型支持排序即可。
接口使用上的差异
在接口使用方面，std::map 和 std::unordered_map 有很多相似之处，这使得在许多情况下可以相对容易地在两者之间切换。但是，由于它们的内部实现和特性不同，还是存在一些差异。以下是一些关键点：
- 插入:
- 对于两者，你都可以使用
insert方法或operator[]来插入键值对。
- 查找:
std::map和std::unordered_map都提供了find方法来查找特定的键。
- 删除:
- 两者都使用
erase方法来删除键值对。
- 取值:
- 使用
operator[]或at方法可以从两种映射中获取值。但要注意，operator[]在键不存在时会插入该键并默认初始化其值。
- 遍历:
- 由于
std::map是有序的，你可以期望按键的顺序遍历它。而std::unordered_map的遍历顺序是不确定的。
- 特定功能:
std::map有一些std::unordered_map没有的方法，如lower_bound和upper_bound，这些方法用于范围查询。std::unordered_map允许你访问和修改其哈希函数和负载因子，这些在std::map中不适用。
总的来说，对于基本的插入、查找、删除和取值操作，两者的接口非常相似，可以相对无缝地替换。但是，如果你的代码依赖于 std::map 的排序特性或使用了特定于其中一个容器的功能，那么替换可能会更加复杂。在进行替换之前，最好仔细检查代码以确保没有任何潜在的问题。
代码举例
使用方式相似的场景：存储学生的成绩
#include <iostream> #include <map> #include <unordered_map> int main() { // 使用 std::map std::map<std::string, int> studentScoresMap; studentScoresMap["Alice"] = 90; studentScoresMap["Bob"] = 85; studentScoresMap["Charlie"] = 88; // 查找学生的成绩 if (studentScoresMap.find("Alice") != studentScoresMap.end()) { std::cout << "Alice's score: " << studentScoresMap["Alice"] << std::endl; } // 使用 std::unordered_map std::unordered_map<std::string, int> studentScoresUnorderedMap; studentScoresUnorderedMap["Alice"] = 90; studentScoresUnorderedMap["Bob"] = 85; studentScoresUnorderedMap["Charlie"] = 88; // 查找学生的成绩 if (studentScoresUnorderedMap.find("Alice") != studentScoresUnorderedMap.end()) { std::cout << "Alice's score: " << studentScoresUnorderedMap["Alice"] << std::endl; } return 0; }
在上述代码中，我们使用 std::map 和 std::unordered_map 的方式几乎完全相同。
使用方式不同的场景：存储并按顺序遍历学生的成绩
#include <iostream> #include <map> #include <unordered_map> int main() { // 使用 std::map std::map<std::string, int> studentScoresMap; studentScoresMap["Charlie"] = 88; studentScoresMap["Alice"] = 90; studentScoresMap["Bob"] = 85; // 按学生姓名的字母顺序遍历成绩 std::cout << "Using std::map:" << std::endl; for (const auto& pair : studentScoresMap) { std::cout << pair.first << ": " << pair.second << std::endl; } // 使用 std::unordered_map std::unordered_map<std::string, int> studentScoresUnorderedMap; studentScoresUnorderedMap["Charlie"] = 88; studentScoresUnorderedMap["Alice"] = 90; studentScoresUnorderedMap["Bob"] = 85; // 遍历成绩（顺序不确定） std::cout << "Using std::unordered_map:" << std::endl; for (const auto& pair : studentScoresUnorderedMap) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }
在这个例子中，使用 std::map 可以确保按学生姓名的字母顺序遍历成绩，而使用 std::unordered_map 则不能保证遍历的顺序。这是两者在使用上的一个主要区别。
结语
在我们的编程学习之旅中，理解是我们迈向更高层次的重要一步。然而，掌握新技能、新理念，始终需要时间和坚持。从心理学的角度看，学习往往伴随着不断的试错和调整，这就像是我们的大脑在逐渐优化其解决问题的“算法”。
这就是为什么当我们遇到错误，我们应该将其视为学习和进步的机会，而不仅仅是困扰。通过理解和解决这些问题，我们不仅可以修复当前的代码，更可以提升我们的编程能力，防止在未来的项目中犯相同的错误。
我鼓励大家积极参与进来，不断提升自己的编程技术。无论你是初学者还是有经验的开发者，我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用，不妨点击收藏，或者留下你的评论分享你的见解和经验，也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持，也是对我持续分享和创作的动力。
