名前付き要件: UnorderedAssociativeContainer

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

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

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

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

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

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

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

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

[編集] 要件

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