C++で2つのリストの共通要素を求める方法｜set_intersectionの使い方

二人がそれぞれ別々のリストに希望する都市を挙げているとしましょう。このとき、両者が共通して選んでいる都市を見つけたい場面はよくあります。プログラミングにおいて「2つの集合に共通する要素」を求める処理は頻出のタスクであり、C++では標準ライブラリのset_intersectionを使うことで簡単に実現できます。

共通要素を求める基本的な考え方

この操作は、数学における「集合の積（インターセクション）」と同じ性質を持っています。2つのリストをそれぞれ集合とみなし、その積集合を求めることで、両方のリストに含まれる要素だけを取り出すことができます。

ただし、std::set_intersectionを使用する際には重要な前提条件があります。それは、入力となる両方の範囲があらかじめソートされている必要があるという点です。そのため、サンプルコードでは最初にsortを使って両リストを昇順に並べ替えています。

サンプルコード

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

vector<string> commonInterest(string set1[], int n1, string set2[], int n2) {
    vector<string> v(min(n1, n2));
    vector<string>::iterator it;
    // 両方のリストをソート
    sort(set1, set1 + n1);
    sort(set2, set2 + n2);
    it = set_intersection(set1, set1 + n1, set2, set2 + n2,
        v.begin());
    return v;
}

int main() {
    string first[] = { "Kolkata", "Hyderabad", "Chennai", "Delhi" };
    int n1 = sizeof(first) / sizeof(first[0]);
    string second[] = { "Mumbai", "Kolkata", "Durgapur", "Delhi" };
    int n2 = sizeof(second) / sizeof(second[0]);
    vector<string> v = commonInterest(first, n1, second, n2);
    cout << "Common cities: ";
    for (int i = 0; i < v.size(); i++)
        cout << ' ' << v[i];
    cout << endl;
}

実行結果

Common cities: Delhi Kolkata

1つ目のリスト（Kolkata、Hyderabad、Chennai、Delhi）と2つ目のリスト（Mumbai、Kolkata、Durgapur、Delhi）の両方に含まれているのは「Delhi」と「Kolkata」の2つであることが確認できます。なお、set_intersectionはソート済みの範囲を扱うため、結果も昇順に出力されます。

コードのポイント解説

• 結果格納用ベクターのサイズ： 共通要素の数は、小さい方のリストの要素数を超えることはないため、min(n1, n2)で必要十分なサイズを確保しています。
• 戻り値のイテレータ： set_intersectionは、書き込んだ最後の要素の次を指すイテレータを返します。実際の共通要素数を取得したい場合は、この戻り値とv.begin()の差分（it - v.begin()）を利用します。
• 計算量： ソートにO(N log N)、積集合の計算自体はO(N + M)で行えるため、全体の計算量はO(N log N + M log M)となります。
• 元の配列を変更したくない場合： この例では引数として渡された配列を直接ソートしているため、元の順序が失われます。元のデータを保持したい場合は、事前にvectorへコピーしてからソートするとよいでしょう。

なお、データが未ソートで元の順序を維持したいケースでは、unordered_setを使って片方のリストの要素を登録し、もう片方のリストを走査しながら存在チェックを行う方法もあります。要件に応じて使い分けることで、より柔軟な実装が可能です。