c++如何合并两个有序的vector _c++有序vector合并方法-C++-PHP中文网

c++如何合并两个有序的vector _c++有序vector合并方法

穿越時空

发布： 2025-10-24 16:16:02

原创

346人浏览过

使用std::merge是合并两个有序vector的首选方法，时间复杂度O(n+m)。示例代码展示通过预分配空间并调用std::merge实现高效合并，也可手动实现双指针法以理解原理或定制逻辑。

c++如何合并两个有序的vector _c++有序vector合并方法

合并两个有序的 vector 在 C++ 中是一个常见操作，最高效且标准的方法是使用 std::merge。它要求两个输入容器已经按顺序排列（升序或降序），并生成一个新的有序序列。

使用 std::merge 合并两个有序 vector

这是最推荐的方式，时间复杂度为 O(n + m)，其中 n 和 m 分别是两个 vector 的长度。

示例代码：

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec1 = {1, 3, 5, 7};
    std::vector<int> vec2 = {2, 4, 6, 8, 9};
    std::vector<int> merged;

    // 预分配空间，提升性能
    merged.reserve(vec1.size() + vec2.size());

    // 执行合并
    std::merge(vec1.begin(), vec1.end(),
               vec2.begin(), vec2.end(),
               std::back_inserter(merged));

    // 输出结果
    for (int val : merged) {
        std::cout << val << " ";
    }
    return 0;
}

登录后复制

手动合并（双指针法）

如果不使用 STL 算法，也可以通过双指针方式手动实现，适合理解原理或定制比较逻辑。

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

std::vector<int> mergeManual(const std::vector<int>& v1,
                              const std::vector<int>& v2) {
    std::vector<int> result;
    size_t i = 0, j = 0;

    while (i < v1.size() && j < v2.size()) {
        if (v1[i] <= v2[j]) {
            result.push_back(v1[i++]);
        } else {
            result.push_back(v2[j++]);
        }
    }

    // 添加剩余元素
    while (i < v1.size()) result.push_back(v1[i++]);
    while (j < v2.size()) result.push_back(v2[j++]);

    return result;
}

登录后复制