std::unordered_set

unordered set は Key 型の一意なオブジェクトの集合を格納する連想コンテナです。 検索、挿入、削除は平均定数時間の計算量です。

内部的には、要素は特定の順序にソートされず、複数のバケットにまとめられます。 要素がどのバケットに配置されるかはもっぱらその値のハッシュに依存します。 これにより、いったんハッシュが計算されればその要素が配置される正確なバケットを参照できるため、個々の要素への高速なアクセスが可能になります。

コンテナの要素は (非 const なイテレータであっても) 変更できません。 変更は要素のハッシュを変更し、コンテナを破損させるためです。

std::unordered_set は Container, AllocatorAwareContainer, UnorderedAssociativeContainer の要件を満たします。

[編集] イテレータの無効化

[編集] ノート

• swap 関数はコンテナ内部のいかなるイテレータも無効化しませんが、 swap 範囲の終端をマークするイテレータは無効化されます。

• コンテナに格納されているキーまたはデータへの参照およびポインタは、対応するイテレータが無効化されたとしても、その要素が削除された場合にしか無効化されません。

• コンテナのムーブ代入を行ったとき (アロケータが非互換であることによって要素単位のムーブ代入が行われた場合は除きます)、ムーブ元コンテナへの参照、ポインタ、およびイテレータ (終端イテレータは除きます) は有効なままですが、その参照先の要素は以降 *this 内の要素になります。

[編集] メンバ型

template <class Iter, class NodeType> struct /*unspecified*/ {
    Iter     position;
    bool     inserted;
    NodeType node;
};

[編集] メンバ関数

[編集] 非メンバ関数

[編集] 推定ガイド(C++17以上)

[編集] ノート

メンバ型 iterator および const_iterator は同じ型のエイリアスである場合があります。 これは、これら2つの型を引数として取る一組の関数オーバーロードの定義は単一定義規則に違反するかもしれない、という意味です。 iterator は const_iterator に変換可能であるため、代わりに const_iterator を引数の型として用いた関数がひとつあれば良いでしょう。