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
複製元素範圍 （函式模板）