C++如何使用merge算法合并两个有序容器-C++-PHP中文网

C++如何使用merge算法合并两个有序容器

P粉602998670

发布： 2025-09-09 11:01:01

原创

676人浏览过

C++中使用std::merge可将两个有序容器合并为有序序列，需包含<algorithm>头文件，支持vector等随机访问容器，通过指定迭代器范围和输出目标完成合并，可结合greater实现降序合并，或使用back_inserter动态扩展结果容器，时间复杂度O(n+m)。

c++如何使用merge算法合并两个有序容器

在C++中，可以使用标准库中的 std::merge 算法将两个有序容器合并成一个有序序列。这个算法定义在 algorithm 头文件中，适用于任何支持随机访问迭代器的有序容器，比如 std::vector、std::array 或原生数组。

包含必要头文件和命名空间

使用 merge 前需要引入头文件：

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

通常使用 using namespace std; 简化代码（在示例中使用，实际项目中建议避免）。

基本用法：合并两个有序 vector

std::merge 接收两个有序区间的起始和结束迭代器，以及一个输出迭代器，将合并结果写入目标位置。

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

示例代码：

vector<int> vec1 = {1, 3, 5, 7};
vector<int> vec2 = {2, 4, 6, 8};
vector<int> result(vec1.size() + vec2.size()); // 预分配空间

merge(vec1.begin(), vec1.end(),
vec2.begin(), vec2.end(),
result.begin());

合并完成后，result 容器中元素为 {1, 2, 3, 4, 5, 6, 7, 8}，保持升序。

自定义比较函数

如果容器按降序排列，或需要自定义排序规则，可传入比较函数或函数对象。

MakeSong

AI音乐生成，生成高质量音乐，仅需30秒的时间

145

查看详情

例如合并两个降序 vector：

vector<int> vec1 = {7, 5, 3, 1};
vector<int> vec2 = {8, 6, 4, 2};
vector<int> result(8);

merge(vec1.begin(), vec1.end(),
     vec2.begin(), vec2.end(),
     result.begin(),
     greater<int>()); // 使用 greater 表示降序

此时 result 中元素为 {8, 7, 6, 5, 4, 3, 2, 1}。

使用 back_inserter 动态扩展目标容器

如果不想预先分配空间，可以用 back_inserter 自动扩展目标容器。

需要包含 <iterator> 头文件：

vector<int> vec1 = {1, 3, 5};
vector<int> vec2 = {2, 4, 6};
vector<int> result;

merge(vec1.begin(), vec1.end(),
vec2.begin(), vec2.end(),
back_inserter(result));

这种方式更灵活，适合不确定合并后大小的场景。

基本上就这些。只要两个源容器有序，std::merge 就能高效合并出有序结果，时间复杂度为 O(n + m)，使用时注意目标空间足够或使用插入迭代器。不复杂但容易忽略预分配问题。

以上就是C++如何使用merge算法合并两个有序容器的详细内容，更多请关注php中文网其它相关文章！