C++のSTLによるマージ操作を解説｜merge()・includes()・set_union()・set_intersection()・set_difference()・inplace_merge

このチュートリアルでは、C++のSTL（標準テンプレートライブラリ）を活用したさまざまなマージ操作について解説します。

merge()関数は、ソート済みの2つのコンテナを1つに統合するための関数です。統合後の新しいコンテナも自動的にソートされた状態になります。一方、includes()関数は、あるソート済み範囲の要素がすべて別の範囲に含まれているかどうか（部分集合の関係にあるか）を判定するために使用されます。

merge()とincludes()の使用例

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    vector<int> v1 = {1, 3, 4, 5, 20, 30};
    vector<int> v2 = {1, 5, 6, 7, 25, 30};

    // 結果を格納するベクターを初期化
    vector<int> v3(12);

    merge(v1.begin(), v1.end(), v2.begin(),
          v2.end(), v3.begin());

    cout << "マージ後の新しいコンテナ：\n";
    for (int &x : v3)
        cout << x << " ";
    cout << endl;

    vector<int> v4 = {1, 3, 4, 5, 6, 20, 25, 30};

    includes(v4.begin(), v4.end(), v1.begin(), v1.end())
        ? cout << "v4はv1を含んでいます"
        : cout << "v4はv1を含んでいません";

    return 0;
}

実行結果

マージ後の新しいコンテナ：
1 1 3 4 5 5 6 7 20 25 30 30
v4はv1を含んでいます

出力を見ると、merge()によって両方のベクターの要素が昇順を保ったまま正しく統合されていることがわかります。また、v4にはv1の全要素（1, 3, 4, 5, 20, 30）が含まれているため、includes()はtrueを返しています。

その他のマージ・集合操作関数

<algorithm>ヘッダーには、マージ関連の操作として以下のような関数も用意されています。いずれも引数に渡す範囲がソート済みであることを前提として動作する点に注意してください。

set_union()

2つのソート済み範囲の和集合を求めます。どちらかの範囲に存在するすべての要素を、重複なく格納した結果を生成します。

set_intersection()

2つのソート済み範囲の積集合を求めます。両方の範囲に共通して存在する要素だけを出力先に書き込みます。

set_difference()

2つのソート済み範囲の差集合を求めます。1つ目の範囲には存在するものの、2つ目の範囲には存在しない要素を出力します。

inplace_merge()

同じコンテナ内で連続する2つのソート済み部分列を、その場で（in-place）マージします。別の作業用コンテナを用意する必要がなく、メモリ効率に優れているのが特徴です。

まとめ

C++のSTLを活用すれば、ソート済みデータの結合や集合演算を簡単かつ効率的に実装できます。merge()やincludes()をはじめとするこれらのアルゴリズムを使いこなすことで、手作業のループ処理を置き換え、より簡潔でバグの少ないコードを書けるようになります。