C++中std::merge怎么合并有序序列_C++标准库归并算法使用方法【操作】

std::merge要求两输入区间均已排序，否则行为未定义；输出容器需预先分配足够空间；自定义比较函数须与输入序列排序方式一致；返回输出末尾迭代器，可用于链式操作。

std::merge 要求输入区间必须已排序，否则行为未定义

它不负责排序，只做归并（类似归并排序的“合并”阶段）。如果传入乱序序列，std::merge 仍会逐个比较、按规则搬运元素，但结果既不是有序的，也不保证包含全部原始数据——因为它的逻辑依赖于两个输入序列各自单调递增（或按指定 comp 可比较）的前提。

常见错误现象：
• 输出容器里元素重复或缺失
• 看似“合并成功”，但结果无法二分查找或用于后续 std::set_union 等要求有序的操作
• 在 debug 模式下可能触发断言失败（取决于 STL 实现）

• 使用前务必确认：is_sorted(first1, last1) 和 is_sorted(first2, last2) 都返回 true
• 若不确定是否有序，先用 std::sort 或 std::stable_sort 预处理（注意：这会改变原序列）
• 若源数据来自 std::set 或 std::map 的 begin()/end()，可直接用——它们天然有序

输出迭代器必须预留足够空间，不能用 back_inserter 混淆语义

std::merge 是“写入型”算法，它不会自动扩容目标容器。如果你传入 std::vector::begin() 作为输出起点，而 vector 大小不足，就会越界写入——UB（未定义行为），通常表现为崩溃或静默数据损坏。

正确做法是提前分配空间：
• 输出容器大小 = std::distance(first1, last1) + std::distance(first2, last2)
• 或用 reserve() + back_inserter，但注意：此时你传的是 back_inserter(vec)，不是 vec.begin()

闪剪

AI数字人视频在线创作平台-AI一键成片

下载

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

• 推荐写法：

  std::vector out;
  out.reserve(v1.size() + v2.size());
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(out));

• 错误写法：std::merge(..., out.begin()) —— 即使 out.size() 为 0，out.begin() 也合法，但写入即越界
• 若输出到 C 数组，确保数组长度 ≥ 两输入长度之和

自定义比较函数需满足严格弱序，且与输入序列排序方式一致

如果你用 std::greater() 排过两个输入 vector，那调用 std::merge 时也必须传同样的 std::greater()；混用 std::less 会导致归并逻辑错乱——比如把本该排在前面的大数跳过。

• 检查点：输入序列的排序谓词、std::merge 的第 5 个参数（comp），二者必须完全等价
• 自定义 lambda 时，捕获列表要安全（避免悬垂引用），且不能修改参数（应为 const T& 形参）
• 若比较函数抛异常，std::merge 不保证强异常安全（部分元素可能已写入输出区间）

std::merge 返回输出末尾迭代器，可用于链式操作但需小心类型匹配

它返回的是「最后一个被写入元素的下一位置」，类型与第三个迭代器参数（output iterator）相同。这个返回值常被忽略，但它能帮你省一次 std::distance 计算，或衔接后续算法。

• 例如合并后立刻去重：

  auto out_end = std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());
  auto unique_end = std::unique(out.begin(), out_end);
  out.erase(unique_end, out.end());

• 注意：若 output 是 std::back_inserter，返回值是同一 back_insert_iterator，无法直接用于 erase；此时应改用预分配 + begin() 输出，再用返回值截断
• 返回迭代器不表示新 size，它只是位置标记；对 vector 来说，你要用 std::distance(out.begin(), ret) 才知道实际写了多少元素