• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(UTC):
    が更新

    履歴 編集

    class template
    <unordered_map>

    std::unordered_map

    namespace std {
      template <class Key,
                class T,
                class Hash = std::hash<Key>,
                class Pred = std::equal_to<Key>,
                class Allocator = std::allocator<std::pair<const Key, T> > >
      class unordered_map;
    
      namespace pmr {
        template <class Key,
                  class T,
                  class Hash = hash<Key>,
                  class Pred = equal_to<Key>>
          using unordered_map =
            std::unordered_map<Key, T, Hash, Pred,
                               polymorphic_allocator<pair<const Key, T>>>;  // C++17から
    
      }
    }
    

    概要

    unordered_map は、同一キーの要素を複数格納できず、格納順が規定されていないコンテナである。

    一般的には hash map と呼ばれるコンテナであるが、標準への採用が遅かったことから、既に存在する各種コンテナとの名前の衝突を避けるため、unordered_map と名付けられた。

    unordered_map の特徴は以下の通りである。

    • 連想
      標準の配列や std::vector と異なり、コンテナ内の要素へのアクセスは絶対的な位置(添え字)によるのではなく、キーによる。
    • 非順序
      コンテナ内の各要素は、キーのハッシュ値に基づきハッシュテーブルに格納されるため、決められた順序で並んでいるわけではない。
    • マップ(map)
      キーと、それに対応する値がペアとなった要素を持ち、かつ、同一のキー値を格納することはできない。

    テンプレートパラメータ Hash は、以下に示す Hash requirements を満たし、テンプレートパラメータ Key のハッシュ関数として振る舞わなければならない。

    • 関数オブジェクト型である。
    • CopyConstructible requirements と Destructible requirements の要件を満たす。
    • hHash 型のオブジェクト、KeyHash 型のオブジェクトの引数の型、uKey 型の左辺値、kKey 型(あるいは const Key 型)に変換可能な値とすると、以下の要件を満たす。
      • h(k) は戻り値の型が std::size_t で、戻り値は引数 k のみにしかよらない
      • h(u)u を変更しない

    テンプレートパラメータ Pred は二項述語で、テンプレート引数 Key に対する同値関係でなければならない。

    テンプレートパラメータ Allocator は、Allocator requirements を満たさなければならない。

    メンバ関数

    構築/コピー/破棄

    名前 説明 対応バージョン
    (constructor) コンストラクタ C++11
    (destructor) デストラクタ C++11
    operator= 代入演算子 C++11

    領域

    名前 説明 対応バージョン
    empty コンテナが空かどうかを判定 C++11
    size 要素数の取得 C++11
    max_size 格納可能な最大の要素数の取得 C++11

    イテレータ

    名前 説明 対応バージョン
    begin 先頭要素を指すイテレータの取得 C++11
    end 最終要素の次を指すイテレータの取得 C++11
    cbegin 先頭要素を指す読み取り専用イテレータの取得 C++11
    cend 最終要素の次を指す読み取り専用イテレータの取得 C++11

    アロケータ

    名前 説明 対応バージョン
    get_allocator アロケータオブジェクトの取得 C++11

    コンテナの変更

    名前 説明 対応バージョン
    emplace コンテナ内への要素の直接構築 C++11
    emplace_hint 挿入位置のヒントを使用したコンテナ内への要素の直接構築 C++11
    try_emplace キーが存在しない場合のみコンテナ内への要素の直接構築 C++17
    insert 要素の追加 C++11
    insert_or_assign 要素の追加、あるいは代入 C++17
    insert_range Rangeの要素を挿入する C++23
    erase 要素の削除 C++11
    clear 全要素の削除 C++11
    swap 内容の交換 C++11
    extract ノードハンドルを取得する C++17
    merge 他のオブジェクトの要素をマージする C++17

    オブザーバー

    名前 説明 対応バージョン
    hash_function ハッシュ関数オブジェクトの取得 C++11
    key_eq キー比較用関数オブジェクトの取得 C++11

    検索

    名前 説明 対応バージョン
    find 指定したキーの位置を検索 C++11
    count 指定したキーの要素数を取得 C++11
    contains 指定したキーの要素が含まれているかを判定する C++20
    equal_range 指定したキーの範囲を取得 C++11
    operator[] 要素の値へのアクセス C++11
    at 要素の値へのアクセス C++11

    バケットインタフェース

    名前 説明 対応バージョン
    bucket_count バケット数の取得 C++11
    max_bucket_count 最大バケット数の取得 C++11
    bucket_size インデックス(添え字)で指定したバケット内の要素数を取得 C++11
    bucket キーで指定したバケットのインデックス(添え字)を取得 C++11
    begin(size_type) インデックス(添え字)で指定したバケット内の先頭要素を指すイテレータを取得 C++11
    end(size_type) インデックス(添え字)で指定したバケット内の最終要素の次を指すイテレータを取得 C++11
    cbegin(size_type) インデックス(添え字)で指定したバケット内の先頭要素を指す読み取り専用イテレータを取得 C++11
    cend(size_type) インデックス(添え字)で指定したバケット内の最終要素の次を指す読み取り専用イテレータを取得 C++11

    ハッシュポリシー

    名前 説明 対応バージョン
    load_factor 現在の負荷率(バケットあたりの要素数の平均)を取得 C++11
    max_load_factor 負荷率の最大値を取得、設定 C++11
    rehash 最小バケット数指定によるバケット数の調整 C++11
    reserve 最小要素数指定によるバケット数の調整 C++11

    メンバ型

    名前 説明 対応バージョン
    key_type キーの型。テンプレートパラメータ Key C++11
    value_type 要素の型。std::pair<const Key, T> C++11
    mapped_type 値の型。テンプレートパラメータ T C++11
    hasher キーのハッシュ関数の型。テンプレートパラメータ Hash C++11
    key_equal キーが等値か否かを判断するための二項述語の型。テンプレートパラメータ Pred C++11
    allocator_type アロケータの型。テンプレートパラメータ Allocator C++11
    pointer 要素 value_type= std::pair<const Key, T>)へのポインタ。スマートポインタも可であるが、通常は value_type*
    規格書では、allocator_type::pointer となっているが、これは規格書の誤りで、ドラフト N3376 で既に std::allocator_traits<Allocator>::pointer に修正されている。
    (さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため)
    C++11
    const_pointer 要素 value_type= std::pair<const Key, T>)へのコンストポインタ。スマートポインタも可であるが、通常は const value_type*
    規格書では、allocator_type::const_pointer となっているが、これは規格書の誤りで、ドラフト N3376 で既に std::allocator_traits<Allocator>::const_pointer に修正されている。
    (さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため)
    C++11
    reference 要素 value_type= std::pair<const Key, T>)への参照。
    規格書では、allocator_type::reference となっているが、これは規格書の誤りで、ドラフト N3376 で既に value_type& に修正されている。
    (さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため)
    C++11
    const_reference 要素 value_type= std::pair<const Key, T>)へのコンスト参照。
    規格書では、allocator_type::const_reference となっているが、これは規格書の誤りで、ドラフト N3376 で既に const value_type& に修正されている。
    (さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため)
    C++11
    size_type 要素数を表す符号なし整数型。difference_type で表現可能な非負整数(0以上の整数)を表すことが可能。(通常は size_t) C++11
    difference_type 同一のコンテナを指す iterator の差を表す符号付き整数型(通常は ptrdiff_t)
    std::iterator_traits<iterator>::difference_type、および、std::iterator_traits<const_iterator>::difference_type と同じ。
    C++11
    iterator 前方向イテレータ C++11
    const_iterator 読み取り専用前方向イテレータ C++11
    local_iterator 同一バケット内のみで有効なイテレータ。
    規格書には記載はないが、iterator と同様)const_local_iterator と同じ型か否かは実装依存であるものと思われる。
    iterator と、iterator_categoryvalue_typedifference_typepointerreference は同一である。
    C++11
    const_local_iterator 同一バケット内のみで有効な読み取り専用イテレータ。
    const_iterator と、iterator_categoryvalue_typedifference_typepointerreference は同一である。
    C++11
    node_type node_handleクラステンプレートの特殊化。 C++17
    insert_return_type ノードを挿入した結果を記述するために使用されるクラス型。以下に示すinsert-return-typeテンプレートの特殊化である。ただし、これは説明用のクラスであり、実装定義である。 C++17

    template <class Iterator, class NodeType>
    struct insert-return-type {
      Iterator position;
      bool inserted;
      NodeType node;
    };
    

    非メンバ関数

    比較演算子

    名前 説明 対応バージョン
    operator== 等値比較 C++11
    operator!= 非等値比較 C++11

    入れ替え

    名前 説明 対応バージョン
    swap 内容の交換 C++11

    要素削除

    名前 説明 対応バージョン
    erase_if 指定した条件に合致する要素とその分の領域を、コンテナから削除する C++20

    推論補助

    名前 説明 対応バージョン
    (deduction_guide) クラステンプレートの推論補助 C++17

    #include <iostream>
    #include <unordered_map>
    #include <iterator>
    #include <algorithm>
    #include <string>
    
    template <class C>
    void print(const C& c, std::ostream& os = std::cout)
    {
      std::for_each(std::begin(c), std::end(c), [&os](typename C::value_type p) { os << '{' << p.first << ',' << p.second << "}, "; });
      os << std::endl;
    }
    
    int main()
    {
      std::unordered_map<std::string, int> um{ {"1st", 1}, {"2nd", 2}, {"3rd", 3}, };
    
      print(um);
    
      std::cout << "3rd:" << um.at("3rd") << std::endl;
    
      um.emplace("4th", 4);
    
      print(um);
    
      um.erase("2nd");
    
      print(um);
    
      std::cout << "5th:" << um["5th"] << std::endl;
    
      print(um);
    }
    

    出力

    {2nd,2}, {3rd,3}, {1st,1},
    3rd:3
    {4th,4}, {2nd,2}, {3rd,3}, {1st,1},
    {4th,4}, {3rd,3}, {1st,1},
    5th:0
    {5th,0}, {4th,4}, {3rd,3}, {1st,1},
    

    バージョン

    言語

    • C++11

    参照