C++のSTLを使って2つの配列の共通要素を求める方法

このチュートリアルでは、C++のSTL（標準テンプレートライブラリ）を使用して、2つの配列に共通する要素を見つける方法について解説します。

2つの配列の共通要素を求めるには、set_intersection()メソッドを使用します。この関数は、あらかじめソートされた2つの範囲を受け取り、双方に存在する要素だけを出力先のコンテナへコピーします。そのため、呼び出し前に必ずsort()などで配列を昇順に並べておく必要があります。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int main(){
    // 配列の定義
    int arr1[] = { 1, 45, 54, 71, 76, 12 };
    int arr2[] = { 1, 7, 5, 4, 6, 12 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    sort(arr1, arr1 + n1);
    sort(arr2, arr2 + n2);
    cout << "First Array: ";
    for (int i = 0; i < n1; i++)
        cout << arr1[i] << " ";
    cout << endl;
    cout << "Second Array: ";
    for (int i = 0; i < n2; i++)
        cout << arr2[i] << " ";
    cout << endl;
    vector<int> v(n1 + n2);
    vector<int>::iterator it, st;
    // 共通要素の検索
    it = set_intersection(arr1, arr1 + n1, arr2, arr2 + n2, v.begin());
    cout << "\nCommon elements:\n";
    for (st = v.begin(); st != it; ++st)
        cout << *st << ", ";
    cout << '\n';
    return 0;
}

実行結果

First Array: 1 12 45 54 71 76
Second Array: 1 4 5 6 7 12
Common elements:
1, 12,

コードのポイント

• 事前のソートが必須： set_intersection()はソート済みの範囲を前提として動作するため、まずsort()で両方の配列を昇順に並べ替えています。
• 結果格納用のvector： 共通要素の数は最大でも小さい方の配列の要素数以下ですが、ここでは余裕を持ってn1 + n2のサイズでvectorを確保しています。
• 戻り値の活用： set_intersection()は結果の末尾を指すイテレータを返します。v.begin()からこの戻り値までの範囲が、実際に格納された共通要素となります。

なお、重複した要素が配列内に存在する場合、set_intersection()はその最小の出現回数分だけ結果に含める点にも注意してください。