【C++STL学習の3】容器deque深く学習

C++STLコンテナdequeはvectorとよく似ており,要素を管理するために動的配列を採用している.
Dequeを使用する前にヘッダファイルを含める必要があります.
#include
名前空間std内に定義されたclass templateです.
templateclass _Ax = allocator<_ty>>class deque;
最初のtemplateパラメータは要素の型別を表し、2番目の有無はメモリモデルを指定します.一般的には、デフォルトのメモリモデルが使用されます.
vectorとは異なりdequeの動的配列の先頭が開放されているため,先頭で迅速な挿入と削除操作が可能である.
dequeの論理構造:
Dequeの内部構造
dequeは、シーケンスの両端要素の追加と削除操作を最適化した基本シーケンスコンテナです.通常、いくつかの独立したブロックからなり、第1のブロックはある方向に拡張され、最後のブロックは別の方向に拡張される.これにより、vectorのようにすべてのオブジェクトを連続したメモリブロックに保存するのではなく、複数の連続したメモリブロックに迅速にランダムにアクセスできます.これらのブロックおよび順序の追跡は、マッピング構造に保存される.
その内部構造は下図の通りです.
Dequeの特徴:
1、ランダムアクセス、すなわち[]およびat()をサポートするが、性能はvectorほどよくない.
2、内部で挿入と削除はできますが、性能はlistに及ばない.
dequeとvectorの違い:
1、両端ともエレメントをすばやく挿入、削除できます.vectorは末端でしか行えません.
2、dequeの要素アクセスと反復器の操作は少し遅いです.Dequeの内部構造には間接的なプロセスが1つ増えるからです.
3、反復器は特殊なスマートポインタで、一般的なポインタではありません.異なるブロック間をジャンプする必要があります.
4、dequeはより多くの要素を含むことができ、そのmax_sizeはもっと大きいかもしれません.メモリが1つだけではないからです.
5、容量とメモリの割り当てタイミングの制御をサポートしない.
注意:最初と最後の両端を除く場所で要素を挿入および削除すると、deque要素を指すpointers、references、iteratorsが無効になります.ただし、dequeのメモリ再割り当てはvectorより優れています.内部構造は、すべての要素をコピーする必要がないためです.
6、dequeのメモリブロックが使用されなくなった場合、解放されます.dequeのメモリサイズは縮小可能です.しかし、そうするかどうか、どうするかは実作バージョンで定義されています.
 
dequeとvectorの類似の特性:
1.すべてのエレメントが移動されるため、中間部でのエレメントの挿入と削除が比較的遅い.
2、反復器は即時アクセス反復器に属する.
 
Dequeを使用する場合は、次のようにします.
1.両端にエレメントを挿入、削除する必要があります.
2.コンテナ内の要素を参照する必要はありません.
3、容器に使用しなくなった元素を解放するように要求する.
 
Dequeの操作関数
コンストラクション関数とコンストラクション関数:
非変動アクション:
変動アクション:
Dequeの各操作はvectorと異なる2点だけです.
dequeは容量操作:capacity()とreverse()を提供しません.
dequeは、関数の最初と最後の要素の挿入と削除を直接提供します.
その他はvectorと同じです.
注意:
1、at()関数を除いて、他のメンバー関数はインデックスまたは反復器が有効かどうかをチェックしません.
2、要素の挿入と削除によってメモリが再割り当てされる可能性があります.したがって、deque要素を指すpointers、reference、iteratorsは、挿入または削除操作によって無効になります.唯一の例外は、最初の最後に要素を挿入した後もpointersとreferenceが有効である可能性があります.
プログラムの例:

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
	deque strDeq;

	strDeq.assign(4,string("CHINA"));
	strDeq.push_back("first_string");
	strDeq.push_front("last_string");

	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator(cout," "));
	cout << endl;
	cout << endl;

	for(int i = 0;i < strDeq.size();++i)
		cout << "strDeq[" << i << "] : " << strDeq[i] << endl;
	cout << endl;
	
	for(int i = 0;i < strDeq.size();++i)
		cout << "strDeq.at(" << i << ") : " << strDeq.at(i) << endl;
	cout << endl;

	strDeq.pop_front();
	strDeq.pop_back();

	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator(cout," "));
	cout << endl;
	cout << endl;

	for(int i = 1;i < strDeq.size();++i)
		strDeq[i] = "pre" + strDeq[i];
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator(cout," "));
	cout << endl;
	cout << endl;

	strDeq.resize(4,"resized string");

	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator(cout," "));
	cout << endl;
	cout << endl;
}

実行結果: