dequeの使い方と実現

Dequeとは「double ended queue」の略で、両端キューは末尾や頭部に要素を挿入しても非常に迅速です.中間に要素を挿入すると、中間の他の要素を移動する必要があるため、時間がかかります.デュアル・エンド・キューはランダム・アクセスのデータ型で、シーケンスの両端で迅速に挿入および削除する機能を提供し、必要に応じて自分のサイズを変更し、標準的なC++データ構造のキューのすべての機能を完了します. 
Vectorは一方向開口の連続線形空間であり、dequeは双方向開口の連続線形空間である.Dequeオブジェクトは、キューの両端に要素を配置したり削除したりするのに効率的ですが、ベクトルvectorはシーケンスの末尾を挿入するときにのみ効率的です.dequeとvectorの最大の違いは、dequeが一定時間にわたってヘッダに要素の挿入または除去操作を行うことを可能にすることである.2つ目は、dequeがいわゆるcapacity観念を持たないことである.これは、動的にセグメント連続空間で結合されているため、いつでも新しい空間を追加してリンクすることができるからである.すなわちvectorのように「古い空間が不足しているため、より大きな空間を再構成し、要素をコピーして古い空間を解放する」ということはdequeでは起こりません.したがって、dequeは、いわゆる空間予約(reserved)機能を提供する必要はない. 
DequeはRandom Access Iteratorも提供していますが、反復器は通常のポインタではなく、複雑さとvectorは同じではありません.これはもちろん、各演算レベルに関連しています.したがって、必要でない限り、dequeではなくvectorを使用することをできるだけ選択する必要があります.Dequeに対するソート操作は、最も効率的にするために、dequeを1つのvectorに完全にコピーし、vectorをソートした後(STLのsortアルゴリズムを利用)、dequeにコピーすることができます. 
dequeは、シーケンスの両端要素の追加と削除操作を最適化した基本シーケンスコンテナです.通常、いくつかの独立したブロックからなり、第1のブロックはある方向に拡張され、最後のブロックは別の方向に拡張される.これにより、vectorのようにすべてのオブジェクトを連続したメモリブロックに保存するのではなく、複数の連続したメモリブロックに迅速にランダムにアクセスできます.これらのブロックおよび順序の追跡は、マッピング構造に保存される.
Dequeコンテナの宣言

#include  //    
deque deq;  //          type     que
deque deq(size);  //        type、  size               que
deque deq(size, value);  //          type、  size value       que
deque deq(mydeque);  // deq mydeque     
deque deq(first, last);  //      first、last         deq

dequeの共通メンバー関数:

deq[]:双方向キュー内の単一の要素にアクセスします.

deq.front():最初の要素の参照を返します.

deq.back():最後の要素の参照を返します.

deq.push_front(x):要素xを双方向キューのヘッダに挿入します.

deq.pop_front():双方向キューの最初の要素をポップアップします.

deq.push_back(x):要素xを双方向キューの末尾に挿入します.

deq.pop_back():双方向キューの最後の要素をポップアップします.

Dequeの特徴:

はランダムアクセス、すなわち[]およびat()をサポートするが、パフォーマンスはvectorほどよくない.

は内部で挿入および削除操作を行うことができるが、listには及ばない.

dequeの両端は要素をすばやく挿入および削除できますが、vectorは末尾でのみ実行できます.

dequeの要素アクセスと反復器の操作は、dequeの内部構造に間接的なプロセスが1つ増えるため、少し遅いです.

deque反復器は、一般的なポインタではなく、特殊なスマートポインタであり、異なるブロック間でジャンプする必要があります.

dequeは、max_のより多くの要素を含むことができる.sizeは、メモリが1つだけではないため、より大きくなる可能性があります.

dequeでは、容量とメモリの割り当てタイミングの制御はサポートされていません.

最初と最後の両端を除く他の場所で要素を挿入および削除すると、deque要素を指すpointers、references、iteratorsが無効になります.ただし、dequeのメモリ再割り当てはvectorよりも優れています.内部構造はすべての要素をコピーする必要がないことを示しています.

dequeのメモリブロックが使用されなくなると解放され、dequeのメモリサイズが縮小されます.ただし、そうするかどうか、およびどのようにするかは、実際の操作バージョンによって定義されます.

dequeは容量操作を提供しません:capacity()とreverse()ですが、vectorはできます.

≪インスタンス｜Instance｜emdw≫

#include
#include
#include
using namespace std;
int main(void)
{
	int i;
	int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
	deque q;
	for (i = 0; i <= 9; i++)
	{
		if (i % 2 == 0)
			q.push_front(a[i]);
		else
			q.push_back(a[i]);
	}                                  /*         : {8,6,4,2,0,1,3,5,7,9}*/
	q.pop_front();
	printf("%d
", q.front());    /*             (6)*/
	q.pop_back();
	printf("%d
", q.back());     /*               (7)*/
	deque::iterator it;
	for (it = q.begin(); it != q.end(); it++) {
		cout << *it << '\t';
	}
	cout << endl;
	system("pause");
	return 0;
}