【C++】STLのset_difference()で1つ目の配列にのみ存在する要素を見つける方法

2つの配列が与えられたとき、C++のSTL(標準テンプレートライブラリ)を活用して、「1番目の配列には存在するが、2番目の配列には存在しない要素」を効率的に見つける方法を解説します。

例

入力: array1[ ] = {1, 2, 3, 4, 5, 7}
      array2[ ] = {2, 3, 4, 5, 6, 8}
出力: 1, 7

入力: array1[ ] = {1, 20, 33, 45, 67}
      array2[ ] = {1, 12, 13, 114, 15, 13}
出力: 20, 33, 45, 67

解決のアプローチ

このプログラムでは、1番目の配列に存在し、2番目の配列には存在しない要素を抽出します。手順は以下のとおりです。

• まず2つの配列を用意し、該当する要素を検索するための関数「find」を作成します。
• 関数内では、結果を格納するためのvector(要素の追加・削除に応じて自動的にサイズが変化する動的配列)を宣言し、あわせてvectorを走査するためのイテレータも宣言します。
• 両方の配列をソートしたうえで、STLのset_difference()メソッドを使って差分(欠落要素)を求めます。
• 結果の要素数に合わせてvectorをリサイズし、値を格納してから出力します。

set_difference()メソッドとは

STLでは、set_difference()メソッドを使うことで「array1 − array2」に相当する差集合を簡単に求められます。差集合とは、1番目の集合には存在するが、2番目の集合には存在しない要素の集まりのことです。関数によってコピーされる要素は常に第1の範囲から取り出され、元の順序が保たれます。なお、この関数を正しく動作させるには、両方の範囲の要素があらかじめソート済みである必要があります。

構文

OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2, InputIterator2 last2,
                               OutputIterator result);

アルゴリズム

開始
ステップ1: 欠落要素を見つける関数を作成する
    void find(int array1[], int array2[], int x, int y)
    結果を格納するvector<int> v(x + y) を宣言
    vectorを走査するイテレータ vector<int>::iterator it を宣言
    両方の配列をソートする
    sort(array1, array1 + x) と sort(array2, array2 + y)
    欠落要素を求める
    diff = set_difference(array1, array1 + x, array2, array2 + y, v.begin())
    結果の要素数に合わせてvectorをリサイズ
    v.resize(diff - v.begin())
    array1[]に存在しarray2[]に存在しない要素を出力
    for (diff = v.begin(); diff != v.end(); ++diff)
        *diff を出力
    終了
ステップ2: main()内で
    int型の配列 array1 と array2 を宣言
    配列のサイズを求める変数 x と y を宣言
    int x = sizeof(array1) / sizeof(array1[0])
    int y = sizeof(array2) / sizeof(array2[0])
    find(array1, array2, x, y) を呼び出す
終了

実装例

#include <bits/stdc++.h>
using namespace std;

// 欠落要素を見つけるための関数「find」
void find(int array1[], int array2[], int x, int y) {
    // 結果を格納するvectorを宣言
    vector<int> v(x + y);
    // vectorを走査するイテレータを宣言
    vector<int>::iterator it;
    // 両方の配列をソート
    sort(array1, array1 + x);
    sort(array2, array2 + y);
    // 欠落要素を見つける
    it = set_difference(array1, array1 + x, array2, array2 + y, v.begin());
    // 結果の要素数に合わせてvectorをリサイズ
    v.resize(it - v.begin());
    cout << "array1[]に存在しarray2[]に存在しない要素: ";
    for (it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

int main() {
    int array1[] = { 1, 2, 3, 4, 5, 7 };
    int array2[] = { 2, 3, 4, 5, 6, 8 };
    int x = sizeof(array1) / sizeof(array1[0]);
    int y = sizeof(array2) / sizeof(array2[0]);
    find(array1, array2, x, y);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

array1[]に存在しarray2[]に存在しない要素: 1 7

まとめ

STLのset_difference()を使えば、ソート済みの2つの配列から「片方にのみ存在する要素」を簡潔なコードで抽出できます。差分の抽出はO(N)で動作するため、二重ループで総当たりする方法(O(N×M))と比べて効率的です。set_intersection()やset_union()など、他の集合演算アルゴリズムとあわせて覚えておくと、さまざまな場面で役立ちます。