第12回は新しいset、mapについてです。 C++のSTLには<set>、<map>の2つのコンテナがあります。 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は要素でソート) 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と同じように扱うことが出来ます。 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の方が速いことが分かります。 このハッシュを利用した2つのコンテナは、使い方が従来のset、mapとほとんど同じなので順序を気にしなくていい場合はこちらを使うようにしたほうがいいでしょう。 以上で、ハッシュを利用したset、mapの説明を終わります。 前→C++11講座11回 |