今日も窓辺でプログラム

外資系企業勤めのエンジニアが勉強した内容をまとめておくブログ

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つの子となるキーへの参照を持っているイメージです。下記ページに視覚的にわかりやすい図も掲載されています。
C++ 連想配列クラス std::map 入門


平衡二分探索木で実装されているので、時間・空間計算量は平衡二分探索木のそれと同じです。
例えば赤黒木で実装されている環境は、時間計算量については参照・追加・削除に関してそれぞれ最悪計算量が 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:キーと値のペアを保持したデータ構造