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

履歴 編集

class template
<unordered_set>

# std::unordered_multiset(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_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 を満たさなければならない。

## メンバ関数

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

名前 | 説明 | 対応バージョン
--- | --- | ---
`(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
`insert` | 要素の追加 | C++11
`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

### バケットインタフェース

名前 | 説明 | 対応バージョン
--- | --- | ---
`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` | 要素の型。テンプレートパラメータ `Key`。 | C++11
`hasher` | キーのハッシュ関数の型。テンプレートパラメータ `Hash`。 | C++11
`key_equal` | キーが等値か否かを判断するための二項述語の型。テンプレートパラメータ `Pred`。 | C++11
`allocator_type` | アロケータの型。テンプレートパラメータ `Allocator`。 | C++11
`pointer` | 要素 `value_type`（`= Key`） へのポインタ。スマートポインタも可であるが、通常は `value_type*`。 規格書では、`allocator_type::pointer` となっているが、これは規格書の誤りで、ドラフト N3376 で既に `std::allocator_traits<Allocator>::pointer` に修正されている。 （さもないと、必須である `allocator_type::value_type` のみを定義したユーザ定義のアロケータを使用することができないため） | C++11
`const_pointer` | 要素 `value_type`（`= Key`） へのコンストポインタ。スマートポインタも可であるが、通常は `const value_type*`。 規格書では、`allocator_type::const_pointer` となっているが、これは規格書の誤りで、ドラフト N3376 で既に `std::allocator_traits<Allocator>::const_pointer` に修正されている。 （さもないと、必須である `allocator_type::value_type` のみを定義したユーザ定義のアロケータを使用することができないため） | C++11
`reference` | 要素 `value_type`（`= Key`） への参照。 規格書では、`allocator_type::reference` となっているが、これは規格書の誤りで、ドラフト N3376 で既に `value_type&` に修正されている。 （さもないと、必須である `allocator_type::value_type` のみを定義したユーザ定義のアロケータを使用することができないため） | C++11
`const_reference` | 要素 `value_type`（`= Key`） へのコンスト参照。 規格書では、`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` | "読み取り専用"前方向イテレータ（誤植ではない） 規格書に記載はないが、（連想コンテナがそうであるように）`const_iterator` と同じ型か否かは実装依存であるものと思われる。 従って、ODR（One Definition Rule）に違反しないようにするため、関数のパラメータ型には常に `const_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

## 非メンバ関数

### 比較演算子

名前 | 説明 | 対応バージョン
--- | --- | ---
`operator==` | 等値比較 | C++11
`operator!=` | 非等値比較 | C++11

### 入れ替え

名前 | 説明 | 対応バージョン
--- | --- | ---
`swap` | 内容の交換 | C++11

### 要素削除

名前 | 説明 | 対応バージョン
--- | --- | ---
`erase_if` | 指定した条件に合致する要素とその分の領域を、コンテナから削除する | C++20

## 推論補助

名前 | 説明 | 対応バージョン
--- | --- | ---
`(deduction_guide)` | クラステンプレートの推論補助 | C++17

## 例

    #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