C++ vector怎么合并两个已排序的数组-C++-PHP中文网

std::merge是最安全高效的合并方式，要求输入已排序、输出容器预分配空间或使用back_inserter，时间复杂度o(n+m)，不检查输入有序性与区间重叠，需确保比较规则一致。

c++ vector怎么合并两个已排序的数组

用 `std::merge` 合并两个已排序的 `vector`

直接调用 std::merge 是最安全、最高效的方式，它专为合并两个有序序列设计，时间复杂度 O(n+m)，且不破坏原数组。

常见错误是手动写双指针循环却漏掉某一方剩余元素，或误用 insert + sort 导致 O((n+m) log(n+m)) 的无谓开销。

使用前需确保：两个输入 vector 确实升序（或同为降序），目标容器有足够空间（或用 back_inserter）。

#include <vector>
#include <algorithm>
#include <iterator>

std::vector<int> a = {1, 3, 5, 7};
std::vector<int> b = {2, 4, 6, 8, 9};
std::vector<int> result;
result.reserve(a.size() + b.size()); // 避免多次 realloc

std::merge(a.begin(), a.end(),
           b.begin(), b.end(),
           std::back_inserter(result));
// result == {1,2,3,4,5,6,7,8,9}
</int></int></int></iterator></algorithm></vector>

合并到已有容器时要注意迭代器有效性

如果想复用某个容器（比如把 b 合并进 a），不能直接往 a 里 merge —— 因为 a 正在被读取，同时又被修改，迭代器会失效。

必须先拷贝一份，或用临时容器中转
若坚持原地合并，得反向操作：先 resize 目标容器，再从后往前归并（类似归并排序的 merge step）
std::merge 不检查目标区间是否与输入重叠，重叠时行为未定义

自定义比较逻辑（比如降序合并）

默认按 比较，但可通过第 5 个参数传入仿函数或 lambda。注意两边必须用同一套规则，否则结果无序。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

例如合并两个降序 vector：

std::vector<int> a = {9, 7, 5, 3, 1};
std::vector<int> b = {8, 6, 4, 2};
std::vector<int> result;
result.reserve(a.size() + b.size());

std::merge(a.begin(), a.end(),
           b.begin(), b.end(),
           std::back_inserter(result),
           std::greater<int>{}); // 或 [](int x, int y){ return x > y; }
// result == {9,8,7,6,5,4,3,2,1}
</int></int></int></int>

混用升序和降序输入会导致输出错乱，std::merge 不做校验。