c++oding="utf-8" ?>
unordered_map插入和查找比map快，因底层用哈希表实现，平均时间复杂度o(1)，而map基于红黑树为o(log n)；但哈希碰撞多时最坏o(n)，且不保证有序。
unordered_map插入和查找为什么比map快
因为底层用哈希表实现，平均时间复杂度是 O(1)，而 map 是红黑树，O(log n)。但要注意：哈希碰撞多时退化成链表，最坏可能到 O(n)；而且不保证元素顺序。
实际写法上，unordered_map 和 map 接口相似，但不支持按 key 有序遍历——别指望用 for (auto& p : umap) 得到升序结果。
初始化和常见插入方式有哪些
构造空容器、列表初始化、复制/移动，都支持。但注意初始化列表里不能有重复 key，否则后出现的会覆盖前面的：
std::unordered_map<int std::string> m1; // 空
std::unordered_map<int std::string> m2 = {{1,"a"}, {2,"b"}}; // OK
std::unordered_map<int std::string> m3 = {{1,"x"}, {1,"y"}}; // 插入后只有 {1,"y"}</int></int></int>
-
insert()对已存在 key 无效，返回std::pair<iterator bool></iterator>，可据此判断是否新增成功 -
emplace()更高效（原地构造），适合 value 类型较重的场景 -
operator[]会默认构造 value（比如int变 0，std::string变空串），即使 key 不存在也会“创建”一项
自定义类型作 key 怎么写 hash 和 ==
编译器只提供内置类型（int、std::string 等）的特化，用结构体或类当 key 必须手动提供哈希函数和相等比较：
struct Point {
int x, y;
bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};
namespace std {
template struct hash<point> {
size_t operator()(const Point& p) const {
return hash<int>{}(p.x) ^ (hash<int>{}(p.y) <p>上面的异或写法简单但不抗碰撞，生产环境建议用 <code>std::hash<int>{}(p.x) * 31 + std::hash<int>{}(p.y)</int></int></code> 这类乘加组合。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img
src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a>
<p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p>
</div>
<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>另外，<code>operator==</code> 必须和 hash 逻辑一致：如果 <code>a == b</code> 为 true，它们的 hash 值必须相同；反过来不强制，但 hash 冲突太多就慢。</p>
<h3>clear()之后内存一定释放吗</h3>
<p>不一定。<code>clear()</code> 只销毁所有元素并调用析构函数，但底层桶数组（bucket array）容量通常保持不变——这是为了后续插入避免反复 rehash。</p>
<p>想真正释放内存，得配合 <code>shrink_to_fit()</code>（C++11 起支持）：</p>
<pre class="brush:php;toolbar:false;">umap.clear();
umap.shrink_to_fit(); // 建议在 clear 后立即调用
不过这个调用是“提示”，实现可忽略；某些 libstdc++ 版本甚至没实现它。更稳妥的做法是用移动赋值：umap = std::unordered_map<k>{};</k>，这能确保释放旧空间。
迭代器失效规则也要小心：只有 rehash（比如 insert 导致扩容）会让全部迭代器失效；单个 erase() 只让被删元素的迭代器失效，其余仍可用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
