【C++】mapとunordered_mapの違い｜使い分けと速度を比較

サムネイル画像 C++

C++でキーと値のペアを扱いたい時、「mapとunordered_mapってどっちを使えばいいの？」と迷ったことはありませんか？

どちらも「キーから値を検索する」という役割は同じですが、内部構造が全く違うため、速度やメモリ使用量に大きな差があります。

この記事を読み終えると、あなたはmapとunordered_mapを正しく使い分けられるようになると思いますので、ぜひ最後まで読んでいただけると嬉しいです。

mapとunordered_mapの違い

mapは赤黒木という木構造で実装されていて、キーが常にソート順(昇順)で管理されます。

unordered_mapはハッシュテーブルで実装されていて、キーはランダムな順序で管理されます。

それぞれの特徴を詳しく見ていきましょう。

mapの特徴

mapは、キーが自動的にソートされるのが最大の特徴です。

▼main.cpp

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> players;
    
    // バラバラな順序で追加
    players[3] = "Alice";
    players[1] = "Bob";
    players[2] = "Charlie";
    
    // キー順(昇順)で自動ソートされる
    for (const auto& p : players) {
        std::cout << p.first << ": " << p.second << "\n";
    }
    
    return 0;
}

実行結果

1: Bob
2: Charlie
3: Alice

追加した順序に関係なく、キーが昇順に並んでいます。

mapの計算量

  • ✅ 検索・挿入・削除: O(log N)
  • ✅ 範囲検索: 得意(lower_bound, upper_boundが使える)
  • ✅ 順序保証: キーが常にソート済み
  • ❌ 速度: unordered_mapより少し遅い

unordered_mapの特徴

unordered_mapは、ハッシュテーブルを使った高速な検索が特徴です。

▼main.cpp

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> players;
    
    // バラバラな順序で追加
    players[3] = "Alice";
    players[1] = "Bob";
    players[2] = "Charlie";
    
    // 順序は保証されない(ランダム)
    for (const auto& p : players) {
        std::cout << p.first << ": " << p.second << "\n";
    }
    
    return 0;
}

実行結果(例)

2: Charlie
1: Bob
3: Alice

順序がバラバラです。実行するたびに順序が変わることもあります。

unordered_mapの計算量

  • ✅ 検索・挿入・削除: O(1) 平均(最悪 O(N))
  • ✅ 速度: mapより高速
  • ❌ 順序保証: なし(ランダム)
  • ❌ 範囲検索: 不可能
  • ❌ メモリ使用量: mapより多い

速度比較実験

実際に100万回の検索を行って、速度を比較してみましょう。

▼main.cpp

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>

int main() {
    const int N = 100000;
    
    // map
    std::map<int, int> m;
    for (int i = 0; i < N; i++) {
        m[i] = i * 2;
    }
    
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        int val = m[i];
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto map_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    // unordered_map
    std::unordered_map<int, int> um;
    for (int i = 0; i < N; i++) {
        um[i] = i * 2;
    }
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        int val = um[i];
    }
    end = std::chrono::high_resolution_clock::now();
    auto umap_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    std::cout << "map: " << map_time << "ms\n";
    std::cout << "unordered_map: " << umap_time << "ms\n";
    
    return 0;
}

実行結果(例)

map: 45ms
unordered_map: 12ms

unordered_mapの方が約3~4倍高速でした。

【重要】私が実際にmapで困った体験談

体験談1: ゲームのスコアボードがランダムに並んでしまった

勉強として「スコアボードを表示するゲーム」を作っていた時のことです。プレイヤー名とスコアを管理するために、unordered_mapを使いました。

std::unordered_map<std::string, int> scores;
scores["Alice"] = 1000;
scores["Bob"] = 850;
scores["Charlie"] = 920;

for (const auto& s : scores) {
    std::cout << s.first << ": " << s.second << "\n";
}

実行すると、スコアがランダムな順序で表示されてしまいました。

Charlie: 920
Alice: 1000
Bob: 850

本来は、スコアが高い順に表示したかったです。

原因は、unordered_mapは順序を保証しないこと。mapに変更したら、名前順に整列されるようになりました(スコア順にするにはvectorに移してソートが必要でしたが)。

体験談2: mapの検索が遅すぎてゲームがカクついた

個人開発でRPGを作っていた時、敵のIDからステータスを取得する処理にmapを使っていました。

std::map<int, EnemyData> enemies; // 敵データベース

// 毎フレーム数百回検索
for (int i = 0; i < enemyCount; i++) {
    auto data = enemies[enemyIDs[i]]; // ここが遅い
}

敵が多い場面でFPSが30以下に落ちてカクカクになりました。

原因は、mapの検索がO(log N)で、毎フレーム数百回検索していたこと。unordered_mapに変更したら、FPSが60に回復しました。

この経験から、「頻繁に検索するならunordered_map、順序が必要ならmap」と使い分けるようになりました。

よくある失敗例と対処法

失敗例1: unordered_mapでイテレータが無効化された

症状: 要素を追加・削除した後、イテレータを使うとクラッシュする
原因: unordered_mapは再ハッシュ時に全イテレータが無効化される
対処法: イテレータを保持せず、毎回新しく取得する

// NG
auto it = umap.begin();
umap[100] = "new"; // 再ハッシュでitが無効化
std::cout << it->second; // クラッシュ！

// OK
umap[100] = "new";
auto it = umap.find(100); // 新しく取得
if (it != umap.end()) {
    std::cout << it->second;
}

失敗例2: カスタム型をunordered_mapのキーにできない

症状: std::unordered_map<MyClass, int>でコンパイルエラー
原因: unordered_mapはハッシュ関数が必要だが、カスタム型にはデフォルトで存在しない
対処法: ハッシュ関数を自作するか、mapを使う

// 解決策1: mapを使う(比較演算子<が必要)
std::map<MyClass, int> m;

// 解決策2: ハッシュ関数を自作
struct MyClassHash {
    size_t operator()(const MyClass& obj) const {
        return std::hash<int>()(obj.id);
    }
};
std::unordered_map<MyClass, int, MyClassHash> um;

失敗例3: mapで範囲検索しようとして遅かった

症状: 「スコアが800~900の間のプレイヤーを探す」処理が遅い
原因: 全要素をループで確認していた
対処法: mapならlower_boundとupper_boundを使う

std::map<int, std::string> scores;
// ... データ追加 ...

// NG(全要素チェックで遅い)
for (const auto& s : scores) {
    if (s.first >= 800 && s.first <= 900) {
        std::cout << s.second << "\n";
    }
}

// OK(範囲検索で高速)
auto start = scores.lower_bound(800);
auto end = scores.upper_bound(900);
for (auto it = start; it != end; ++it) {
    std::cout << it->second << "\n";
}

実践的な使い分け例

プレイヤーIDから名前を取得(unordered_map推奨)

▼main.cpp

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> players;
    players[1001] = "Alice";
    players[1002] = "Bob";
    players[1003] = "Charlie";
    
    // 高速検索(O(1))
    int id = 1002;
    std::cout << "Player " << id << ": " << players[id] << "\n";
    
    return 0;
}

実行結果

Player 1002: Bob

スコアランキング(map推奨)

▼main.cpp

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> ranking;
    ranking[1000] = "Alice";
    ranking[850] = "Bob";
    ranking[920] = "Charlie";
    
    // スコア順(昇順)で自動ソート
    std::cout << "=== ランキング ===\n";
    for (auto it = ranking.rbegin(); it != ranking.rend(); ++it) {
        std::cout << it->first << "点: " << it->second << "\n";
    }
    
    return 0;
}

実行結果

=== ランキング ===
1000点: Alice
920点: Charlie
850点: Bob

map vs unordered_map 比較表

比較項目mapunordered_map
内部構造赤黒木(木構造)ハッシュテーブル
検索速度O(log N)O(1) 平均
挿入速度O(log N)O(1) 平均
削除速度O(log N)O(1) 平均
順序保証○(昇順)×(ランダム)
範囲検索○(lower_bound等)×
メモリ使用量少ない多い
カスタム型キー比較演算子<が必要ハッシュ関数が必要

どちらを使うべき?

以下の基準で選びましょう。

こういうとき使うべきもの
とにかく検索を高速化したいunordered_map
キーの順序が重要(ソート済みで扱いたい)map
範囲検索がしたい(例: スコア800~900)map
メモリ使用量を抑えたいmap
ゲームのフレーム内で頻繁に検索unordered_map
迷ったらunordered_map

基本的にはunordered_mapの方が高速なので、順序が不要ならunordered_mapを選びましょう。

まとめ

mapとunordered_mapの使い分けをまとめます。

  • ✅ map: 赤黒木で実装、キーがソート順、O(log N)、範囲検索可能
  • ✅ unordered_map: ハッシュテーブルで実装、順序なし、O(1)平均、高速
  • ✅ 検索速度重視: unordered_mapが有利
  • ✅ 順序が必要: mapが必須
  • ✅ 範囲検索: mapのlower_bound/upper_boundを使う
  • ✅ メモリ節約: mapの方が少ない
  • ✅ 迷ったら: unordered_mapを選べばOK

これでmapとunordered_mapの使い分けはバッチリですね！

適切な方を選んで、パフォーマンスの良いC++プログラムを書いてみてください。

ここまで読んでくださり、ありがとうございました。

この記事が皆様の学習に役立てば幸いです。

関連記事