Deque

C ++標準テンプレートライブラリ（STL）のDeque

動的配列クラスで、末尾だけでなく先頭への要素追加・削除も が可能なクラス

先頭への要素追加、削除が出来るため、「両端キュー」と呼ばれる。

動的配列とは

配列サイズを自由に増減できる配列のこと。可変長配列ともいわれる。

コンテナクラスとは

Dequeなどのように、クラス、構造体、PODint 等のいわゆるプレーンな古い型; Plain Old Data）入れることが出来るものをコンテナクラスという。

C++には、多種多様なコンテナクラスが用意されている。

Deque以外に、よく使われるコンテナクラスに、vectorがある。

先頭付近での挿入削除処理が多い場合に、Dequeを使用する。

参考：

使用方法：

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型> オブジェクト名;

deque<int> dq;

//上記名前異空間(using namespace std;)を指定しない場合

//std::deque<int> dq;　とする。

//処理

}

※dequeはクラスなので、使用するために実体化する必要がある。

実体化したものをオブジェクト又はインスタンスと呼ぶ。

このオブジェクトの要素数は0

注意事項：

初期化時にデフォルトコンストラクタが呼ばれることがある。

バッファ拡張時にコピーコンストラクタが呼ばれることがある。

それらが定義されている必要がある。

要素数を指定して、使用する。

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型> オブジェクト名(要素数);

deque<int> dq(10);

//処理

}

要素の初期化

※値が全て同じ場合使用可能

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型> オブジェクト名(要素数);

deque<int> dq(10,5);

//処理

}

例：

code:c++

//ヘッダファイルのインクルード

using namespace std;

int main(void){

//変数宣言

int i; //カウント用変数

// Your code here!

deque<int> dq(4,3); //dequeにより、配列を用意

for(i=0;i<10;i++){

}

}

要素の初期化

※初期化時に値の違うものを使用する場合

※VS2013以降使用可能

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型> オブジェクト名{初期化値1,初期化値2,初期化値3};

deque<int> dq{1,5,3};

//処理

}

例：

code:c++

//ヘッダファイルのインクルード

using namespace std;

int main(void){

//変数宣言

int i; //カウント用変数

// Your code here!

deque<int> dq{4,3,1}; //dequeにより、配列を用意

for(i=0;i<10;i++){

}

}

dequeで用意されているメンバ関数を使用する。

一部を紹介する。

front()　：要素の先端を参照

back()　：要素の終端を参照

constructor() : コンストラクタ、dequeを初期化する。

destrctor() : デストラクタ

size() : サイズ(要素数)を返す。

at(n) : std::dequeのn番目の要素の参照を取得。(範囲外アクセスの場合に例外を送出する)

operator[] : std::dequeのn番目の要素の参照を取得。(範囲外アクセスの動作が未規定、処理速度が早い)

shirink_to_fit :利用していないメモリを解放してメモリ使用料を減らす。

※front()とback()は、値ではなく参照を返すため、値を代入する事も可能

使用方法：

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型> オブジェクト名(要素数);

deque<int> dq(10,5);

//処理

//基本：オブジェクト名.関数名();で使用する。

//変数　= オブジェクト名.関数名();

int x;

int y;

x = dq.front();

y= dq.back();

cout<<"dq.front："<<dq.front()<<endl;

cout<<"x："<<x<<endl;

cout<<"y："<<y<<endl;

}

例：

code:c++

//ヘッダファイルのインクルード

using namespace std;

int main(void){

//変数宣言

int x;

int y;

int z;

// Your code here!

deque<int> dq{4,3,1}; //dequeにより、配列を用意

x = dq.front(); //要素の最初を格納

y = dq.back(); //要素の最後を格納

//要素の最後を133に変更

dq.front() = 133;

z=dq.front(); //要素の最後を格納

cout<<"x："<<x<<endl;

cout<<"y："<<y<<endl;

cout<<"z："<<z<<endl;

}

例2：

code:c++

//ヘッダファイルのインクルード

using namespace std;

int main(void){

//変数宣言

int x;

int y;

int z;

// Your code here!

deque<int> dq{0,1,2,3,4,5,6}; //dequeにより、配列を用意

deque<int> dq2(5,3);

x = dq.size(); //size()を使用。　要素数を返す。

y = dq.at(5); //at()を使用 5番目の値を返す。

// y = dq.at(10); //エラーを出力

cout<<"x："<<x<<endl;

cout<<"y："<<y<<endl;

cout<<"z："<<z<<endl;

}

例3：文字の表示

code:c++

// string::at

using namespace std;

int main ()

{

deque<unsigned char> x(5,'B');

int i;

int y = x.size();

unsigned char z = x.at(2);

std::cout << y<<endl;

std::cout << z<<endl;

return 0;

}

deque、vector、listなどのコンテナクラスにはイテレータというものが用意されている。

インテレータとは

抽象化されたポインタのこと

*演算子でイテレータが指す要素を参照、変更

インクリメントで、次の要素に移動

デクリメントで、前の要素に移動することが可能。

使用方法：

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型>::iterator オブジェクト名;

deque<int>::iterator dq;

//処理

}

下記autoでも可能

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型> オブジェクト名;

//auto オブジェクト名;

deque<int>::iterator dq;

auto dq;

//処理

}

例：

code:c++

//ヘッダファイルのインクルード

using namespace std;

int main(void){

//変数宣言

int x;

int y;

int z;

// Your code here!

deque<int> dq{5,1,2,3,4,5,6}; //dequeにより、配列を用意

deque<int> ::iterator itr; //iteratorの宣言

itr = dq.begin();

auto itr2 = dq.begin(); //autoでのiteratorの宣言

cout<<"itr："<<*itr<<endl; //1番目の要素を表示

cout<<"itr2："<<*itr2<<endl; //1番目の要素を表示

itr2++; //2番目の要素に移動

cout<<"itr2："<<*itr2<<endl; //2番目の要素を表示

*itr2 = 90; //2番目の要素の値を90に変更

//dqのすべての要素を表示

cout <<"すべての要素を表示"<<endl;

for(itr = dq.begin();itr<dq.end();++itr){ //itrのしているする要素を1ずつ移動し、最後まで実行する。

cout<<"itr："<<*itr<<endl;

}

}

データの追加

使用メンバ関数：

push_front() ：先端に要素を追加

push_back() ：末尾に要素を追加

front,backどちらも要素数に依らず常に一定時間で処理が出来る。

insert(iterator,値) ：任意の位置に要素を挿入する。

要素数によって、処理時間が変わる。　要素数が増えると処理時間がその分増す。

データ列の途中に頻繁に挿入、削除などを行う場合、std::dequeではなく、

std::listやギャップベクターなどの他のコンテナクラスの使用を検討した方が良い。

使い方：

code:c++

using namespace std; //名前空間の指定

int main()

{

//deque<型> オブジェクト名;

deque<int> dq;

//先頭に値を追加する

//オブジェクト名.push_front(追加する値);

dq.push_front(10); //先頭に10を追加

//末尾に値を追加する。

//オブジェクト名.push_back(追加する値);

dq.push_back(20); //末尾に20を追加

//n番目に値を追加する。

//dq.insert(dq.begin()+ n, 数値);

//処理

}

例：

code:c++

//ヘッダファイルのインクルード

using namespace std;

int main(void){

//変数宣言

int i; //カウント用変数

// Your code here!

deque<int> dq{0,1}; //dequeにより、配列を用意

for(i=0;i<dq.size();i++){

}

//先頭に数値を追加する。

dq.push_front(10);

//末尾に20を追加する。

dq.push_back(20);

cout<<"先頭と末尾に数値を追加"<<endl;

for(i=0;i<dq.size();i++){

}

//2番目の要素に、2を追加

dq.insert(dq.begin()+2,3);

for(i=0;i<dq.size();i++){

}

}

emplace_front(コンストラクタ引数) ：先頭に要素を直接構築で追加

emplace_back(コンストラクタ引数) ：末尾に要素を直接構築で追加