C++ unordered_map: 高速なハッシュマップ検索を解説

順序が重要でないとき

ちょうど std::map を見たところです。これは平衡木を使ってキーをソート済みに保ち、O(log n) の操作を提供します。しかしソートにはコストがかかり、多くの場合はキーがどの順序で出てくるかなど気にせず、ただ「このキーはここにあるか、その値は何か?」をできるだけ速く尋ねたいだけです。

そのためにあるのが std::unordered_map です。これはハッシュテーブルで、各キーをハッシュ関数に通して格納場所を決めるため、挿入・検索・削除が O(log n) ではなく平均 O(1) になります。トレードオフは、反復処理の順序が未規定であることです。キーはバケットがたまたま保持している順序で出てきます。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

インターフェースは意図的に map とほぼ同一です。多くの場合、型を変えるだけで一方をもう一方に置き換えられます。<map> ではなく <unordered_map> をインクルードすれば、キーはソートされずに出てきます。

挿入と更新

エントリを入れる方法はいくつかあり、すべてが同じ振る舞いをするわけではありません。最もよく使うのは operator[] と insert の 2 つです。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // 作成または上書き
    votes["alice"] = 5;              // 上書き -> 5
    votes.insert({"bob", 2});        // "bob" が無いときだけ挿入
    votes.insert({"bob", 99});       // 無視される、"bob" はすでに存在

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 99 ではなく 2
}

重要な違いは次のとおりです。operator[] は既存の値を上書きしますが、insert はすでに存在するキーには手を付けません。C++17 を使っているなら、insert_or_assign(key, value) は「何があってもこれを設定する」というセマンティクスを与え、try_emplace(key, args...) はキーが新しいときだけ値をその場で構築します。構築コストの高い値に便利です。

operator[] の落とし穴: 読み取りで挿入する

これは最もよくある unordered_map のバグなので、独立した節を設けます。m[key] は純粋な読み取りではありません。キーが無ければデフォルト構築して挿入し(int は 0 に、string は "" になります)、その後で参照を返します。そのため、検索に見えるコードが、こっそりマップを大きくしてしまいます。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // "y" を確認するだけのつもりだったが、[] が挿入してしまった:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 1 ではなく 2!
}

seen["y"] は、ただ言及しただけで "y" -> 0 のエントリを作ってしまいました。マップを変更せずに存在を調べるには、count(0 か 1 を返す)または find を使いましょう。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() は count() より読みやすい
    if (seen.contains("x")) cout << "x is here\n";
}

経験則: [] は作成または更新のつもりがあるときだけ使いましょう。純粋な読み取りには count、contains(C++20)、または find を使います。

find と at: 安全な検索

find はエントリへのイテレータを返し、キーが無ければ end() を返します。決して挿入せず、1 回の検索で it->first と it->second を通じてキーと値の両方に到達できます。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

キーが存在するはずだと分かっていて、無ければ明確に失敗させたい場合は at を使います。[] とは違い、at は挿入しません。キーが無いと std::out_of_range を送出します。

int p = prices.at("pen");   // 問題なし
int q = prices.at("hat");   // std::out_of_range を送出 - キーが無い

つまり検索のスタイルは 3 つあります。[](挿入する)、at(送出する)、find/count(マップに触れずに存在を報告する)です。失敗時の振る舞いが自分の意図に合うものを選びましょう。

反復処理と削除

構造化束縛を使った範囲ベースの for ループは、すべてのエントリをたどるきれいな方法です。順序は任意であることを忘れず、決して頼らないでください。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // 順序は未規定
    }
}

エントリを取り除くには、erase がキーを直接受け取り、削除された個数(0 か 1)を返します。重要な落とし穴: unordered_map では反復処理中の削除は、削除された要素のイテレータだけを無効化するので、安全に進めるには erase(it) の戻り値を使いましょう。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // スコアが 3 未満のチームをすべて削除
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase は次の有効なイテレータを返す
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

wins.erase(it++) のように書いたり、素の erase(it) の後に ++it をしたりするのは、古典的なダングリングイテレータの罠です。削除されたイテレータは無効なので、必ず erase が返すイテレータを受け取りましょう。

map か unordered_map か?

どちらも似た API でキーと値のペアを保持するので、選択は何が必要かに尽きます。

// std::map            -> ソート済みキー、O(log n)、範囲クエリ (lower_bound)
// std::unordered_map  -> 順序なし、      平均 O(1)、最速の単純検索

キーによる高速な検索だけが必要で順序が無関係なら(単語頻度の集計、キャッシュ、重複除去など)、unordered_map を選びましょう。キーをソート順で必要とする、順序どおりに反復したい、範囲クエリを行いたいときは map を選びます。unordered_map には 2 つの注意点があります。その O(1) は平均であり(悪いハッシュは劣化させ得ます)、独自のキー型にはハッシュの特殊化またはハッシュ関数オブジェクトが必要です。一方 map は operator< だけで済みます。

次: Set

これでキーと値のコンテナの両方のタイプを見ました。ただし、値がまったく不要な場合もあります。一意なタグの集まりや訪問済み ID のように、何かが存在するかどうかだけが重要なケースです。次は std::set(およびそのハッシュベースの仲間 unordered_set)を見ていきます。これらはキーだけを保持し、自動的に一意に保ちます。