std::merge是最安全高效的合并方式，要求输入已排序、输出容器预分配空间或使用back_inserter，时间复杂度O(n+m)，不检查输入有序性与区间重叠，需确保比较规则一致。
用 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}
合并到已有容器时要注意迭代器有效性
如果想复用某个容器（比如把 b 合并进 a），不能直接往 a 里 merge —— 因为 a 正在被读取，同时又被修改，迭代器会失效。
立即学习“C++免费学习笔记（深入）”；
- 必须先拷贝一份，或用临时容器中转
- 若坚持原地合并，得反向操作：先
resize目标容器，再从后往前归并（类似归并排序的 merge step） -
std::merge不检查目标区间是否与输入重叠，重叠时行为未定义
自定义比较逻辑（比如降序合并）
默认按 < 比较，但可通过第 5 个参数传入仿函数或 lambda。注意两边必须用同一套规则，否则结果无序。
例如合并两个降序 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}
混用升序和降序输入会导致输出错乱，std::merge 不做校验。
性能关键点：避免隐式拷贝和重复分配
频繁合并小数组时，reserve() 和 back_inserter 的组合比默认构造后 push_back 更快；而用 raw pointer + data() 配合 merge 则适合极致性能场景（需手动管理内存）。
- 别对每个元素调用
push_back而不reserve—— 可能触发多次内存重分配 - 不要用
insert(end(), ...)循环代替merge，那是 O(n×m) - 如果两个数组都来自同一内存池（如 arena allocator），考虑用指针而非迭代器传入，减少封装开销
真正容易被忽略的是：合并后若需去重，std::unique 必须紧跟在 merge 后立即调用，中间插入任何操作都可能破坏相邻相等元素的连续性。
