最近做树上启发式合并（DSU on tree）的题时，看到题解里有这么一行：unordered_map<int, vector<int>> tree;。说实话第一次见这行我是有点懵的——平时建树不都是vector<int> tree[N]吗？怎么把哈希表和变长数组揉在一起了？后来自己动手写了几遍，又踩了几个坑，才明白这短短一行代码背后其实藏着不少 C++ 容器选型的门道。这篇就聊聊我对unordered_map<int, vector<int>> tree;的理解，以及它在算法题和工程里的正确用法。

1. 拆解声明：这行代码在内存里到底长什么样

1.1 从外到内看懂模板参数

先别急着写代码，我们把这行声明一层层剥开。

unordered_map<int, vector<int>>是一个哈希表，存储的元素是键值对（pair）。这里的键（key）是int，值（value）是vector<int>。所以变量tree本质上是一个“从整数映射到整数数组”的字典。

你可以把它想象成一个现实中的柜子：每个抽屉有一个整数标签（比如节点编号），抽屉里放着一张纸条，纸条上写着一串整数（比如该节点的所有邻居）。你要找某个节点的邻居，只需要把抽屉抽出来看纸条即可。

在代码里，访问某个节点的方式非常直观：

tree[1].push_back(2); tree[1].push_back(3); tree[2].push_back(1);

这里tree[1]返回的是一个vector<int>&，我们可以直接对它调用push_back。这就是为什么它能当邻接表用——下标就是起点，vector 里存的就是终点列表。

1.2 它和 vector<vector > 的本质区别：稀疏 vs 稠密

很多人会问：既然最终都是“整数到整数数组”，那用vector<vector<int>> tree(N)不是更简单吗？确实，对于节点编号从 0 到 N-1 的连续情况，vector<vector<int>>是更常规的选择。但两者有一个本质区别：是否提前为所有可能键创建空数组。

vector<vector<int>> tree(N)会一次性构造 N 个空的vector。哪怕你最后只用了其中 3 个，这 N 个空 vector 的构造开销已经付了。每个空vector在主流实现里至少占 24 字节（三个指针：begin、end、capacity），N=100 万时就是 2400 万字节，约 22.9 MB 的纯空壳开销。

而unordered_map<int, vector<int>>是惰性创建的：只有当你第一次访问tree[key]时，这个键对应的vector才会被默认构造并插入哈希表。如果实际只有 1000 个节点有邻居，那内存里就只有 1000 个 vector，再加上哈希表的桶、节点指针等开销，通常比vector<vector<int>>小一个数量级。

所以这两者最本质的区别就是：一个面向稠密编号，一个面向稀疏编号。如果你的节点编号是区间[0, N)内连续分布、并且大概率每个节点都会有邻居，那用vector<vector<int>>；如果编号是稀疏的、跳跃的，或者你不知道上界，那unordered_map是更合理的选择。

2. 为什么选择 unordered_map 而不是 map 或 vector<vector >

2.1 查找复杂度：O(1) 平均 vs O(log n) 下标访问

选容器本质上是选数据结构的复杂度特征，这里直接对比三种方案：

很多情况下，我们对树节点的遍历顺序没有要求，只需要快速找到某个节点对应的 vector。这时候unordered_map的平均 O(1) 查找是最合适的。

map虽然也是映射，但底层是红黑树，每次查找都要从根一路比较到叶子，复杂度 O(log n)。在百万级节点下，log2(1e6) ≈ 20，看起来差距不大，但哈希表的常数通常比红黑树小，而且代码写起来更直接。

2.2 稀疏场景下的内存节省

这是unordered_map最吃香的使用场景。举个例子：假设有一棵树，节点编号来自外部系统，比如数据库里的自增 ID，但实际参与构建的只有几千个节点，最大编号却到了 10 亿。你当然不可能开一个vector<int> tree[1000000001]，这是直接内存爆炸。map虽然能处理，但 O(log n) 的访问在数据量大时慢。unordered_map就刚刚好：编号再大也只是算一次哈希，实际内存只跟节点数量成正比。

还有一类场景是动态建图：读入边的时候你甚至不知道最大节点编号是多少，要用vector<vector<int>>还得先扫一遍输入，或者开一个足够大的数组赌一把。用unordered_map就不需要预先知道上界，边读边建。

2.3 什么时候该用 vector<vector >

虽然讲了不少unordered_map的好处，但我还是想强调：在能开得下vector<vector<int>>的场景，优先用它。原因很实在：

• 外层 vector 的连续内存让 CPU 缓存更友好，遍历子节点时局部性更好。
• 内层vector<int>本身也是连续内存，访问速度快。
• 没有哈希计算开销，没有 rehash，没有桶指针跳转。
• 代码也更好读，tree[u]就是朴素的数组访问。

我个人的决策标准很简单：

• 节点编号范围小（比如 ≤ 10^5），且大部分编号都会被用到 →vector<vector<int>>。
• 节点编号范围大（比如 10^9 级别），或者实际使用到的编号很稀疏 →unordered_map<int, vector<int>>。
• 需要按键的顺序遍历 →map，但这种情况在树上问题里很少见。

3. 实际应用场景：从树的存储到 DSU on tree

3.1 最常见的用途：动态邻接表（建图、建树）

最典型的用法就是建图。

unordered_map<int, vector<int>> 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_map<int, vector<int>>就有用武之地了。

举个例子：有一类题目，需要把每个节点的若干子节点信息合并到一起。如果用unordered_map<int, vector<int>>存储每个节点的“重信息”（比如这个节点子树里所有叶子节点的编号列表），那合并的时候可以这样：

for (auto &[val, vec] : tree[u]) { for (int x : vec) { // 合并到父节点的 vector } }

但这里要注意：DSU on tree 的优化思路核心是复用 heavy child 的信息，所以很多人并不会真的给每个节点都开一个 vector，而是用全局数组 + 标记。只有当你需要保留每个节点独立的数据、又不想承受vector<vector>的固定开销时，unordered_map<int, vector<int>>才是好选择。

我自己在写 DSU on tree 时，有一个小心得：用unordered_map<int, vector<int>>存的是“编号稀疏的节点相关数据”，而不是“每个节点的所有子树数据”。前者能发挥哈希表的优势，后者反而因频繁哈希而变慢。

3.3 树形 DP 中配合 vector 的遍历技巧

树形 DP 也很常用到这种结构。比如计算子树大小：

unordered_map<int, vector<int>> tree; vector<int> 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_map<int, int>，这样就完全不受编号范围限制：

unordered_map<int, 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 的正确姿势

如果预先能估计出大约会插入多少个键，务必先reserve：

unordered_map<int, vector<int>> tree; tree.reserve(100000); // 预分配100000个桶 tree.max_load_factor(0.7); // 让负载因子更低，减少冲突

这里有个小细节：reserve的参数是预存的元素个数，不是桶数。底层实现会根据max_load_factor自动计算需要多少个桶。所以如果你想容下 10 万个键，直接reserve(100000)即可，不必自己换算成桶数量。

另外一个技巧：如果你的键是连续的整数，默认的std::hash<int>在 libstdc++ 里就是返回原值，这其实对连续键很友好，但如果有攻击者构造了所有键除以桶数量后同余的数据，就全部塞进同一个桶了。为了稳妥，很多竞赛选手会写一个自定义哈希（splitmix64），用随机种子打散分布。不过对于一个普通int键的树结构，除非是刻意对抗，否则默认哈希够用。

4.3 内存分配次数：vector 的扩容问题

unordered_map本身的性能问题解决后，别忘了每个vector<int>自己也有内存分配。

tree[u].push_back(v)时，如果这个vector的容量不够，会触发扩容——分配新内存、拷贝旧元素、释放旧内存。如果一个节点的度数很小，扩容次数不多；但如果有一个超级节点（比如星型图中心，度数 10 万），那这个vector会从 1 倍增到 13 万，期间发生大约 17 次分配，每次都要搬移数据，性能损失很明显。

一个简单的优化是：当你确定某个节点的度数很大时，先给它单独reserve：

tree[u].reserve(known_degree);

但如果不确定，也可以接受倍增的摊还代价，不必过度优化。真正需要担心的是“每个节点的 vector 都只 push_back 一两次，却都各扩容一次”的情况，那会造成大量小内存牺牲。这时可以考虑用vector的reserve结合读取边数据的统计。不过对于多数场景，vector的倍增扩容已经够用了。

5. 踩坑实录：默认构造、引用失效、遍历修改

5.1 tree[key] 时 vector 是空的吗

先说结论：tree[key]在键不存在时，会默认构造一个空的vector<int>插入，然后返回这个空 vector 的引用。所以tree[5]的结果永远是一个vector<int>，而且是空的（如果之前没插过）。

这个行为来自std::unordered_map::operator[]，它等价于(this->try_emplace(key)).first->second，即如果键不存在，会进行value_type的默认构造，vector<int>的默认构造函数就是空 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，且不确定是否存在，建议用find：

auto it = tree.find(key); if (it != tree.end()) { auto &v = it->second; // 使用 v }

5.2 返回引用后 push_back 会不会导致迭代器失效

很多刚接触的人会担心：我拿了一个vector<int>& 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_map<int, vector<int>>写起来很长，每次声明都容易打错。我会用别名简化：

using Tree = unordered_map<int, vector<int>>; Tree tree;

如果要在多个函数之间传递，最好封装成类或结构体：

struct Graph { unordered_map<int, vector<int>> adj; void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } };

这样既隐藏了底层类型，也方便以后替换成map或vector<vector<int>>而不影响调用方。

6.2 和 map、vector<vector > 的性能对比实测

我写了一个小测试，在 10 万条边、随机生成 1 到 1e6 之间的节点编号的场景下，分别用三种容器建图，结果如下（环境：C++17，-O2，循环 5 次取平均）：

注意：我这里 N=100 万，但实际只有约 8 万个不同节点被访问。vector<vector<int>>虽然遍历快，但内存空壳开销接近 24MB，而且初始化那 100 万个 vector 本身就花了可观时间。unordered_map建图速度接近，内存也更省。当然，如果节点编号就是 1 到 10 万连续且大部分被用到，vector<vector<int>>通常是最快的，因为哈希计算再快也有成本。

这个测试说明：选择哪种容器，取决于你的数据分布，而不是哪个名字看起来更酷。

6.3 内存池与自定义分配器

如果每个vector<int>都很小、又频繁创建销毁，那默认分配器每次都会调用operator new，这在小对象场景下开销不小。C++17 以后，可以用std::pmr::unsynchronized_pool_resource配合std::pmr::unordered_map来减少内存分配次数。

比如把vector的元素也放到内存池里：

#include <memory_resource> std::pmr::unsynchronized_pool_resource pool; std::pmr::unordered_map<int, std::pmr::vector<int>> tree(&pool);

这样做的好处是，许多小 vector 的堆分配都从池子里拿，而不是频繁向操作系统申请。但说实话，对于一般算法题或中小型工程，这个优化属于“锦上添花”，不建议一开始就引入。先保证逻辑正确，再考虑分配器。

最后再分享一个实际经验

如果让我给一段“模板代码”作为记忆点，那就是：vector<vector<int>>是默认选项，unordered_map<int, vector<int>>是稀疏键场景的救星。

我个人现在遇到类似的树/图结构，第一反应不是上来就写unordered_map，而是先问自己两个问题：节点编号范围多大？实际使用的节点数量有多少？如果答案是“范围上百万且大部分会用到”，我直接上vector<vector<int>>；如果答案是“编号可能上亿但实际只来几千”，我才会拿起unordered_map<int, vector<int>>。另外，如果确定要用unordered_map，我会顺手reserve一下，并用find而不是operator[]去查可能不存在的键。这些小习惯能帮你躲开不少性能上和正确性上的暗坑。