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 の要件を満たす。
• h を Hash 型のオブジェクト、Key を Hash 型のオブジェクトの引数の型、u を Key 型の左辺値、k を Key 型（あるいは const Key 型）に変換可能な値とすると、以下の要件を満たす。
  • h(k) は戻り値の型が std::size_t で、戻り値は引数 k のみにしかよらない
  • h(u) は u を変更しない

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

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

概念・前提知識

• コンテナとは

メンバ関数

構築／コピー／破棄

領域

イテレータ

アロケータ

コンテナの変更

オブザーバー

検索

バケットインタフェース

ハッシュポリシー

メンバ型

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

非メンバ関数

比較演算子

入れ替え

要素削除

推論補助

例

#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

参照

• Unordered associative containers do not use allocator_traits to define member types （上記の pointer、const_pointer、reference、const_reference の問題に対する修正案）
• P0919R3 Heterogeneous lookup for unordered containers
• P3091R6 Better Lookups for map, unordered_map, and flat_map
  • C++29で、指定したキーを持つ要素をoptionalとして取得するlookup()メンバ関数が追加された