set

重複を許さない集合

同じ値を2つ以上持てないコンテナです. さらにC++の set は 常にソートされた状態 で保持されます.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    set<int> s;
 
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(1);  // 既にあるので無視される
 
    cout << s.size() << endl;  // 3
 
    // 中身は {1, 3, 4} の順に並んでいる
    // setの要素を取り出すときには範囲for文をよく使う
    for (int x : s) {
        cout << x << " ";  // 1 3 4
    }
    cout << endl;
}

存在判定

set<int> s = {1, 3, 4};
 
if (s.count(3)) {          // 存在すれば1, なければ0
    cout << "found" << endl;
}

count() のほうが読みやすいので, 存在判定はこちらを使ってください. set は重複を持たないので, count() の戻り値は必ず 0 か 1 です.

削除

s.erase(3);  // 値3を削除. なくてもエラーにならない

Javaとの違い

Javaの HashSet は 順序が保証されません. C++の set は内部が 赤黒木（平衡二分探索木）なので, 常にソートされています.

Javaで順序が欲しければ TreeSet を使いますが, C++では set がデフォルトでそれです.

C++Java
ソート済みsetTreeSet
ハッシュ（順序なし）unordered_setHashSet

計算量は set が O(log N), unordered_set が平均 O(1) です. 速度だけなら unordered_set ですが, ソート済みであることの恩恵が大きいので, 競プロでは set を使う場面が多いです.

lower_bound

set の真価はここです. 「x以上の最小の要素」を O(log N) で見つけられます.

set<int> s = {1, 3, 5, 7, 9};
 
auto it = s.lower_bound(4);  // 4以上で最小 → 5
cout << *it << endl;         // 5
 
auto it2 = s.lower_bound(5); // 5以上で最小 → 5（自分自身を含む）
cout << *it2 << endl;        // 5
 
auto it3 = s.lower_bound(10);  // 該当なし
if (it3 == s.end()) {
    cout << "not found" << endl;
}

auto は型推論です. 正確には set<int>::iterator ですが, 長いので auto で書きます.

イテレータなので, 値を取り出すには *it とします. 該当する要素がないときは s.end() が返るので, 必ずチェックしてください.

注意: std::lower_bound は使えない

vector に対しては lower_bound(v.begin(), v.end(), x) というグローバル関数を使いますが, set に対してこれを使うと O(N) になります.

set<int> s = {1, 3, 5};
 
auto it1 = s.lower_bound(4);                    // O(log N) ← 正しい
auto it2 = lower_bound(s.begin(), s.end(), 4);  // O(N) ← 遅い！

この動作の何がうれしいかというと, 配列に対する二分探索が標準の機能でできるという事です.

正味私はこの辺のやつを書くたびに実装方法忘れる 範囲絞り込み二分探索は頑張ってください

例題

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bc https://atcoder.jp/contests/abc268/tasks/abc268_a

map

キーと値のペア

キーから値を引ける連想配列です. Javaの TreeMap に相当します. 連想配列は何かと言いますと, 今まで配列に対して添え字という数字を使ってきたと思いますが, 添え字の代わりに文字列などを使える配列です. 例えば, よくある例だと果物の値段管理とかで見ます

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    map<string, int> m;
 
    m["apple"] = 100;
    m["banana"] = 200;
 
    cout << m["apple"] << endl;  // 100
    cout << m.size() << endl;    // 2
 
    // キーの昇順で回る
    for (auto p : m) {
        cout << p.first << " " << p.second << endl;
    }
    // apple 100
    // banana 200
}

p.first がキー, p.second が値です. C++17以降なら構造化束縛が使えます.

for (auto [key, value] : m) {
    cout << key << " " << value << endl;
}

こちらのほうが読みやすいので, 積極的に使ってください.

最大の落とし穴: [] の副作用

存在しないキーに [] でアクセスすると, そのキーが勝手に作られます.

map<string, int> m;
m["apple"] = 100;
 
cout << m.size() << endl;    // 1
 
cout << m["banana"] << endl; // 0 が表示される
cout << m.size() << endl;    // 2 ← bananaが作られてしまった！

値の型のデフォルト値（int なら 0, string なら空文字列）で初期化されて挿入されます.

これは意図しない挙動を生みます. 特に「存在チェックのつもりで [] を使う」のは間違いです.

// 間違い
if (m["apple"] != 0) { ... }  // appleが存在しなくても挿入されてしまう
 
// 正しい
if (m.count("apple")) { ... }

存在チェックは必ず count() を使ってください.

意図的に使う場合

一方で, この挙動は カウント処理では便利 です.

map<string, int> cnt;
vector<string> words = {"a", "b", "a", "c", "a"};
 
for (string w : words) {
    cnt[w]++;  // 初回は0から始まるので, そのまま++できる
}
 
// a: 3, b: 1, c: 1

削除と存在判定

map<string, int> m;
m["apple"] = 100;
 
if (m.count("apple")) {   // 存在判定
    cout << "found" << endl;
}
 
m.erase("apple");         // 削除

Javaとの違い

set と同じ構図です.

C++Java
ソート済みmapTreeMap
ハッシュ（順序なし）unordered_mapHashMap

map は O(log N), unordered_map は平均 O(1) です.

キーの順序が不要で速度が欲しいなら unordered_map を使ってください. ただし unordered_map は lower_bound が使えません.

例題

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bb