std::map基于红黑树，有序、O(log n)操作、内存紧凑；std::unordered_map基于哈希表，无序、平均O(1)查找但最坏O(n)、内存开销大、需支持hash和==。
std::map 是红黑树实现，std::unordered_map 是哈希表实现——这直接决定了它们在查找、插入、遍历、内存占用和异常安全上的根本差异。
查找和插入的时间复杂度不同
红黑树是平衡二叉搜索树，所有操作都基于比较和树结构调整；哈希表依赖散列函数和桶数组，冲突处理影响实际性能。
-
std::map::find()、insert()、erase()都是O(log n)，稳定可预测 -
std::unordered_map::find()平均O(1)，但最坏情况（大量哈希冲突）退化为O(n) - 插入时，
std::unordered_map可能触发rehash，导致所有迭代器失效；std::map插入只使指向被插入节点的迭代器有效，其余不变
元素是否有序 & 迭代顺序是否确定
这是最常被忽略但影响接口设计的关键点。
-
std::map的迭代器按key严格升序遍历（使用std::less），可用于范围查询（如lower_bound、upper_bound） -
std::unordered_map迭代顺序**完全不确定**，不保证插入顺序，也不保证哈希桶顺序；C++20 起仍无插入顺序保持机制（那是std::unordered_map的变种，如boost::container::flat_map或自定义链式哈希） - 若需有序遍历又想要哈希性能，只能额外维护一个
std::vector或std::set同步 key，不能靠unordered_map自身
对 Key 类型的要求不同
不是所有类型都能直接用在这两个容器里。
立即学习“C++免费学习笔记（深入）”；
-
std::map要求Key支持operator（或提供自定义比较器），比如int、std::string、自定义结构体（需重载） -
std::unordered_map要求Key有std::hash特化（标准库已提供int、std::string等），且支持operator==；自定义类型必须显式提供哈希函数和相等判断 - 例如：用
std::pair作 key 时，std::map可直接用，std::unordered_map需手动写哈希特化，否则编译失败
内存占用与局部性表现差异大
哈希表空间开销更大，但访问局部性可能更好（取决于哈希函数质量）；红黑树指针跳转多，缓存不友好但内存紧凑。
-
std::unordered_map默认负载因子上限为1.0，内部桶数组常预留较多空位（尤其rehash后），内存占用通常是map的 2–3 倍 -
std::map每个节点含两个指针（left/right）+ 父节点指针（部分实现）+ color 标志，结构固定；unordered_map节点还需额外存储 hash 值（某些实现）或 next 指针（链地址法） - 小数据量（
n ）时，std::map实际性能未必差于unordered_map，因后者哈希计算和指针间接访问开销明显
// 示例：自定义类型用于 unordered_map 必须提供 hash 和 ==
struct Point { int x, y; };
namespace std {
template<> struct hash {
size_t operator()(const Point& p) const {
return hash{}(p.x) ^ (hash{}(p.y) << 1);
}
};
}
bool operator==(const Point& a, const Point& b) {
return a.x == b.x && a.y == b.y;
}
std::unordered_map m; // OK
红黑树和哈希表没有绝对优劣，选错的关键往往不是“快不快”，而是“是否需要有序”“key 是否易哈希”“内存是否敏感”“是否接受最坏 O(n) 查找”。尤其注意：哈希表的迭代器失效规则、自定义类型的哈希实现、以及小规模数据下的实测性能反直觉现象。
