付録(unordered

unordered_set クラス^C++11

[機能]

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

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

template <class Key, class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Allocator = std::allocator<Key>>
    class unordered_set

[使用方法]

#include <unordered_set>
using namespace std;
unordered_set <Key> 変数名;
   unordered_set<int> x;   // 空の unordered_set，昇順
   unordered_set<int> x(it1, it2);   // it1 から it2 の範囲で初期化
   unordered_set<int> x(y);   // unordered_set y で初期化
   unordered_set<int> x ({2, 4, 1});   // 初期化子リスト
   unordered_set<int> x {2, 4, 1};   // 初期化子リスト
   unordered_set<int> x = {2, 4, 1};   // 初期化子リスト

[メンバー関数等]

iterator begin()
const_iterator begin()
最初の要素を指すイテレータを返す
const_iterator cbegin()
先頭要素を指す読み取り専用イテレータ
const_iterator cend()
末尾の1つ次の要素を指す読み取り専用イテレータ
void clear()
すべての要素を削除する
size_type count(const key_type &k)
unordered_set 内に存在する k の数を返す
template <class... Args> pair<iterator, bool> emplace(Args&&... args)
コンテナに新しい要素を直接構築し挿入する（コピーもムーブもされない）．iterator には新しく挿入された要素またはすでに格納されていた要素を指すイテレータが設定され，また，bool には，要素が挿入されたときに true，同じ値の存在のため挿入されなかった場合には false が設定される．
template <class... Args> iterator emplace_hint(const_iterator hint, Args&&... args)
要素が配置されるべき場所を示唆するパラメータ 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()
アロケータを返す
pair<iterator, bool> insert(const T& x)
iterator insert(iterator it, const T& x)
（イテレータ it が指す場所の前に）要素 x を挿入する．iterator には新しく挿入された要素またはすでに格納されていた要素を指すイテレータが設定され，また，bool には，要素が挿入されたときに true，同じ値の存在のため挿入されなかった場合には false が設定される．
template <class lnlter> void insert(lnlter start, lnlter end)
start と end で示されるシーケンスを挿入する
void insert(initializer_list<value_type> init)
初期化子リストを挿入する
size_type max_size()
格納できる最大の要素数を返す
template<class C2> void merge(unordered_set<Key, C2, Allocator>& m) // C++17
引数 m 内の各要素を調べ，等価なキーを持つ要素がない場合はその要素を挿入する（要素はコピーもムーブもされない）．
size_type size()
要素数を返す
void swap(unordered_set& s)
2 つのコンテナの内容を入れ替える

[演算子の多重定義]

=  ==  !=

[使用例]

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

#include <iostream>
#include <unordered_set>

using namespace std;

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

int main()
{
					// 初期設定
	cout << "**初期設定**\n";
	unordered_set<int> s1 = {1, 0, 4, 3, 2};
	print("s1", s1);
					// 2 番目の要素の前に要素を追加
	cout << "**2 番目の要素の前に要素を追加**\n";
	unordered_set<int>::iterator it = s1.begin();
	it++;
	s1.insert(it, 5);
	print("s1", s1);
					// 3 番目の要素，及び，要素 4 を削除
	cout << "**3 番目の要素，及び，要素 4 を削除**\n";
	it = s1.begin();
	it++;
	it++;
	s1.erase(it);
	s1.erase(4);
	print("s1", s1);
					// 要素 3 の位置
	cout << "**要素 3 の位置**\n";
	it = s1.find(3);
	printf("  検索： %d\n", *it);
					// 交換
	cout << "**交換**\n";
	unordered_set<int> s2;
	cout << "入れ替え前:\n";
	print("s1", s1);
	print("s2", s2);
	s1.swap(s2);
	cout << "入れ替え後:\n";
	print("s1", s1);
	print("s2", s2);
					// 演算子で比較
	cout << "**比較**\n";
	s1.insert(5);
	s1.insert(1);
	s1.insert(3);
	s1.insert(2);
	print("s1", s1);
	if (s1 == s2)
		cout << "  2 つのコンテナ内の要素はすべて等しい\n";
					// s1 のすべての要素を削除
	cout << "**s1 のすべての要素を削除**\n";
	s1.clear();
	print("s1", s1);

	return 0;
}

（出力）

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

[参照]

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

unordered_set クラスC++11

unordered_set クラス^C++11