multiset クラス

[機能]

　　同じ値を持つ要素許す set です．一般的に，二分木として実装されます．Comp に対しては，比較を行う二項関数オブジェクト名を指定します．指定しないと less （昇順）が選択されます．なお，以下に示す関数において，一般に，insert よりも，emplace を使ったほうが処理効率は良くなります．

template <class Key, class Comp = less<Key>,
class Allocator = allocator<Key>>
    class multiset		

[使用方法]

#include <set>
using namespace std;
multiset <Key> 変数名;
   multiset<int> x;   // 空の multiset，昇順
   multiset<int, greater<int>> y;   // 空の multiset，降順
   multiset<int> x(it1, it2);   // it1 から it2 の範囲で初期化
   multiset<int> x(y);   // multiset y で初期化
   multiset<int> x ({5, 4, 3, 3, 1});   // 初期化子リスト，C++11
   multiset<int> x {5, 4, 3, 3, 1};   // 初期化子リスト，C++11
   multiset<int> x = {5, 4, 3, 3, 1};   // 初期化子リスト，C++11		

[メンバー関数等]

• iterator begin()
• const_iterator begin()
  最初の要素を指すイテレータを返す

• const_iterator cbegin() // C++11
  先頭要素を指す読み取り専用イテレータ

• const_iterator cend() // C++11
  末尾の1つ次の要素を指す読み取り専用イテレータ

• void clear()
  すべての要素を削除する

• size_type count(const key_type &k)
  multiset 内に存在する k の数を返す

• const_iterator crbegin() // C++11
  末尾の要素を指す読み取り専用逆イテレータ

• const_iterator crend() // C++11
  先頭の1つ前の要素を指す読み取り専用逆イテレータ

• template <class... Args> iterator emplace(Args&&... args) // C++11
  コンテナに新しい要素を直接構築し挿入する（コピーもムーブもされない）．また，以下の 2 行目に示すように，ペアーを自動的に生成するような処理も可能である（ insert との違いに注意）．

  	multiset<pair<int, double>> st{{4, 1.3}, {4, 1.3}, {1, 10.3}};
  	st.emplace(2, 3.14);
  	st.emplace(make_pair(0, 3.5));
  	st.insert(make_pair(0, 3.5));
  	for (auto x : st)
  		cout << " (" << x.first << ", " << x.second <<")";
  	cout << endl;			

• template <class... Args> iterator emplace_hint(const_iterator hint, Args&&... args) // C++11
  要素が配置されるべき場所を示唆するパラメータ hint を使って（例えば，マップの先頭に挿入される可能性が高い場合は，begin() などを指定する），コンテナに新しい要素を直接構築して挿入する（コピーもムーブもされない）．

• bool empty()
  コンテナが空か否かを返す

• iterator end()
• const_iterator end()
  最後の要素の次を指すイテレータを返す

• pair<iterator, iterator> equal_range(const key_type &k)
  指定されたキーに対応する範囲の上限と下限（ iterator の first と second ）を返す

• void erase(iterator it)
  イテレータ it が指す場所の要素を削除する

• void erase(iterator start, iterator end)
  start から end までの要素を削除する

• size_type erase(const key_type &k)
  キーの値が k である要素を削除し，削除された要素の数を返す

• iterator find(const key_type& x)
  キーの値が x である位置に対応するイテレータを返す

• allocate_type get_allocator()
  アロケータを返す

• iterator insert(const T& x)
• iterator insert(iterator it, const T& x)
  （イテレータ it が指す場所の前に）要素 x を挿入する．

• template <class lnlter> void insert(lnlter start, lnlter end)
  start と end で示されるシーケンスを挿入する

• void insert(initializer_list<value_type> init) // C++11
  初期化子リストを挿入する

• iterator lower_bound(const key_type& x)
  キーの値が x 以上である最初の要素に対応するイテレータを返す

• template<class C2> void merge(multiset<Key, C2, Allocator>& m) // C++17
  引数 m 内の各要素を調べ，等価なキーを持つ要素がない場合はその要素を挿入する（要素はコピーもムーブもされない）．

• size_type max_size()
  格納できる最大の要素数を返す

• reverse_iterator rbegin()
• const_reverse_iterator rbegin()
  最後の要素を指す逆イテレータを返す

• reverse_iterator rend()
• const_reverse_iterator rend()
  最初の要素の 1 つ前を指す逆イテレータを返す

• size_type size()
  要素数を返す

• void swap(multiset<T, Allocator> &s)
  2 つのコンテナの内容を入れ替える

• iterator upper_bound(const key_type& x)
  キーの値が x より大きい最初の要素に対応するイテレータを返す

[演算子の多重定義]

=  ==  <  <=  !=  >  >=		

[使用例]

1. multiset の使用方法です．以下に示すプログラム例において，いくつかのコメント部分は，その上または下に記述された方法とほぼ同等なものであることを示しています（複数行の対応関係である場合もある）．

   #include <iostream>
   #include <set>
   
   using namespace std;
   
   void print(string str, multiset<int> &s) {
   	if (s.empty())
   		cout << "  コンテナ " << str << " は空です\n";
   	else {
   		cout << str << " の要素数： " << s.size() << endl;
   		for (auto x : s)
   			cout << "  " << x;
   //		multiset<int>::iterator it;
   //		for (it = s.begin(); it != s.end(); it++)
   //			cout << "  " << *it;
   		cout << endl;
   	}
   }
   int main()
   {
   					// 要素を追加（サイズは自動的に増加）
   	printf("**初期設定**\n");
   	multiset<int> s1 = {2, 0, 0, 0, 2};
   	print("s1", s1);
   					// 2 番目の要素の前に要素を追加
   	printf("**2 番目の要素の前に要素を追加**\n");
   	multiset<int>::iterator it = s1.begin();
   	it++;
   	s1.insert(it, 5);
   	print("s1", s1);
   					// 3 番目の要素，及び，要素 2 を削除
   	printf("**3 番目の要素，及び，要素 2 を削除**\n");
   	it = s1.begin();
   	it++;
   	it++;
   	s1.erase(it);
   	s1.erase(2);
   	print("s1", s1);
   					// 要素 0 の位置
   	printf("**要素 0 の位置**\n");
   	int n = s1.count(0);
   	printf("0 の検索： 数 = %d\n", n);
   	for (it = s1.lower_bound(0); it != s1.upper_bound(0); it++)
   		printf("  %d", *it);
   	printf("\n");
   					// 交換
   	printf("**交換**\n");
   	multiset<int> s2;
   	print("入れ替え前:s1", s1);
   	print("入れ替え前:s2", s2);
   	s1.swap(s2);
   	print("s1", s1);
   	print("s2", s2);
   					// 演算子で比較
   	printf("**比較**\n");
   	s1.insert(0);
   	s1.insert(5);
   	s1.insert(0);
   	print("s1", s1);
   	if (s1 == s2)
   		printf("  2 つのコンテナ内の要素はすべて等しい\n");
   					// すべての要素を削除
   	printf("**s1 のすべての要素を削除**\n");
   	s1.clear();
   	print("s1", s1);
   
   	return 0;
   }
   			

   （出力）

   **初期設定**
   s1 の要素数： 5
     0  0  0  2  2
   **2 番目の要素の前に要素を追加**
   s1 の要素数： 6
     0  0  0  2  2  5
   **3 番目の要素，及び，要素 2 を削除**
   s1 の要素数： 3
     0  0  5
   **要素 0 の位置**
   0 の検索： 数 = 2
     0  0
   **交換**
   入れ替え前:s1 の要素数： 3
     0  0  5
     コンテナ 入れ替え前:s2 は空です
     コンテナ s1 は空です
   s2 の要素数： 3
     0  0  5
   **比較**
   s1 の要素数： 3
     0  0  5
     2 つのコンテナ内の要素はすべて等しい
   **s1 のすべての要素を削除**
     コンテナ s1 は空です
   			

   multiset の使用方法です．クラス Test における 2 つの整数値の和が大きい順に並べ替えています．以下に示すプログラム例において，いくつかのコメント部分は，その上または下に記述された方法とほぼ同等なものであることを示しています（複数行の対応関係である場合もある）．また，コメントとして記述してあるように，比較演算子のオーバーロード（多重定義）を行えば，二項関数オブジェクトを定義しなくても構いません．

   #include <iostream>
   #include <set>
   #include <string>
   
   using namespace std;
   
   class Test {
   	public:
   		string str;
   		int n1, n2;
   		Test (string str1, int m1, int m2) {
   			str = str1;
   			n1  = m1;
   			n2  = m2;
   		}
   };
   					// 二項関数オブジェクト
   class GT
   {
   	public:
   		bool operator() (Test t1, Test t2) const
   		{
   			if (t1.n1+t1.n2 == t2.n1+t2.n2)
   				return (t1.str > t2.str) ? true : false;
   			else
   				return (t1.n1+t1.n2 > t2.n1+t2.n2) ? true : false;
   		}
   };
   					// < 演算子のオーバーロード
   //bool operator< (Test t1, Test t2)
   //{
   //	if (t1.n1+t1.n2 == t2.n1+t2.n2)
   ///		return (t1.str > t2.str) ? true : false;
   //	else
   //		return (t1.n1+t1.n2 > t2.n1+t2.n2) ? true : false;
   //}
   
   int main()
   {
   	Test t0("abc", 20, 30), t1("abc", 20, 30), t2("xyz", 30, 10), t3("ghq", 40, 50), t4("yyy", 30, 10), t5("xyz", 20, 20);
   					// 二項関数オブジェクトを利用する場合
   	multiset<Test, GT> s1 = {t0, t1, t2, t3}, s2;
   					// < 演算子のオーバーロードを利用する場合
   //	multiset<Test> s1 = {t0, t1, t2, t3}, s2;
   					// 初期設定
   	s2.insert(t4);
   //	s2.insert("yyy", 30, 10);   // error
   //	s2.insert({"yyy", 30, 10});   // ok
   	s2.insert(t5);
   //	s2.emplace("xyz", 20, 20);   // ok
   //	s2.emplace({"xyz", 20, 20});   // error
   	cout << "**s1**\n";
   	for (auto x : s1)
   		cout << "  " << x.str << " " << x.n1 << " " << x.n2 << endl;
   	cout << "**s2**\n";
   	for (auto x : s2)
   		cout << "  " << x.str << " " << x.n1 << " " << x.n2 << endl;
   					// merge
   	s1.merge(s2);
   	cout << "**s1 merge後**\n";
   	for (auto x : s1)
   		cout << "  " << x.str << " " << x.n1 << " " << x.n2 << endl;
   	cout << "**s2 merge後**\n";
   	for (auto x : s2)
   		cout << "  " << x.str << " " << x.n1 << " " << x.n2 << endl;
   
   	return 0;
   }
   			

   （出力）

   **s1**
     ghq 40 50
     abc 20 30
     abc 20 30
     xyz 30 10
   **s2**
     yyy 30 10
     xyz 20 20
   **s1 merge後**
     ghq 40 50
     abc 20 30
     abc 20 30
     yyy 30 10
     xyz 30 10
     xyz 20 20
   **s2 merge後**
   			

[参照]

vector， map， multimap， array， forward_list， list， set， priority_queue， queue， stack， deque， unordered_map， unordered_multimap， unordered_set， unordered_multiset