C++で最初の配列に存在し、2番目の配列には存在しない要素を検索する方法

概要

2つの配列AとBが与えられたとき、配列Aには存在するが配列Bには存在しない要素をすべて見つける方法を解説します。AとBをそれぞれ集合（セット）とみなすと、この操作は「差集合（Set Difference）」の計算に相当します。C++では、標準ライブラリの std::set_difference アルゴリズムを使うことで、この差集合を簡単かつ効率的に求めることができます。

set_differenceを使う際のポイント

std::set_difference は <algorithm> ヘッダで定義されているアルゴリズムです。使用する際は、以下の点に注意しましょう。

• 入力となる両方の範囲は、あらかじめソート済みである必要があります。
• 結果は第5引数で指定した出力イテレータ（ここでは res.begin()）に書き込まれます。
• 戻り値は出力先の末尾を指すイテレータであり、これを使うことで実際に書き込まれた要素の範囲を把握できます。

サンプルコード

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

void setDiffResults(int A[], int B[], int An, int Bn) {
    sort(A, A + An);
    sort(B, B + Bn);
    vector<int> res(An);
    vector<int>::iterator it;
    vector<int>::iterator it_res = set_difference(A, A + An, B, B + Bn, res.begin());
    cout << "Elements are: ";
    for (it = res.begin(); it < it_res; ++it) {
        cout << *it << " ";
    }
}

int main() {
    int A[] = {9, 4, 5, 3, 1, 7, 6};
    int B[] = {9, 3, 5};
    int An = 7, Bn = 3;
    setDiffResults(A, B, An, Bn);
}

実行結果

Elements are: 1 4 6 7

処理の解説

この例では、配列A = {9, 4, 5, 3, 1, 7, 6} と配列B = {9, 3, 5} を比較しています。まず両方の配列をソートすると、A = {1, 3, 4, 5, 6, 7, 9}、B = {3, 5, 9} となります。set_difference はこれらのソート済み範囲を先頭から順に走査し、Aにのみ存在する要素「1, 4, 6, 7」を結果ベクトルに格納します。

計算量についても触れておきましょう。差集合の計算自体は O(N + M)（N、Mはそれぞれの配列の要素数）の線形時間で動作します。ただしソートが必要な場合は、全体の計算量は O(N log N + M log M) となります。それでも、配列同士を総当たりで比較する O(N × M) の方法に比べると、大規模なデータでは大幅に高速です。

なお、結果を格納するベクトルは事前に十分なサイズを確保しておく必要があります。ここでは最大でもAの要素数を超えないため、vector<int> res(An) としてAと同じサイズを確保しています。C++17以降では std::back_inserter を使えば、サイズを気にせず動的に結果を追加することも可能です。