std::multiset

namespace std {
  template <class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
  class multiset;

  namespace pmr {
    template <class Key, class Compare = less<Key>>
      using multiset = std::multiset<Key, Compare,
                                     polymorphic_allocator<Key>>;  // C++17から
  }
}

概要

multiset は重複を許可する連想コンテナの一種であり、要素自身がキーとなる、集合を表すクラスである。

連想コンテナは特にそれらキーによる要素アクセスが効率的になるよう設計されたコンテナである（要素への相対位置または絶対位置によるアクセスが効率的であるシーケンシャルコンテナとは異なる）。

内部的には、multiset 内の要素は、コンテナの構築時に設定された狭義の弱順序基準に従って小さいものから大きいものへとソートされる。

setが重複キーを許可しないのに対し、multisetは重複キーを許可する。

setとは違い、find()メンバ関数は、キーに合致した最初の要素へのイテレータを返し、count()メンバ関数はキーに合致する要素数を返す。

このコンテナクラスは、双方向イテレータをサポートする。

テンプレートパラメータ

• Key: キーの型。このコンテナに格納されれる要素の型。multiset に格納される要素はそれぞれはキーでもある。
• Compare: 比較クラス。このクラスは 2 つの引数（同じ型であり、コンテナの要素型でもある）をとり bool 値を返す。狭義の弱順序において a が b よりも前の場所に位置づけられる場合に true である。これはクラスが関数呼び出しオブジェクトを実装したクラスであっても良いし関数ポインタであっても良い（例は コンストラクタ を参照）。これは、operator<() を適用( a < b )したときと同じ値を返す less<Key> がデフォルトである。
• Allocator: ストレージアロケーションモデルを決定づける、アロケータオブジェクトの型である。デフォルトでは、Key への allocator クラステンプレート（これは値に依存しないシンプルなメモリ確保モデルを定義する）が使われる。

メンバ関数

構築・破棄

イテレータ

領域

コンテナの変更

要素アクセス

オブザーバー

メンバ型

非メンバ関数

比較演算子

入れ替え

要素削除

推論補助

例

#include <iostream>
#include <set>

int main()
{
  // intをキーとして扱う集合
  std::multiset<int> s;

  // 挿入
  s.insert(3);
  s.insert(1);
  s.insert(4);
  s.insert(1); // キーを重複させることが可能

  // キー1に該当する要素数を取得する
  std::size_t count = s.count(1);

  // 検索 : キー(int)を指定し、対応する値を得る
  decltype(s)::iterator it = s.find(1);
  if (it != s.end()) {
    // 発見した
    // 同じキーの要素を全て列挙する
    for (std::size_t i = 0; i < count; ++i) {
      int value = *it;
      std::cout << value << std::endl;
      ++it;
    }
  }
  else {
    std::cout << "not found" << std::endl;
  }
}

出力

1
1