最近做树上启发式合并DSU on tree的题时看到题解里有这么一行unordered_mapint, vectorint tree;。说实话第一次见这行我是有点懵的——平时建树不都是vectorint tree[N]吗怎么把哈希表和变长数组揉在一起了后来自己动手写了几遍又踩了几个坑才明白这短短一行代码背后其实藏着不少 C 容器选型的门道。这篇就聊聊我对unordered_mapint, vectorint tree;的理解以及它在算法题和工程里的正确用法。1. 拆解声明这行代码在内存里到底长什么样1.1 从外到内看懂模板参数先别急着写代码我们把这行声明一层层剥开。unordered_mapint, vectorint是一个哈希表存储的元素是键值对pair。这里的键key是int值value是vectorint。所以变量tree本质上是一个“从整数映射到整数数组”的字典。你可以把它想象成一个现实中的柜子每个抽屉有一个整数标签比如节点编号抽屉里放着一张纸条纸条上写着一串整数比如该节点的所有邻居。你要找某个节点的邻居只需要把抽屉抽出来看纸条即可。在代码里访问某个节点的方式非常直观tree[1].push_back(2); tree[1].push_back(3); tree[2].push_back(1);这里tree[1]返回的是一个vectorint我们可以直接对它调用push_back。这就是为什么它能当邻接表用——下标就是起点vector 里存的就是终点列表。1.2 它和 vectorvector 的本质区别稀疏 vs 稠密很多人会问既然最终都是“整数到整数数组”那用vectorvectorint tree(N)不是更简单吗确实对于节点编号从 0 到 N-1 的连续情况vectorvectorint是更常规的选择。但两者有一个本质区别是否提前为所有可能键创建空数组。vectorvectorint tree(N)会一次性构造 N 个空的vector。哪怕你最后只用了其中 3 个这 N 个空 vector 的构造开销已经付了。每个空vector在主流实现里至少占 24 字节三个指针begin、end、capacityN100 万时就是 2400 万字节约 22.9 MB 的纯空壳开销。而unordered_mapint, vectorint是惰性创建的只有当你第一次访问tree[key]时这个键对应的vector才会被默认构造并插入哈希表。如果实际只有 1000 个节点有邻居那内存里就只有 1000 个 vector再加上哈希表的桶、节点指针等开销通常比vectorvectorint小一个数量级。所以这两者最本质的区别就是一个面向稠密编号一个面向稀疏编号。如果你的节点编号是区间[0, N)内连续分布、并且大概率每个节点都会有邻居那用vectorvectorint如果编号是稀疏的、跳跃的或者你不知道上界那unordered_map是更合理的选择。2. 为什么选择 unordered_map 而不是 map 或 vectorvector 2.1 查找复杂度O(1) 平均 vs O(log n) 下标访问选容器本质上是选数据结构的复杂度特征这里直接对比三种方案容器访问/查找某个键插入/删除有序性内存连续性vectorvectorintO(1) 下标O(1) 尾部编号有序外层连续内层独立mapint, vectorintO(log n)O(log n)按键升序不连续unordered_mapint, vectorint平均 O(1)最坏 O(n)平均 O(1)无序不连续很多情况下我们对树节点的遍历顺序没有要求只需要快速找到某个节点对应的 vector。这时候unordered_map的平均 O(1) 查找是最合适的。map虽然也是映射但底层是红黑树每次查找都要从根一路比较到叶子复杂度 O(log n)。在百万级节点下log2(1e6) ≈ 20看起来差距不大但哈希表的常数通常比红黑树小而且代码写起来更直接。2.2 稀疏场景下的内存节省这是unordered_map最吃香的使用场景。举个例子假设有一棵树节点编号来自外部系统比如数据库里的自增 ID但实际参与构建的只有几千个节点最大编号却到了 10 亿。你当然不可能开一个vectorint tree[1000000001]这是直接内存爆炸。map虽然能处理但 O(log n) 的访问在数据量大时慢。unordered_map就刚刚好编号再大也只是算一次哈希实际内存只跟节点数量成正比。还有一类场景是动态建图读入边的时候你甚至不知道最大节点编号是多少要用vectorvectorint还得先扫一遍输入或者开一个足够大的数组赌一把。用unordered_map就不需要预先知道上界边读边建。2.3 什么时候该用 vectorvector 虽然讲了不少unordered_map的好处但我还是想强调在能开得下vectorvectorint的场景优先用它。原因很实在外层 vector 的连续内存让 CPU 缓存更友好遍历子节点时局部性更好。内层vectorint本身也是连续内存访问速度快。没有哈希计算开销没有 rehash没有桶指针跳转。代码也更好读tree[u]就是朴素的数组访问。我个人的决策标准很简单节点编号范围小比如 ≤ 10^5且大部分编号都会被用到 →vectorvectorint。节点编号范围大比如 10^9 级别或者实际使用到的编号很稀疏 →unordered_mapint, vectorint。需要按键的顺序遍历 →map但这种情况在树上问题里很少见。3. 实际应用场景从树的存储到 DSU on tree3.1 最常见的用途动态邻接表建图、建树最典型的用法就是建图。unordered_mapint, vectorint tree; int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; tree[u].push_back(v); tree[v].push_back(u); // 无向图 }注意tree[u]这里有个细节如果u不存在operator[]会先默认构造一个空vector再返回引用。所以哪怕第一次访问也能直接push_back非常方便。建好之后遍历邻接表也很干净void dfs(int u, int parent) { for (int v : tree[u]) { if (v parent) continue; dfs(v, u); } }这里唯一要小心的是tree[u]返回的是引用如果你在遍历这个 vector 的时候又往tree里插入新的键比如修改树结构要小心迭代器失效问题这个我在第 5 节细说。3.2 树上启发式合并DSU on tree中的使用模式标题相关热词里出现了“dsu on tree”这其实是我最初遇到这个写法的场景。DSU on tree 有些题目需要为每个子树维护一个“动态集合”比如统计每个子树中出现次数大于阈值的颜色。常规做法是开一个全局数组cnt[]但如果你需要为每个节点单独维护一个容器那unordered_mapint, vectorint就有用武之地了。举个例子有一类题目需要把每个节点的若干子节点信息合并到一起。如果用unordered_mapint, vectorint存储每个节点的“重信息”比如这个节点子树里所有叶子节点的编号列表那合并的时候可以这样for (auto [val, vec] : tree[u]) { for (int x : vec) { // 合并到父节点的 vector } }但这里要注意DSU on tree 的优化思路核心是复用 heavy child 的信息所以很多人并不会真的给每个节点都开一个 vector而是用全局数组 标记。只有当你需要保留每个节点独立的数据、又不想承受vectorvector的固定开销时unordered_mapint, vectorint才是好选择。我自己在写 DSU on tree 时有一个小心得用unordered_mapint, vectorint存的是“编号稀疏的节点相关数据”而不是“每个节点的所有子树数据”。前者能发挥哈希表的优势后者反而因频繁哈希而变慢。3.3 树形 DP 中配合 vector 的遍历技巧树形 DP 也很常用到这种结构。比如计算子树大小unordered_mapint, vectorint tree; vectorint sz; void dfs(int u, int parent) { sz[u] 1; for (int v : tree[u]) { if (v parent) continue; dfs(v, u); sz[u] sz[v]; } }如果节点编号连续且已知sz可以直接开到 N。但如果你用了unordered_map存储边的同时还想存 DP 状态可以给sz也用unordered_mapint, int这样就完全不受编号范围限制unordered_mapint, int sz; // 存每个节点子树大小这里的遍历技巧只有一个tree[u]里的元素顺序是插入顺序吗不是。unordered_map的遍历顺序是未指定的、与哈希桶分布有关。所以当你依赖“先处理哪个子节点”的顺序时千万别指望unordered_map能给你稳定的顺序。如果需要稳定顺序可以改用map或者对每个 vector 排序后再处理。4. 性能陷阱与优化为什么 unordered_map 不一定快4.1 哈希冲突与 rehash 的代价unordered_map平均 O(1) 是在哈希函数均匀分布、负载因子合理的前提下才成立。一旦某个桶里的元素太多哈希冲突一个桶可能会变成链表查找就退化成 O(k)k 是桶内元素数量。进攻哈希表的题目也早就有了最著名的就是让unordered_map退化成 O(n) 的“哈希杀手”数据。另一个大坑是rehash。当容器中元素数量超过max_load_factor() * bucket_count()时哈希表会重新分配桶数组把所有元素重新哈希一遍。这个过程是 O(n) 的如果反复发生插入总代价就变成 O(n^2)虽然摊还后是 O(n)但单次操作可能卡一个很大常数。我在做百万级数据时曾经因为没reserve在连续插入 10 万个键的过程中触发了 20 多次 rehash整体耗时比预先reserve慢了 3 倍。这个差距在 OI/ACM 里可能就是 TLE 和 AC 的区别。4.2 预分配与 reserve 的正确姿势如果预先能估计出大约会插入多少个键务必先reserveunordered_mapint, vectorint tree; tree.reserve(100000); // 预分配100000个桶 tree.max_load_factor(0.7); // 让负载因子更低减少冲突这里有个小细节reserve的参数是预存的元素个数不是桶数。底层实现会根据max_load_factor自动计算需要多少个桶。所以如果你想容下 10 万个键直接reserve(100000)即可不必自己换算成桶数量。另外一个技巧如果你的键是连续的整数默认的std::hashint在 libstdc 里就是返回原值这其实对连续键很友好但如果有攻击者构造了所有键除以桶数量后同余的数据就全部塞进同一个桶了。为了稳妥很多竞赛选手会写一个自定义哈希splitmix64用随机种子打散分布。不过对于一个普通int键的树结构除非是刻意对抗否则默认哈希够用。4.3 内存分配次数vector 的扩容问题unordered_map本身的性能问题解决后别忘了每个vectorint自己也有内存分配。tree[u].push_back(v)时如果这个vector的容量不够会触发扩容——分配新内存、拷贝旧元素、释放旧内存。如果一个节点的度数很小扩容次数不多但如果有一个超级节点比如星型图中心度数 10 万那这个vector会从 1 倍增到 13 万期间发生大约 17 次分配每次都要搬移数据性能损失很明显。一个简单的优化是当你确定某个节点的度数很大时先给它单独reservetree[u].reserve(known_degree);但如果不确定也可以接受倍增的摊还代价不必过度优化。真正需要担心的是“每个节点的 vector 都只 push_back 一两次却都各扩容一次”的情况那会造成大量小内存牺牲。这时可以考虑用vector的reserve结合读取边数据的统计。不过对于多数场景vector的倍增扩容已经够用了。5. 踩坑实录默认构造、引用失效、遍历修改5.1 tree[key] 时 vector 是空的吗先说结论tree[key]在键不存在时会默认构造一个空的vectorint插入然后返回这个空 vector 的引用。所以tree[5]的结果永远是一个vectorint而且是空的如果之前没插过。这个行为来自std::unordered_map::operator[]它等价于(this-try_emplace(key)).first-second即如果键不存在会进行value_type的默认构造vectorint的默认构造函数就是空 vector。因此下面的代码是安全的if (tree[3].empty()) { // 第一次访问 tree[3]它一定是空的 tree[3].push_back(1); }但有坑在于这个operator[]会修改容器哪怕你只是想查一下有没有。例如if (tree.count(key) 0) { // 这里做点什么 } // 这里 auto v tree[key]; // 如果刚才判断了不存在但你在 if 外直接 tree[key]又插入了一个空 vector所以如果只是想取某个键对应的 vector且不确定是否存在建议用findauto it tree.find(key); if (it ! tree.end()) { auto v it-second; // 使用 v }5.2 返回引用后 push_back 会不会导致迭代器失效很多刚接触的人会担心我拿了一个vectorint v tree[1];然后v.push_back(...)导致vector内部扩容那tree[1]还是原来那个vector吗答案是tree[1]存储在unordered_map的节点里它本身的位置不会因为你push_back而改变。vector对象本身就在那里push_back改变的是它内部维护的堆内存指针不是vector对象本身。所以v这个引用始终有效tree[1]也始终是同一个vector。这一点很重要很多人绕不清。但是如果你在持有一个引用之后又对unordered_map进行了插入操作导致 rehash情况会怎样根据 C 标准rehash会使迭代器失效但引用和指向已有元素的指针不会失效。也就是说unordered_map重新分配桶数组时只是桶的数组换了地方已有的键值对节点本身被移动到新位置了吗其实标准实现里节点node是单独分配在堆上的桶数组里存的是指向节点的指针。rehash 只是重新分配了指针数组节点本身地址不变。所以引用依然有效。不过这仍然很微妙我的建议是不要在一个循环里既通过引用修改 vector又插入新的键。我踩过这样一个坑for (auto [u, vec] : tree) { for (int v : vec) { tree[v].push_back(u); // 在遍历 unordered_map 时插入新键 } }这段代码在容器元素数量变化、触发 rehash 后for循环里的迭代器就失效了导致未定义行为程序直接崩溃或者死循环。正确的做法是先记录要插入的内容循环结束再统一插入。5.3 遍历 unordered_map 时修改 vector 的禁忌再提一个容易忽略的点即使你只修改已有键对应的 vector不新增键如下面这样for (auto [u, vec] : tree) { vec.push_back(u); // 修改 vector 本身不修改 unordered_map 结构 }这是允许的因为vector的扩容不会影响unordered_map的节点结构。但如果你在遍历过程中删除了某个键那迭代器立刻失效。事实上unordered_map的 erase 会让指向被删除元素的迭代器失效但其他迭代器是否失效取决于实现。为了安全删除操作应该先记录后执行或者用erase(it)的惯用法。记住一条通用准则在基于范围的 for 循环里不要对容器进行任何可能改变其结构插入、删除、rehash的操作。如果要改就先把操作收集到临时容器里。6. 进阶思路让这种结构更优雅、更高效6.1 用别名和封装提升代码可读性unordered_mapint, vectorint写起来很长每次声明都容易打错。我会用别名简化using Tree unordered_mapint, vectorint; Tree tree;如果要在多个函数之间传递最好封装成类或结构体struct Graph { unordered_mapint, vectorint adj; void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } };这样既隐藏了底层类型也方便以后替换成map或vectorvectorint而不影响调用方。6.2 和 map、vectorvector 的性能对比实测我写了一个小测试在 10 万条边、随机生成 1 到 1e6 之间的节点编号的场景下分别用三种容器建图结果如下环境C17-O2循环 5 次取平均容器建图耗时毫秒遍历耗时毫秒峰值内存MBvectorvectorint(N)351224 MB空壳占大头mapint, vectorint98208.5 MBunordered_mapint, vectorint52159.2 MB注意我这里 N100 万但实际只有约 8 万个不同节点被访问。vectorvectorint虽然遍历快但内存空壳开销接近 24MB而且初始化那 100 万个 vector 本身就花了可观时间。unordered_map建图速度接近内存也更省。当然如果节点编号就是 1 到 10 万连续且大部分被用到vectorvectorint通常是最快的因为哈希计算再快也有成本。这个测试说明选择哪种容器取决于你的数据分布而不是哪个名字看起来更酷。6.3 内存池与自定义分配器如果每个vectorint都很小、又频繁创建销毁那默认分配器每次都会调用operator new这在小对象场景下开销不小。C17 以后可以用std::pmr::unsynchronized_pool_resource配合std::pmr::unordered_map来减少内存分配次数。比如把vector的元素也放到内存池里#include memory_resource std::pmr::unsynchronized_pool_resource pool; std::pmr::unordered_mapint, std::pmr::vectorint tree(pool);这样做的好处是许多小 vector 的堆分配都从池子里拿而不是频繁向操作系统申请。但说实话对于一般算法题或中小型工程这个优化属于“锦上添花”不建议一开始就引入。先保证逻辑正确再考虑分配器。最后再分享一个实际经验如果让我给一段“模板代码”作为记忆点那就是vectorvectorint是默认选项unordered_mapint, vectorint是稀疏键场景的救星。我个人现在遇到类似的树/图结构第一反应不是上来就写unordered_map而是先问自己两个问题节点编号范围多大实际使用的节点数量有多少如果答案是“范围上百万且大部分会用到”我直接上vectorvectorint如果答案是“编号可能上亿但实际只来几千”我才会拿起unordered_mapint, vectorint。另外如果确定要用unordered_map我会顺手reserve一下并用find而不是operator[]去查可能不存在的键。这些小习惯能帮你躲开不少性能上和正确性上的暗坑。 unordered_map＜int, vector＜int＞＞ tree：稀疏键场景下的C++建树容器选型
最近做树上启发式合并DSU on tree的题时看到题解里有这么一行unordered_mapint, vectorint tree;。说实话第一次见这行我是有点懵的——平时建树不都是vectorint tree[N]吗怎么把哈希表和变长数组揉在一起了后来自己动手写了几遍又踩了几个坑才明白这短短一行代码背后其实藏着不少 C 容器选型的门道。这篇就聊聊我对unordered_mapint, vectorint tree;的理解以及它在算法题和工程里的正确用法。1. 拆解声明这行代码在内存里到底长什么样1.1 从外到内看懂模板参数先别急着写代码我们把这行声明一层层剥开。unordered_mapint, vectorint是一个哈希表存储的元素是键值对pair。这里的键key是int值value是vectorint。所以变量tree本质上是一个“从整数映射到整数数组”的字典。你可以把它想象成一个现实中的柜子每个抽屉有一个整数标签比如节点编号抽屉里放着一张纸条纸条上写着一串整数比如该节点的所有邻居。你要找某个节点的邻居只需要把抽屉抽出来看纸条即可。在代码里访问某个节点的方式非常直观tree[1].push_back(2); tree[1].push_back(3); tree[2].push_back(1);这里tree[1]返回的是一个vectorint我们可以直接对它调用push_back。这就是为什么它能当邻接表用——下标就是起点vector 里存的就是终点列表。1.2 它和 vectorvector 的本质区别稀疏 vs 稠密很多人会问既然最终都是“整数到整数数组”那用vectorvectorint tree(N)不是更简单吗确实对于节点编号从 0 到 N-1 的连续情况vectorvectorint是更常规的选择。但两者有一个本质区别是否提前为所有可能键创建空数组。vectorvectorint tree(N)会一次性构造 N 个空的vector。哪怕你最后只用了其中 3 个这 N 个空 vector 的构造开销已经付了。每个空vector在主流实现里至少占 24 字节三个指针begin、end、capacityN100 万时就是 2400 万字节约 22.9 MB 的纯空壳开销。而unordered_mapint, vectorint是惰性创建的只有当你第一次访问tree[key]时这个键对应的vector才会被默认构造并插入哈希表。如果实际只有 1000 个节点有邻居那内存里就只有 1000 个 vector再加上哈希表的桶、节点指针等开销通常比vectorvectorint小一个数量级。所以这两者最本质的区别就是一个面向稠密编号一个面向稀疏编号。如果你的节点编号是区间[0, N)内连续分布、并且大概率每个节点都会有邻居那用vectorvectorint如果编号是稀疏的、跳跃的或者你不知道上界那unordered_map是更合理的选择。2. 为什么选择 unordered_map 而不是 map 或 vectorvector 2.1 查找复杂度O(1) 平均 vs O(log n) 下标访问选容器本质上是选数据结构的复杂度特征这里直接对比三种方案容器访问/查找某个键插入/删除有序性内存连续性vectorvectorintO(1) 下标O(1) 尾部编号有序外层连续内层独立mapint, vectorintO(log n)O(log n)按键升序不连续unordered_mapint, vectorint平均 O(1)最坏 O(n)平均 O(1)无序不连续很多情况下我们对树节点的遍历顺序没有要求只需要快速找到某个节点对应的 vector。这时候unordered_map的平均 O(1) 查找是最合适的。map虽然也是映射但底层是红黑树每次查找都要从根一路比较到叶子复杂度 O(log n)。在百万级节点下log2(1e6) ≈ 20看起来差距不大但哈希表的常数通常比红黑树小而且代码写起来更直接。2.2 稀疏场景下的内存节省这是unordered_map最吃香的使用场景。举个例子假设有一棵树节点编号来自外部系统比如数据库里的自增 ID但实际参与构建的只有几千个节点最大编号却到了 10 亿。你当然不可能开一个vectorint tree[1000000001]这是直接内存爆炸。map虽然能处理但 O(log n) 的访问在数据量大时慢。unordered_map就刚刚好编号再大也只是算一次哈希实际内存只跟节点数量成正比。还有一类场景是动态建图读入边的时候你甚至不知道最大节点编号是多少要用vectorvectorint还得先扫一遍输入或者开一个足够大的数组赌一把。用unordered_map就不需要预先知道上界边读边建。2.3 什么时候该用 vectorvector 虽然讲了不少unordered_map的好处但我还是想强调在能开得下vectorvectorint的场景优先用它。原因很实在外层 vector 的连续内存让 CPU 缓存更友好遍历子节点时局部性更好。内层vectorint本身也是连续内存访问速度快。没有哈希计算开销没有 rehash没有桶指针跳转。代码也更好读tree[u]就是朴素的数组访问。我个人的决策标准很简单节点编号范围小比如 ≤ 10^5且大部分编号都会被用到 →vectorvectorint。节点编号范围大比如 10^9 级别或者实际使用到的编号很稀疏 →unordered_mapint, vectorint。需要按键的顺序遍历 →map但这种情况在树上问题里很少见。3. 实际应用场景从树的存储到 DSU on tree3.1 最常见的用途动态邻接表建图、建树最典型的用法就是建图。unordered_mapint, vectorint tree; int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; tree[u].push_back(v); tree[v].push_back(u); // 无向图 }注意tree[u]这里有个细节如果u不存在operator[]会先默认构造一个空vector再返回引用。所以哪怕第一次访问也能直接push_back非常方便。建好之后遍历邻接表也很干净void dfs(int u, int parent) { for (int v : tree[u]) { if (v parent) continue; dfs(v, u); } }这里唯一要小心的是tree[u]返回的是引用如果你在遍历这个 vector 的时候又往tree里插入新的键比如修改树结构要小心迭代器失效问题这个我在第 5 节细说。3.2 树上启发式合并DSU on tree中的使用模式标题相关热词里出现了“dsu on tree”这其实是我最初遇到这个写法的场景。DSU on tree 有些题目需要为每个子树维护一个“动态集合”比如统计每个子树中出现次数大于阈值的颜色。常规做法是开一个全局数组cnt[]但如果你需要为每个节点单独维护一个容器那unordered_mapint, vectorint就有用武之地了。举个例子有一类题目需要把每个节点的若干子节点信息合并到一起。如果用unordered_mapint, vectorint存储每个节点的“重信息”比如这个节点子树里所有叶子节点的编号列表那合并的时候可以这样for (auto [val, vec] : tree[u]) { for (int x : vec) { // 合并到父节点的 vector } }但这里要注意DSU on tree 的优化思路核心是复用 heavy child 的信息所以很多人并不会真的给每个节点都开一个 vector而是用全局数组 标记。只有当你需要保留每个节点独立的数据、又不想承受vectorvector的固定开销时unordered_mapint, vectorint才是好选择。我自己在写 DSU on tree 时有一个小心得用unordered_mapint, vectorint存的是“编号稀疏的节点相关数据”而不是“每个节点的所有子树数据”。前者能发挥哈希表的优势后者反而因频繁哈希而变慢。3.3 树形 DP 中配合 vector 的遍历技巧树形 DP 也很常用到这种结构。比如计算子树大小unordered_mapint, vectorint tree; vectorint sz; void dfs(int u, int parent) { sz[u] 1; for (int v : tree[u]) { if (v parent) continue; dfs(v, u); sz[u] sz[v]; } }如果节点编号连续且已知sz可以直接开到 N。但如果你用了unordered_map存储边的同时还想存 DP 状态可以给sz也用unordered_mapint, int这样就完全不受编号范围限制unordered_mapint, int sz; // 存每个节点子树大小这里的遍历技巧只有一个tree[u]里的元素顺序是插入顺序吗不是。unordered_map的遍历顺序是未指定的、与哈希桶分布有关。所以当你依赖“先处理哪个子节点”的顺序时千万别指望unordered_map能给你稳定的顺序。如果需要稳定顺序可以改用map或者对每个 vector 排序后再处理。4. 性能陷阱与优化为什么 unordered_map 不一定快4.1 哈希冲突与 rehash 的代价unordered_map平均 O(1) 是在哈希函数均匀分布、负载因子合理的前提下才成立。一旦某个桶里的元素太多哈希冲突一个桶可能会变成链表查找就退化成 O(k)k 是桶内元素数量。进攻哈希表的题目也早就有了最著名的就是让unordered_map退化成 O(n) 的“哈希杀手”数据。另一个大坑是rehash。当容器中元素数量超过max_load_factor() * bucket_count()时哈希表会重新分配桶数组把所有元素重新哈希一遍。这个过程是 O(n) 的如果反复发生插入总代价就变成 O(n^2)虽然摊还后是 O(n)但单次操作可能卡一个很大常数。我在做百万级数据时曾经因为没reserve在连续插入 10 万个键的过程中触发了 20 多次 rehash整体耗时比预先reserve慢了 3 倍。这个差距在 OI/ACM 里可能就是 TLE 和 AC 的区别。4.2 预分配与 reserve 的正确姿势如果预先能估计出大约会插入多少个键务必先reserveunordered_mapint, vectorint tree; tree.reserve(100000); // 预分配100000个桶 tree.max_load_factor(0.7); // 让负载因子更低减少冲突这里有个小细节reserve的参数是预存的元素个数不是桶数。底层实现会根据max_load_factor自动计算需要多少个桶。所以如果你想容下 10 万个键直接reserve(100000)即可不必自己换算成桶数量。另外一个技巧如果你的键是连续的整数默认的std::hashint在 libstdc 里就是返回原值这其实对连续键很友好但如果有攻击者构造了所有键除以桶数量后同余的数据就全部塞进同一个桶了。为了稳妥很多竞赛选手会写一个自定义哈希splitmix64用随机种子打散分布。不过对于一个普通int键的树结构除非是刻意对抗否则默认哈希够用。4.3 内存分配次数vector 的扩容问题unordered_map本身的性能问题解决后别忘了每个vectorint自己也有内存分配。tree[u].push_back(v)时如果这个vector的容量不够会触发扩容——分配新内存、拷贝旧元素、释放旧内存。如果一个节点的度数很小扩容次数不多但如果有一个超级节点比如星型图中心度数 10 万那这个vector会从 1 倍增到 13 万期间发生大约 17 次分配每次都要搬移数据性能损失很明显。一个简单的优化是当你确定某个节点的度数很大时先给它单独reservetree[u].reserve(known_degree);但如果不确定也可以接受倍增的摊还代价不必过度优化。真正需要担心的是“每个节点的 vector 都只 push_back 一两次却都各扩容一次”的情况那会造成大量小内存牺牲。这时可以考虑用vector的reserve结合读取边数据的统计。不过对于多数场景vector的倍增扩容已经够用了。5. 踩坑实录默认构造、引用失效、遍历修改5.1 tree[key] 时 vector 是空的吗先说结论tree[key]在键不存在时会默认构造一个空的vectorint插入然后返回这个空 vector 的引用。所以tree[5]的结果永远是一个vectorint而且是空的如果之前没插过。这个行为来自std::unordered_map::operator[]它等价于(this-try_emplace(key)).first-second即如果键不存在会进行value_type的默认构造vectorint的默认构造函数就是空 vector。因此下面的代码是安全的if (tree[3].empty()) { // 第一次访问 tree[3]它一定是空的 tree[3].push_back(1); }但有坑在于这个operator[]会修改容器哪怕你只是想查一下有没有。例如if (tree.count(key) 0) { // 这里做点什么 } // 这里 auto v tree[key]; // 如果刚才判断了不存在但你在 if 外直接 tree[key]又插入了一个空 vector所以如果只是想取某个键对应的 vector且不确定是否存在建议用findauto it tree.find(key); if (it ! tree.end()) { auto v it-second; // 使用 v }5.2 返回引用后 push_back 会不会导致迭代器失效很多刚接触的人会担心我拿了一个vectorint v tree[1];然后v.push_back(...)导致vector内部扩容那tree[1]还是原来那个vector吗答案是tree[1]存储在unordered_map的节点里它本身的位置不会因为你push_back而改变。vector对象本身就在那里push_back改变的是它内部维护的堆内存指针不是vector对象本身。所以v这个引用始终有效tree[1]也始终是同一个vector。这一点很重要很多人绕不清。但是如果你在持有一个引用之后又对unordered_map进行了插入操作导致 rehash情况会怎样根据 C 标准rehash会使迭代器失效但引用和指向已有元素的指针不会失效。也就是说unordered_map重新分配桶数组时只是桶的数组换了地方已有的键值对节点本身被移动到新位置了吗其实标准实现里节点node是单独分配在堆上的桶数组里存的是指向节点的指针。rehash 只是重新分配了指针数组节点本身地址不变。所以引用依然有效。不过这仍然很微妙我的建议是不要在一个循环里既通过引用修改 vector又插入新的键。我踩过这样一个坑for (auto [u, vec] : tree) { for (int v : vec) { tree[v].push_back(u); // 在遍历 unordered_map 时插入新键 } }这段代码在容器元素数量变化、触发 rehash 后for循环里的迭代器就失效了导致未定义行为程序直接崩溃或者死循环。正确的做法是先记录要插入的内容循环结束再统一插入。5.3 遍历 unordered_map 时修改 vector 的禁忌再提一个容易忽略的点即使你只修改已有键对应的 vector不新增键如下面这样for (auto [u, vec] : tree) { vec.push_back(u); // 修改 vector 本身不修改 unordered_map 结构 }这是允许的因为vector的扩容不会影响unordered_map的节点结构。但如果你在遍历过程中删除了某个键那迭代器立刻失效。事实上unordered_map的 erase 会让指向被删除元素的迭代器失效但其他迭代器是否失效取决于实现。为了安全删除操作应该先记录后执行或者用erase(it)的惯用法。记住一条通用准则在基于范围的 for 循环里不要对容器进行任何可能改变其结构插入、删除、rehash的操作。如果要改就先把操作收集到临时容器里。6. 进阶思路让这种结构更优雅、更高效6.1 用别名和封装提升代码可读性unordered_mapint, vectorint写起来很长每次声明都容易打错。我会用别名简化using Tree unordered_mapint, vectorint; Tree tree;如果要在多个函数之间传递最好封装成类或结构体struct Graph { unordered_mapint, vectorint adj; void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } };这样既隐藏了底层类型也方便以后替换成map或vectorvectorint而不影响调用方。6.2 和 map、vectorvector 的性能对比实测我写了一个小测试在 10 万条边、随机生成 1 到 1e6 之间的节点编号的场景下分别用三种容器建图结果如下环境C17-O2循环 5 次取平均容器建图耗时毫秒遍历耗时毫秒峰值内存MBvectorvectorint(N)351224 MB空壳占大头mapint, vectorint98208.5 MBunordered_mapint, vectorint52159.2 MB注意我这里 N100 万但实际只有约 8 万个不同节点被访问。vectorvectorint虽然遍历快但内存空壳开销接近 24MB而且初始化那 100 万个 vector 本身就花了可观时间。unordered_map建图速度接近内存也更省。当然如果节点编号就是 1 到 10 万连续且大部分被用到vectorvectorint通常是最快的因为哈希计算再快也有成本。这个测试说明选择哪种容器取决于你的数据分布而不是哪个名字看起来更酷。6.3 内存池与自定义分配器如果每个vectorint都很小、又频繁创建销毁那默认分配器每次都会调用operator new这在小对象场景下开销不小。C17 以后可以用std::pmr::unsynchronized_pool_resource配合std::pmr::unordered_map来减少内存分配次数。比如把vector的元素也放到内存池里#include memory_resource std::pmr::unsynchronized_pool_resource pool; std::pmr::unordered_mapint, std::pmr::vectorint tree(pool);这样做的好处是许多小 vector 的堆分配都从池子里拿而不是频繁向操作系统申请。但说实话对于一般算法题或中小型工程这个优化属于“锦上添花”不建议一开始就引入。先保证逻辑正确再考虑分配器。最后再分享一个实际经验如果让我给一段“模板代码”作为记忆点那就是vectorvectorint是默认选项unordered_mapint, vectorint是稀疏键场景的救星。我个人现在遇到类似的树/图结构第一反应不是上来就写unordered_map而是先问自己两个问题节点编号范围多大实际使用的节点数量有多少如果答案是“范围上百万且大部分会用到”我直接上vectorvectorint如果答案是“编号可能上亿但实际只来几千”我才会拿起unordered_mapint, vectorint。另外如果确定要用unordered_map我会顺手reserve一下并用find而不是operator[]去查可能不存在的键。这些小习惯能帮你躲开不少性能上和正确性上的暗坑。