unordered_map と set ― 高速検索と重複なし

導入

map はキーがソートされる代わりに、検索がやや遅め（対数時間）です。順序が要らず速度が欲しいなら unordered_map。「重複しない集合」が欲しいなら set / unordered_set を使います。用途で使い分けましょう。

説明

unordered_map は map とほぼ同じ使い方で、内部はハッシュテーブルです。平均して定数時間で検索でき、大量データで有利です。代わりに要素の順序は保証されません。

flowchart TB
  a["map：キーがソート順・検索は O(log n)<br/>順序が必要なとき"]
  b["unordered_map：順序なし・検索は平均 O(1)<br/>速度が欲しいとき"]
  a --- b

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

int main() {
    unordered_map<string, int> score;
    score["たろう"] = 80;
    score["はな"] = 95;
    cout << score["はな"] << endl;   // 95（使い方は map と同じ）
    return 0;
}

set は「重複しない値の集合」です。同じ値を入れても1つにまとまり、存在確認が速いのが特徴です。順序ありが set、順序なし（高速）が unordered_set です。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(3);   // 重複は無視される
    s.insert(2);

    cout << s.size() << endl;   // 3（3 は1つだけ）
    cout << (s.count(2) ? "ある" : "ない") << endl;   // ある

    for (int x : s) cout << x << " ";   // 1 2 3（set は昇順）
    cout << endl;
    return 0;
}

まとめ

順序が要るなら map/set、速度優先で順序不要なら unordered_map/unordered_set。set は「重複を自動で除く」「あるか判定が速い」のが持ち味です。「重複を消したい」「含まれるか調べたい」ときの定番です。