8.2 set 演算と multiset 演算

set および multiset データ型で提供されるメンバー関数については、以降の節で説明します。メンバー関数が基本演算を提供する一方で、これらのデータ構造のユーティリティは、第 IV 部で説明する汎用アルゴリズムの使用によって大きく拡張されることに注意してください。

set は含まれる要素の型と、キーの比較に使用される演算子によって特殊化される、テンプレートデータ構造です。後者の引数は省略可能で、指定されない場合は、キーの型に対する小なり演算子が仮定されます。要素型は integer や double、ポインタ型、ユーザーが定義した型などと同様に、基本言語型とすることもできます。要素型は、等価テスト演算子 == と小なり比較演算子 < の両方を認識する必要があります。

set は初期要素なしで宣言でき、また、1 組の反復子を提供することによって、他のコンテナから初期化することもできます。1 組の反復子を使用するコンテナの初期化には、一部のコンパイラではまだサポートされていないメカニズムが要求されます。提供されない場合は、空の set を宣言し、copy() 汎用アルゴリズムを使用することによって値を set にコピーすると、同じ効果を得ることができます。

初期要素なしで宣言するか、または他のコンテナから初期化して、任意の引数を代替比較関数とします。この値はテンプレートパラメータによって提供される値を上書きします。同じ値で順序付けが異なる 2 つ以上の set がプログラムに含まれる場合に、このメカニズムは有効で、set メンバー関数の複数のコピーがインスタンス化されるのを防ぐことができます。ただし、含まれるテンプレートパラメータの型とコンテナコンストラクタに渡される型は同じでなくてはなりません。コピーコンストラクタは、既存のセットのクローンやコピーである新しい set を形成するために使用することができます。

set <int> set_one;

set <int, greater<int> > set_two;
set <int, greater<int> > set_three(greater<int>());

set <gadget, less<gadget> > gset;
set <gadget> gset(less<gadget>());

set <int> set_four (aList.begin(), aList.end());
set <int, greater<int>> set_five 
   (aList.begin(), aList.end(), greater<int>());

   set <int> set_six (set_four);                // コピーコンストラクタ

set は他の set に代入することが可能で、他の標準 C++ ライブラリコンテナと類似した方法で swap() 演算を使用して、2 つの set の値を交換することができます。

set_one = set_five;
set_six.swap(set_two);

クラス set と multiset には多数の型の定義が含まれ、一般的には宣言文で使用されます。たとえば、integer の set の反復子は、次のように宣言することができます。

set<int>::iterator location;

iterator に加えて、表 12 では次の型を定義します。

list や vector とは異なり、set に要素を追加する方法は 1 つだけです。insert() メンバー関数を使用すると、値を set または multiset に挿入することができます。multiset の場合、関数は直前に挿入された値を示す反復子を返します。set への挿入演算は、pair を返します。最初のフィールドは反復子を含みます。２番目のフィールドはブール型の値で要素が挿入された場合には true を、それ以外の場合には false が設定されます。

---

注: map を使用せずに pair データ型を使用する場合、utility という名前のヘッダーファイルを取り込む必要があります。

---

set では、すでにコレクションに含まれている要素と一致する要素は、挿入されないことに注意してください。

set_one.insert (18);

if (set_one.insert(18).second)
   cout << "element was inserted" << endl;
else
   cout << "element was not inserted " << endl;

他のコンテナからの複数の要素の挿入は、反復子 pair を使用して実行することもできます。

set_one.insert (set_three.begin(), set_three.end());

pair データ構造は、値の組です。最初の値はフィールド名 first からアクセスされ、2 番目の値は、自動的に second という名前になります。make_pair() という名前の関数は、クラス pair のインスタンスを作成するタスクを単純にします。

template <class T1, class T2>
struct pair {
   T1 first;
   T2 second;
   pair (const T1 & x, const T2 & y) : first(x), second(y) { }
};

template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1& x, const T2& y)
   { return pair<T1, T2>(x, y); }

たとえば、キーの等価を調べるには、新しい要素のキー部分が既存のキーと一致しているかどうかを調べるために、等価演算子 == ではなく、キーの比較関数が使用されます。キー値の順序付けを行うために使用される比較関数が双方向で false となった場合、2 つのキーは等価であると考えられます。つまり、Compare(key1, key2) が false の場合、および Compare(key2, key1) が false の場合、key1 と key2 は等価であるとみなされます。

メンバー関数 erase() を使用して、値を set から削除することができます。引数は特定の値、1 つの値を示す反復子、値の範囲を示す 1 組の反復子のいずれかにすることができます。multiset で最初の形式が使用される場合、引数値と一致するすべての引数が削除され、返される値が消去された要素の数を示します。

// 4 と等しい要素を消去する
set_three.erase(4);

// 要素 5 を消去する    set<int>::iterator five = set_three.find(5);
set_three.erase(five);

// 7 と 11 の間のすべての値を消去する
set<int>::iterator seven = set_three.find(7);
set<int>::iterator eleven = set_three.find(11);
set_three.erase (seven, eleven);

配下の要素型にデストラクタがある場合、コレクションから要素が削除される前に、デストラクタが呼び出されます。

メンバー関数 size() は、コンテナに保持される要素数を算出します。コンテナが空白の場合、メンバー関数 empty() はブール値 true を返し、通常、ゼロに対する size() のテストよりも高速です。

メンバー関数 find() は要素の値を使用し、set の値の位置を示す反復子がある場合はそれを返し、ない場合は関数 end() によって算出される セットの終端値と一致する値を返します。multiset に複数の一致する要素が含まれている場合、返される値は任意の適切な値となります。

set<int>::iterator five = set_three.find(5);
if (five != set_three.end())
    cout << "set contains a five" << endl;

メンバー関数 lower_bound() と upper_bound() は、setで使用すると単に関数 find() と同じ働きをするため、multiset で使用すると最も効果的です。メンバー関数 lower_bound() は、引数キーと一致する最初のエントリを算出し、メンバー関数 upper_bound() は引数と一致する最後のエントリを越えた後の最初の値を返します。最後に、メンバー関数 equal_range() は、上限と下限をもつ反復子の pair を返します。

メンバー関数 count() は、引数と一致する要素の数を返します。set の場合、この値は 0 または 1 となり、multiset の場合は、負にならない値とすることができます。0 でない整数値が ture として扱われるため、set に要素があるかどうかを確認するために必要な場合は、count() 関数を要素の包含のテストに使用することができます。また、find() を使用するには、コレクションの終端反復子に対して find() によって返される結果をテストすることが要求されます。

if (set_three.count(5))
   cout << "set contains a five" << endl;

メンバー関数の begin() と end() は、set と multiset の両方に反復子を作成します。この 2 つの関数によって作成される反復子は定数で、set 要素への新しい値の代入によって、set への順序付けの関係が偶然、または意図的に破壊されることはありません。set が宣言されると、反復子は、指定された比較演算子によって順序付けられた要素をシーケンスに生成します。メンバー関数 rbegin() と rend() は、逆の順序で要素を算出する反復子を作成します。

---

注: vector や deque とは異なり、値の挿入または削除によってコレクションの他の要素への反復子や参照が無効になることはありません。

---

従来の set 演算の subset test、set union、set intersection、set difference がメンバー関数として提供されることはありませんが、代わりに任意の順序付き構造で動作する汎用アルゴリズムとして実装されます。これらの関数の詳細は、14.7 節に記述されています。次の節では、set と multiset のコンテナクラスで使用することができる関数について説明します。

関数 includes() は、 set が他の set の subset であるかどうかを確認するために使用することができます。つまり、1 番目のすべての要素が 2 番目に格納されているかどうかをテストします。multiset の場合、2 番目の set に一致する要素の数は、1 番目の set の要素の数より多い必要があります。4 つの引数は (おそらく) 小さい方の set を表現する 1 組の反復子と、(潜在的に) 大きい方の set を表現する 1 組の反復子です。

if (includes(set_one.begin(), set_one.end(),
   set_two.begin(), set_two.end()))
      cout << "set_one is a subset of set_two" << endl;

小なり演算子 < は、set の宣言に使用される演算子に関係なく、要素の比較に使用されます。これが適切ではない場合、includes() の代替となる関数が使用されます。この形式が 5 番目の引数となり、2 つの set の要素の順序付けに使用される比較関数です。

関数 set_union() は、2 つの set の和集合の作成に使用することができます。2 つの set は反復子の組み合わせで指定され、和集合は 5 番目の引数として使用される出力反復子にコピーされます。結果を set として形成するには、挿入反復子を出力反復子の形成に使用する必要があります (2.4 節)。要求される結果が 1 つの set と他の set の和集合の場合、一時 set の作成後、一時 set が削除されるまで、引数 set の結果が入れ替えられます。

// 2 つの set の和集合、結果を vector にコピーする
vector<int> v_one (set_one.size() + set_two.size());

set_union(set_one.begin(), set_one.end(), 
   set_two.begin(), set_two.end(), v_one.begin());

// 和集合を同じ場所で形成する
set<int> temp_set;
set_union(set_one.begin(), set_one.end(), 
   set_two.begin(), set_two.end(), 
   inserter(temp_set, temp_set.begin()));
set_one.swap(temp_set);  // temp_set が削除される

関数 set_intersection() も同様に、2 つの set の積集合を形成します。

includes() 関数と同様に、小なり演算子 < は、set の宣言に使用される演算子に関係なく、2 つの引数 set を比較するために使用されます。これが適切ではない場合、set_union() または set_intersection() の代替となる関数で、6 番目の引数として指定される set を形成するために比較演算子を使用することができます。

2 つの multiset の和集合の演算は、2 つの set をマージする演算と区別する必要があります。たとえば、1 つの引数 set に要素 7 の 3 つのインスタンスが含まれ、2 番目の set に同じ値の 2 つのインスタンスが含まれるとします。和集合にはこのうちの 3 つの値だけが含まれ、マージには 5 つが含まれます。マージを形成するには、関数 merge() を使用することができます (14.6 節)。この関数への引数は、set_union() 関数の引数と完全に一致します。

set の差には 2 つの形式があります。単純な set の差は、2 番目の set には含まれない 1 番目の set の要素を表します。対称的な set の差は、2 番目の set には含まれない 1 番目の set の要素と、1 番目の set には含まれない 2 番目の要素との和集合です。この 2 つの値は、それぞれ関数 set_difference() および set_symmetric_difference() によって作成されます。これらの関数の使用は、前述の set_union() 関数の使用と同様です。

set は順序付けられ、定数の反復子があるため、第 IV 部と第 14 章に記述する汎用関数の多くは set に適用できないか、それほど有効ではありません。表 13 に set データ型と結合して使用するいくつかの関数を示します。

表 13 -- set データ型に有効な関数