C++ STLのforward_list::merge()関数の使い方を徹底解説

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

STLにおけるforward_listとは？

forward_list（前方リスト）は、シーケンス内の任意の位置に対して定数時間で挿入・削除操作を行えるシーケンスコンテナです。内部的には単方向連結リストとして実装されており、各要素が次の要素へのリンクを持つことで順序が維持されます。

forward_list::merge()とは？

forward_list::merge()は、C++ STLに組み込まれた関数で、ヘッダーファイル<forward_list>内で宣言されています。この関数は、ソート済みの2つのforward_listを1つにマージ（統合）するために使用されます。

2つのリストをマージする前に、両方のリストがソート済みであることを確認する必要があります。比較関数（コンパレータ）を渡さない場合は、2つのリストが1つのソート済みリストに統合されます。また、リスト間で独自の内部比較を行いたい場合は、コンパレータを指定する必要があります。

構文

flist_container1.merge(flist_container2); // 両方のリストをマージする
flist_container1.merge(flist_container2, comparator);

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

パラメータ

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

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

戻り値

この関数は何も返しません。

使用例

/* 以下のコードでは、ソート済みの2つのforward_listを作成し、C++のmerge()関数を使ってソートされた状態のままマージします。 */

#include <bits/stdc++.h>
using namespace std;
int main() {
   // ソート済みの値を挿入してforward_listを作成
   forward_list<int> myForwardList1 = { 1, 3, 5, 7 };
   forward_list<int> myForwardList2 = { 2, 4, 6 };
   // ソート済みの2つのforward_listをマージ
   myForwardList1.merge(myForwardList2);
   cout << "elements after merging" << endl;
   for (auto i = myForwardList1.begin(); i != myForwardList1.end(); ++i)
      cout << *i << " ";
   return 0;
}

出力結果

上記のコードを実行すると、次の出力が生成されます。

elements after merging
1 2 3 4 5 6 7

コンパレータを使用した場合

使用例

/* 以下のコードでは、ソートされていない2つのforward_listを作成し、まずsort()関数でソートしてから、merge()関数を使ってマージします。 */

#include <bits/stdc++.h>
using namespace std;
int main (){
   // ソートされていないforward_listを作成
   forward_list<int> myForwardList1 = {3, 2, 9};
   forward_list<int> myForwardList2 = {8, 1, 2};
   // sort()関数を使ってforward_listをソート
   myForwardList1.sort();
   myForwardList2.sort();
   myForwardList1.merge(myForwardList2);
   cout << "Elements after merging" << endl;
   for (auto i = myForwardList1.begin(); i != myForwardList1.end(); ++i)
      cout << *i << " ";
   return 0;
}

出力結果

上記のコードを実行すると、次の出力が生成されます。

Elements after merging
1 2 2 3 8 9