std::unordered_set(C++11)

namespace std {
  template <class Key,
            class Hash = std::hash<Key>,
            class Pred = std::equal_to<Key>,
            class Allocator = std::allocator<Key> >
  class unordered_set;

  namespace pmr {
    template <class Key,
              class Hash = hash<Key>,
              class Pred = equal_to<Key>>
      using unordered_set = std::unordered_set<Key, Hash, Pred,
                                               polymorphic_allocator<Key>>;  // C++17から
  }
}

概要

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

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

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

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

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

• 関数オブジェクト型である。
• CopyConstructible requirements と Destructible requirements の要件を満たす。
• h を Hash 型のオブジェクト、Key を Hash 型のオブジェクトの引数の型、u を Key 型の lvalue、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_set>
#include <iterator>
#include <algorithm>
#include <string>

template <class C>
void print(const C& c, std::ostream& os = std::cout)
{
  std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, ", "));
  os << std::endl;
}

int main()
{
  std::unordered_set<std::string> us{ "1st element", "2nd element", "3rd element", };

  print(us);

  us.emplace("4th element");

  print(us);

  us.erase("2nd element");

  print(us);
}

出力例

3rd element, 2nd element, 1st element, 
4th element, 3rd element, 2nd element, 1st element, 
4th element, 3rd element, 1st element, 

バージョン

言語

• 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