std::map: 連想配列

キーと値のペアを格納。順序が必要なら map、速度なら unordered_map。

std::map
順序付き連想配列（赤黒木）。
unordered_map
ハッシュテーブル。O(1)アクセス。
std::pair
key-value のペア。

map とは？

電話帳 (Phonebook / Dictionary)

mapは電話帳です。「名前（キー）」を使って「電話番号（値）」を高速に検索できます。配列は「出席番号（インデックス）」で探しますが、mapは「中身」で探せます。

C++の `std::map` は通常、赤黒木（Red-Black Tree）で実装されており、キーは常にソートされた状態で保持されます。挿入や検索の計算量は O(log N) です。順序が不要なら、より高速な `std::unordered_map` (Hash Table) が推奨されます。

Basic map Operations
#include <map>
#include <string>


std::map<std::string, int> ages;


// 挿入
ages["Alice"] = 30;
ages.insert({"Bob", 25});
ages.emplace("Charlie", 35);


// アクセス
int age = ages["Alice"];       // 存在しなければ挿入
int safe = ages.at("Bob");     // 存在しなければ例外


// 検索
if (auto it = ages.find("Dave"); it != ages.end()) {
    std::cout << it->second << "
";
}
実行結果
ages["Alice"] = 30
ages.at("Bob") = 25
ages.find("Dave") == ages.end()
Bad
// ❌ Bad: [] で存在確認
if (ages["Unknown"] == 0) {  // 挿入されてしまう！
    // ...
}
Good
// ✅ Good: find で存在確認
if (ages.find("Unknown") == ages.end()) {
    // 存在しない
}
// C++20: contains
if (!ages.contains("Unknown")) { }

map vs unordered_map

Ordered vs Unordered
// std::map: 順序付き（赤黒木）
std::map<int, std::string> ordered;  // キーでソート


// std::unordered_map: ハッシュテーブル（高速）
std::unordered_map<int, std::string> fast;  // O(1)


// イテレーション
for (const auto& [key, value] : ages) {  // C++17 構造化束縛
    std::cout << key << ": " << value << "
";
}


// 削除
ages.erase("Bob");
ages.clear();
Tip: 順序が不要なら unordered_map（O(1)）を選ぶ。

合格ライン

☐ find で存在確認できる
☐ map と unordered_map の違いを説明できる

参考リンク

cppreference - map

演習課題

課題1: 単語カウント
文章中の各単語の出現回数をカウントするプログラムを作成してください。
課題2: find vs [ ]
存在しないキーに対する find と [] の違いを実験してください。

次のステップ

std::set
重複なし集合