C++ STLのlist::merge()関数とは？使い方とサンプルコードを解説

本記事では、C++ STLのlist::merge()関数について、その動作・構文・具体的な使用例を詳しく解説します。

STLにおけるlist（リスト）とは？

listは、シーケンス内の任意の位置に対して一定時間での挿入・削除が可能なデータ構造です。内部は双方向連結リストとして実装されており、連続しないメモリ領域への配置が許容されています。そのため、配列やvector、dequeと比較して、コンテナ内の任意の位置への要素の挿入・抽出・移動において優れたパフォーマンスを発揮します。一方で、要素への直接アクセスは低速であるという特徴があります。また、listはforward_listと似ていますが、forward_listは片方向連結リストであり、前方方向にしかイテレートできない点が異なります。

list::merge()とは？

list::merge()は、C++ STLに組み込まれた関数で、<list>ヘッダーファイル内で宣言されています。merge()は、2つのリストを1つに統合するために使用されます。単純に2つのリストをマージするだけでなく、比較条件を細かく制御したい場合には、コンパレータ（比較関数）を追加することも可能です。

重要な注意点として、2つのリストをマージする前に、両方のリストがソート済みであることを確認する必要があります。コンパレータを渡さない場合は、operator< による比較で2つのリストが1つのソート済みリストに統合されます。リスト同士で独自の内部比較を行いたい場合は、コンパレータを指定する必要があります。

構文

list_container1.merge(list_container2); // 両方のリストをlist_container1にマージ
list_container1.merge(list_container2, comparator);

この関数は、1つまたは2つのパラメータを受け取ることができます。

パラメータ

• list_container2 − マージ対象となる第2のリストのオブジェクトです。

• comparator − 内部比較を定義します。これは二項述語（binary predicate）であり、リストコンテナに定義された値と同じ型の2つの入力を受け取ります。list_container1の要素がlist_container2の要素より先に来ると判断される場合はtrueを、そうでない場合はfalseを返します。

戻り値

この関数は何も返しません（void型です）。マージ結果は呼び出し元のリスト（list_container1）に直接反映されます。

コンパレータなしの場合

例

以下のコードでは、2つのソート済みリストを作成し、それらをマージします。マージ後の出力もソートされた状態になっている必要があります。

#include <bits/stdc++.h>
using namespace std;
int main(){
    // ソート済みリストを作成
    list<int> myList_1 = {2, 4, 6, 8 };
    list<int> myList_2 = {1, 3, 5, 7 };
    // merge()関数を使ってリストをマージ
    myList_2.merge(myList_1);
    cout << "Lists after merging : ";
    for(auto i = myList_2.begin(); i != myList_2.end(); ++i)
        cout << *i << " ";
    return 0;
}

出力

上記のコードを実行すると、以下のような出力が生成されます。

Lists after merging : 1 2 3 4 5 6 7 8

コンパレータありの場合

例

以下のコードでは、2つのリストをマージし、最終的な出力として生成されたリストをソートします。

#include <bits/stdc++.h>
using namespace std;
bool compare(int myList_1, int myList_2){
    return ( int(myList_1)<int(myList_2) );
}
int main(){
    // リストを作成
    list<int> myList_1 = {2, 4, 1 };
    list<int> myList_2 = {7, 6, 5 };
    myList_1.sort();
    myList_2.sort();
    // merge()関数を使ってリストをマージ
    myList_1.merge(myList_2);
    myList_2.push_back(3);
    myList_1.merge(myList_2, compare);
    cout << "List Elements are : ";
    for(auto i = myList_1.begin(); i != myList_1.end(); ++i)
        cout << ' ' << *i;
    return 0;
}

出力

上記のコードを実行すると、以下のような出力が生成されます。

List Elements are : 1 2 3 4 5 6 7