mapとunordered_mapの実装や性能の違い - 今日も窓辺でプログラム

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

平衡二分探索木で実装されているので、時間・空間計算量は平衡二分探索木のそれと同じです。
例えば赤黒木で実装されている環境は、時間計算量については参照・追加・削除に関してそれぞれ最悪計算量が $O(\log n)$ 、空間計算量については $O(n)$ です。ノード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はハッシュテーブルを使用して実装されているようです。
時間計算量は平均が $O(1)$ となります。ハッシュ値が衝突するような悪いデータの入れ方をしていると $O(n)$ かかってしまう場合もあります。
一方、空間計算量はどの程度のサイズのハッシュテーブルを確保しているかに依存します。
このStackOverflowによるとバケットのサイズが $m$ のとき $O(n + m)$ で実装されているのではないか、とのことです。

実際にmapとunordered_mapのサイズを比較している記事も結構あって、確かにunordered_mapの方が小さくなっていることの方が多いです。

参考記事

*1:キーと値のペアを保持したデータ構造