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

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

概要

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

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

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

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

テンプレートパラメータ 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 を満たさなければならない。

概念・前提知識

• コンテナとは

メンバ関数

構築／コピー／破棄

領域

イテレータ

アロケータ

コンテナの変更

オブザーバー

検索

バケットインタフェース

ハッシュポリシー

メンバ型

非メンバ関数

比較演算子

入れ替え

要素削除

推論補助

例

#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_multiset<std::string> ums{ "1st element", "2nd element", "3rd element", };

  print(ums);

  ums.insert({"2nd element", "4th element"});

  print(ums);

  ums.erase("2nd element");

  print(ums);
}

出力例

3rd element, 1st element, 2nd element, 
4th element, 3rd element, 1st element, 2nd element, 2nd 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