Skip to content

Latest commit

 

History

History
284 lines (208 loc) · 16.9 KB

unordered_map.md

File metadata and controls

284 lines (208 loc) · 16.9 KB
Raw

unordered_map

  • unordered_map[meta header]
  • std[meta namespace]
  • class template[meta id-type]
  • cpp11[meta cpp]
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から

  }
}
  • std::hash[link /reference/functional/hash.md]
  • std::equal_to[link /reference/functional/equal_to.md]
  • polymorphic_allocator[link /reference/memory_resource/polymorphic_allocator.md]

概要

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
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);
}
  • std::unordered_map[color ff0000]
  • std::ostream[link /reference/ostream/basic_ostream.md]
  • um.at[link unordered_map/at.md]
  • um.emplace[link unordered_map/emplace.md]
  • um.erase[link unordered_map/erase.md]
  • um["5th"][link unordered_map/op_at.md]

出力

{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

参照