map基于红黑树，有序且性能稳定，适用于需排序或范围查询的场景；unordered_map基于哈希表，平均操作为O(1)，但无序且最坏情况为O(N)，适合对性能敏感且无需排序的场景。选择时应根据是否需要键的顺序、性能要求及自定义类型的支持复杂度来决定。两者在API上相似，但底层机制不同，理解差异有助于高效编程。使用自定义类型作键时，map需定义正确的operator
C++ STL中的
map
和
unordered_map
都是用来存储键值对（key-value pairs）的容器，它们的核心功能都是通过键快速查找对应的值。但它们在底层实现、性能特性以及适用场景上有着本质的区别：
map
基于红黑树实现，键默认是有序的，而
unordered_map
则基于哈希表实现，键的顺序是不可预测的，但平均查找速度更快。选择哪一个，往往取决于你对数据有序性的需求以及对性能稳定性的考量。
std::map
和
std::unordered_map
的使用方法在API层面有很多相似之处，但理解其内部机制对高效编程至关重要。
解决方案
std::map
是一个有序关联容器，它将键值对按照键的严格弱序进行排序。这意味着当你遍历
map
时，会得到一个按键升序排列的序列。
#include #include
std::unordered_map
是一个无序关联容器，它通过哈希表来组织元素，这使得它在平均情况下具有O(1)的查找、插入和删除时间复杂度。但它的缺点是元素没有固定的顺序，并且在最坏情况下（哈希冲突严重）性能可能退化到O(N)。
立即学习“C++免费学习笔记（深入）”；
#include #include #include void demonstrate_unordered_map() { std::unordered_map word_counts; // 插入元素 word_counts["apple"] = 5; word_counts.insert({"banana", 3}); word_counts["apple"]++; // 更新现有元素 // 访问元素 std::cout << "Count of apple: " << word_counts["apple"] << std::endl; // 遍历unordered_map（元素顺序不确定） std::cout << "Unordered Map contents:" << std::endl; for (const auto& pair : word_counts) { std::cout << "Word: " << pair.first << ", Count: " << pair.second << std::endl; } // 查找元素 auto it = word_counts.find("banana"); if (it != word_counts.end()) { std::cout << "Found banana with count: " <second << std::endl; } // 删除元素 word_counts.erase("apple"); std::cout << "After deleting apple, map size: " << word_counts.size() << std::endl;}int main() { std::cout << "--- Demonstrating std::map ---" << std::endl; demonstrate_map(); std::cout << "n--- Demonstrating std::unordered_map ---" << std::endl; demonstrate_unordered_map(); return 0;}
map
map
和
unordered_map
到底该怎么选？性能差异真的那么大吗？
选择
map
还是
unordered_map
，这确实是C++开发中一个很常见的决策点，而且它往往不是一个非黑即白的问题。我个人在项目中遇到这种选择时，通常会先问自己几个问题：数据需要排序吗？性能瓶颈在哪里？键的类型复杂吗？
从底层机制来看，
map
基于红黑树（一种自平衡二叉搜索树），而
unordered_map
基于哈希表。这两种数据结构决定了它们各自的性能曲线和适用场景。
性能差异：
std::map
(红黑树):时间复杂度: 插入、删除、查找操作的平均和最坏时间复杂度都是O(log N)。这里的N是容器中元素的数量。优点: 性能非常稳定和可预测，不会出现哈希表在最坏情况下的性能骤降。键默认有序，可以直接进行范围查询和有序遍历。缺点: 相比哈希表，
log N
操作在N很大时仍然比常数时间慢，而且每个节点通常需要额外的指针存储（比如父、左、右子节点），内存开销相对较大。
std::unordered_map
(哈希表):时间复杂度: 插入、删除、查找操作的平均时间复杂度是O(1)。在理想的哈希函数和负载因子下，这几乎是瞬间完成的。但最坏情况下，如果所有键都哈希到同一个桶（哈希冲突），操作会退化到O(N)，因为此时它就变成了一个链表。优点: 在大多数实际场景中，
unordered_map
的平均性能要远超
map
，尤其是在需要频繁进行查找和插入操作时。缺点: 性能波动性大，依赖于哈希函数的质量和负载因子。如果哈希函数设计不佳或数据分布特殊，可能导致大量冲突，从而使性能急剧下降。元素无序，不能直接进行有序遍历。内存开销也可能因为需要维护哈希桶数组而变大。
我的看法是，性能差异确实可能“非常大”，尤其是在处理大量数据时。一个O(1)的操作和O(log N)的操作，在N达到百万级别时，差距会是好几倍甚至几十倍。举个例子，如果N是100万，log₂(100万)大约是20。这意味着
map
可能需要20次比较，而
unordered_map
平均只需要1次。但是，这个“大”是平均意义上的，
unordered_map
的那个O(N)的“坑”一旦踩到，可能比
map
的O(log N)还要慢得多。
如何选择？
需要键的顺序吗？ 这是最直接的判断标准。如果你需要按键排序遍历，或者需要查找某个范围内的键（比如
lower_bound
,
upper_bound
），那么
map
是唯一的选择。性能是绝对优先吗？ 如果你的应用对速度极度敏感，并且你可以接受在极少数情况下可能出现的性能波动，或者你能确保键的哈希分布良好，那么
unordered_map
通常是更好的选择。键的类型复杂吗？ 如果键是自定义类型，
unordered_map
需要你提供哈希函数和相等比较运算符，这可能会比
map
仅仅需要小于运算符更麻烦一些（后面会详细讲）。内存消耗呢？ 尽管
map
每个节点有额外指针，但
unordered_map
在负载因子较低时也可能因为维护大量空桶而消耗更多内存。这需要具体分析。
我通常的经验是，如果对顺序没有特殊要求，我会倾向于先尝试
unordered_map
，因为它在平均情况下的表现确实令人惊艳。但如果遇到性能问题，或者键的类型难以提供高效哈希，又或者需要有序遍历，我就会毫不犹豫地切换到
map
。性能优化很多时候就是这样，在实际场景中不断权衡和调整。
自定义类型作为键，
map
map
和
unordered_map
各有什么“坑”？
当我们将自定义的结构体或类作为
map
或
unordered_map
的键时，会遇到一些需要特别处理的地方，否则程序可能无法编译，或者运行结果不符合预期。这些“坑”主要是因为两种容器对键的要求不同。
std::map
使用自定义类型作为键的“坑”：
std::map
的底层是红黑树，它需要知道如何对键进行排序。这意味着你的自定义类型必须提供一个严格弱序（Strict Weak Ordering）的比较方式。默认情况下，
map
会尝试使用键类型的
operator<
。
坑1：忘记或错误定义
operator<
。如果你的自定义类型没有定义
operator<
，或者定义的
operator<
不满足严格弱序的要求，编译器会报错。即使编译通过，如果
operator<
定义不正确（比如不满足传递性，或者
a < b
和
b < a
同时为false时
a
和
b
却不相等），
map
的内部结构可能会被破坏，导致查找失败或行为异常。示例：假设我们有一个
Point
结构体作为键。
struct Point { int x, y; // 错误的operator< 定义：只比较x，如果x相同则认为是相等，但y可能不同 // 这样会导致 (1,5) 和 (1,10) 被认为是相等的，但它们实际不同 // bool operator<(const Point& other) const { // return x < other.x; // } // 正确的operator< 定义：先比较x，x相同再比较y bool operator<(const Point& other) const { if (x != other.x) { return x < other.x; } return y < other.y; }};// 或者，你可以提供一个自定义的比较器作为map的模板参数struct PointCmp { bool operator()(const Point& a, const Point& b) const { if (a.x != b.x) return a.x < b.x; return a.y < b.y; }};// std::map myMap;
建议： 始终确保你的
operator<
是
const
成员函数，并且满足严格弱序的要求。对于复合类型，通常是按成员逐个比较。C++20引入的
operator
（三向比较运算符）可以大大简化这个过程。
std::unordered_map
使用自定义类型作为键的“坑”：
std::unordered_map
依赖哈希表，它需要知道如何计算键的哈希值以及如何判断两个键是否相等。
坑1：忘记或错误定义哈希函数。
unordered_map
默认会尝试使用
std::hash
。如果你的自定义类型没有对应的
std::hash
特化，或者你没有提供一个自定义的哈希函数，编译器会报错。示例：继续使用
Point
结构体。
struct Point { int x, y; // unordered_map还需要这个来判断两个键是否真正相等 bool operator==(const Point& other) const { return x == other.x && y == other.y; }};// 方式一：特化std::hashnamespace std { template struct hash { std::size_t operator()(const Point& p) const { // 一个简单的哈希组合方式，实际项目中可能需要更复杂的算法 // 这里使用std::hash对int进行哈希，然后异或组合 return std::hash()(p.x) ^ (std::hash()(p.y) << 1); } };}// 此时可以直接：std::unordered_map myUnorderedMap;// 方式二：提供一个自定义哈希函数对象作为模板参数struct PointHash { std::size_t operator()(const Point& p) const { return std::hash()(p.x) ^ (std::hash()(p.y) << 1); }};// std::unordered_map myUnorderedMap;
建议： 确保哈希函数返回
std::size_t
。哈希函数的质量直接影响
unordered_map
的性能，一个好的哈希函数应该能将不同的键均匀地分布到不同的哈希值。
坑2：忘记或错误定义
operator==
。
unordered_map
在哈希冲突时，会使用
operator==
来判断桶中哪个元素才是我们要找的。如果你的自定义类型没有定义
operator==
，或者定义不正确，程序可能无法编译，或者在哈希冲突时找不到正确的元素。建议：
operator==
也应该是
const
成员函数，并且要确保它能正确判断两个对象是否相等。
坑3：哈希函数与
operator==
不一致。这是最隐蔽也最致命的“坑”。C++标准要求，如果两个键
a
和
b
通过
operator==
判断是相等的（即
a == b
为真），那么它们的哈希值也必须相等（即
std::hash()(a) == std::hash()(b)
）。如果这个要求不满足，
unordered_map
的行为将是未定义的，可能会导致元素丢失、查找失败等各种奇怪问题。**示例
以上就是C++STL映射map和unordered_map使用方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1475240.html
微信扫一扫 
支付宝扫一扫 
