C++のdequeとは
C++のdequeは、標準ライブラリで提供されているシーケンスコンテナの一つです。
dequeは「double-ended queue」の略で、日本語では「両端キュー」と呼ばれます。
最大の特徴は、コンテナの先頭と末尾の両方に対して、要素を高速に追加・削除できることです。
dequeを使用するには、次のように<deque>ヘッダーをインクルードします。
#include <deque>
基本的な宣言方法は次のとおりです。
std::deque<int> numbers;
dequeはvectorと同じように添字によるランダムアクセスが可能ですが、vectorとは異なり、先頭への追加・削除も効率的に行えます。
そのため、先頭と末尾の両方を頻繁に操作する処理に適したコンテナです。
dequeの主な特徴
先頭と末尾への追加・削除が高速
dequeでは、先頭と末尾に対する追加・削除を定数時間で行えます。
代表的なメンバ関数は次の4つです。
push_front()
push_back()
pop_front()
pop_back()
例えば、次のように使用できます。
#include <iostream>
#include <deque>
int main()
{
std::deque<int> numbers;
numbers.push_back(20);
numbers.push_back(30);
numbers.push_front(10);
for (int value : numbers)
{
std::cout << value << " ";
}
return 0;
}
実行結果は次のとおりです。
10 20 30
push_front()では先頭へ、push_back()では末尾へ要素を追加できます。
先頭への追加を頻繁に行う処理では、vectorよりdequeのほうが適しています。
ランダムアクセスが可能
dequeは、vectorと同じように[]演算子を使って任意の位置にアクセスできます。
std::deque<int> numbers = {10, 20, 30};
std::cout << numbers[0] << std::endl;
std::cout << numbers[2] << std::endl;
実行結果は次のとおりです。
10
30
at()を使用することもできます。
std::cout << numbers.at(1) << std::endl;
[]は範囲チェックを行いません。
一方、at()では範囲外の位置を指定するとstd::out_of_range例外が送出されます。
全要素が連続したメモリに配置されるとは限らない
vectorでは、すべての要素が連続したメモリ領域に格納されることが保証されています。
一方、dequeでは、全要素が一つの連続したメモリ領域に配置されることは保証されていません。
一般的な実装では、複数のメモリブロックを内部で管理する構造が採用されています。
ただし、具体的な内部構造はC++標準によって固定されているわけではなく、処理系によって異なる場合があります。
この点はvectorとの大きな違いです。
dequeの基本的な宣言方法
空のdequeを作成する
空のdequeを作成する場合は、次のように記述します。
std::deque<int> numbers;
この時点では要素数は0です。
初期値を指定して作成する
初期化リストを使えば、作成時に要素を指定できます。
std::deque<int> numbers = {10, 20, 30, 40};
C++11以降では一般的な初期化方法です。
要素数を指定する
指定した数だけ要素を持つdequeを作成することもできます。
std::deque<int> numbers(5);
intの場合は値初期化されるため、各要素は0になります。
0 0 0 0 0
要素数と初期値を指定する
次のように記述すると、すべての要素を同じ値で初期化できます。
std::deque<int> numbers(5, 100);
この場合、内容は次のようになります。
100 100 100 100 100
dequeに要素を追加する方法
push_back()で末尾に追加する
push_back()は、コンテナの末尾に要素を追加するメンバ関数です。
std::deque<int> numbers;
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
結果は次のようになります。
10 20 30
push_front()で先頭に追加する
push_front()を使用すると、先頭に要素を追加できます。
std::deque<int> numbers;
numbers.push_front(30);
numbers.push_front(20);
numbers.push_front(10);
結果は次のとおりです。
10 20 30
push_front()を高速に利用できることが、dequeの代表的な強みです。
emplace_back()で末尾に直接構築する
クラスや構造体などのオブジェクトを格納する場合は、emplace_back()も利用できます。
#include <deque>
#include <string>
#include <utility>
struct User
{
std::string name;
int age;
User(std::string n, int a)
: name(std::move(n)), age(a)
{
}
};
int main()
{
std::deque<User> users;
users.emplace_back("Alice", 25);
}
emplace_back()は、渡された引数を利用してコンテナの末尾に要素を直接構築します。
emplace_front()で先頭に直接構築する
先頭にオブジェクトを直接構築したい場合は、emplace_front()を使用します。
users.emplace_front("Bob", 30);
クラスや構造体をdequeに格納するときに便利なメンバ関数です。
dequeから要素を削除する方法
pop_back()で末尾を削除する
pop_back()を使うと、末尾の要素を削除できます。
std::deque<int> numbers = {10, 20, 30};
numbers.pop_back();
結果は次のとおりです。
10 20
pop_back()は、削除した値を戻り値として返しません。
削除前の値が必要な場合は、先にback()で取得します。
int value = numbers.back();
numbers.pop_back();
pop_front()で先頭を削除する
pop_front()を使用すると、先頭の要素を削除できます。
std::deque<int> numbers = {10, 20, 30};
numbers.pop_front();
結果は次のようになります。
20 30
こちらも削除した値は返しません。
また、空のdequeに対してpop_front()やpop_back()を呼び出してはいけません。
安全に使用するなら、次のようにempty()で確認します。
if (!numbers.empty())
{
numbers.pop_front();
}
erase()で途中の要素を削除する
任意の位置にある要素を削除したい場合はerase()を使用します。
std::deque<int> numbers = {10, 20, 30, 40};
numbers.erase(numbers.begin() + 1);
結果は次のとおりです。
10 30 40
ただし、途中の要素を削除すると周辺の要素を移動する必要があるため、先頭や末尾からの削除より一般的にコストが高くなります。
dequeの要素を取得する方法
[]演算子で取得する
添字を使用して要素へアクセスできます。
std::deque<int> numbers = {10, 20, 30};
std::cout << numbers[1];
実行結果は次のとおりです。
20
ただし、[]では範囲チェックが行われません。
存在しない位置を指定すると未定義動作になるため注意が必要です。
at()で安全に取得する
at()は範囲チェックを行います。
std::cout << numbers.at(1);
範囲外の位置を指定した場合は、std::out_of_range例外が送出されます。
安全性を重視する場合に便利です。
front()で先頭要素を取得する
先頭の要素を取得したい場合はfront()を使用します。
std::cout << numbers.front();
back()で末尾要素を取得する
末尾の要素はback()で取得できます。
std::cout << numbers.back();
空のdequeに対してfront()やback()を呼び出してはいけません。
次のように事前に確認すると安全です。
if (!numbers.empty())
{
std::cout << numbers.front();
}
dequeの要素数を調べる方法
size()で要素数を取得する
size()を使うと、現在格納されている要素数を取得できます。
std::deque<int> numbers = {10, 20, 30};
std::cout << numbers.size();
実行結果は次のとおりです。
3
size()の戻り値は、コンテナのsize_typeです。
通常は符号なし整数型になります。
empty()で空かどうかを調べる
empty()を使うと、要素が一つも存在しないかを判定できます。
if (numbers.empty())
{
std::cout << "空です";
}
空ならtrue、一つ以上要素が存在すればfalseを返します。
要素の有無だけを確認したい場合は、size() == 0よりもempty()を使うと意図が分かりやすくなります。
dequeをループ処理する方法
範囲for文を使用する
C++11以降では、範囲for文を使うと簡潔に記述できます。
std::deque<int> numbers = {10, 20, 30};
for (int value : numbers)
{
std::cout << value << " ";
}
参照を使って要素を変更する
要素を直接変更したい場合は参照を使用します。
for (int& value : numbers)
{
value *= 2;
}
元の要素が、
10 20 30
だった場合、処理後は次のようになります。
20 40 60
const参照を使用する
大きなオブジェクトをコピーせず読み取りだけ行いたい場合は、const参照が便利です。
for (const auto& value : numbers)
{
std::cout << value << std::endl;
}
イテレータを使用する
イテレータを使って走査することもできます。
for (auto it = numbers.begin(); it != numbers.end(); ++it)
{
std::cout << *it << " ";
}
dequeのイテレータはランダムアクセスイテレータなので、次のような操作も可能です。
auto it = numbers.begin() + 2;
dequeを空にする方法
clear()ですべて削除する
すべての要素を削除したい場合はclear()を使用します。
std::deque<int> numbers = {10, 20, 30};
numbers.clear();
実行後は、
numbers.empty() == true
numbers.size() == 0
となります。
ただし、clear()を呼び出したからといって、内部で確保されていたメモリが必ずすべてOSへ返却されるとは限りません。
メモリの管理方法は実装にも依存します。
dequeの途中に要素を挿入する方法
insert()を使用する
任意の位置に要素を追加したい場合はinsert()を使用できます。
std::deque<int> numbers = {10, 30};
numbers.insert(numbers.begin() + 1, 20);
結果は次のとおりです。
10 20 30
ただし、途中への挿入では周辺の要素を移動する処理が必要になります。
そのため、先頭や末尾への追加ほど効率的ではありません。
dequeの計算量
主な操作の計算量
代表的な操作の計算量は、概ね次のとおりです。
| 操作 | 計算量 |
|---|---|
push_front() | O(1) |
push_back() | O(1) |
pop_front() | O(1) |
pop_back() | O(1) |
operator[] | O(1) |
at() | O(1) |
front() | O(1) |
back() | O(1) |
size() | O(1) |
| 途中への挿入・削除 | O(n) |
dequeは、両端操作とランダムアクセスをどちらも効率的に行えることが特徴です。
ただし、途中への挿入・削除では要素移動が発生するため、基本的に要素数に比例するコストがかかります。
dequeとvectorの違い
先頭への追加・削除性能が異なる
dequeとvectorは似ていますが、特に先頭操作の性能に大きな違いがあります。
| 比較項目 | deque | vector |
|---|---|---|
| 末尾への追加 | O(1) | 償却O(1) |
| 末尾からの削除 | O(1) | O(1) |
| 先頭への追加 | O(1) | O(n) |
| 先頭からの削除 | O(1) | O(n) |
| ランダムアクセス | O(1) | O(1) |
| 全要素の連続配置 | 保証されない | 保証される |
| 両端操作 | 得意 | 先頭操作は不得意 |
| C APIとの相性 | あまり向かない | 良い |
| キャッシュ効率 | 一般にやや不利 | 一般に高い |
vectorで先頭に要素を追加すると、後続の多数の要素を移動させる必要があります。
一方、dequeではpush_front()を定数時間で行えます。
vectorのpush_back()は償却O(1)
vector::push_back()は通常高速ですが、厳密には償却O(1)です。
内部容量が不足すると、より大きな連続メモリ領域を確保して既存要素を移動する処理が発生することがあります。
その1回の処理だけを見ればO(n)になる場合がありますが、一連の追加操作全体で見ると償却O(1)になります。
dequeとlistの違い
dequeはランダムアクセスできる
std::listも先頭と末尾の操作を高速に行えるコンテナですが、dequeとは内部構造や得意な処理が異なります。
| 比較項目 | deque | list |
|---|---|---|
push_front() | 高速 | 高速 |
push_back() | 高速 | 高速 |
| 添字アクセス | 可能 | 不可 |
begin() + n | 可能 | 不可 |
| ランダムアクセス | 可能 | 不可 |
| 任意位置の挿入・削除 | O(n)になり得る | 位置が分かっていればO(1) |
例えば、dequeでは次のようにアクセスできます。
numbers[100];
一方、listではoperator[]が用意されていません。
両端操作とランダムアクセスの両方が必要なら、dequeが有力な選択肢になります。
dequeをキューとして使用する方法
FIFOを実装する
dequeは、FIFO（First In, First Out）のキューとして使用できます。
#include <iostream>
#include <deque>
int main()
{
std::deque<int> queue;
queue.push_back(10);
queue.push_back(20);
queue.push_back(30);
while (!queue.empty())
{
std::cout << queue.front() << std::endl;
queue.pop_front();
}
return 0;
}
実行結果は次のとおりです。
10
20
30
末尾へ追加し、先頭から削除することでFIFOを実現できます。
単純なキューならstd::queueも選択肢
単純にFIFO処理だけを行いたいのであれば、std::queueを利用する方法もあります。
#include <queue>
std::queue<int> q;
std::queueはコンテナアダプタであり、デフォルトでは内部コンテナとしてstd::dequeを使用します。
FIFO操作だけが必要なら、std::queueを使うことでコードの意図を明確にできます。
dequeをスタックとして使用する方法
LIFOを実装する
末尾に追加し、末尾から取り出せばLIFO（Last In, First Out）のスタックとして使用できます。
#include <iostream>
#include <deque>
int main()
{
std::deque<int> stack;
stack.push_back(10);
stack.push_back(20);
stack.push_back(30);
while (!stack.empty())
{
std::cout << stack.back() << std::endl;
stack.pop_back();
}
return 0;
}
実行結果は次のとおりです。
30
20
10
ただし、スタックとしてのみ利用するのであれば、std::stackを使ったほうがコードの目的が明確になります。
dequeのメリット
両端への追加・削除が高速
dequeの最大のメリットです。
例えば、次のような処理を頻繁に繰り返す場合に向いています。
data.push_back(value);
data.pop_front();
新しいデータを末尾へ追加し、古いデータを先頭から削除する処理を効率的に実装できます。
ランダムアクセスも可能
listとは異なり、添字を使ったアクセスができます。
data[100];
そのため、両端操作を行いつつ、途中の要素へ高速にアクセスしたい場合にも利用できます。
vectorのような全要素の再配置を必要としにくい
vectorでは容量が不足すると、より大きな連続メモリ領域を確保し、既存要素を移動することがあります。
dequeでは通常、複数のメモリブロックを管理する方式が使われるため、コンテナ全体の要素を一つの巨大な領域へまとめて移動する必要がありません。
dequeのデメリット
vectorよりキャッシュ効率が低くなりやすい
vectorは全要素が連続したメモリに配置されます。
そのため、要素を先頭から順番に走査する処理では、CPUキャッシュを利用しやすい傾向があります。
一方、dequeでは全要素が連続していないため、単純な順次走査ではvectorより不利になる場合があります。
ただし、実際の速度はCPU、コンパイラ、要素型、データ量、アクセスパターンなどによって変化します。
性能が重要な場合は、実際の環境でベンチマークを取るのが確実です。
連続メモリが必要な処理には向かない
例えば、C APIへ配列を渡す場合など、連続したメモリ領域を必要とする処理があります。
vectorなら次のように利用できます。
std::vector<int> values = {1, 2, 3};
some_function(values.data(), values.size());
dequeでは全要素の連続配置が保証されていないため、コンテナ全体を同じように連続配列として扱うことはできません。
少数要素ではメモリ効率が悪くなる場合がある
dequeは内部で複数のメモリブロックや管理情報を持つことがあります。
そのため、要素数が非常に少ない場合は、vectorより内部オーバーヘッドが大きくなる可能性があります。
dequeのイテレータ無効化に注意する
push_front()やpush_back()後のイテレータ
dequeでは、コンテナへ要素を追加すると既存のイテレータが無効になる場合があります。
例えば、次のようなコードには注意が必要です。
std::deque<int> numbers = {10, 20, 30};
auto it = numbers.begin();
numbers.push_back(40);
// 変更前に取得したitをそのまま使わない
特にpush_front()やpush_back()では、既存要素への参照は維持される一方、イテレータは無効化されます。
そのため、コンテナを変更した後もイテレータを使う必要がある場合は、必要に応じて取得し直すのが安全です。
vectorとは無効化ルールが異なる
vectorでは再確保が発生すると、既存要素へのイテレータだけでなく、参照やポインタも無効になる可能性があります。
dequeとは無効化ルールが異なるため、両者を同じ感覚で扱わないことが重要です。
dequeが向いているケース
先頭と末尾を頻繁に操作する処理
dequeは、次のような用途に適しています。
- 先頭と末尾の両方に頻繁に要素を追加する
- 先頭と末尾の両方から頻繁に要素を削除する
- FIFO形式のデータ処理
- 双方向キュー
- スライディングウィンドウ
- 幅優先探索
- 一定件数だけ履歴を保存する処理
- 両端操作とランダムアクセスの両方が必要な処理
例えば、最新10件のデータだけ保持したい場合は次のように書けます。
std::deque<int> history;
history.push_back(100);
if (history.size() > 10)
{
history.pop_front();
}
このように、新しいデータを末尾へ追加し、古いデータを先頭から削除する処理はdequeが得意です。
dequeが向いていないケース
末尾にしか要素を追加しない場合
基本的に末尾へ要素を追加するだけなら、通常はvectorが第一候補になります。
data.push_back(value);
vectorはメモリが連続しているため、順次アクセス性能や外部APIとの連携などで有利です。
C APIへ配列を渡す場合
連続したメモリ領域が必要ならvectorのほうが適しています。
大量の要素を順番に走査する場合
大量のデータを単純に先頭から末尾まで走査することが中心なら、連続メモリを使用するvectorのほうが高い性能を発揮する可能性があります。
dequeの実践的なサンプルコード
主要な操作をまとめて使用する
次のコードでは、dequeの代表的な操作をまとめて確認できます。
#include <iostream>
#include <deque>
int main()
{
std::deque<int> numbers;
// 末尾に追加
numbers.push_back(20);
numbers.push_back(30);
// 先頭に追加
numbers.push_front(10);
std::cout << "全要素:" << std::endl;
for (const int value : numbers)
{
std::cout << value << " ";
}
std::cout << std::endl;
// 要素へのアクセス
std::cout << "先頭: " << numbers.front() << std::endl;
std::cout << "末尾: " << numbers.back() << std::endl;
std::cout << "2番目: " << numbers[1] << std::endl;
// 先頭を削除
numbers.pop_front();
// 末尾を削除
numbers.pop_back();
std::cout << "削除後:" << std::endl;
for (const int value : numbers)
{
std::cout << value << " ";
}
return 0;
}
最初は次の3要素が格納されています。
10 20 30
その後、先頭の10と末尾の30を削除するため、最終的に残るのは次の値です。
20
dequeを使うときに覚えておきたいポイント
「両端操作＋ランダムアクセス」が最大の特徴
std::dequeは、vectorのようにランダムアクセスを行いながら、先頭と末尾への追加・削除も高速に行いたい場合に便利なコンテナです。
まずは次のメンバ関数を覚えておくとよいでしょう。
push_front()
push_back()
pop_front()
pop_back()
front()
back()
size()
empty()
at()
operator[]
末尾への追加を中心に使用するなら、一般的にはvectorが第一候補です。
一方、先頭と末尾の両方を頻繁に操作するなら、dequeを検討する価値があります。
また、FIFOだけが必要ならstd::queue、LIFOだけが必要ならstd::stackを利用すると、コードの目的をより明確にできます。
dequeを理解するうえでは、特に「両端への追加・削除が高速」「ランダムアクセスが可能」「全要素の連続配置は保証されない」という3つの特徴を押さえておくことが重要です。
以上、C++のdequeの特徴や使い方についてでした。
最後までお読みいただき、ありがとうございました。
