C++ 算法 merge() 函数

C++ algorithm 库

定义和用法

merge() 函数将两个数据范围的值合并复制到目标数据范围中。

目标数据范围需要足够大以容纳两个源数据范围的所有元素。

如果两个源数据范围是有序的，合并后的目标数据范围也将保持有序。

数据范围通过迭代器指定。

实例

合并两个 vector：

vector<int> numbers1 = {1, 4, 9, 16};
vector<int> numbers2 = {2, 4, 6, 8};
vector<int> merged(8);  // 预分配足够空间
merge(numbers1.begin(), numbers1.end(), numbers2.begin(), numbers2.end(), 
     merged.begin());
for (int item : merged) {
    cout << item << " ";  // 输出：1 2 4 4 6 8 9 16
}

亲自试一试

语法

merge(iterator start1, iterator end1, iterator start2, iterator end2, iterator destination);

参数

参数 描述
start1 必需。指向第一个数据范围起始位置的迭代器。
end1

必需。指向第一个数据范围结束位置的迭代器。

将合并到该位置之前的元素。
start2 必需。指向第二个数据范围起始位置的迭代器。
end2

必需。指向第二个数据范围结束位置的迭代器。

将合并到该位置之前的元素。
destination 必需。指向目标数据范围起始位置的迭代器。

技术细节

返回： 指向合并后数据范围末尾的迭代器（最后一个被写入元素的下一个位置）。

说明：

  • 该函数时间复杂度为 O(n+m)，其中 n 和 m 分别是两个源数据范围的大小
  • 合并前不需要对目标数据范围进行初始化
  • 若输入范围有序，结果将保持有序；若输入无序，结果也将是无序的合并

相关页面

教程：C++ 数据结构

教程：C++ 迭代器

教程：C++ 算法

C++ algorithm 库