データ構造って何

データ構造は コンピューター上でデータを効率よく保存、管理するための方法です.

おいしいデータ構造を使うことで, 例えばデータの検索や追加、削除などの操作を高速に行うことができます.

しかも自分で処理を書くよりも, すでに用意されているデータ構造||用意したデータ構造を用いることで, コードの可読性が上がり, バグを減らすことができます.

参考：https://zenn.dev/brainyblog/articles/data-structures-beginners-guide

今日扱うもの

データ構造Javaでの相当物ひとことで言うと
queueQueue (ArrayDeque)先入れ先出し（FIFO）
stackStack (ArrayDeque)後入れ先出し（LIFO）
setTreeSet重複なし・ソート済み
mapTreeMapキーと値のペア・ソート済み

計算量の話

データ構造を選ぶ基準は「その操作が何回のステップで終わるか」です. これを 計算量 と呼び, O(1), O(N), O(log N) のように書きます.

  • O(1) : データが何個あっても一定時間. 速い.
  • O(log N) : データが100万個でも20回程度. かなり速い.
  • O(N) : データの個数に比例. 100万個なら100万回. AtCoderでは 1秒間に 10^8 回 程度の計算ができると考えてください. N = 10^5 のデータに対して O(N) の操作を N 回繰り返すと O(N^2) = 10^10 回になり, 間に合いません.

これが「適切なデータ構造を選ぶ」ということの意味です.

(最悪)計算量算出

高校数学で, 極限をを習った人もいると思います. 計算量の算出方法としては, nを大きくしたときに一番影響をが出てくる項を係数なしで残すのが基本です. 例えば, 以下のような式があったとします.

f(n) = 3n^2 + 5n + 7

この場合はnが大きくなると3n^2が最も大きくなるので, n^2の項を残します. さらには, nが大きくなると係数があまり影響しなくなるので省きます. したがって, f(n)の計算量はO(n^2)となります.

このたとえが分かりにくい人がいるかもしれません. 具体例として, n=1億みたいな大きい数字を入れてみると,

f(10^8) = 3*10^16 + 5*10^8 + 7

となります. 3*10^16が圧倒的に大きいので, 5*10^8や7は無視してもあんまり変わらなそう…という感じの捉え方です. さらには係数も無視も. 10^16の3倍と1倍では, 10^16の中ではあまり変わらないので, 係数も無視してよさそう…という感じです.

競プロではこういう見積もりを良くします.

queue

FIFO（先入れ先出し）

先に入れたものが先に出てくる データ構造です. 行列（レジ待ち）をイメージしてください.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    queue<int> q;
 
    q.push(1);   // 末尾に追加
    q.push(2);
    q.push(3);
 
    cout << q.front() << endl;  // 1 (先頭を見る)
    q.pop();                    // 先頭を削除（値は返らない！）
    cout << q.front() << endl;  // 2
 
    cout << q.size() << endl;   // 2
    cout << q.empty() << endl;  // 0 (空ならtrue)
}

Javaとの違い

ここが最大の落とし穴です.

Javaの Queue は poll() が 値を返しながら削除 します.

int x = q.poll();  // 取り出して削除

C++の queue は front() で見る と pop() で削除する が分離しています.

int x = q.front();  // 見るだけ
q.pop();            // 削除するだけ（戻り値なし）

int x = q.pop(); と書くとコンパイルエラーになります. 必ず2行に分けてください.

空のqueueに対する操作

q.empty() が true のときに q.front() を呼ぶと 未定義動作 です. エラーにならず, 変な値が返ってきたり, 実行時エラーになったりします.

Javaの poll() は空なら null を返してくれますが, C++は何も守ってくれません. ループの条件に !q.empty() を必ず入れる癖をつけてください.

while (!q.empty()) {
    int x = q.front();
    q.pop();
    // xを使う処理
}

使いどころ

queue の主戦場は 幅優先探索（BFS） です. 迷路の最短経路を求めるときなどに使います.

BFSは今日は扱いませんが, 「近いところから順番に調べる」という処理は queue が担当する, と覚えておいてください.

例題

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_az https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_dy

stack

LIFO（後入れ先出し）

後に入れたものが先に出てくる データ構造です. 積み上げた本の山をイメージしてください. 上から取るしかありません.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    stack<int> st;
 
    st.push(1);  // 積む
    st.push(2);
    st.push(3);
 
    cout << st.top() << endl;  // 3 (一番上を見る)
    st.pop();                  // 一番上を削除
    cout << st.top() << endl;  // 2
 
    cout << st.size() << endl;  // 2
    cout << st.empty() << endl; // 0
}

queueとの対応

見る削除追加
queuefront()pop()push()
stacktop()pop()push()

見るときのメソッド名だけが違います. stack は「上を見る」ので top() です.

pop() が値を返さないのは queue と同じです.

使いどころ

括弧の対応チェック, 逆ポーランド記法の計算, 深さ優先探索（DFS）の非再帰実装などです.

「直前の状態に戻る」「入れ子構造を処理する」というパターンが出てきたら stack を疑ってください.

括弧の対応チェック

典型例なので, コードを見ておきましょう.

bool is_valid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else {  // c == ')'
            if (st.empty()) return false;  // 閉じすぎ
            st.pop();
        }
    }
    return st.empty();  // 開きっぱなしがなければOK
}

( が来たら積み, ) が来たら取り除く. 最後に空ならバランスが取れている, という考え方です.

例題

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ay https://atcoder.jp/contests/joi2022yo2/tasks/joi2022_yo2_a https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_dx

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