C++11講座12回

第12回は新しいset、mapについてです。

C++のSTLには<set>、<map>の２つのコンテナがあります。

 1: #include <map>
 2: #include <set>
 3: #include <iostream>
 4:
 5: using namespace std;
 6: 
 7: int main()
 8: {
 9:	map<int, const char*> m{ { 5, "hoge" }, { 1, "hogehoge" }, { 10, "hogehogehoge" } };
10:	set<int> s{300, 100, 200};
11:
12:	//mapの要素表示
13:	for (const auto& i : m)
14:	{
15:		cout << i.first << ":" << i.second << endl;
16:	}
17:
18:	//setの要素表示
19:	for (const auto& i : s)
20:	{
21:		cout << i << endl;;
22:	}
23:
24:	return 0;
25: }

この2つのコンテナは要素を自動的（条件定義可能）にソートします。(mapはキー、setは要素でソート)
しかし、自動的にソートするため大量の値を扱う時に遅い問題があります。
C++11ではハッシュによる格納を行う<unordered_set><unordered_map>が登場しました。

 1: #include <unordered_map>
 2: #include <unordered_set>
 3: #include <iostream>
 4:
 5: using namespace std;
 6:
 7: int main()
 8: {
 9:	unordered_map<int, const char*> m{ { 5, "hoge" }, { 1, "hogehoge" }, { 10, "hogehogehoge" } };
10:	unordered_set<int> s{300, 100, 200};
11:
12:	//mapの要素表示
13:	for (const auto& i : m)
14:	{
15:		cout << i.first << ":" << i.second << endl;
16:	}
17:
18:	//setの要素表示
19:	for (const auto& i : s)
20:	{
21:		cout << i << endl;;
22:	}
23:
24:	return 0;
25: }

型名が違うだけで、基本的にはほとんど従来のmap、setと同じように扱うことが出来ます。
違いとして基本的にunordered_set、unordered_mapのほうが、自動ソート無し+ハッシュを利用しており速いということらしいです。
計測用プログラム

 1: #include <unordered_set>
 2: #include <set>
 3: #include <array>
 4: #include <algorithm>
 5: #include <random>
 6: #include <chrono>
 7: #include <iostream>
 8:
 9: using namespace std;
10:
11: static const int N = 100000;//データ数
12:
13: int main()
14: {
15:	array<int, N> arr;
16:
17:	random_device rd;
18:	mt19937 mt(rd());
19:
20:	set<int> s;
21:	unordered_set<int> us;
22:
23:	//あらかじめ追加する要素を作成しておく
24:	generate(arr.begin(), arr.end(), [&mt](){return mt(); });
25:
26:	cout << "要素追加" << endl;
27:	//setの要素追加の計測
28:	auto s_start = chrono::system_clock::now();
29:	for_each(arr.cbegin(), arr.cend(), [&s](const int i){s.insert(i);});
30:	auto s_end = chrono::system_clock::now();
31:
32:	cout << "set = " << chrono::duration_cast<chrono::milliseconds>(s_end - s_start).count() << "[ms] " << endl;
33:
34:	//unordered_setの要素追加の計測
35:	auto us_start = chrono::system_clock::now();
36:	for_each(arr.cbegin(), arr.cend(), [&us](const int i){us.insert(i);});
37:	auto us_end = chrono::system_clock::now();
38:
39:	cout << "unordered_set = " << chrono::duration_cast<chrono::milliseconds>(us_end - us_start).count() << "[ms]" << endl;
40:
41:	cout << endl;
42:	
43:	cout << "走査" << endl;
44:	//setの走査の計測
45:	int sum = 0;
46:	s_start = chrono::system_clock::now();
47:	for_each(s.cbegin(), s.cend(), [&sum](const int i){sum += i;});
48:	s_end = chrono::system_clock::now();
49:
50:	cout << "set = " << chrono::duration_cast<chrono::milliseconds>(s_end - s_start).count() << "[ms]" << endl;
51:
52:	//unordered_setの計測
53:	sum = 0;
54:	us_start = chrono::system_clock::now();
55:	for_each(us.cbegin(), us.cend(), [&sum](const int i){sum += i; });
56:	us_end = chrono::system_clock::now();
57:
58:	cout << "unordered_set = " << chrono::duration_cast<chrono::milliseconds>(us_end - us_start).count() << "[ms]" << endl;
59:
60:	return 0;
61: }

・結果(VS2013、Releaseモード)

要素追加
set = 102[ms]
unordered_set = 54[ms]

走査
set = 10[ms]
unordered_set = 6[ms]

データが10万個程度ではそこまで差はありませんが、unordered_setの方が速いことが分かります。
※どうもVCのunorderd_setは他のコンパイラに比べて遅いみたいです。

このハッシュを利用した2つのコンテナは、使い方が従来のset、mapとほとんど同じなので順序を気にしなくていい場合はこちらを使うようにしたほうがいいでしょう。

以上で、ハッシュを利用したset、mapの説明を終わります。

前→C++11講座11回
次→C++11講座13回