std::unordered_set
ヘッダ <unordered_set> で定義 | ||
template< class Key, | (1) | (C++11以上) |
namespace pmr { template<class Key, | (2) | (C++17以上) |
unordered set は Key 型の一意なオブジェクトの集合を格納する連想コンテナです。 検索、挿入、削除は平均定数時間の計算量です。
内部的には、要素は特定の順序にソートされず、複数のバケットにまとめられます。 要素がどのバケットに配置されるかはもっぱらその値のハッシュに依存します。 これにより、いったんハッシュが計算されればその要素が配置される正確なバケットを参照できるため、個々の要素への高速なアクセスが可能になります。
コンテナの要素は (非 const なイテレータであっても) 変更できません。 変更は要素のハッシュを変更し、コンテナを破損させるためです。
std::unordered_set は Container, AllocatorAwareContainer, UnorderedAssociativeContainer の要件を満たします。
目次 |
[編集]イテレータの無効化
| 操作 | 無効化 |
|---|---|
| すべての読み込み専用操作および swap, std::swap | 決して無効化されません |
| clear, rehash, reserve, operator= | 常に無効化されます |
| insert, emplace, emplace_hint | 再ハッシュが発生した場合のみ無効化されます |
| erase | 削除された要素のみ無効化されます |
[編集]ノート
- swap 関数はコンテナ内部のいかなるイテレータも無効化しませんが、 swap 範囲の終端をマークするイテレータは無効化されます。
- コンテナに格納されているキーまたはデータへの参照およびポインタは、対応するイテレータが無効化されたとしても、その要素が削除された場合にしか無効化されません。
- コンテナのムーブ代入を行ったとき (アロケータが非互換であることによって要素単位のムーブ代入が行われた場合は除きます)、ムーブ元コンテナへの参照、ポインタ、およびイテレータ (終端イテレータは除きます) は有効なままですが、その参照先の要素は以降 *this 内の要素になります。
[編集]メンバ型
| メンバ型 | 定義 |
key_type | Key |
value_type | Key |
size_type | 符号なし整数型 (通常 std::size_t) |
difference_type | 符号付き整数型 (通常 std::ptrdiff_t) |
hasher | Hash |
key_equal | KeyEqual |
allocator_type | Allocator |
reference | value_type& |
const_reference | const value_type& |
pointer | std::allocator_traits<Allocator>::pointer |
const_pointer | std::allocator_traits<Allocator>::const_pointer |
iterator | const LegacyForwardIterator |
const_iterator | const LegacyForwardIterator |
local_iterator | カテゴリおよび value, difference, pointer, reference の各型が iterator と同じイテレータ型。 このイテレータはバケット内をイテレートするために使用することができますが、別のバケットには移動できません |
const_local_iterator | カテゴリおよび value, difference, pointer, reference の各型が const_iterator と同じイテレータ型。 このイテレータはバケット内をイテレートするために使用することができますが、別のバケットには移動できません |
node_type(C++17以上) | コンテナノードを表すノードハンドルの特殊化 |
insert_return_type(C++17以上) | node_type を挿入した結果を表す型。 テンプレート引数 iterator および node_type でインスタンス化された template<class Iter, class NodeType>struct/*unspecified*/{ Iter position;bool inserted; NodeType node;}; |
[編集]メンバ関数
unordered_set を構築します (パブリックメンバ関数) | |
unordered_set を破棄します (パブリックメンバ関数) | |
| コンテナに値を代入します (パブリックメンバ関数) | |
| 関連付けられているアロケータを返します (パブリックメンバ関数) | |
挿入 | |
| 先頭を指すイテレータを返します (パブリックメンバ関数) | |
| 終端を指すイテレータを返します (パブリックメンバ関数) | |
容量 | |
| コンテナが空かどうか調べます (パブリックメンバ関数) | |
| 要素数を返します (パブリックメンバ関数) | |
| 可能な最大の要素数を返します (パブリックメンバ関数) | |
変更 | |
| すべての要素を削除します (パブリックメンバ関数) | |
| 要素またはノード(C++17以上)を挿入します (パブリックメンバ関数) | |
| 要素をその場で構築します (パブリックメンバ関数) | |
| ヒントを使用して要素をその場で構築します (パブリックメンバ関数) | |
| 要素を削除します (パブリックメンバ関数) | |
(C++11) | 内容を入れ替えます (パブリックメンバ関数) |
(C++17) | コンテナからノードを抽出します (パブリックメンバ関数) |
(C++17) | 他のコンテナからノードを接合します (パブリックメンバ関数) |
検索 | |
| 指定されたキーと一致する要素の数を返します (パブリックメンバ関数) | |
| 指定されたキーを持つ要素を探します (パブリックメンバ関数) | |
(C++20) | コンテナが指定されたキーを持つ要素を格納しているかどうか調べます (パブリックメンバ関数) |
| 指定されたキーに一致する要素の範囲を返します (パブリックメンバ関数) | |
バケットインタフェース | |
| 指定されたバケットの先頭を指すイテレータを返します (パブリックメンバ関数) | |
| 指定されたバケットの終端を指すイテレータを返します (パブリックメンバ関数) | |
| バケットの数を返します (パブリックメンバ関数) | |
| バケットの最大数を返します (パブリックメンバ関数) | |
| 特定のバケットの要素数を返します (パブリックメンバ関数) | |
| 指定されたキーのためのバケットを返します (パブリックメンバ関数) | |
ハッシュポリシー | |
| バケットあたりの平均要素数を返します (パブリックメンバ関数) | |
| バケットあたりの平均要素数の最大値を管理します (パブリックメンバ関数) | |
| 少なくとも指定された数のバケットを予約します。 これによりハッシュテーブルが再生成されます。 (パブリックメンバ関数) | |
| 少なくとも指定された数の要素のための空間を予約します。 これによりハッシュテーブルが再生成されます。 (パブリックメンバ関数) | |
観察 | |
| キーをハッシュするために使用される関数を返します (パブリックメンバ関数) | |
| キーが等しいかどうかを比較するために使用される関数を返します (パブリックメンバ関数) | |
[編集]非メンバ関数
(C++20で削除) | unordered_set 内の値を比較します (関数テンプレート) |
| std::swap アルゴリズムの特殊化 (関数テンプレート) | |
(C++20) | 特定の基準を満たすすべての要素を削除します (関数テンプレート) |
[編集]推定ガイド(C++17以上)
[編集]ノート
メンバ型 iterator および const_iterator は同じ型のエイリアスである場合があります。 これは、これら2つの型を引数として取る一組の関数オーバーロードの定義は単一定義規則に違反するかもしれない、という意味です。 iterator は const_iterator に変換可能であるため、代わりに const_iterator を引数の型として用いた関数がひとつあれば良いでしょう。
