map基于红黑树实现，元素按键顺序存储，插入查找时间复杂度稳定o(log n)；unordered_map基于哈希表实现，无序存储，理想情况操作时间复杂度o(1)，但受哈希冲突影响可能退化为o(n)。1.底层结构：map使用红黑树保证有序，默认升序
排列
；unordered_map使用哈希表实现，依赖哈希函数映射键值。2.性能对比：map插入查找效率稳定，适合数据量小或频繁变动场景；unordered_map平均更快，但性能依赖哈希函数质量。3.内存与扩容：map内存分配稳定，无明显扩容行为；unordered_map插入可能触发rehash，导致偶尔延迟尖峰，可通过reserve()预留空间避免。4.自定义类型支持：map需提供比较函数或重载<运算符；unordered_map需自定义哈希函数和相等判断函数。选择依据在于是否需要有序遍历、稳定性要求以及对查找速度的需求。
C++ 中的
和
都是用来存储
键值对
的数据结构，但它们底层实现不同，也导致了在使用场景和性能上有一些明显区别。
1. 底层结构：红黑树 vs 哈希表
是基于
红黑树
实现的，而
则是用
哈希表
来实现的。
红黑树是一种自平衡的二叉搜索树，这意味着插入、查找、删除的时间复杂度都是
O(log n)
。它能保证元素按照键的顺序存储，默认是升序排列。
立即学习
“
C++免费学习笔记（深入）
”；
哈希表则是通过哈希函数将键映射到特定的位置，理想情况下这些操作的时间复杂度可以达到
O(1)
，但在冲突严重时会退化为 O(n)（比如所有键都哈希到同一个桶中）。
所以如果你需要有序遍历键值对，就选
；如果更在意访问速度且不需要顺序，那
更合适。
2. 插入与查找性能对比
map 的插入和查找
：
C函数速查手册（CHM版）
C函数速查手册（CHM版）
下载
插入一个元素需要找到合适位置并调整树结构以维持平衡，时间稳定在 O(log n)。
查找也是通过比较进行，效率稳定，适合数据量不大或变化频繁的情况。
unordered_map 的插入和查找
：
插入和查找依赖哈希函数，理想情况非常快，O(1)，但如果哈希冲突多就会变慢。
所以它的性能受哈希函数质量影响较大，写一个合理的哈希函数很关键。
举个例子：如果你要频繁查找几万个字符串键，
可能比
快很多；但如果键类型是 int，而且范围集中，简单的哈希可能反而造成大量冲突，这时候
反倒更稳。
3. 内存占用与扩容机制
的内存分配相对稳定，每个节点单独申请空间，不会有明显的“扩容”行为。
在插入过程中可能会触发 rehash，也就是重新分配整个哈希表的空间，并把旧数据迁移过去，这会导致某些插入操作耗时突然增加。
所以如果你的应用对响应时间敏感，或者不希望偶尔出现延迟尖峰，那就要注意
的 rehash 行为。可以通过
提前预留足够空间来避免这个问题。
4. 是否支持自定义类型直接使用
要求键类型支持比较操作，通常默认是
运算符。如果是自定义类型，你需要提供一个比较函数或重载
。
需要提供一个哈希函数和相等判断函数（
），否则编译会报错。
例如：
相比之下，
对自定义类型的使用更简单些，只要能比较大小就行。
基本上就这些。选择
还是
，主要看你是更在意顺序、稳定性，还是追求平均更快的查找速度。
mapunordered_mapmapunordered_mapmapunordered_mapunordered_mapmapmapmapunordered_mapunordered_mapreserve()map<<unordered_map==struct MyKey {
int x, y;
};
// 要让 unordered_map 支持这个类型，你得写一个 hash 函数对象
namespace std {
template<>
struct hash {
size_t operator()(const MyKey& k) const {
return hash()(k.x) ^ hash()(k.y);
}
};
} mapmapunordered_map