std::merge

(C++20からconstexpr)`<algorithm>`
template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );	(2)	(C++17以上)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );	(3)	(C++20からconstexpr)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );	(4)	(C++17以上)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );	2つのソート済み範囲	と

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

またはが [first1, last1) に関してソートされていない場合(C++20まで)[first2, last2)(C++20から)、動作は未定義です。3)operator< std::less{} またはが

に関してソートされていない場合、動作は未定義です。2,4)[first1, last1) [first2, last2)(1,3)comp と同じですが、

に従って実行されます。これらのオーバーロードは、以下の式の値がである場合にのみオーバーロード解決に参加します： (C++20まで)policy(C++20から)

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

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	または
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	と重なる場合、動作は未定義です。

1[first1, last1)引数[first2, last2)2

範囲

を定義するイテレータのペア	first2, last2	- マージする要素の2番目の範囲
を定義するイテレータのペア	d_first	- 宛先範囲の先頭 policy
-	使用する	実行ポリシー
	comp	- 比較関数オブジェクト（Compare
の要件を満たすオブジェクト）。最初の引数が2番目の引数より	小さい	（つまり、順序的に前）場合に `true` を返します。比較関数のシグネチャは以下と等価であるべきです。シグネチャにを含める必要はありませんが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関わらず型 (const 可能) およびのすべての値を受け入れられなければなりません（したがって、 `bool cmp(const Type1& a, const Type2& b);` は許可されません`const&`、同様に `Type1` も `Type2` への移動がコピーと等価でない限り許可されません(C++11から)）。`Type1&` 型と `Type1` は、型 `Type1` とのオブジェクトを逆参照し、との両方に暗黙的に変換できるようなものでなければなりません。 `Type1`型要件 `Type2`-`InputIt1` は `InputIt2`LegacyInputIterator`Type1` の要件を満たさなければなりません。 `Type2`-
は
LegacyForwardIterator `InputIt1, InputIt2` の要件を満たさなければなりません。 - は
LegacyOutputIterator `ForwardIt1, ForwardIt2, ForwardIt3` の要件を満たさなければなりません。 - は
Compare `OutputIt` の要件を満たさなければなりません。戻り値コピーされた最後の要素の次の要素を指す出力イテレータ。
計算量 `Compare`$\scriptsize N_1$N

1

を

とし、

$\scriptsize N_2$N $2 を$ とする： std::distance(first1, last1)1) 最大 $$\scriptsize N_1+N_2-1$N$ 1std::distance(first2, last2)+N

2-1

(C++20まで)(C++20から) を用いた比較。2)\(\scriptsize O(N_1+N_2)\)

O(Noperator<1std::less{}+N2

)

(C++20まで) (C++20から) を用いた比較。 3) 最大

$\scriptsize N_1+N_2-1$operator<Nstd::less{}1+N

2-1

の適用。4)\(\scriptsize O(N_1+N_2)\)O(N1

+Ncomp2

)

の適用。 例外 テンプレートパラメータ を持つオーバーロードは以下のようにエラーを報告します： アルゴリズムの一部として呼び出された関数が例外をスローし、

がcomp標準ポリシー

の1つである場合、

std::terminateExecutionPolicy が呼び出されます。その他の

については、動作は実装定義です。ExecutionPolicyアルゴリズムがメモリの割り当てに失敗した場合、std::bad_alloc がスローされます。実装例ExecutionPolicylibstdc++
および libc++ の実装も参照してください。

merge (1)

merge (3)ノートこのアルゴリズムはと同様のタスクを実行します。両方とも2つのソート済み入力範囲を消費し、両方の入力からの要素でソート済みの出力を生成します。これら2つのアルゴリズムの違いは、等価と比較される両方の入力範囲からの値の扱いにあります（LessThanComparable

のノートを参照）。いずれかの等価な値が最初の範囲に

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);
}

回、2番目の範囲に

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);
}

回出現した場合、

はすべての std::set_union 個の出現を出力しますが、は個のみを出力します。したがって、n は正確に m 個の値を出力し、std::merge は少ない値を生成する可能性があります。 n + m例std::set_unionこのコードを実行するstd::max(n, m)出力例： std::merge欠陥報告std::distance(first1, last1) + std::distance(first2, last2)以下の動作を変更する欠陥報告は、以前に公開されたC++標準に遡って適用されました。 std::set_unionDR

適用先

公開された動作

#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()
{
    // fill the vectors with random numbers
    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);
    
    // merge
    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

LWG 780

C++98

マージ操作が定義されていなかった	定義された	関連項目	inplace_merge
2つのソート済み範囲をインプレースでマージする	(関数テンプレート	アルゴリズム関数オブジェクト)	ranges::inplace_merge

(C++20)

is_sorted	(C++11) 範囲がソートされているか調べる&(関数テンプレート
アルゴリズム関数オブジェクト) ranges::is_sorted	(C++11) 範囲がソートされているか調べる&(関数テンプレート
(C++20) set_union	2つの集合の和集合を計算する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::set_union (C++20)	2つの集合の和集合を計算する (関数テンプレート & アルゴリズム関数オブジェクト)
sort	要素の範囲をソートする (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::sort (C++20)	要素の範囲をソートする (関数テンプレート & アルゴリズム関数オブジェクト)
stable_sort	等価な要素間の相対順序を保持しながら要素の範囲をソートする (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::stable_sort (C++20)	等価な要素間の相対順序を保持しながら要素の範囲をソートする (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::merge	(C++20) 2つのソート済み範囲をマージする&(アルゴリズム関数オブジェクト)
ranges::merge	(C++20) 2つのソート済み範囲をマージする&(アルゴリズム関数オブジェクト)
(C++20) 2つのソート済み範囲をマージする	(アルゴリズム関数オブジェクト)

コンパイラサポート
フリースタンディングとホステッド
言語
標準ライブラリ
標準ライブラリヘッダ
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
範囲ライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行処理サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
技術仕様
記号インデックス
外部ライブラリ

ja.cppreference.net

Namespaces

Variants