C++ std::map：キー、値、検索、挿入

キーでの検索

vector は、位置でインデックス指定するとき—要素 0、要素 1 など—に最適です。しかし多くの場合、あなたが持っているのは位置ではなく名前で、それに紐づくものが欲しいのです。ユーザー名とそのスコア、単語とその出現回数、国コードとその首都など。一致するものを探して vector を走査するのは O(n) で、すぐに遅くなります。

std::map がこれを解決します。キー・バリューのペアを格納し、キーでソートした状態に保ち、キーから値を O(log n) 時間で検索できます。使うには <map> をインクルードします。

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

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> は「string のキーから int の値への map」と読みます。キーは一意で、同じキーに二度代入すると後の値が勝ちます。内部的には map は平衡二分探索木であり、これがすべてがソートされたままになり、検索が定数ではなく対数時間になる理由です。

要素の挿入

エントリを入れる方法はいくつかあり、それらの違いが重要です。最も一般的なのは operator[] で、キーが存在しなければ作成し、代入できる参照を返します。

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

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // 作成 + 代入
    inventory["apples"] += 3;     // 読み取り・変更・書き込み、現在 15

    cout << "apples: " << inventory["apples"] << "\n";
}

既存のキーの上書きを拒否する挿入が欲しい場合は、insert か emplace を使います。どちらも pair を返し、その .second は挿入が実際に行われたかどうかを示す bool です。

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada はすでに存在する
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36、変化なし
}

「最後に書き込んだものが勝つ」のが望みなら [] を、既存のキーをそのままにしておきたいなら insert/emplace を使いましょう。

operator[] の落とし穴：読み取りで挿入される

これは最もよくある map のバグです。operator[] は純粋な読み取りではありません。キーが無いと、デフォルト構築された値（int なら 0、string なら "" など）でこっそり挿入し、それへの参照を返します。したがって、[] でキーを単にチェックするだけでも map が変化します。

map<string, int> m;
if (m["maybe"] == 0) {   // バグ：これは "maybe" -> 0 を作成しただけ
    // ...
}
cout << m.size();        // 0 ではなく 1 - うっかりキーを挿入してしまった

これは const map でも問題になります。operator[] は挿入が必要になる可能性があるため、そもそもコンパイルできません。挿入せずに読み取るには、find、count/contains、または at を使います。

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: イテレータを返す、無ければ == end()
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) または count (どのバージョンでも)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: 無ければ std::out_of_range を投げる - 決して挿入しない
    cout << "a = " << m.at("a") << "\n";
}

経験則：読み取るつもりなら、決して [] に手を伸ばさないこと。キーが必ず存在するべきときは at を、存在しないかもしれないときは find/contains を使いましょう。

ソート順での反復処理

map は木構造で実装されているため、反復処理ではキーを昇順にソートされた順序で—常に、無料で—たどります。各要素は pair<const Key, Value> なので、構造化束縛を使ってキーと値をすっきり取り出しましょう。

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // 存在しないキーは 0 から始まり、その後 ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

束縛のキーが const であることに注意してください。auto& を使えばループ内で値は変更できますが、キーをその場で変更することは決してできません（ソート順が壊れてしまうため）。出力はソートのステップを一切踏まずにアルファベット順（blue、sea、sky）で出てきます。これこそ、順序付きの走査が重要なときにハッシュテーブルではなく map を選ぶ理由です。

この wordCount[w]++ というイディオムは、アクセス時挿入の振る舞いの典型的な使い方でもあります。ここでは存在しないキーを 0 から始めたいので、[] が正しい道具です。

要素の削除とサイズ

キーで削除するには erase を使い、削除された要素の数（map では 0 か 1）を返します。find から得たイテレータを使って削除することもできます。コンテナの状態は size() と empty() で確認します。

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (存在しなかった)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

ループ内で削除するときの落とし穴：m.erase(it) は it を無効化するため、その後に ++it はできません。C++11 以降の安全なパターンは it = m.erase(it) で、次の要素へのイテレータを返します。map 全体にわたる一括の条件付き削除には、std::erase_if(m, predicate)（C++20）の方がすっきりします。

次へ：unordered_map

std::map はソートされたキーと予測可能な O(log n) の操作を提供しますが、その順序の代償をすべての検索で支払うことになります。キーの順序を気にせず、とにかく最速の検索が欲しいときは、unordered_map がソート済みの木をハッシュテーブルに置き換え—平均 O(1) のアクセスを実現します。次は、その仕組み、平均定数時間が map の対数を上回るのはいつか、そしてそれに伴うハッシュの落とし穴（カスタムキー型、最悪ケースの衝突）を見ていきます。