最終更新日時(UTC): 2026年02月11日 05時29分19秒
yoh が更新

履歴 編集

class template
<unordered_map>

# std::unordered_map(C++11)

    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 を満たさなければならない。

## メンバ関数

### 構築／コピー／破棄

名前 | 説明 | 対応バージョン
--- | --- | ---
`(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_category`、`value_type`、`difference_type`、`pointer`、`reference` は同一である。 | C++11
`const_local_iterator` | 同一バケット内のみで有効な読み取り専用イテレータ。 `const_iterator` と、`iterator_category`、`value_type`、`difference_type`、`pointer`、`reference` は同一である。 | 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

## 参照

- Unordered associative containers do not use allocator_traits to define member types （上記の `pointer`、`const_pointer`、`reference`、`const_reference` の問題に対する修正案）
- P0919R3 Heterogeneous lookup for unordered containers