第19回 `std::deque` ― 両端に追加できる配列

std::deque（double-ended queue）は、先頭にも末尾にも O(1) で追加／削除できる動的配列です。std::vector と違って push_front が速いのが特徴で、キュー（先入れ先出し）のような使い方や履歴バッファで効きます。本章では vector との違いと使い分けを整理します。

このページで押さえること

✅ 最低限ここだけ覚える

push_front / push_back が両方 O(1) 償却
インデックスアクセス dq[i] も使える
pop_front / pop_back で両端を消せる
ほとんどの場面は vector で足り、両端操作が必要なときに deque

⭐ 余裕があれば読む

内部はブロック（チャンク）の配列
vector と違いメモリは連続ではない
再確保でポインタが無効化されにくい
キャッシュ効率は vector より少し悪い

1. まず触ってみる ― 両端から追加

push_front と push_back を押して、両端にどう要素が入るかを見てください。インデックスは 0 が常に先頭（front）、size-1 が末尾（back）を指します。

▶ std::deque<int> のインタラクティブ操作

値:

2. 基本操作と vector との違い

deque 基本C++

#include <deque> std::deque<int> dq; dq.push_back(10); // 末尾に追加 dq.push_front(5); // 先頭に追加 (vector にはない) dq.push_back(20); // dq = {5, 10, 20} dq.pop_front(); // 先頭削除 dq.pop_back(); // 末尾削除 dq[0]; // vector と同じインデックスアクセス

vector と比べると違い

// vector: 先頭追加は全要素シフトで O(n) std::vector<int> v; v.insert(v.begin(), 5); // 遅い O(n) // v に push_front はない // deque: 両端とも O(1) 償却 std::deque<int> dq; dq.push_front(5); // 高速 O(1) 償却

vector と共通のメソッド

dq.size() / dq.empty()
dq[i]（範囲チェックなし）／ dq.at(i)（範囲チェック付き）
dq.front() / dq.back()
範囲 for for (auto x : dq)

deque だけの追加メソッド

dq.push_front(x) / dq.pop_front() ― 先頭操作

使い勝手は vector と 8 割同じ： vector のコードを std::vector → std::deque に置き換えるだけで大抵動きます。追加で push_front / pop_front が使える分だけ柔軟、というのが第一印象で合っています。

3. 内部構造（なぜ両端 O(1) ？）

メモリ上の deque は、小さなブロック（チャンク）の配列として管理されます。vector のように単一の連続領域ではありません。

deque の内部イメージ（ブロックサイズ 4 の例）

map (中央管理):  [ブロック0][ブロック1][ブロック2][ブロック3]
                      ↓          ↓          ↓          ↓
ブロック0 (空き 2):   [ . ][ . ][3][5]
ブロック1:            [8][10][12][20]
ブロック2:            [25][30][33][40]
ブロック3 (空き 2):   [50][60][ . ][ . ]

「中央」の管理配列（map）が各ブロックへのポインタを持つ
先頭・末尾にはあらかじめ余白があり、push_front / push_back は空きブロックに書き込むだけなので O(1)
余白が尽きたら新しいブロックを確保し、map に追記する

vector にない利点： 要素が連続領域に置かれない代わりに、拡張しても既存要素のメモリ位置が動かない（ブロック単位で確保するため）。イテレータや要素へのポインタが無効化されにくいのも deque の特徴。

キャッシュ効率は少し劣る： 連続領域の vector に比べ、ブロックを跨ぐたびにキャッシュミスが起きやすい。要素数が多くランダムアクセスが中心の用途では、vector のほうが速いことがほとんど。deque は「両端操作が必要」という明確な理由があるときに選ぶ。

4. 使い所 ― vector との使い分け

deque が効くケース：

キュー（FIFO）として使う：末尾に追加、先頭から取り出す処理（BFS、ログ処理など）
履歴バッファ：新しいものを先頭に追加、古いものを末尾から消す
末尾の要素へのポインタが生き続けてほしい場面（vector だと再確保で無効化する可能性あり）

vector のほうがいいケース：

末尾追加と v[i] だけで足りる（多数派）
要素数が少ない or キャッシュヒット率を稼ぎたい
data() で T* を取り出して C API に渡したい（deque は連続していないので不可）

std::queue / std::stack との関係： 「FIFO にしたい」なら std::queue（内部は deque）、「LIFO にしたい」なら std::stack（内部は deque）がより簡潔です。アダプタは第 22 回で扱います。

確認クイズ

2 問。

Q1. 「ログを末尾に追加し続け、一番古いログ（先頭）から順に処理する」を最も自然に書けるのは？

std::vector（push_back + erase(begin())）

std::list

std::deque（または std::queue アダプタ）

std::set

「末尾に追加 + 先頭から取り出す」= FIFO キュー。deque（または deque を内部に持つ std::queue）が最適。vector は先頭削除が O(n) で遅いです。

Q2. deque について正しい説明は？

内部メモリは単一の連続領域である

インデックス dq[i] で要素にアクセスできる

push_front は O(n) かかる

data() で T* を取り出せる

deque はブロック（チャンク）配列なのでメモリは連続していない。そのため data() もありません。ただしインデックスアクセス dq[i] は使えるし、push_front は O(1) 償却です。