合并


类别：算法	组件类型：函数

原型

Merge是一个重载名称：实际上有两个合并函数。

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

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

描述

Merge将两个已排序的范围[first1, last1)和[first2, last2)合并成一个已排序的范围。也就是说，它将元素从[first1, last1)和[first2, last2)复制到[result, result + (last1 - first1) + (last2 - first2))使得结果范围按升序排列。Merge是稳定的，这意味着每个输入范围内的元素的相对顺序都得以保留，并且对于两个输入范围中相等的[1]元素，第一个范围中的元素位于第二个范围中的元素之前。返回值为result + (last1 - first1) + (last2 - first2).

的两个版本合并在元素比较的方式上有所不同。第一个版本使用operator<。也就是说，输入范围和输出范围满足以下条件：对于每一对迭代器i和j使得i在j, *j < *i是假。第二个版本使用函数对象comp。也就是说，输入范围和输出范围满足以下条件：对于每一对迭代器i和j使得i在j, comp(*j, *i)是假.

定义

在标准头文件algorithm中定义，并在非标准向后兼容头文件algo.h中定义。

类型要求

对于第一个版本

InputIterator1是输入迭代器的模型。
InputIterator2是输入迭代器的模型。
InputIterator1的值类型与InputIterator2的值类型相同。
InputIterator1的值类型是小于可比较的模型。
对InputIterator1的值类型的对象的排序是严格弱排序，如小于可比较要求中所定义。
InputIterator1的值类型可转换为OutputIterator的值类型集合中的类型。

对于第二个版本

InputIterator1是输入迭代器的模型。
InputIterator2是输入迭代器的模型。
InputIterator1的值类型与InputIterator2的值类型相同。
StrictWeakOrdering是严格弱排序的模型。
InputIterator1的值类型可转换为StrictWeakOrdering的参数类型。
InputIterator1的值类型可转换为OutputIterator的值类型集合中的类型。

先决条件

对于第一个版本

[first1, last1)是一个有效的范围。
[first1, last1)按升序排列。也就是说，对于每一对迭代器i和j在[first1, last1)使得i在j, *j < *i是假.
[first2, last2)是一个有效的范围。
[first2, last2)按升序排列。也就是说，对于每一对迭代器i和j在[first2, last2)使得i在j, *j < *i是假.
范围[first1, last1)和[result, result + (last1 - first1) + (last2 - first2))不重叠。
范围[first2, last2)和[result, result + (last1 - first1) + (last2 - first2))不重叠。
有足够的空间容纳所有正在复制的元素。更正式地说，要求是[result, result + (last1 - first1) + (last2 - first2))是一个有效的范围。

对于第二个版本

[first1, last1)是一个有效的范围。
[first1, last1)按升序排列。也就是说，对于每一对迭代器i和j在[first1, last1)使得i在j, comp(*j, *i)是假.
[first2, last2)是一个有效的范围。
[first2, last2)按升序排列。也就是说，对于每一对迭代器i和j在[first2, last2)使得i在j, comp(*j, *i)是假.
范围[first1, last1)和[result, result + (last1 - first1) + (last2 - first2))不重叠。
范围[first2, last2)和[result, result + (last1 - first1) + (last2 - first2))不重叠。
有足够的空间容纳所有正在复制的元素。更正式地说，要求是[result, result + (last1 - first1) + (last2 - first2))是一个有效的范围。

复杂度

线性。如果两个[first1, last1)和[first2, last2)都是空范围，则不进行比较，否则最多进行(last1 - first1) + (last2 - first2) - 1次比较。

示例

int main()
{
  int A1[] = { 1, 3, 5, 7 };
  int A2[] = { 2, 4, 6, 8 };
  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int);

  merge(A1, A1 + N1, A2, A2 + N2, 
        ostream_iterator<int>(cout, " "));
  // The output is "1 2 3 4 5 6 7 8"
}

注释

[1] 请注意，您可以使用严格弱排序但不是全排序的排序；也就是说，可能存在值x和y使得x < y, x > y，以及x == y都是假。（请参阅小于可比较要求以了解更多信息。）两个元素x和y是等价的，如果既不x < y也不y < x。但是，如果您使用全排序（例如，如果您使用strcmp，或者如果您对整数使用普通的算术比较），那么您可以忽略此技术区别：对于全排序，相等和等价是相同的。

另请参阅

inplace_merge, set_union, sort