set は値のコレクションです。set の抽象化概念は、順序付きコレクションを必ず意味するわけではありませんが、set データ型は必ず順序付けられます。
注: 必要であれば、順序付けることができない値のコレクションは、リストなどの代替データ構造で維持することができます。
set データ構造に実装するために使用されるコンテナでは順序付き表現で値を維持するため、set は要素の挿入と削除、および特定の値がコレクションに含まれているかどうかを確認するテストのために最適化されます。この各演算は、実行に必要なステップが要素数に対して対数的に増加するのに対して、list、vector、deque の場合は、最悪のケースでは、コンテナに含まれる全要素の検証が必要になる場合もあります。この理由から、値の挿入、削除、包含のテストが問題となる場合、set がデータ構造として選択される必要があります。list と同様に、set にもサイズの制限はなく、要素のコレクションへの追加や削除に応じて、拡張や縮小が行われます。
標準 C++ ライブラリで提供される set には、2 種類あります。set コンテナでは、すべての要素が一意であり、すでに set に含まれている値の挿入は無視されます。一方、multiset コンテナでは同じ値が複数出現することが許可されています。
注: 他のプログラミング言語では、multiset は bag と呼ばれることがあります。
set または multiset を使用する場合は、必ずヘッダーファイルをインクルードする必要があります。
# include <set>