C++のset STLで挿入・削除・検索を実装するプログラム

整数型のデータを格納するセット(set)データ構造について考えます。標準入力からn個のクエリが与えられ、各クエリ(各行)には2つの値が含まれています。1つ目は操作の種類を示す番号、2つ目は対象となる要素です。各操作の内容は以下の通りです。

• 挿入(Insert):指定された要素をセットに追加します。

• 削除(Delete):指定された要素をセットから削除します(存在しない場合は何も行いません)。

• 検索(Search):指定された要素がセット内に存在するかを調べ、存在すれば「Yes」、存在しなければ「No」を出力します。

問題例

たとえば、n = 7、queries = [[1,5],[1,8],[1,3],[2,8],[1,9],[3,8],[3,3]] という入力が与えられた場合を考えてみましょう。このときの出力は [No, Yes] となります。これは、8 は先にセットから削除されているため存在せず、3 はセット内に存在するためです。

解法のアプローチ

この問題は、以下の手順に従って解くことができます。

• セット s を定義します。
• s を走査するためのイテレータ it を定義します。
• 変数 q にクエリの個数を読み込みます。
• q が0になるまで、1回ごとに q を減らしながら以下を繰り返します。
  • クエリの種類 qt と要素 x を読み込みます。
  • qt の値に応じて処理を分岐させます。
    • qt が 1 の場合:x をセット s に挿入します。
    • qt が 2 の場合:セット s から x を削除します。
    • qt が 3 の場合:find(x) を呼び出して結果をイテレータ it に格納し、it が s.end()(終端)と一致した場合は「No」を出力し、そうでなければ「Yes」を出力します。

実装例

それでは、より理解を深めるために実際のC++コードを見てみましょう。

#include <iostream>
#include <set>
using namespace std;
int main(){
    set<int> s;
    set<int>::iterator it;
    int q,x;
    int qt;
    cin >> q;
    while(q--){
        cin>>qt>>x;
        switch(qt){
            case 1:s.insert(x);
                   break;
            case 2:s.erase(x);
                   break;
            case 3:it=s.find(x);
                   if(it==s.end())
                       cout<<"No"<<endl;
                   else
                       cout<<"Yes"<<endl;
                   break;
        }
    }
    return 0;
}

入力例

7
1 5
1 8
1 3
2 8
1 9
3 8
3 3

出力例

No
Yes

コードのポイント

このプログラムでは、std::set の内部構造として平衡二分探索木(赤黒木)が使用されているため、挿入・削除・検索はいずれも O(log n) の計算量で効率的に処理されます。また、find() メンバ関数は、要素が見つかった場合にその位置を指すイテレータを、見つからなかった場合には end() を返すという性質を持っています。この性質を利用することで、シンプルな条件分岐だけで要素の存在判定を実現できます。