STL-deque(両端キュー)

7049 ワード

Dequeの概要
dequeは「double-ended queue」の略で、vectorと同様にSTLのコンテナで、dequeは両端配列であり、vectorは単端である.
dequeはインタフェースでvectorとよく似ており、多くの操作の場所で直接置き換えることができます.
dequeはランダムに要素にアクセスできます(インデックス値の直接アクセスをサポートし、[]オペレータまたはat()メソッドを使用します.これは後で詳しく説明します).
dequeヘッダとテールの要素の追加または削除は非常に迅速です.ただし、エレメントを中央に挿入したり除去したりするのに時間がかかります.
#include
dequeオブジェクトのデフォルト構造
dequeはテンプレートクラスで実装され、dequeオブジェクトのデフォルト構造形式:deque deqT;
deque deqInt;//intを格納するdequeコンテナ.
deque deq Float;//floatを格納するdequeコンテナです.
deque deq String;//stringを格納するdequeコンテナ.
...
//括弧内では、ポインタタイプやカスタムタイプを設定することもできます.
dequeの最後の追加削除操作
理論知識:
deque.push_back(elem);//コンテナの末尾にデータを追加
deque.push_front(elem);//コンテナヘッダにデータを挿入
deque.pop_back();//コンテナの最後のデータを削除
deque.pop_front();//コンテナの最初のデータを削除
	deque deqInt;
	deqInt.push_back(1);
	deqInt.push_back(3);
	deqInt.push_back(5);
	deqInt.push_back(7);
	deqInt.push_back(9);
	deqInt.pop_front();
	deqInt.pop_front();
	deqInt.push_front(11);
	deqInt.push_front(13);
	deqInt.pop_back();
	deqInt.pop_back();
//deqInt  { 13,11,5}

dequeのデータアクセス
理論知識:
deque.at(idx);//インデックスidxが指すデータを返し、idxが境界を越えた場合out_を投げ出すof_range.
deque[idx];//インデックスidxが指すデータを返します.idxが境界を越えて異常を投げ出さないと、直接エラーが発生します.
deque.front();//最初のデータを返します.
deque.back();//最後のデータを返す
	deque deqInt;
	deqInt.push_back(1);
	deqInt.push_back(3);
	deqInt.push_back(5);
	deqInt.push_back(7);
	deqInt.push_back(9);
	int iA = deqInt.at(0);		//1
	int iB = deqInt[1];			//3
	deqInt.at(0) = 99;			//99
	deqInt[1] = 88;			//88

	int iFront = deqInt.front();	//99
	int iBack = deqInt.back();	//9
	deqInt.front() = 77;			//77
	deqInt.back() = 66;			//66

dequeと反復器
理論知識.
deque.begin();//コンテナ内の最初の要素の反復器を返します.
deque.end();//コンテナ内の最後の要素の後にある反復器を返します.
deque.rbegin();//コンテナ内の最後から最初の要素の反復器を返します.
deque.rend();//コンテナの最後の要素の後ろにある反復器を返します.
		deque deqInt;
		deqInt.push_back(1);
		deqInt.push_back(3);
		deqInt.push_back(5);
		deqInt.push_back(7);
		deqInt.push_back(9);

		for (deque::iterator it=deqInt.begin(); it!=deqInt.end(); ++it)
		{
			cout << *it;
			cout << "";
		}
	// 1 3 5 7 9

		for (deque::reverse_iterator rit=deqInt.rbegin(); rit!=deqInt.rend(); ++rit)
		{
			cout << *rit;
			cout << "";
		}
	//9 7 5 3 1

Dequeオブジェクトのパラメータ付き構造
理論知識.
deque(beg,end);//コンストラクション関数は[beg,end)区間の要素を自身にコピーします.この区間は左閉右開の区間であることに注意してください.
deque(n,elem);//コンストラクション関数はn個のelemを自身にコピーする.
deque(const deque &deq);//コピーコンストラクタ.
		deque deqIntA;
		deqIntA.push_back(1);
		deqIntA.push_back(3);
		deqIntA.push_back(5);
		deqIntA.push_back(7);
		deqIntA.push_back(9);

		deque deqIntB(deqIntA.begin(),deqIntA.end());		//1 3 5 7 9
		deque deqIntC(5,8);							//8 8 8 8 8
		deque deqIntD(deqIntA);						//1 3 5 7 9

dequeの付与
理論知識.
deque.assign(beg,end);//[beg,end)区間のデータコピーを自身に付与します.この区間は左閉右開の区間であることに注意してください.
deque.assign(n,elem);//n個のelemコピーを自身に割り当てます.
deque& operator=(const deque &deq);//等号オペレータの再ロード
deque.swap(deq);//vecを自分の要素と交換する
		deque deqIntA,deqIntB,deqIntC,deqIntD;
		deqIntA.push_back(1);
		deqIntA.push_back(3);
		deqIntA.push_back(5);
		deqIntA.push_back(7);
		deqIntA.push_back(9);

		deqIntB.assign(deqIntA.begin(),deqIntA.end());	// 1 3 5 7 9
		
		deqIntC.assign(5,8);						//8 8 8 8 8

		deqIntD = deqIntA;							//1 3 5 7 9

		deqIntC.swap(deqIntD);						//  

dequeのサイズ
理論知識.
deque.size();//コンテナ内の要素の数を返します.
deque.empty();//容器が空かどうかを判断する
deque.resize(num);//コンテナの長さをnumに再指定し、コンテナが長くなると新しい位置をデフォルト値で塗りつぶします.コンテナが短くなると、最後にコンテナの長さを超えた要素が削除されます.
deque.resize(num, elem);//コンテナの長さをnumに再指定し、コンテナが長くなるとelem値で新しい位置を埋めます.コンテナが短くなると、最後にコンテナの長さを超えた要素が削除されます.
		deque deqIntA;
		deqIntA.push_back(1);
		deqIntA.push_back(3);
		deqIntA.push_back(5);

		int iSize = deqIntA.size();  //3

		if (!deqIntA.empty())
		{
			deqIntA.resize(5);		//1 3 5 0 0
			deqIntA.resize(7,1);	//1 3 5 0 0 1 1
			deqIntA.resize(2);		//1 3
		}

dequeの挿入
理論知識.
deque.insert(pos,elem);//posの場所にelem要素のコピーを挿入し、新しいデータの場所を返します.
deque.insert(pos,n,elem);//pos位置にn個のelemデータを挿入し、戻り値はありません.
deque.insert(pos,beg,end);//pos位置に[beg,end)区間のデータを挿入し,戻り値はない.
	deque deqA;
	deque deqB;

	deqA.push_back(1);
	deqA.push_back(3);
	deqA.push_back(5);
	deqA.push_back(7);
	deqA.push_back(9);

	deqB.push_back(2);
	deqB.push_back(4);
	deqB.push_back(6);
	deqB.push_back(8);
	
	deqA.insert(deqA.begin(), 11);		//{11, 1, 3, 5, 7, 9}
	deqA.insert(deqA.begin()+1,2,33);		//{11,33,33,1,3,5,7,9}
	deqA.insert(deqA.begin() , deqB.begin() , deqB.end() );	//{2,4,6,8,11,33,33,1,3,5,7,9}

dequeの削除
理論知識.
deque.clear();//コンテナのすべてのデータを削除
deque.erase(beg,end);//[beg,end)区間のデータを削除し,次のデータの位置を返す.
deque.erase(pos);//pos位置のデータを削除し、次のデータの位置を返します.
        
deqInt  deque     ,        1,3,5,6,9  。
deque::iterator itBegin=deqInt.begin()+1;
deque::iterator itEnd=deqInt.begin()+3;
deqInt.erase(itBegin,itEnd);
//    deqInt      1,6,9    。



   deqInt   1,3,2,3,3,3,4,3,5,3,       3   
for(deque::iterator it=deqInt.being(); it!=deqInt.end(); )    //         ++it
{
   if(*it == 3)
   {
        it  =  deqInt.erase(it);       //       ,    3,                     。
         //  ,     ++it;  
   }
   else
   {
       ++it;
   }
}

//  deqInt     
deqInt.clear();			//    

demo
#include 
#include 
#include 
#include 

using namespace std;

void printDeque(deque &d)
{
	for (deque::iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << ' ';
	}
	cout << endl;
}

void dequeInit()
{
	deque d1;
	d1.push_back(1);
	d1.push_back(3);
	d1.push_back(5);

	d1.push_front(-11);
	d1.push_front(-33);
	d1.push_front(-55);
	printDeque(d1);
	// -55 -33 -11 1 3 5

	cout << "front element: " << d1.front() << endl;
	// front element: -55
	cout << "back element: " << d1.back() << endl;
	// back element: 5
	
	d1.pop_front();
	d1.pop_back();
	printDeque(d1);
	// -33 -11 1 3

	//   1 d1    
	deque::iterator it = find(d1.begin(), d1.end(), 1);
	if (it != d1.end()) {
		cout << "position of 1: " << distance(d1.begin(), it) << endl;
	}
	else {
		cout << "no 1
"; } // position of 1: 2 } int main() { dequeInit(); return 0; }