名前空間
変種
操作

名前付き要件: UnorderedAssociativeContainer

提供: cppreference.com
< cpp‎ | named req
 
 
名前付き要件
基本
レイアウト
ライブラリ全体
コンテナ
UnorderedAssociativeContainer
(C++11)

コンテナの要素
イテレータ
ストリーム入出力
乱数
並行処理
(C++11)

(C++11)
(C++11)
その他
 

非順序連想コンテナはキーを基にオブジェクトの高速な検索を提供する Container です。 ワーストケースの計算量は線形時間ですが、平均的にはほとんどの操作に対してもっと速くなります。

非順序連想コンテナは KeyHashPred によってパラメータ化されます。 HashKey に対してハッシュ関数として動作する関数オブジェクト、 PredKey 間の同等性を評価する BinaryPredicate です。 std::unordered_map および std::unordered_multimapKey と紐付けるマップされた型 T も持ちます。

2つの KeyPred に従って等しい場合、 Hash は両方のキーに対して同じ値を返さなければなりません。

Hash::transparent_key_equal が存在し、型を表す場合、 Hash::transparent_key_equal::is_transparent は有効であって型を表さなければならず、 PredHash::transparent_key_equal または std::equal_to<Key> のいずれかでなければなりません (そうでなければプログラムは ill-formed です)。

このとき、メンバ関数 findcontainscount および equal_rangeKey 以外の型の引数を受理し、 Hash がそれらの型の値で呼び出し可能であることと、 Hash::transparent_key_equalstd::equal_to<> のような透過的な比較関数であることが期待されます。

(C++20以上)

std::unordered_map および std::unordered_set は指定されたキーを持つ要素を多くとも1個格納でき、それに対して std::unordered_multiset および std::unordered_multimap は同じキーを持つ要素を複数持つことができます (イテレート時、必ず隣接していなければなりません)。

std::unordered_set および std::unordered_multiset については、値の型はキーの型と同じであり、 iteratorconst_iterator はどちらも定数イテレータです。 std::unordered_map および std::unordered_multimap については、値の型は std::pair<const Key, T> です。

非順序連想コンテナ内の要素はバケットに整理され、同じハッシュを持つキーは同じバケットに格納されます。 コンテナのサイズが増加したとき、各バケットの平均要素数を一定の値以下に維持するために、バケットの数が増加します。

再ハッシュはイテレータを無効化し、要素を異なるバケットに再配置する可能性がありますが、要素への参照は無効化しません。

非順序連想コンテナは AllocatorAwareContainer の要件を満たします。 std::unordered_map および std::unordered_multimap については、 AllocatorAwareContainervalue_type の要件が {tt|key_type}} および mapped_type に適用されます (しかし value_type には適用されません)。

[編集] 要件

凡例

X コンテナの型
a X 型のオブジェクト
b X 型の const オブジェクト
a_uniq X が一意なキーをサポートするときの X 内のオブジェクト
a_eq X が複数の同等なキーをサポートするときの X 内のオブジェクト
i, j 有効は範囲を示す LegacyInputIterator
p, q2 a への有効な const_iterator
q, q1 有効な範囲を示す a への逆参照可能な const_iterator
il std::initializer_list<X::value_type> のオブジェクト
t X::value_type 型のオブジェクト
k X::key_type 型のオブジェクト
hf X::hasher 型の const オブジェクト
eq X::key_equal 型の const オブジェクト
n X::size_type 型の値
z float 型の値


戻り値の型 事前/要件 事後/効果 計算量
X::key_type Key コンパイル時
X::mapped_type T std::unordered_map および std::unordered_multimap のみ。 コンパイル時
X::value_type Key std::unordered_set および std::unordered_multiset のみ。 X 内で Erasable である。 コンパイル時
X::value_type std::pair<const Key, T> std::unordered_map および std::unordered_multimap のみ。 X 内で Erasable である。 コンパイル時
X::hasher Hash Hash コンパイル時
X::key_equal
Pred (C++20未満)
有効であり型を表す場合は Hash::transparent_key_equal、そうでなければ Pred (C++20以上)
Key 型の2つの引数を取り同等関係を表現する BinaryPredicate コンパイル時
X::local_iterator X::iterator と同じカテゴリと型を持つ LegacyIterator 単一のバケットを通してイテレートするために使用できる。 コンパイル時
X::const_local_iterator X::const_iterator と同じカテゴリと型を持つ LegacyIterator 単一のバケットを通してイテレートするために使用できる。 コンパイル時
X(n,hf,eq) X hasher および key_equalCopyConstructible である 指定されたハッシュ関数および等しさの述語を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築します。 n の線形時間
X(n,hf) X hasherCopyConstructible であり、 key_equalDefaultConstructible である 指定されたハッシュ関数および等しさの述語として key_equal() を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築します。 n の線形時間
X(n) X hasher および key_equalDefaultConstructible である ハッシュ関数として hasher() を、等しさの述語として key_equal() を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築します。 n の線形時間
X() X hasher および key_equalDefaultConstructible である。 ハッシュ関数として hasher() を、等しさの述語として key_equal() を使用して、未規定の数のバケットを持つ空のコンテナを構築します。 定数時間
X(i,j,n,hf,eq) X hasher および key_equalCopyConstructible であり、 value_type が {ttb|X}} に *i から EmplaceConstructible である。 指定されたハッシュ関数および等しさの述語を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築し、 [i,j) の要素を挿入します。 平均的なケースでは線形、ワーストケースでは二乗 (ij の距離に対して)
X(i,j,n,hf) X key_equalDefaultConstructible である。 同上、ただし eq=key_equal() 同上
X(i,j,n) X hasherDefaultConstructible である。 同上、ただし hf=hasher() 同上
X(i,j) X 同上、ただしバケット数は未規定 同上
X(il) X X(il.begin(),il.end() 同上
X(il,n) X X(il.begin(),il.end(),n 同上
X(il,n,hf) X X(il.begin(),il.end(),n,hf 同上
X(il,n,hf,eq) X X(il.begin(),il.end(),n,hf,eq 同上
X(b) X コピーコンストラクタ。 ハッシュ関数、述語および最大負荷係数もコピーする。 平均的なケースでは線形、ワーストケースでは二乗 (b.size() に対して)
a = b X& コピー代入。 ハッシュ関数、述語および最大負荷係数もコピーする。 平均的なケースでは線形、ワーストケースでは二乗 (b.size() に対して)
a = il X& value_typeCopyAssignable であり、さらに XCopyInsertable である。 a = X(il) 同上

[編集] 標準ライブラリの非順序連想コンテナ

一意なキーによってハッシュされた、キーのコレクション
(クラステンプレート) [edit]
キーによってハッシュされた、キーのコレクション
(クラステンプレート) [edit]
一意なキーによってハッシュされた、キー値ペアのコレクション
(クラステンプレート) [edit]
キーによってハッシュされた、キー値ペアのコレクション
(クラステンプレート) [edit]