名前空間
変種

    名前付き要件: UnorderedAssociativeContainer

    提供: cppreference.com
     
    C++
     
    名前付き要件
    基本
    型の性質
    ライブラリ全体
    コンテナ
    コンテナの要素
    イテレータ
    ストリーム入出力
    乱数
    並行処理
    (C++11)
    (C++11)
    (C++11)

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

    非順序連想コンテナはキーを基にオブジェクトの高速な検索を提供する 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) 同上
    This section is incomplete
    Reason: requirements regarding member functions

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

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