C++ STL map vs unordered_map

2023年6月5日 23:38

C++のSTL (Standard Template Library) には unordered_map と map の二つの異なる種類のマップ (連想配列) が含まれています。これらは、キーと値のペアを格納するデータ構造で、キーを通じて値を効率的に検索することが可能です。

しかし、これら二つのデータ構造は、内部的な実装とそれによる振る舞いにおいてはかなり異なります。

map

map はバランス木（具体的には赤黒木）によって実装されています。このため、挿入、削除、検索のすべての操作の時間計算量が O(log n) です。ここで n はマップに含まれる要素の数です。

また、 map はキーに基づいて要素をソートします。したがって、イテレータを使用して map を通過すると、要素はキーの順に取得されます。

unordered_map

一方、 unordered_map はハッシュテーブルによって実装されています。ハッシュ関数を使用して、キーをハッシュテーブル内のインデックスにマッピングします。これにより、理想的な条件下では、挿入、削除、検索の操作の時間計算量が平均的に O(1) になります。しかし、最悪のケース（全てのキーが同一のハッシュ値を持つ場合など）では、これらの操作は O(n) の時間計算量となります。

unordered_map は名前が示す通り、要素は順不同で保存されます。つまり、イテレータを使用して unordered_map を通過すると、要素は一定の順序で取得されるわけではありません。

以上の特性から、要素の挿入、削除、検索のパフォーマンスが優先され、要素の順序は重要でない場合は unordered_map を、要素を特定の順序で取得する必要がある場合や、要素の数が非常に少ない場合は map を使用すると良いでしょう。

おそらくほとんどの人にとって std::unordered_map の方が馴染みがないかと思います。そこでサンプル・テンプレ集を纏めてみました。

1. 初期化と挿入

#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> ages;

    // 挿入方法 1
    ages["Alice"] = 25;

    // 挿入方法 2
    ages.insert(std::make_pair("Bob", 30));

    // 挿入方法 3
    ages.emplace("Charlie", 35);
}

2. 要素の検索

// 'find'関数を使うと指定したキーが存在するか調べられます
auto it = ages.find("Alice");
if(it != ages.end()) {
    // 見つかった場合、itは要素のペア (キーと値) を指すイテレータとなります
    std::cout << it->first << " is " << it->second << " years old." << std::endl;
} else {
    // 見つからなかった場合
    std::cout << "Alice is not in the map." << std::endl;
}

3. 要素の削除

ages.erase("Alice");  // Aliceのエントリを削除します

4. すべての要素の巡回

for(const auto &pair : ages) {
    std::cout << pair.first << " is " << pair.second << " years old." << std::endl;
}

5. マップのサイズとクリア

std::cout << "Size of map: " << ages.size() << std::endl;

ages.clear();  // マップからすべての要素を削除します

std::cout << "Size of map after clear: " << ages.size() << std::endl;