名前付き要件: UnorderedAssociativeContainer

 

C++

言語

標準ライブラリヘッダ

フリースタンディング処理系とホスト処理系

名前付き要件

言語サポートライブラリ

コンセプトライブラリ (C++20)

診断ライブラリ

ユーティリティライブラリ

文字列ライブラリ

コンテナライブラリ

イテレータライブラリ

範囲ライブラリ (C++20)

アルゴリズムライブラリ

数値演算ライブラリ

ローカライゼーションライブラリ

入出力ライブラリ

ファイルシステムライブラリ (C++17)

正規表現ライブラリ (C++11)

アトミック操作ライブラリ (C++11)

スレッドサポートライブラリ (C++11)

技術仕様書

 

名前付き要件

基本
DefaultConstructible CopyAssignable CopyConstructible	MoveAssignable (C++11) MoveConstructible (C++11) Destructible
型の性質
TrivialType (C++11) TriviallyCopyable (C++11)	StandardLayoutType (C++11) PODType
ライブラリ全体
EqualityComparable LessThanComparable Swappable (C++11) ValueSwappable (C++11) NullablePointer (C++11) Hash (C++11)	Allocator FunctionObject Callable Predicate BinaryPredicate Compare
コンテナ
Container SequenceContainer ContiguousContainer (C++17) ReversibleContainer	AssociativeContainer AllocatorAwareContainer UnorderedAssociativeContainer (C++11)
コンテナの要素
DefaultInsertable (C++11) CopyInsertable (C++11) MoveInsertable (C++11)	EmplaceConstructible (C++11) Erasable (C++11)
イテレータ
LegacyIterator LegacyOutputIterator LegacyInputIterator LegacyForwardIterator	LegacyBidirectionalIterator LegacyRandomAccessIterator LegacyContiguousIterator (C++17) ConstexprIterator (C++20)
ストリーム入出力
FormattedInputFunction UnformattedInputFunction	FormattedOutputFunction UnformattedOutputFunction
乱数
SeedSequence (C++11) RandomNumberEngine (C++11)	RandomNumberDistribution (C++11) UniformRandomBitGenerator (C++11) RandomNumberEngineAdaptor (C++11)
並行処理
BasicLockable (C++11) Lockable (C++11) TimedLockable (C++11)	Mutex (C++11) TimedMutex (C++11) SharedMutex (C++17) SharedTimedMutex (C++14)
その他
CharTraits RegexTraits (C++11) BitmaskType NumericType LiteralType (C++11)	UnaryTypeTrait (C++11) BinaryTypeTrait (C++11) TransformationTrait (C++11) Clock (C++11) TrivialClock (C++11)

 

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

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

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

Hash::transparent_key_equal が存在し、型を表す場合、 Hash::transparent_key_equal::is_transparent は有効であって型を表さなければならず、 Pred は Hash::transparent_key_equal または std::equal_to<Key> のいずれかでなければなりません (そうでなければプログラムは ill-formed です)。 このとき、メンバ関数 find、 contains、 count および equal_range は Key 以外の型の引数を受理し、 Hash がそれらの型の値で呼び出し可能であることと、 Hash::transparent_key_equal が std::equal_to<> のような透過的な比較関数であることが期待されます。

(C++20以上)

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 には適用されません)。

要件

凡例
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_equal が CopyConstructible である	指定されたハッシュ関数および等しさの述語を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築します。	n の線形時間
X(n,hf)	X	hasher が CopyConstructible であり、 key_equal が DefaultConstructible である	指定されたハッシュ関数および等しさの述語として key_equal() を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築します。	n の線形時間
X(n)	X	hasher および key_equal が DefaultConstructible である	ハッシュ関数として hasher() を、等しさの述語として key_equal() を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築します。	n の線形時間
X()	X	hasher および key_equal が DefaultConstructible である。	ハッシュ関数として hasher() を、等しさの述語として key_equal() を使用して、未規定の数のバケットを持つ空のコンテナを構築します。	定数時間
X(i,j,n,hf,eq)	X	hasher および key_equal が CopyConstructible であり、 value_type が {ttb|X}} に *i から EmplaceConstructible である。	指定されたハッシュ関数および等しさの述語を使用して、少なくとも n 個のバケットを持つ空のコンテナを構築し、 [i,j) の要素を挿入します。	平均的なケースでは線形、ワーストケースでは二乗 (i と j の距離に対して)
X(i,j,n,hf)	X	key_equal が DefaultConstructible である。	同上、ただし eq=key_equal()	同上
X(i,j,n)	X	hasher が DefaultConstructible である。	同上、ただし 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_type が CopyAssignable であり、さらに X に CopyInsertable である。	a = X(il)	同上

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

unordered_set (C++11)	一意なキーによってハッシュされた、キーのコレクション (クラステンプレート)
unordered_multiset (C++11)	キーによってハッシュされた、キーのコレクション (クラステンプレート)
unordered_map (C++11)	一意なキーによってハッシュされた、キー値ペアのコレクション (クラステンプレート)
unordered_multimap (C++11)	キーによってハッシュされた、キー値ペアのコレクション (クラステンプレート)