付録(unordered

unordered_multimap クラス^C++11

[機能]

　　標準の配列や vector と異なり，コンテナ内の要素へのアクセスは絶対的な位置（添え字）によるのではなくキーによります．コンテナ内の各要素は，キーのハッシュ値に基づきハッシュテーブルに格納されるため，決められた順序で並んでいるわけではありません．キーとそれに対応する値がペアとなった要素を持ち，かつ，同一のキー値を格納することができます．

　　ハッシュ法において，データが格納される配列のことをハッシュ表（ハッシュテーブル）と呼び，ハッシュ表の各要素をバケットと呼びます．unordered_map クラスには，ハッシュ表やバケットに関する情報を得るための関数も存在しますが，ここでは省略します．また，以下に示す関数において，一般に，insert よりも，emplace を使ったほうが処理効率は良くなります．

template <class Key, class T, class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Allocator = allocator<pair<const Key, T>>>
    class unordered_multimap;

[使用方法]

#include <unordered_map>
using namespace std;
unordered_multimap <Key, T> 変数名;
   unordered_multimap<int, string> x;   // 空の unordered_map，昇順
   unordered_multimap<int, string> x(it1, it2);   // it1 から it2 の範囲で初期化
   unordered_multimap<int, string> x(y);   // unordered_map y で初期化
   unordered_multimap<int, string> x ({{3, "abc"}, {2, "xyz"}, {2, "efg"}});   // 初期化子リスト
   unordered_multimap<int, string> x {{3, "abc"}, {2, "xyz"}, {2, "efg"}};   // 初期化子リスト
   unordered_multimap<int, string> x = {{3, "abc"}, {2, "xyz"}, {2, "efg"}};   // 初期化子リスト

[メンバー関数等]

iterator begin()
最初の要素を指すイテレータを返す
const_iterator cbegin()
先頭要素を指す読み取り専用イテレータ
const_iterator cend()
末尾の1つ次の要素を指す読み取り専用イテレータ
void clear()
すべての要素を削除する
size_type count(const key_type& x)
キー x を検索し，コンテナ内に見つかった要素の数を返す
template <class... Args> pair<iterator, bool> emplace(Args&&... args)
コンテナに新しい要素を直接構築し挿入する（コピーもムーブもされない）．iterator には新しく挿入された要素またはすでに格納されていた要素を指すイテレータが設定され，また，bool には，要素が挿入されたときに true，同じ値の存在のため挿入されなかった場合には false が設定される．また，以下の 2 行目に示すように，ペアーを自動的に生成するような処理も可能である（ insert との違いに注意）．
```
	unordered_multimap<int, string> mp {{1, "abc"}, {3, "efg"}, {1, "xyz"}};
	mp.emplace(3, "xxx");
	mp.emplace(make_pair(3, "yyy"));
//	mp.insert(2, "xyz");   // error
	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)
要素が配置されるべき場所を示唆するパラメータ hint を使って（例えば，マップの先頭に挿入される可能性が高い場合は，begin() などを指定する），コンテナに新しい要素を直接構築して挿入する（コピーもムーブもされない）．
bool empty()
コンテナが空か否かを返す
iterator end()
最後の要素の次を指すイテレータを返す
pair<iterator, iterator> equal_range(const key_type &k)
指定されたキーに対応する範囲の上限と下限（ iterator の first と second ）を返す
iterator erase(const_iterator it)
イテレータ it が指す場所の要素を削除し，次の要素に対するイテレータを返す．
iterator erase(const_iterator start, const_iterator end)
start から end までの要素を削除し，次の要素に対するイテレータを返す．
size_type erase(const key_type &k)
キーの値が k である要素を削除し，削除された要素の数を返す
iterator find(const key_type& x)
キーが x に等しい要素に対応するイテレータを返す
allocate_type get_allocator()
アロケータを返す
pair<iterator, bool> insert(const value_type& x)
iterator insert(const_iterator it, const value_type& x)
（イテレータ it が指す場所の前に） pair 型オブジェクトである要素 x を挿入する．iterator には新しく挿入された要素またはすでに格納されていた要素を指すイテレータが設定され，また，bool には，要素が挿入されたときに true，同じ値の存在のため挿入されなかった場合には false が設定される．
template <class InputIterator> void insert(InputIterator first, InputIterator last)
範囲 [first, last) を挿入する
void insert(initializer_list<value_type> init)
初期化子リストを挿入する
size_type max_size()
格納できる最大の要素数を返す
template<lass H2, class P2> void merge(unordered_multimap& m) // C++17
引数 m 内の各要素を調べ，等価なキーを持つ要素がない場合はその要素を挿入する（要素はコピーもムーブもされない）．
size_type size()
要素数を返す
void swap(unordered_multimap& m)
2 つのコンテナの内容を入れ替える

[演算子の多重定義]

=  ==  !=

[使用例]

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

#include <iostream>
#include <unordered_map>

using namespace std;
using itr = unordered_multimap<string, int>::iterator;

void print(string str, unordered_multimap<string, int> &m) {
	if (m.empty())
		cout << "  コンテナ " << str << " は空です\n";
	else {
		cout << str << " の要素数： " << m.size() << endl;
		for (auto x : m)
			cout << "  " << x.first << " " << x.second;
//		unordered_multimap<string, int>::iterator it;
//		for (it = m.begin(); it != m.end(); it++)
//			cout << "  " << (*it).first << " " << (*it).second;
		cout << endl;
	}
}

int main()
{
					// 要素を追加，キーが string，値が int
	cout << "**初期設定**\n";
	unordered_multimap<string, int> m1;   
	m1.insert(pair<string, int>("suzuki", 40));
	m1.insert(pair<string, int>("sato", 60));
	m1.insert(pair<string, int>("suzuki", 70));
	m1.insert(pair<string, int>("suzuki", 50));
	m1.insert(pair<string, int>("kato", 90));
	print("m1", m1);
					// 2 番目の要素の前に要素を追加
	cout << "**2 番目の要素の前に要素を追加**\n";
	unordered_multimap<string, int>::iterator it = m1.begin();
	it++;
	m1.insert(it, pair<string, int>("naito", 20));
	print("m1", m1);
					// 2 番目の要素，及び，要素 naito を削除
	cout << "**2 番目の要素，及び，要素 tanaka を削除**\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;   // 最初のデータ
	pair<itr, itr> x = m1.equal_range("suzuki");
	for (it = x.first; it != x.second; it++)
		cout << " (" << (*it).first << ", " << (*it).second << ")";
	cout << endl;
					// 演算子で比較
	cout << "**比較**\n";
	unordered_multimap<string, int> m2 = {{"naito", 20}, {"suzuki", 50},
	                                      {"suzuki", 70}, {"suzuki", 40}};
	print("m2", m2);
	if (m1 == m2)
		cout << "  2 つのコンテナ内の要素はすべて等しい\n";
					// 要素 suzuki を削除
	m1.erase("suzuki");
	print("m1", m1);
					// 交換
	cout << "**交換**\n";
	print("入れ替え前:m1", m1);
	print("入れ替え前:m2", m2);
	m1.swap(m2);
	print("m1", m1);
	print("m2", m2);
					// m1 のすべての要素を削除
	cout << "**m1 のすべての要素を削除**\n";
	m1.clear();
	print("m1", m1);

	return 0;
}

（出力）

**初期設定**
m1 の要素数： 5
  kato 90  suzuki 50  suzuki 70  suzuki 40  sato 60
**2 番目の要素の前に要素を追加**
m1 の要素数： 6
  naito 20  sato 60  suzuki 50  suzuki 70  suzuki 40  kato 90
**2 番目の要素，及び，要素 tanaka を削除**
m1 の要素数： 4
  naito 20  suzuki 50  suzuki 70  suzuki 40
**キー suzuki の値**
  値： 50
 (suzuki, 50) (suzuki, 70) (suzuki, 40)
**比較**
m2 の要素数： 4
  suzuki 40  suzuki 70  suzuki 50  naito 20
  2 つのコンテナ内の要素はすべて等しい
m1 の要素数： 1
  naito 20
**交換**
入れ替え前:m1 の要素数： 1
  naito 20
入れ替え前:m2 の要素数： 4
  suzuki 40  suzuki 70  suzuki 50  naito 20
m1 の要素数： 4
  suzuki 40  suzuki 70  suzuki 50  naito 20
m2 の要素数： 1
  naito 20
**m1 のすべての要素を削除**
  コンテナ m1 は空です

[参照]

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

unordered_multimap クラスC++11

unordered_multimap クラス^C++11