このページでは STL の set(セット≒集合)の使い方について解説します。
set は、数学では集合(=モノの集まり)という意味ですが、STL の set はこれに近いもです。しかし、要素数が有限であるという制限があります。
set の中には、各要素がソートされて格納されます。これも set が数学でいう集合とは異なる部分であると言えるでしょう。
set には C++ のオブジェクトを要素として入れる事になります。要素の変数型はテンプレート引数で指定するようになっているので、様々な型の要素を入れることが出来ますが、一つの set には、一つの型の要素しか入れられません。
set は、map のキーだけしか無いようなものとも言えます。map は pair<キー, 値> を要素としていますが、これと対比すると set は キー だけを要素としている事になるでしょう。
例として int 型の要素を二つ set に入れてみましょう。
#pragma warning(disable:4786) #include <set> using namespace std; int main() { set<int> setiPool; // int 型の要素を入れる set コンテナ setiPool を用意する。 setiPool.insert(2); // 要素として 2 を追加する。 setiPool.insert(3); // 要素として 3 を追加する。 return 0; }
これで、コンテナ setiPool に整数型の要素 2 と 3 が入ったことになります。
set の中に要素があるかどうかは、次のように判断します。
set<int>::iterator iti = setiPool.find(3); // find() で要素が見つかれば、要素へのイテレータが得られる。 if (iti == setiPool.end()) { // 要素が見つからなかった。 } else { // 要素が見つかった。 }
当該要素がある場合には iti にその要素を指すイテレータが得られます。
当該要素がない場合には iti に end() が得られます。
上記例の setiPool から要素を削除するには、次のようにします。
int i1 = setiPool.erase(2); // 要素 2 が削除される。削除された要素の数 1 が返る。 int i2 = setiPool.erase(4); // 要素 4 は無いので、0 が返る。
別法として setiPool 中に存在する要素を指すイテレータ iti が分かっている場合には、次のようにして削除することも出来ます。
set<int>::iterator itiNext = setiPool.erase(iti);
上記の場合 itiNext には、削除された要素の次の要素を指すイテレータが得られます。
もし、全ての要素が削除されてしまうと itNext は setiPool.end() となります。
上記を使うと、setiPool の要素を、初めの要素から最後の要素まで順次削除していくコードは次のようになるでしょう(役に立つかどうかは別にして)。
for (set<int>::iterator iti = setiPool.begin(); iti != setiPool.end(); iti = setiPool.erase(iti)) {}
ちなみに、setiPool が最初から空(=要素数が 0)の場合には、setiPool.begin() は setiPool.end() と一致し、上記の for 文は一度も実行されないことになります。
set の中には、要素がソートされて格納されるので、set に要素を入れるだけで、実質的にソートが完了している事になります。
従って、要素を追加した後は、for 文で begin() から end() までスキャンすれば、要素が昇順に得られるわけです。
しかし、ソートのためにこの方法を使うのは、vector にデータを入れて algorithm の sort() を使うという直接的な方法と比較して、相当に動作が遅いので、実際に使う場面はないかもしれません。
set に insert() で要素を入れるのは、vector に push_back() で要素を追加するよりも相当に重い処理であると認識しておくべきでしょう。
set の利点とは、set の中に要素が有るか無いかを比較的短時間に検出できるということでしょう。しかしそれには set に要素を追加するときにそれなりのコストが掛かっているとも言えるわけです。
set で集合演算が使えても良さそうなのですが、STL の set には、直接的にそのような機能は実装されていません。
実際上、例えば整数全体の集合などは、要素が無限個あるので、STL の set では表現できないという制限があり、いわゆる数学で言う集合とは異なるものだと認識すべきであると言えます。
それでも、要素が有限個であるような集合としては使用可能です。
和集合、積集合、補集合を計算するテンプレート関数を定義してみましょう。
コメントをざっと眺めれば、何をやっているのかはすぐに分かると思います。
#pragma warning(disable:4786) #include <stdio.h> #include <set> using namespace std; // デバグ用プリント void Print(set<int>& rseti) { for (set<int>::iterator iti = rseti.begin(); iti != rseti.end(); iti++) { printf("%3d ", *iti); } printf("\n"); } // 和集合の計算 template<class T> set<T> Union(set<T>& rsettA, set<T>&rsettB) { set<T> settUnion(rsettA); for (set<T>::iterator itt = rsettB.begin(); itt != rsettB.end(); itt++) { settUnion.insert(*itt); } return settUnion; } // 積集合の計算 template<class T> set<T> Product(set<T>& rsettA, set<T>&rsettB) { set<T> settProduct; for (set<T>::iterator itt = rsettB.begin(); itt != rsettB.end(); itt++) { if (rsettA.find(*itt) != rsettA.end()) { settProduct.insert(*itt); } } return settProduct; } // 補集合の計算 template<class T> set<T> Complement(set<T>& rsettA, set<T>&rsettB) { set<T> settComplement(rsettA); for (set<T>::iterator itt = rsettB.begin(); itt != rsettB.end(); itt++) { settComplement.erase(*itt); } return settComplement; } int main() { // 集合 A を用意する。 set<int> setiPoolA; { setiPoolA.insert(2); setiPoolA.insert(3); setiPoolA.insert(4); Print(setiPoolA); } // 集合 B を用意する。 set<int> setiPoolB; { setiPoolB.insert(2); setiPoolB.insert(5); setiPoolB.insert(1); Print(setiPoolB); } // 和集合、積集合、補集合を計算する。 set<int> setiUnion = Union (setiPoolA, setiPoolB); // A + B set<int> setiProcduct = Product (setiPoolA, setiPoolB); // A * B set<int> setiComplement = Complement(setiPoolA, setiPoolB); // A - B // プリントしてみる。 Print(setiUnion ); Print(setiProcduct ); Print(setiComplement); return 0; }
上記を実行すると、結果は次のようになります。
2 3 4 1 2 5 1 2 3 4 5 2 3 4
set は、map と同様に、要素がソートされて保存されるため、要素はソート可能ではくてはなりません。つまり、要素型には < 演算子が定義されている必要があります。
この事情は map のキーと同じなので、詳細については map の「要素がキーでソートされて保存されるということは」を参照してください。
ナオ : 店長、夕食の用意ができました。
店主 : ... 食えねぇ。
ナオ : ええっ。食べないんですか?
店主 : イャー、セットってのはなかなか食えねぇってんだ。
ナオ : 何のことを言っているのやら?