C++のstd::mapとstd::unordered_mapの実装の違いを知らなくて恥ずかしい思いをしたので、調べた結果をまとめておきます。
記事のまとめ
std::mapは平衡二分探索木、std::unordered_mapはハッシュテーブルで実装されている。
キーの順番を保持したい場合はmapを使用したほうが良いが、そうでない場合はunordered_mapの方が性能的には優れている。
map
mapとは何か?
マップはキーの順番を保持している連想配列*1です。キーの順番を保持しているので、このようにイテレーションを回すこともできます。
// map.cpp #include <iostream> #include <string> #include <map> using namespace std; int main(void) { // キーがstring型, 値がint型のstd::mapを宣言 map<string, int> scores; // 生徒の名前と成績を適当な順番で追加していく scores["Suzuki"] = 86; scores["Yamada"] = 70; scores["Tanaka"] = 62; scores["Sato"] = 91; // キーの順番を保持しているので、イテレータを回すと生徒の名前順になっている for (auto it = scores.begin(); it != scores.end(); ++it) { cout << it->first << "\t" << it->second << endl; } return 0; }
これを -std=c+11 オプションをつけてコンパイル・実行してあげると、ちゃんと名前順にソートされているのが確認できます。
g++ -std=c++11 map.cpp && ./a.out
Sato 91
Suzuki 86
Tanaka 62
Yamada 70
実装
平衡二分探索木(赤黒木など)で実装されている環境が多いようです。キーが木のノードになり、そのキーに対応する値と、2つの子となるキーへの参照を持っているイメージです。下記ページに視覚的にわかりやすい図も掲載されています。
https://vivi.dyndns.org/tech/cpp/map.html
平衡二分探索木で実装されているので、時間・空間計算量は平衡二分探索木のそれと同じです。
例えば赤黒木で実装されている環境は、時間計算量については参照・追加・削除に関してそれぞれ最悪計算量が、空間計算量については
です。ノード1つに対して子ノード2つを保持するので、2n * (ポインタのサイズ)は最低限使用する形になるでしょうか。
unordered_map
unordered_mapとは何か?
unordered_mapもmapと同じようにキーと値のペアを保持する連想配列なのですが、名前の通りキーの順番を保持しません。
mapの部分で紹介したコードをunordered_mapに変えて実行してみると、キーの順番がバラバラになって保持されていることが確認できます。
#include <iostream> #include <string> #include <unordered_map> using namespace std; int main(void) { // キーがstring型, 値がint型のstd::unordered_mapを宣言 unordered_map<string, int> scores; // 生徒の名前と成績を適当な順番で追加していく scores["Suzuki"] = 86; scores["Yamada"] = 70; scores["Tanaka"] = 62; scores["Sato"] = 91; // キーの順番は気にせず保持しているので、順番はランダムに入れ替わる for (auto it = scores.begin(); it != scores.end(); ++it) { cout << it->first << "\t" << it->second << endl; } return 0; }
Sato 91
Tanaka 62
Yamada 70
Suzuki 86
実装
unordered_mapはハッシュテーブルを使用して実装されているようです。
時間計算量は平均がとなります。ハッシュ値が衝突するような悪いデータの入れ方をしていると
かかってしまう場合もあります。
一方、空間計算量はどの程度のサイズのハッシュテーブルを確保しているかに依存します。
このStackOverflowによるとバケットのサイズがのとき
で実装されているのではないか、とのことです。
実際にmapとunordered_mapのサイズを比較している記事も結構あって、確かにunordered_mapの方が小さくなっていることの方が多いです。
参考記事
- https://vivi.dyndns.org/tech/cpp/map.html
- https://vivi.dyndns.org/tech/cpp/unordered_map.html
- https://www.cplusplus.com/reference/map/map/
- https://www.cplusplus.com/reference/unordered_map/unordered_map/
- STL風に使えるマップ型コンテナの紹介と性能比較 | Preferred Research
- mapとunordered_mapのアイテム全走査の比較とmapの存在意義について考える - 睡眠不足?!
*1:キーと値のペアを保持したデータ構造