C++ dequeの使い方

dequeとは

• vectorと似た構造だが、先頭 or 末尾への追加・削除が高速で行えるという特徴がある。
• ↓↓日本語リファレンス(本記事での参考サイト)

cpprefjp.github.io

基本機能

宣言と初期化

dequeの宣言はvectorと同様にできます。

std::deque<int> deq1; // 宣言のみ
std::deque<int> deq2{ 1, 2, 3 }; //宣言と初期化を同時に

要素数の取得

変数名.size()で要素数を取得できる。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> deq{ 1, 2, 3 };
    std::cout << "deq.size() = " << deq.size() << std::endl;
}

要素へのアクセス(先頭・末尾・任意)

要素へのアクセス方法は主に以下の3種類がある。

先頭	変数名.front()
任意のi番目	変数名.at(i)
末尾	変数名.back()

サンプルコード

#include <iostream>
#include <deque>

int main() {
	std::deque<int> deq{ 2, 4, 1, 3 };
	std::cout << "先頭：deq.front() = " << deq.front() << std::endl;
	std::cout << "2番目：deq.at(2) = " << deq.at(2) << std::endl;
	std::cout << "末尾：deq.back() = " << deq.back() << std::endl;
}

実行結果

先頭：deq.front() = 2
2番目：deq.at(2) = 1
末尾：deq.back() = 3

for文で全要素を表示

1. atとsizeを使った方法
2. 範囲for文を使った方法

の2つがある。

サンプルコード1(atとsizeを使用)

#include <iostream>
#include <deque>

int main() {
	std::deque<int> deq{ 2, 4, 1, 3 };
	for (int i = 0; i < deq.size(); i++)
		std::cout << deq.at(i) << ", ";
}

サンプルコード2(範囲for文を使用)

#include <iostream>
#include <deque>

int main() {
	std::deque<int> deq{ 2, 4, 1, 3 };
	for (int x: deq)
		std::cout << x << ", ";
}

実行結果(どちらも結果は同じ)

2, 4, 1, 3,

要素の追加(先頭・末尾・任意)

追加方法も主に3種類ある。追加したい要素をxとすれば以下のように表せる。

先頭	変数名.push_front(x)
任意番目	変数名.insert(イテレータ, x)
末尾	変数名.push_back(x)

サンプルコード

#include <iostream>
#include <deque>

int main() {
	std::deque<int> deq{ 2, 4, 1, 3 };
	
	deq.push_front(0); // 先頭に0を追加
	deq.insert(deq.begin() + 1, 10); // 先頭の次に10を追加
	deq.push_back(-1); // 末尾に-1を追加

	for (int x : deq)
		std::cout << x << ", ";
}

実行結果

0, 10, 2, 4, 1, 3, -1,

要素の削除(先頭・末尾・任意)

削除も主に3種類ある。

先頭	変数名.pop_front()
任意番目	変数名.erase(イテレータ)
末尾	変数名.pop_back(x)

サンプルコード

#include <iostream>
#include <deque>

int main() {
	std::deque<int> deq{ 0, 10, 2, 4, 1, 3, -1 };
	
	deq.erase(deq.begin() + 1); // 先頭の次(10)を削除
	deq.pop_front(); // 先頭(0)を削除
	deq.pop_back(); // 末尾を削除

	for (int x : deq)
		std::cout << x << ", ";
}

実行結果

2, 4, 1, 3,