データ構造の基礎：配列、スタック、キュー、木、ハッシュテーブル

この記事は講義を目的として作成しています。例は理解のために単純化しています。実際のC++では、独自実装に明確な理由がない限り標準ライブラリのコンテナを優先してください。

データ構造の学習はpush、pop、連結リストのノード名を覚える作業に見えることがある。しかし本質は、プログラムが頻繁に行う操作を単純で安価にするため、データをどの形で置くか判断することだ。

同じ十個の値でも、添字で読むなら配列、直前の操作を戻すならスタック、古い要求から処理するならキュー、キーで探すならハッシュテーブルが自然である。

データ構造と抽象データ型

スタックは「最後に入れた値を最初に取り出す」という規則だ。内部は連続配列でも連結リストでもよい。利用者に見える操作と規則を抽象データ型、実際の保存方法を実装として分けると理解しやすい。

スタックの代表的な操作は次の通りである。

• pushは一番上に値を入れる。
• popは一番上の値を削除する。
• topまたはpeekは削除せずに値を見る。
• emptyは空かどうかを返す。
• sizeは要素数を返す。

C++のstd::stackはコンテナアダプタで、既定ではstd::dequeを内部に使う。

最低限の計算量

Big Oだけでなく、メモリ量、キャッシュ局所性、再割り当て、参照の無効化、実装の複雑さも重要である。

配列は連続して保存する

int scores[5] = { 10, 20, 30, 40, 50 };

先頭アドレスと要素サイズから任意の添字のアドレスを直接計算できる。

address(i) = base + i × sizeof(element)

添字アクセスはO(1)で、連続走査はキャッシュにも有利なことが多い。中間への挿入は後続要素を移動するため最悪O(N)になる。固定長のC++配列にはstd::arrayが使える。

動的配列とstd::vector

std::vector<int> values;
values.push_back(10);
values.push_back(20);
values.push_back(30);

vectorは連続メモリ、現在のsize、再割り当てなしで入るcapacityを管理する。空きがあれば末尾追加は定数時間で、満杯なら大きな領域へ要素を移す。一回の再割り当てはO(N)だが、多数のpush_back全体では一回あたり償却O(1)になる。

概算個数が分かるならreserveで再割り当てを減らせる。再割り当て後は以前の要素を指すポインタ、参照、イテレータが無効になる可能性がある。

連結リスト

struct Node
{
    int value;
    Node* next;
};

対象ノードをすでに知っていれば、その直後への挿入はリンクを数個変えるだけなのでO(1)である。しかし100番目の要素には前からたどる必要があり、ランダムアクセスはO(N)だ。

リストはポインタ分のメモリを使い、ノードが散らばるためキャッシュ効率が低い場合がある。挿入位置を探す時間も含めると、挿入が多いだけでvectorより速いとは限らない。標準にはstd::forward_listとstd::listがある。

スタックは最後の値を先に取り出す

スタックはLIFO、Last In First Outである。

std::stack<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);

int top = numbers.top();
numbers.pop();

topは30で、その後スタックには10と20が残る。

popは値を返さない

C++のstd::stack::pop()は削除だけを行い、戻り値はvoidである。先に値を読み、その後で削除する。

if (!numbers.empty())
{
    int value = numbers.top();
    numbers.pop();
    use(value);
}

空のスタックでtopやpopを呼んではいけない。

vectorで作る小さなスタック

template <typename T>
class SimpleStack
{
public:
    void push(const T& value) { values_.push_back(value); }

    void pop()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        values_.pop_back();
    }

    T& top()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        return values_.back();
    }

    bool empty() const { return values_.empty(); }

private:
    std::vector<T> values_;
};

スタックは関数呼び出し、Undo履歴、括弧検査、深さ優先探索、後置式計算、再帰の反復化に使われる。

キューは最初の値を先に取り出す

キューはFIFO、First In First Outである。

std::queue<int> jobs;
jobs.push(101);
jobs.push(102);
jobs.push(103);

int first = jobs.front();
jobs.pop();

firstは101になる。タスクスケジュール、メッセージ処理、プリンタジョブ、幅優先探索、パケットバッファに適している。

リングバッファ

配列の先頭削除で全要素を移さず、headとtailの添字を別に管理できる。末尾に達した添字は剰余で0に戻す。

tail = (tail + 1) % Capacity;
head = (head + 1) % Capacity;

固定容量リングバッファは音声、ゲームイベント、上限のある生産者・消費者処理に向く。複数スレッドで使うには同期または専用のconcurrent queueが必要である。

デックと優先度付きキュー

std::dequeは前後の両方で挿入と削除ができる。work stealing、sliding window、双方向待ち行列に向くが、vectorのように全体が一つの連続領域である保証はない。

優先度付きキューは到着順ではなく優先度の最も高い値を先に返す。

std::priority_queue<int> scores;
scores.push(30);
scores.push(10);
scores.push(50);
int highest = scores.top();
scores.pop();

通常はヒープで実装され、先頭確認はO(1)、挿入と先頭削除はO(log N)である。

ハッシュテーブル

std::unordered_map<std::string, int> health;
health["knight"] = 120;
health["mage"] = 70;

ハッシュ関数がキーからバケットを選ぶ。分布とload factorが適切なら検索、挿入、削除は平均O(1)だが、衝突は必ず考慮する。最悪はO(N)になり得る。

独自キーでは等価比較とハッシュの意味を一致させる。同じと判断されるキーは必ず同じハッシュ値を持たなければならない。

木と二分探索木

木はファイルシステム、UI、scene graph、文書の階層を表す。rootは親を持たず、leafは子を持たない。depthはrootからの距離、heightは最深leafまでの距離である。

二分探索木は各ノードが最大二つの子を持ち、一般に小さいキーを左、大きいキーを右へ置く。平衡なら検索、挿入、削除はO(log N)だが、単純な木へ整列済みデータを入れると一列になりO(N)へ悪化する。

std::mapはキー順を保ってO(log N)の操作を提供する。順序が不要で平均定数時間の検索を優先するならstd::unordered_mapを検討する。

ヒープ

最大ヒープでは親が子以上、最小ヒープでは親が子以下になる。全体が完全にソートされているわけではない。

完全二分木は配列へ効率よく格納できる。0始まりの添字iでは次の関係を使う。

left child  = 2 × i + 1
right child = 2 × i + 2
parent      = (i - 1) / 2

最小値または最大値を繰り返し取り出す処理に強いが、任意の値の検索は通常O(N)である。

trieとグラフ

trieはキーの文字やビットを経路にする木で、接頭辞を共有できる。検索はキー長Lに対してO(L)と説明されることが多い。自動補完、辞書、ルーティングに利用される。

グラフはvertexとedgeで一般的な接続を表す。隣接行列は接続確認がO(1)だがメモリがO(V²)になる。隣接リストは約O(V + E)で疎なグラフに向く。

using Graph = std::vector<std::vector<int>>;

Graph graph(4);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);

BFSはキューを、DFSは呼び出しスタックまたは明示的なスタックを使う。

代表的な計算量

選び方

最も多い操作、順序の必要性、添字アクセス、キー検索、最小最大の反復、最大要素数、ポインタ安定性、連続メモリAPI、複数スレッド利用を確認する。通常の値列ならまずstd::vectorから始め、具体的な要件が見つかったときに別構造へ移るとよい。

よくある間違い

• 空のstackやqueueでtop、front、popを呼ぶ。
• C++のpopが削除値を返すと思う。
• vector再割り当て後も古いポインタを使う。
• 挿入位置の検索を無視してlistが常に速いと思う。
• ハッシュ操作が必ずO(1)だと説明する。
• 再帰DFSの呼び出し深さを無視する。
• 所有者不明のraw pointerで木を構成する。

まとめ

配列とvectorは高速な添字アクセスと良い局所性を持つ。連結リストは既知位置のリンク変更に強いが、走査と分散メモリに費用がある。stackは新しい値、queueは古い値、dequeは両端、priority queueは最重要値を先に扱う。ハッシュテーブルは平均的に速いキー検索、平衡木は順序、ヒープは極値、グラフは一般的な接続を表す。

最良のデータ構造は最も複雑なものではない。実際の操作を明確で予測可能にするものが良い選択である。