C++

参考

<algorithm>

函数模板
<algorithm>

std::merge

默认 (1)
template <class InputIterator1, class InputIterator2, class OutputIterator>  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,                        InputIterator2 first2, InputIterator2 last2,                        OutputIterator result);
自定义 (2)
template <class InputIterator1, class InputIterator2,          class OutputIterator, class Compare>  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,                        InputIterator2 first2, InputIterator2 last2,                        OutputIterator result, Compare comp);
合并已排序的范围
将范围 [first1,last1) 和 [first2,last2) 中的元素合并，并以已排序的方式存入以 result 开始的新范围中。

元素使用第一个版本的 operator< 进行比较，第二个版本使用 comp 进行比较。两个范围中的元素本身也应按照相同的标准（operator< 或 comp）排序。生成的新范围也按照此标准排序。

此函数模板的行为等同于
1
2
3
4
5
6
7
8
9
10
11
 
template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result)
{
  while (true) {
    if (first1==last1) return std::copy(first2,last2,result);
    if (first2==last2) return std::copy(first1,last1,result);
    *result++ = (*first2<*first1)? *first2++ : *first1++;
  }
}

参数

first1, last1
输入迭代器，指向第一个已排序序列的起始和结束位置。所涉及的范围是 [first1,last1)，它包含 first1 和 last1 之间的所有元素，包括 first1 指向的元素，但不包括 last1 指向的元素。
first2, last2
输入迭代器，指向第二个已排序序列的起始和结束位置。使用的范围是 [first2,last2)。
result
输出迭代器，指向存储合并后范围的起始位置。其大小等于上面两个范围大小的总和。
comp
二元函数，接受由迭代器指向的类型的两个参数，并返回可转换为 bool 的值。返回的值表示第一个参数在它定义的特定 *严格弱序* 中是否应排在第二个参数之前。
该函数不得修改其任何参数。
这可以是函数指针，也可以是函数对象。

这些范围不应重叠。
两个输入范围中的元素应能 赋值 给 result 指向的范围中的元素。它们也应是可比较的（对于版本 (1) 使用 operator<，对于版本 (2) 使用 comp）。

返回值

指向结果序列中“尾后”元素的迭代器。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
// merge algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::merge, std::sort
#include <vector>       // std::vector

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);

  std::sort (first,first+5);
  std::sort (second,second+5);
  std::merge (first,first+5,second,second+5,v.begin());

  std::cout << "The resulting vector contains:";
  for (std::vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

输出
The resulting vector contains: 5 10 10 15 20 20 25 30 40 50


复杂度

最多线性于 (1+count1-count2)，其中 countX 是 firstX 和 lastX 之间的 距离：比较并赋值所有元素。

数据竞争

访问范围 [first1,last1) 和 [first2,last2) 中的对象。
修改 result 和返回的迭代器之间的范围内的对象。

异常

如果任何元素比较、元素赋值或迭代器操作抛出异常，则此函数也会抛出异常。
请注意，无效参数会导致未定义行为。

另见

inplace_merge
合并连续的已排序范围 (函数模板)
set_union
两个已排序范围的并集 （函数模板）
copy
复制元素范围 （函数模板）