如何通过实战详述使用std::merge高效合并两个已排序的std::vector？

本文共计943个文字，预计阅读时间需要4分钟。

许多人使用std::merge后发现输出乱序，首个反应是函数存在bug。实际上，根本原因是传入了无序数据。它不验证输入，也不报错，仅按升序逻辑逐个比较并归并。若输入本身不满足单调性，结果自然错乱。

• 两个 vector 必须同为升序（或同为降序），不能一个升序一个降序
• 升序指满足 a[i] ，空容器或单元素视为合法
• 若不确定是否有序，先用 std::is_sorted(v.begin(), v.end()) 检查（调试时加断言）
• 误用场景典型例子：把刚 push_back 几个数的 vector 当作已排序序列传入

目标容器空间不足会导致越界写入或未定义行为

std::merge 不会自动扩容目标容器，它只按你给的迭代器位置写入。传 result.begin() 却没提前分配空间，轻则覆盖栈内存，重则崩溃；用 back_inserter 虽安全但性能打折。

• 推荐方式：result.reserve(a.size() + b.size()); merge(..., back_inserter(result));
• 若需精确控制内存（如嵌入式或高频调用），改用 result.resize(a.size() + b.size()); merge(..., result.begin());
• 绝对不要写 vector<int> result; merge(..., result.begin());</int> —— 此时 result.begin() 是 result.end()，写入即越界
• 注意 reserve() 不改变 size()，所以 back_inserter 仍能正确追加

std::inplace_merge不适合合并两个独立vector

看到 “inplace” 就以为能省空间？实际它是为“同一容器内两段有序区间”设计的。硬把 b 插入 a 尾部再调用它，等于白干一次 O(n) 移动，还可能触发多次 realloc。

• 正确适用场景：比如 a = {1,3,5,2,4,6}，前3个和后3个各自有序，想原地合并成一个有序序列
• 错误做法：a.insert(a.end(), b.begin(), b.end()); inplace_merge(a.begin(), a.begin() + a_size, a.end());
• 若真要“零拷贝”，可 swap + merge：vector<int> temp; temp.swap(a); merge(temp.begin(), temp.end(), b.begin(), b.end(), back_inserter(a));</int>
• inplace_merge 内部策略不透明（可能用缓存，也可能不用），性能不可控，别为省几字节冒险

自定义比较函数必须与输入顺序一致

升序输入却传 greater<int></int>，结果是倒序排列的乱序混合体——因为 std::merge 只负责“按你给的规则归并”，不关心你逻辑是否自洽。

立即学习“C++免费学习笔记（深入）”；

• 升序输入 → 用默认 或 <code>less<int></int>
• 降序输入 → 显式传 greater<int></int>，且两个输入都得是降序
• 自定义类型务必保证比较函数满足严格弱序（transitivity、irreflexivity 等）
• 常见陷阱：用 abs 比较整数，导致 -3 和 3 视为相等，破坏归并逻辑

真正容易被忽略的是：std::merge 的输出迭代器必须可写、可递增，且指向的位置数量不少于输入总长——这个约束不靠编译器检查，全靠人脑预判。 一旦漏掉 reserve 或 resize，问题往往在压测时才暴露，且难以复现。