名前空間
変種
操作

std::merge

From cppreference.com
< cpp‎ | algorithm
 
C++
コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ
 
アルゴリズムライブラリ
制約付きアルゴリズムとRangeアルゴリズム (C++20)
制約付きアルゴリズム、例: ranges::copy, ranges::sort, ...
実行ポリシー (C++17)
シーケンスを変更しない操作
一括操作
(C++17)
検索操作
(C++11)                (C++11)(C++11)

シーケンスを変更する操作
コピー操作
(C++11)
(C++11)
(C++11)
スワップ操作
変換操作
生成操作
削除操作
順序変更操作
(C++17まで)(C++11)
(C++20)(C++20)
サンプリング操作
(C++17)

ソートおよび関連操作
パーティション操作
ソート操作
二分探索操作
(パーティション化された範囲)
集合操作 (ソート済み範囲)
マージ操作 (ソート済み範囲)
merge
ヒープ操作
最小/最大操作
(C++11)
(C++17)
辞書順比較操作
(C++20)
順列操作
Cライブラリ
数値演算
未初期化メモリに対する操作
 
ヘッダー <algorithm> で定義
template< class InputIt1, class InputIt2, class OutputIt >

OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2,

                OutputIt d_first );
 (1) (C++20 以降 constexpr)
template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 merge( ExecutionPolicy&& policy,
                  ForwardIt1 first1, ForwardIt1 last1,
                  ForwardIt2 first2, ForwardIt2 last2,

                  ForwardIt3 d_first );
 (2) (C++17以降)
template< class InputIt1, class InputIt2,

          class OutputIt, class Compare >
OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2,

                OutputIt d_first, Compare comp );
 (3) (C++20 以降 constexpr)
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 );
 (4) (C++17以降)

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

1) [first1, last1) または [first2, last2) が ソート済みでない場合、動作は未定義です。
3) もし [first1, last1) または [first2, last2) が comp に関してソートされていない場合、動作は未定義です。
2,4) (1,3)と同じだが、policyに従って実行される。
これらのオーバーロードは、以下のすべての条件が満たされた場合にのみオーバーロード解決に参加する。

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true である。

 (C++20まで)

std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> は true です。

 (C++20以降)

このマージ関数は安定であり、元の2つの範囲内の等価な要素については、最初の範囲の要素（元の順序を維持）が2番目の範囲の要素（元の順序を維持）の前に来ます。

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

目次

[edit] Parameters

first1, last1 - マージする最初の範囲を定義するイテレータのペア
first2, last2 - マージする2番目の範囲を定義するイテレータのペア
d_first - コピー先範囲の先頭
policy - 使用する 実行ポリシー
comp - 比較関数オブジェクト（つまり、Compare の要件を満たすオブジェクト）。最初の引数が2番目の引数より小さい（つまり、前に順序付けられる）場合に true を返します。

比較関数のシグネチャは、以下と同等でなければならない。

bool cmp(const Type1& a, const Type2& b);

シグネチャは const& を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはならず、値カテゴリ に関係なく、(おそらく const の) Type1 と Type2 のすべての値を受け入れられる必要があります (したがって、Type1& は許可されません。また、Type1 のムーブがコピーと同等でない限り、Type1 も許可されません(C++11以降))。
Type1 および Type2 は、InputIt1 および InputIt2 のオブジェクトを間接参照してから、Type1 および Type2 の両方に暗黙的に変換できる型でなければなりません。

型要件
-
InputIt1, InputIt2 は LegacyInputIterator の要件を満たす必要がある。
-
ForwardIt1, ForwardIt2, ForwardIt3 は LegacyForwardIterator の要件を満たしている必要があります。
-
OutputIt は LegacyOutputIterator の要件を満たさなければなりません。
-
CompareはCompareの要件を満たす必要がある。

[edit] Return value

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

[edit] Complexity

std::distance(first1, last1) を N1 とし、std::distance(first2, last2) を N2 とする。

1) 比較操作は最大 N1+N2-1 回。
2) O(N1+N2) 回。
3) 比較関数 comp の適用は最大 N1+N2-1 回。
4) 比較関数 comp の適用は O(N1+N2) 回。

[edit] Exceptions

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

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

[edit] Possible implementation

libstdc++ および libc++ の実装も参照してください。

merge (1) 
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);
}
merge (3) 
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);
}

[edit] Notes

このアルゴリズムは、std::set_union と同様のタスクを実行します。どちらも2つのソート済み入力範囲を消費し、両方の入力からの要素を持つソート済み出力を生成します。これらの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 はそれより少ない値を生成する可能性があります。

[edit] Example

このコードを実行
#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

[edit] Defect reports

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR 適用対象 公開された動作 正しい動作
LWG 780 C++98 merge 操作が定義されていませんでした。 defined

[edit] See also

 2つの順序付けられた範囲をインプレースでマージする
(関数テンプレート) [編集]
(C++11)
 範囲が昇順にソートされているかどうかをチェックする
(関数テンプレート) [編集]
 2つの集合の和を計算する
(関数テンプレート) [編集]
 範囲を昇順にソートする
(関数テンプレート) [編集]
 等しい要素間の順序を維持しながら要素の範囲をソートする
(関数テンプレート) [編集]
(C++20)
 2つのソート済み範囲をマージする
(アルゴリズム関数オブジェクト)[編集]
"https://ja.cppreference.dev/mwiki/index.php?title=cpp/algorithm/merge&oldid=180435" から取得
English 日本語 中文(简体) 中文(繁體)