deque クラス

[機能]

　　deque は double-ended queue （二重終端キュー）の頭文字をとったものであり，シーケンスコンテナの一種です．vector と同様の機能を提供しますが，vector とは異なり，連続した位置のストレージに全ての要素を持つことを保証していません．なお，以下に示す関数において，一般に，insert，push_back，push_front よりも，emplace，emplace_back，emplace_front を使ったほうが処理効率は良くなります．

template <class T, class Allocator = allocator<T>>
    class deque		

[使用方法]

#include <deque>
using namespace std;
deque<T> 変数名;
   deque<int> x;   // 空の deque
   deque<int> x(3);   // 要素数が 3
   deque<int> x(5, 10);   // 5 つの要素を 10 で初期化
   deque<int> x(y.it1, y.it2);   // it1 から it2 の範囲で初期化
   deque<int> x(y);   // deque y で初期化
   deque<int> x ({1, 2, 3});   // 初期化子リスト，C++11
   deque<int> x {1, 2, 3};   // 初期化子リスト，C++11
   deque<int> x = {1, 2, 3};   // 初期化子リスト，C++11		

[メンバー関数等]

• template <class InputIterator> void assign(InputIterator start, InputIterator end)
  start と end で示されるシーケンスを代入する

• void assign(size_type n, const T &v)
  n 個の値 v を代入する

• void assign(initializer_list init) // C++11
  初期化子リストを使用して代入する

• reference at(size_type i)
• const_reference at(size_type i)
  i で示される要素を指す参照を返す

• iterator back()
• const_iterator back()
  最後の要素を指すイテレータを返す

• iterator begin()
• const_iterator begin()
  最初の要素を指すイテレータを返す

• const_iterator cbegin() // C++11
  先頭要素を指す読み取り専用イテレータ

• const_iterator cend() // C++11
  末尾の1つ次の要素を指す読み取り専用イテレータ

• void clear()
  すべての要素を削除する

• const_iterator crbegin() // C++11
  末尾の要素を指す読み取り専用逆イテレータ

• const_iterator crend() // C++11
  先頭の1つ前の要素を指す読み取り専用逆イテレータ

• template <class ... Args> iterator emplace(const_iterator it, Args&&... args) // C++11
  イテレータ it が指す場所の前に，要素を直接構築で挿入する（コピーもムーブもされない）．また，以下の 2 行目に示すように，ペアーを自動的に生成するような処理も可能である（ insert との違いに注意）．

  	deque<pair<int, double>> dq;
  	dq.emplace(dq.begin(), 5, 3.14);
  	dq.emplace(dq.begin(), make_pair(5, 3.14));
  	dq.insert(dq.begin(), make_pair(10, 1.23));
  	for (auto x : dq)
  		cout << x.first << " " << x.second << endl;			

• template <class ... Args> reference emplace_back(Args&&... args) // C++17
  直接構築で新たな要素を末尾に追加する（ push_back との違いに注意，emplace 参照）

• template <class ... Args> reference emplace_front(Args&&... args) // C++17
  直接構築で新たな要素を先頭に追加する（ push_front との違いに注意，emplace 参照）

• bool empty()
  コンテナが空か否かを返す

• iterator end()
• const_iterator end()
  最後の要素の次を指すイテレータを返す

• iterator erase(iterator it)
  イテレータ it が指す場所の要素を削除，削除された次の要素を指すイテレータを返す

• iterator erase(iterator start, iterator end)
  start から end までの要素を削除し，削除された次の要素を指すイテレータを返す

• iterator front()
• const_iterator front()
  最初の要素を指すイテレータを返す

• allocate_type get_allocator()
  アロケータを返す

• iterator insert(iterator it, const T& x)
• iterator insert(iterator it, size_type n, const T& x) // C++11
  イテレータ it が指す場所の前に（ n 個の）要素 x を挿入する

• template <class InputIterator> void insert(iterator it, InputIterator start, InputIterator end) // C++11
  イテレータ it が指す場所の前に，start と end で示されるシーケンスを挿入する

• iterator insert(const_iterator it, initializer_list init) // C++11
  イテレータ it が指す場所の前に初期化子リスト init を挿入する

• size_type max_size()
  格納できる最大の要素数を返す

• void pop_back()
  最後の要素を削除する

• void pop_front()
  最初の要素を削除する

• void push_back(const T& t)
  最後に要素を追加する

• void push_front(const T& t)
  最初に要素を追加する

• reverse_iterator rbegin()
• const_reverse_iterator rbegin()
  最後の要素を指す逆イテレータを返す

• reverse_iterator rend()
• const_reverse_iterator rend()
  最初の要素の 1 つ前を指す逆イテレータを返す

• void resize(size_type num) // C++11
  サイズを num に変更する．拡大する場合は，初期化された T 型オブジェクトのコピーを追加する．

• void resize(size_type num, T val = T()) // C++11
  サイズを num に変更する．拡大する場合は，val が末尾に追加される．

• void shrink_to_fit() // C++11
  利用していないメモリを解放してメモリ使用量を減らす

• size_type size()
  要素数を返す

• void swap(deque& other)
  2 つのコンテナの内容を入れ替える

[演算子の多重定義]

=  ==  <  <=  !=  >  >=  []		

[使用例]

1. deque の使用方法です．以下に示すプログラム例において，いくつかのコメント部分は，その上または下に記述された方法とほぼ同等なものであることを示しています（複数行の対応関係である場合もある）．

   #include <iostream>
   #include <deque>
   
   using namespace std;
   
   void print(string str, deque<int> &q) {
   	if (q.empty())
   		cout << "  コンテナ " << str << " は空です\n";
   	else {
   		cout << str << " の要素数： " << q.size() << endl;
   		for (auto x : q)
   			cout << " " << x;
   //		for (int i1 = 0; i1 < (int)q.size(); i1++)
   //			cout << " " << q[i1];
   		cout << endl;
   	}
   }
   
   int main()
   {
   					// 要素を最後に追加（サイズは自動的に増加）
   //	deque<int> q1 = {0, 1, 2, 3, 4};
   //	deque<int> q1 {0, 1, 2, 3, 4};
   	deque<int> q1;
   	for(int i1 = 0; i1 < 5; i1++)
   		q1.push_back(i1);
   	cout << "**初期設定**\n";
   	print("q1", q1);
   					// 2 番目の要素の前，及び，先頭に要素を追加
   	deque<int>::iterator it = q1.begin() + 1;
   	q1.emplace(it, 5);
   //	q1.insert(it, 5);
   	q1.emplace_front(-1);
   //	q1.push_front(-1);
   	cout << "**2 番目の要素の前，及び，先頭に要素を追加**\n";
   	print("q1", q1);
   					// 3 番目の要素，最初，及び，最後の要素を削除
   	it = q1.begin() + 2;
   	q1.erase(it);
   	q1.pop_front();
   	q1.pop_back();
   	cout << "**3 番目の要素，最初，及び，最後の要素を削除**\n";
   	print("q1", q1);
   					// 演算子で比較
   	cout << "**演算子で比較**\n";
   	deque<int> q2 = {0, 1, 2, 3};   // 初期化子リストの利用
   //	deque<int> q2 {0, 1, 2, 3};   // 初期化子リストの利用
   	print("q2", q2);
   	if (q1 == q2)
   		cout << "  2 つのコンテナ内の要素はすべて等しい\n";
   					// q2 の最初の 3 つの要素を q1 に代入
   	cout << "**q2 の最初の 3 つの要素を q1 に代入**\n";
   	q1.assign(q2.begin(), q2.end()-1);
   //	q1.assign({0, 1, 2});
   	print("q1", q1);
   					// q1 と q2 を入れ替える
   	cout << "**q1 と q2 を入れ替える**\n";
   	print("入れ替え前:q1", q1);
   	print("入れ替え前:q2", q2);
   	q1.swap(q2);
   	print("q1", q1);
   	print("q2", q2);
   					// q1 のすべての要素を削除
   	cout << "**q1 すべての要素を削除**\n";
   	q1.clear();
   	print("q1", q1);
   
   	return 0;
   }
   			

   （出力）

   **初期設定**
   q1 の要素数： 5
     0  1  2  3  4
   **2 番目の要素の前，及び，先頭に要素を追加**
   q1 の要素数： 7
     -1  0  5  1  2  3  4
   **3 番目の要素，最初，及び，最後の要素を削除**
   q1 の要素数： 4
     0  1  2  3
   **演算子で比較**
   q2 の要素数： 4
     0  1  2  3
     2 つのコンテナ内の要素はすべて等しい
   **q2 の最初の 3 つの要素を q1 に代入**
   q1 の要素数： 3
     0  1  2
   **q1 と q2 を入れ替える**
   入れ替え前:q1 の要素数： 3
     0  1  2
   入れ替え前:q2 の要素数： 4
     0  1  2  3
   q1 の要素数： 4
     0  1  2  3
   q2 の要素数： 3
     0  1  2
   **q1 すべての要素を削除**
     コンテナ q1 は空です
   			

[参照]

vector， set， multimap， array， list， map， multiset， priority_queue， queue， stack， forward_list， unordered_map， unordered_multimap， unordered_set， unordered_multiset