std:: merge

二つのソート済み範囲 [ first1 , last1 ) と [ first2 , last2 ) を d_first から始まる一つのソート済み範囲にマージします。

このマージ関数は安定しています。つまり、元の2つの範囲で等価な要素の場合、最初の範囲の要素（元の順序を保持）が2番目の範囲の要素（元の順序を保持）よりも前に配置されます。

出力範囲が [ first1 , last1 ) または [ first2 , last2 ) と重なる場合、動作は未定義です。

パラメータ

戻り値

コピーされた最後の要素の次の要素を指す出力イテレータ。

計算量

\(\scriptsize N_1\) N 1 を std:: distance ( first1, last1 ) として、 \(\scriptsize N_2\) N 2 を std:: distance ( first2, last2 ) として定義する：

例外

ExecutionPolicy という名前のテンプレートパラメータを持つオーバーロードは、 以下のようにエラーを報告します：

• アルゴリズムの一部として呼び出された関数の実行が例外をスローした場合、 ExecutionPolicy が 標準ポリシー のいずれかであるとき、 std::terminate が呼び出されます。それ以外の ExecutionPolicy については、動作は実装定義です。
• アルゴリズムがメモリの確保に失敗した場合、 std::bad_alloc がスローされます。

実装例

実装例については libstdc++ および libc++ も参照してください。

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        if (*first2 < *first1)
        {
            *d_first = *first2;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1))
        {
            *d_first = *first2;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

タグ内のテキスト、C++固有の用語は翻訳せず、元のフォーマットを保持しています）

注記

このアルゴリズムは std:: set_union と同様の処理を実行します。両アルゴリズムとも2つのソート済み入力範囲を消費し、両入力の要素を含むソート済み出力を生成します。これらのアルゴリズムの違いは、両方の入力範囲から等価と比較される値（ LessThanComparable に関する注記を参照）の扱いにあります。等価な値が最初の範囲に n 回、2番目の範囲に m 回現れた場合、 std::merge は n + m 個の全ての出現を出力しますが、 std::set_union は std:: max ( n, m ) 個のみを出力します。したがって std::merge は正確に std:: distance ( first1, last1 ) + std:: distance ( first2, last2 ) 個の値を出力しますが、 std::set_union はより少ない数を出力する可能性があります。

例

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
auto print = [](const auto rem, const auto& v)
{
    std::cout << rem;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
};
int main()
{
    // ベクターに乱数を格納
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<> dis(0, 9);
    std::vector<int> v1(10), v2(10);
    std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));
    std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));
    print("Originally:\nv1: ", v1);
    print("v2: ", v2);
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    print("After sorting:\nv1: ", v1);
    print("v2: ", v2);
    // マージ
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
    print("After merging:\ndst: ", dst);
}

Originally:
v1: 2 6 5 7 4 2 2 6 7 0
v2: 8 3 2 5 0 1 9 6 5 0
After sorting:
v1: 0 2 2 2 4 5 6 6 7 7
v2: 0 0 1 2 3 5 5 6 8 9
After merging:
dst: 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

関連項目