merge-c和c++中文资料站

C&C++标准库

std::

merge

函数模板 <algorithm>

default (1)

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result);

custom (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开始，所有元素都已排序。

第一个版本使用操作符<比较元素，第二个版本使用comp操作符比较元素。两个范围内的元素应该已经按照相同的标准排序(操作符<或comp)。得到的范围也是根据这个排序的。

这个函数模板的行为相当于:

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之间的所有元素，包括first指向的元素，但不包括last指向的元素。
first2, last2: 指向第二个排序序列的初始和最终位置的迭代器。使用的范围是[first2,last2)。
result: 指向存储合并后的范围的初始位置的输出迭代器。它的大小等于上面两个范围的和。
comp: 二元函数，接受两个由迭代器指向的类型参数，并返回一个可转换为bool类型的值。返回的值表示在它定义的特定严格弱排序中，第一个参数是否被认为在第二个参数之前。。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。

范围不得重叠。
两个输入范围中的元素都应该赋值给result所指向的范围中的元素。它们也应该是可比较的(操作符< for(1)和comp for(2))。

☉ 返回值

指向结果序列中最后一个元素的迭代器。

☣ 示例

// 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	复制范围的元素(函数模板)