高效合并两个有序vector

题目

高效合并两个有序vector

信息

• 类型：问答
• 难度：⭐⭐

考点

STL算法应用,迭代器使用,性能优化

快速回答

使用std::merge算法是最佳解决方案：

• 确保输入vector已排序（升序）
• 预分配目标vector内存避免多次扩容
• 时间复杂度为O(n+m)，空间复杂度O(n+m)
• 示例代码：
  std::vector<int> merged;
merged.reserve(v1.size() + v2.size());
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(merged));

问题核心

合并两个已排序的vector是常见操作，需要高效实现并正确使用STL工具。

最佳解决方案

使用std::merge算法（需包含<algorithm>）：

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

std::vector<int> mergeSortedVectors(const std::vector<int>& v1, 
                                const std::vector<int>& v2) {
    std::vector<int> merged;
    // 预分配内存避免多次扩容
    merged.reserve(v1.size() + v2.size());

    // 核心合并操作
    std::merge(v1.begin(), v1.end(),
               v2.begin(), v2.end(),
               std::back_inserter(merged));

    return merged;
}

原理说明

• std::merge：STL提供的归并算法，要求输入范围已排序，通过双指针遍历实现高效合并
• 时间复杂度：O(n+m)，每个元素仅比较一次
• 空间复杂度：O(n+m)，需要存储所有元素

常见错误

• 未预分配内存：导致多次扩容，时间复杂度退化为O((n+m)log(n+m))
• 输入未排序：std::merge要求输入必须有序，否则结果错误
• 错误使用迭代器：std::back_inserter必须配合reserve()才能避免性能损失
• 手动循环合并：易出现边界条件错误，且性能通常低于STL实现

性能优化

• 原地合并：若一个vector有足够空间，可用v1.insert()配合std::inplace_merge
• 移动语义：对于右值引用输入，使用std::make_move_iterator避免拷贝
• 自定义比较：对非基础类型需提供比较函数：
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(merged), [](const auto& a, const auto& b){ return a.key < b.key; });

扩展知识

• set_union vs merge：需要去重时用std::set_union（时间复杂度相同）
• 并行合并：C++17支持并行执行策略：
  std::merge(std::execution::par, ...)
• 链表合并：合并std::list时优先使用成员函数list.merge()（时间复杂度相同但无需额外空间）

备选方案对比