multimap クラス

[機能]

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

template <class Key, class T, class Comp = less<Key>,
class Allocator = allocator<Key>>
    class multimap		

[使用方法]

#include <map>
using namespace std;
multimap <Key, T, Comp> 変数名;
   multimap<int, string> x;   // 空の multimap，昇順
   multimap<int, string, greater<int>> x;   // 空の multimap，降順
   multimap<int, string> x(it1, it2);   // it1 から it2 の範囲で初期化
   multimap<int, string> x(y);   // multimap y で初期化
   multimap<int, string> x ({{1, "abc"}, {2, "efg"}});   // 初期化子リスト，C++11
   multimap<int, string> x {{1, "abc"}, {2, "efg"}};   // 初期化子リスト，C++11
   multimap<int, string> x = {{1, "abc"}, {2, "efg"}};   // 初期化子リスト，C++11		

[メンバー関数等]

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

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

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

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

• size_type count(const key_type& x)
  キー x を検索し，コンテナ内に見つかった要素の数を返す

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

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

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

  	multimap<int, string> mp {{1, "abc"}, {3, "efg"}};
  	mp.emplace(0, "xxx");
  	mp.emplace(make_pair(3, "yyy"));
  	mp.insert(make_pair(2, "xyz"));
  	for (auto x : mp)
  		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()
  最後の要素の次を指すイテレータを返す

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

• void erase(iterator it)
• iterator erase(const_iterator it) // C++11
  イテレータ it が指す場所の要素を削除し，次の要素に対するイテレータを返す．

• void erase(iterator start, iterator end)
• iterator erase(const_iterator start, const_iterator end) // C++11
  start から end までの要素を削除し，次の要素に対するイテレータを返す．

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

• iterator find(const key_type& x)
  キーが x に等しい要素に対応するイテレータを返す

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

• iterator insert(const value_type& x)
• iterator insert(const_iterator it, const value_type& x)
  （イテレータ it が指す場所の前に） pair 型オブジェクトである要素 x を挿入する

• template <class InputIterator> void insert(InputIterator first, InputIterator last)
  範囲 [first, last) を挿入する

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

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

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

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

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

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

• size_type size()
  要素数を返す

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

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

[演算子の多重定義]

=  ==  <  <=  !=  >  >=		

[使用例]

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

   #include <iostream>
   #include <map>
   
   using namespace std;
   
   void print(string str, multimap<string, int, greater<string> > &m) {
   	if (m.empty())
   		cout << "  コンテナ " << str << " は空です\n";
   	else {
   		cout << str << " の要素数： " << m.size() << endl;
   		for (auto x : m)
   			cout << "  " << x.first << " " << x.second;
   //		multimap<string, int, greater<string> >::iterator it;
   //		for (it = m.begin(); it != m.end(); it++)
   //			cout << "  " << (*it).first << " " << (*it).second;
   		cout << endl;
   	}
   }
   
   int main()
   {
   					// 要素を追加（サイズは自動的に増加）
   	cout << "**初期設定**\n";
   	multimap<string, int, greater<string>> m1;   // キーが string，値が int，二項関数オブジェクト greater
   	m1.insert(pair<string, int>("kato", 80));
   	m1.insert(pair<string, int>("sato", 50));
   	m1.insert(pair<string, int>("sato", 30));
   	m1.insert(pair<string, int>("sato", 70));
   	m1.insert(pair<string, int>("kato", 90));
   	print("m1", m1);
   					// 2 番目の要素の前に要素を追加
   	cout << "**2 番目の要素の前に要素を追加**\n";
   	multimap<string, int, greater<string> >::iterator it = m1.begin();
   	it++;
   	m1.insert(it, pair<string, int>("suzuki", 20));
   	print("m1", m1);
   					// 2 番目の要素，及び，要素 kato を削除
   	cout << "**2 番目の要素，及び，要素 kato を削除**\n";
   	it = m1.begin();
   	it++;
   	m1.erase(it);
   	m1.erase("kato");
   	print("m1", m1);
   					// キー suzuki の値
   	cout << "**キー suzuki の値**\n";
   	it = m1.find("suzuki");
   	cout << "検索： " << it->second << endl;
   					// キー sato の要素
   	cout << "**キー sato の要素**\n";
   	int n = m1.count("sato");
   	cout <<"  sato の検索： 数 = " << n << endl;
   	for (it = m1.lower_bound("sato"); it != m1.upper_bound("sato"); it++)
   		cout << "  " << (*it).first << " " << (*it).second;
   	cout << endl;
   					// 交換
   	cout << "**交換**\n";
   	multimap<string, int, greater<string>> m2 = {{"aoki", 30}, {"yamada", 0}};
   	print("入れ替え前:m1", m1);
   	print("入れ替え前:m2", m2);
   	m1.swap(m2);
   	print("m1", m1);
   	print("m2", m2);
   					// 演算子で比較
   	cout << "**比較++\n";
   	m1.emplace("suzuki", 20);
   	m1.emplace("sato", 30);
   	m1.emplace("sato", 70);
   	m2.emplace("yamada", 0);
   	m2.emplace("aoki", 30);
   	print("m1", m1);
   	print("m2", m2);
   	if (m1 == m2)
   		cout << "  2 つのコンテナ内の要素はすべて等しい\n";
   					// m1 のすべての要素を削除
   	cout << "**m1 のすべての要素を削除**\n";
   	m1.clear();
   	print("m1", m1);
   
   	return 0;
   }
   			

   （出力）

   **初期設定**
   m1 の要素数： 5
     sato 50  sato 30  sato 70  kato 80  kato 90
   **2 番目の要素の前に要素を追加**
   m1 の要素数： 6
     suzuki 20  sato 50  sato 30  sato 70  kato 80  kato 90
   **2 番目の要素，及び，要素 kato を削除**
   m1 の要素数： 3
     suzuki 20  sato 30  sato 70
   **キー suzuki の値**
   検索： 20
   **キー sato の要素**
     sato の検索： 数 = 2
     sato 30  sato 70
   **交換**
   入れ替え前:m1 の要素数： 3
     suzuki 20  sato 30  sato 70
   入れ替え前:m2 の要素数： 2
     yamada 0  aoki 30
   m1 の要素数： 2
     yamada 0  aoki 30
   m2 の要素数： 3
     suzuki 20  sato 30  sato 70
   **比較++
   m1 の要素数： 5
     yamada 0  suzuki 20  sato 30  sato 70  aoki 30
   m2 の要素数： 5
     yamada 0  suzuki 20  sato 30  sato 70  aoki 30
     2 つのコンテナ内の要素はすべて等しい
   **m1 のすべての要素を削除**
     コンテナ m1 は空です
   			

   multimap の使用方法です．クラス Test における整数値の和が大きい順にソートしています．コメントとして記述してあるように，比較演算子のオーバーロード（多重定義）を行えば，二項関数オブジェクトを定義しなくても構いません．

   #include <iostream>
   #include <map>
   #include <string>
   
   using namespace std;
   
   class Test {
   	public:
   		int n1, n2;
   		Test (int m1, int m2) {
   			n1 = m1;
   			n2 = m2;
   		}
   };
   					// 二項関数オブジェクト
   class GT
   {
   	public:
   		bool operator() (Test t1, Test t2) const
   		{
   			return (t1.n1+t1.n2 > t2.n1+t2.n2) ? true : false;
   		}
   };
   					// < 演算子のオーバーロード
   //bool operator< (Test t1, Test t2)
   //{
   //	return (t1.n1+t1.n2 > t2.n1+t2.n2) ? true : false;
   //}
   
   int main()
   {
   	Test t1(20, 30), t2(30, 10), t3(40, 50), t4(30, 10), t5(30, 40);
   					// 二項関数オブジェクトを利用する場合
   	multimap<Test, string, GT> s1 = {{t1, "abc"}, {t2, "kkk"}, {t2, "kkk"}, {t3, "xyz"}}, s2;
   					// < 演算子のオーバーロードを利用する場合
   //	multimap<Test, string> s1 = {{t1, "abc"}, {t2, "kkk"}, {t2, "kkk"}, {t3, "xyz"}}, s2;
   
   	cout << "**s1**\n";
   	for (auto x : s1)
   		cout << "   (" << (x.first).n1 << ", " << (x.first).n2 << ") " << x.second << endl;
   					// merge
   	s2 = {{t4, "xxx"}, {t5, "yyy"}};
   	cout << "**s2**\n";
   	for (auto x : s2)
   		cout << "   (" << (x.first).n1 << ", " << (x.first).n2 << ") " << x.second << endl;
   	s1.merge(s2);
   	cout << "**after merge s1**\n";
   	if (s1.empty())
   		cout << "   s1 は空です\n";
   	else {
   		for (auto x : s1)
   			cout << "   (" << (x.first).n1 << ", " << (x.first).n2 << ") " << x.second << endl;
   	}
   	cout << "**after merge s2**\n";
   	if (s2.empty())
   		cout << "   s2 は空です\n";
   	else {
   		for (auto x : s2)
   			cout << "   (" << (x.first).n1 << ", " << (x.first).n2 << ") " << x.second << endl;
   	}
   
   	return 0;
   }
   			

   （出力）

   **s1**
      (40, 50) xyz
      (20, 30) abc
      (30, 10) kkk
      (30, 10) kkk
   **s2**
      (30, 40) yyy
      (30, 10) xxx
   **after merge s1**
      (40, 50) xyz
      (30, 40) yyy
      (20, 30) abc
      (30, 10) kkk
      (30, 10) kkk
      (30, 10) xxx
   **after merge s2**
      s2 は空です
   			

[参照]

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