C++/C++11中std::dequeの使用
23626 ワード
std::dequeは両端キューであり、効率的にヘッダーの両端に要素を挿入および削除できます.std::dequeの両端に要素を挿入および削除しても、他の要素のポインタまたは参照が無効になることはありません.インタフェースではstd::vectorと似ています.sdk::vectorとは逆にstd::dequeの要素は連続的に格納されていない:典型的な実装は、個別に割り当てられた固定サイズ配列を使用するシーケンスである.std::dequeのストレージスペースは自動的にオンデマンドで拡大および縮小されます.拡張std::dequeは拡張std::vectorよりも安いです.既存の要素が新しいメモリ位置にコピーされないためです.
デュアル・エンド・キュー(Double-ended queue、Dequeと略称)は、サイズが動的に変化し、両端で拡張または縮小できるシーケンス・コンテナです.シーケンスコンテナの要素は、厳密な線形シーケンスでソートされます.対応する要素には、要素のシーケンス内の位置からアクセスできます.異なるライブラリでは、通常、ダイナミック配列として実装される両端キューが異なる方法で実装される場合があります.いずれにしても、両端キューはランダム反復器を使用して各要素に直接アクセスでき、内部のストレージスペースは必要に応じて自動的に拡張または縮小されます.コンテナが実際に割り当てたメモリの数は、追加のメモリが将来増加する部分で使用されるため、現在のすべての有効な要素を収容するのに必要なメモリの数を超えています.そのため、エレメントを挿入すると、コンテナにメモリを頻繁に割り当てる必要はありません.したがって、両端キューは、ベクトル(std::vector)のような機能を提供し、コンテナの末尾だけでなく、コンテナの先頭で要素を効率的に挿入または削除することができます.ただし、ベクトルに比べて、両端キューは内部の要素が連続した記憶空間で格納されることを保証しないため、ポインタを直接オフセット操作して要素に直接アクセスすることは許されない.内部では、両端キューとベクトルの動作はまったく異なります.ベクトルは単一配列のデータ構造を使用し、要素が増加する過程で、たまにメモリの再割り当てが必要ですが、両端キューの要素は異なるメモリブロックにばらばらに保存されます.コンテナ内には、一定時間および統一された順序のインタフェースで任意の要素に直接アクセスできるように、必要なデータが保存されます.したがって、両端キューの内部実装はベクトルよりもやや複雑であるが、特に非常に長いシーケンスでは、メモリ再割り当てのコストが高く、特定の環境でより効率的に増加することができる.開始または終了以外の任意の場所で要素を挿入または削除する操作が多く含まれる場合、dequeはリスト(std::list)および順方向リスト(std::forward_list)に比べて性能が極めて悪く、操作前後の反復器、参照の一貫性が低い.
A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of these quence, and linear time insertion and removal of elements in the middle. The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.
1つのコンテナは、特定のタイプのオブジェクトの集合です.シーケンスコンテナ(sequential container)は、プログラマに要素の格納とアクセスの順序を制御する能力を提供します.この順序は、要素の値に依存せず、要素が容器に添加されたときの位置に対応します.
標準ライブラリのシーケンスコンテナは次のとおりです.
(1)、vector:可変サイズ配列.高速ランダムアクセスをサポートします.末尾以外の場所で要素を挿入または削除するのは遅い場合があります.
(2)、deque:両端キュー.高速ランダムアクセスをサポートします.先頭と末尾の位置での挿入/削除が高速です.
(3)、list:双方向チェーンテーブル.双方向シーケンスアクセスのみをサポートします.リスト内の任意の場所での挿入/削除操作は高速です.
(4)、forward_List:一方向チェーンテーブル.ワンウェイ・シーケンス・アクセスのみがサポートされます.チェーンテーブルの任意の場所での挿入/削除操作は高速です.
(5)、array:固定サイズ配列.高速ランダムアクセスをサポートします.要素を追加または削除できません.
(6)、string:vectorに似たコンテナですが、文字の保存に特化しています.ランダムアクセスが速い.末尾での挿入/削除速度が速い.
固定サイズのarrayに加えて、他のコンテナは効率的で柔軟なメモリ管理を提供します.要素を追加および削除し、コンテナのサイズを拡張および縮小できます.コンテナ保存要素のポリシーは、コンテナ操作の効率に固定され、大きな影響を及ぼす場合があります.場合によっては、ストレージポリシーは、特定のコンテナが特定の操作をサポートしているかどうかにも影響します.
たとえばstringとvectorは、要素を連続したメモリ領域に保存します.エレメントは連続的に格納されるため、エレメントの下付きスケールでアドレスを計算するのは非常に高速です.ただし、2つのコンテナの中間位置で要素を追加または削除するには時間がかかります.1回の挿入または削除操作後、挿入/削除位置以降のすべての要素を移動して、連続的なストレージを維持する必要があります.また、要素を追加するには、追加のストレージ領域を割り当てる必要がある場合があります.この場合、各要素は新しいストレージスペースに移動する必要があります.
リストとforward_Listの2つのコンテナの設計目的は、コンテナの任意の場所での追加と削除操作を迅速にすることです.代わりに、この2つのコンテナは要素のランダムアクセスをサポートしません.1つの要素にアクセスするには、コンテナ全体を巡回するしかありません.また、vector、deque、arrayに比べて、この2つのコンテナの追加メモリのオーバーヘッドも大きい.
dequeはより複雑なデータ構造です.stringやvectorと同様に、dequeは迅速なランダムアクセスをサポートします.stringやvectorと同様にdequeの中間位置で要素を追加または削除するコストが高い.ただし、dequeの両端に要素を追加または削除するのはlistまたはforward_とすぐです.list削除要素を追加する速度は同等です.
forward_Listとarrayは新しいC++標準が追加されたタイプです.内蔵配列に比べてarrayは、より安全で使いやすい配列タイプです.内蔵配列と同様にarrayオブジェクトのサイズは固定されます.したがってarrayでは、要素の追加と削除、コンテナサイズの変更はサポートされていません.forward_Listの設計目標は,最良の手書きの一方向チェーンテーブルデータ構造に相当する性能を達成することである.だからforward_listにはsize操作はありません.そのサイズを保存または計算すると、手書きチェーンテーブルよりも追加のオーバーヘッドが発生します.他の容器にとってsizeは、高速な定数時間の操作であることを保証します.
通常、vectorを使うのが一番いいです.除法には他の容器を選ぶ理由があります.
以下に、コンテナを選択するための基本的な原則を示します.
(1)、除算には他の容器を選ぶ理由があります.そうしないとvectorを使うべきです.
(2)、プログラムに小さな要素が多く、スペースの追加コストが重要である場合はlistやforward_を使用しないでください.list;
(3)、プログラムが要素にランダムにアクセスする必要がある場合はvectorまたはdequeを使用する.
(4)、コンテナの中間に要素を挿入または削除する必要がある場合はlistまたはforward_を使用するlist;
(5)、プログラムがヘッダの最後の位置で要素を挿入または削除する必要があるが、中間の位置で挿入または削除操作を行わない場合はdequeを使用する.
(6)、プログラムが読み込み入力時にのみコンテナの中間位置に要素を挿入し、その後ランダムに要素にアクセスする必要がある場合は、まず、本当にコンテナの中間位置に要素を追加する必要があるかどうかを決定します.入力データを処理する場合、通常はvectorにデータをコンテナ的に追加し、標準ライブラリのsort関数を呼び出してコンテナ内の要素を並べ替え、中間位置に要素を追加しないようにすることができます.要素を中間位置に挿入する必要がある場合は、入力フェーズでlistを使用することを考慮し、入力が完了するとlistの内容をvectorにコピーします.
どのコンテナを使用するべきか分からない場合は、vectorとlistの共通の操作のみをプログラムで使用できます.反復器を使用し、下付きの操作を使用せず、ランダムなアクセスを避けることができます.これにより、必要に応じてvectorやlistを選択するのに便利です.
一般的に、各コンテナはヘッダファイルに定義され、ファイル名はタイプ名と同じです.すなわち、dequeはヘッダファイルdequeに定義され、listはヘッダファイルlistに定義され、これに類する.コンテナはテンプレートクラスとして定義されます.
シーケンスコンテナは、ほとんど任意のタイプの要素を保存できます.特に、エレメントのタイプが別のコンテナであるコンテナを定義できます.このコンテナの定義は、他のコンテナタイプとまったく同じです.カッコで要素タイプを指定します(この場合、別のコンテナタイプ).
標準ライブラリでは、シーケンスコンテナに加えて、stack、queue、priorityの3つのシーケンスコンテナアダプタが定義されています.queue.アダプタ(adaptor)は、標準ライブラリの一般的な概念です.コンテナ、反復器、関数にはアダプタがあります.本質的に、1つのアダプタは、あるものの行為を別のもののように見せるメカニズムです.1つのコンテナアダプタは、既存のコンテナタイプを受け入れ、異なるタイプのように動作させます.
次は、他の記事のcopyのテストコードです.詳細は、対応するreferenceを参照してください.
GitHub: https://github.com/fengbingchun/Messy_Test
デュアル・エンド・キュー(Double-ended queue、Dequeと略称)は、サイズが動的に変化し、両端で拡張または縮小できるシーケンス・コンテナです.シーケンスコンテナの要素は、厳密な線形シーケンスでソートされます.対応する要素には、要素のシーケンス内の位置からアクセスできます.異なるライブラリでは、通常、ダイナミック配列として実装される両端キューが異なる方法で実装される場合があります.いずれにしても、両端キューはランダム反復器を使用して各要素に直接アクセスでき、内部のストレージスペースは必要に応じて自動的に拡張または縮小されます.コンテナが実際に割り当てたメモリの数は、追加のメモリが将来増加する部分で使用されるため、現在のすべての有効な要素を収容するのに必要なメモリの数を超えています.そのため、エレメントを挿入すると、コンテナにメモリを頻繁に割り当てる必要はありません.したがって、両端キューは、ベクトル(std::vector)のような機能を提供し、コンテナの末尾だけでなく、コンテナの先頭で要素を効率的に挿入または削除することができます.ただし、ベクトルに比べて、両端キューは内部の要素が連続した記憶空間で格納されることを保証しないため、ポインタを直接オフセット操作して要素に直接アクセスすることは許されない.内部では、両端キューとベクトルの動作はまったく異なります.ベクトルは単一配列のデータ構造を使用し、要素が増加する過程で、たまにメモリの再割り当てが必要ですが、両端キューの要素は異なるメモリブロックにばらばらに保存されます.コンテナ内には、一定時間および統一された順序のインタフェースで任意の要素に直接アクセスできるように、必要なデータが保存されます.したがって、両端キューの内部実装はベクトルよりもやや複雑であるが、特に非常に長いシーケンスでは、メモリ再割り当てのコストが高く、特定の環境でより効率的に増加することができる.開始または終了以外の任意の場所で要素を挿入または削除する操作が多く含まれる場合、dequeはリスト(std::list)および順方向リスト(std::forward_list)に比べて性能が極めて悪く、操作前後の反復器、参照の一貫性が低い.
A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of these quence, and linear time insertion and removal of elements in the middle. The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.
1つのコンテナは、特定のタイプのオブジェクトの集合です.シーケンスコンテナ(sequential container)は、プログラマに要素の格納とアクセスの順序を制御する能力を提供します.この順序は、要素の値に依存せず、要素が容器に添加されたときの位置に対応します.
標準ライブラリのシーケンスコンテナは次のとおりです.
(1)、vector:可変サイズ配列.高速ランダムアクセスをサポートします.末尾以外の場所で要素を挿入または削除するのは遅い場合があります.
(2)、deque:両端キュー.高速ランダムアクセスをサポートします.先頭と末尾の位置での挿入/削除が高速です.
(3)、list:双方向チェーンテーブル.双方向シーケンスアクセスのみをサポートします.リスト内の任意の場所での挿入/削除操作は高速です.
(4)、forward_List:一方向チェーンテーブル.ワンウェイ・シーケンス・アクセスのみがサポートされます.チェーンテーブルの任意の場所での挿入/削除操作は高速です.
(5)、array:固定サイズ配列.高速ランダムアクセスをサポートします.要素を追加または削除できません.
(6)、string:vectorに似たコンテナですが、文字の保存に特化しています.ランダムアクセスが速い.末尾での挿入/削除速度が速い.
固定サイズのarrayに加えて、他のコンテナは効率的で柔軟なメモリ管理を提供します.要素を追加および削除し、コンテナのサイズを拡張および縮小できます.コンテナ保存要素のポリシーは、コンテナ操作の効率に固定され、大きな影響を及ぼす場合があります.場合によっては、ストレージポリシーは、特定のコンテナが特定の操作をサポートしているかどうかにも影響します.
たとえばstringとvectorは、要素を連続したメモリ領域に保存します.エレメントは連続的に格納されるため、エレメントの下付きスケールでアドレスを計算するのは非常に高速です.ただし、2つのコンテナの中間位置で要素を追加または削除するには時間がかかります.1回の挿入または削除操作後、挿入/削除位置以降のすべての要素を移動して、連続的なストレージを維持する必要があります.また、要素を追加するには、追加のストレージ領域を割り当てる必要がある場合があります.この場合、各要素は新しいストレージスペースに移動する必要があります.
リストとforward_Listの2つのコンテナの設計目的は、コンテナの任意の場所での追加と削除操作を迅速にすることです.代わりに、この2つのコンテナは要素のランダムアクセスをサポートしません.1つの要素にアクセスするには、コンテナ全体を巡回するしかありません.また、vector、deque、arrayに比べて、この2つのコンテナの追加メモリのオーバーヘッドも大きい.
dequeはより複雑なデータ構造です.stringやvectorと同様に、dequeは迅速なランダムアクセスをサポートします.stringやvectorと同様にdequeの中間位置で要素を追加または削除するコストが高い.ただし、dequeの両端に要素を追加または削除するのはlistまたはforward_とすぐです.list削除要素を追加する速度は同等です.
forward_Listとarrayは新しいC++標準が追加されたタイプです.内蔵配列に比べてarrayは、より安全で使いやすい配列タイプです.内蔵配列と同様にarrayオブジェクトのサイズは固定されます.したがってarrayでは、要素の追加と削除、コンテナサイズの変更はサポートされていません.forward_Listの設計目標は,最良の手書きの一方向チェーンテーブルデータ構造に相当する性能を達成することである.だからforward_listにはsize操作はありません.そのサイズを保存または計算すると、手書きチェーンテーブルよりも追加のオーバーヘッドが発生します.他の容器にとってsizeは、高速な定数時間の操作であることを保証します.
通常、vectorを使うのが一番いいです.除法には他の容器を選ぶ理由があります.
以下に、コンテナを選択するための基本的な原則を示します.
(1)、除算には他の容器を選ぶ理由があります.そうしないとvectorを使うべきです.
(2)、プログラムに小さな要素が多く、スペースの追加コストが重要である場合はlistやforward_を使用しないでください.list;
(3)、プログラムが要素にランダムにアクセスする必要がある場合はvectorまたはdequeを使用する.
(4)、コンテナの中間に要素を挿入または削除する必要がある場合はlistまたはforward_を使用するlist;
(5)、プログラムがヘッダの最後の位置で要素を挿入または削除する必要があるが、中間の位置で挿入または削除操作を行わない場合はdequeを使用する.
(6)、プログラムが読み込み入力時にのみコンテナの中間位置に要素を挿入し、その後ランダムに要素にアクセスする必要がある場合は、まず、本当にコンテナの中間位置に要素を追加する必要があるかどうかを決定します.入力データを処理する場合、通常はvectorにデータをコンテナ的に追加し、標準ライブラリのsort関数を呼び出してコンテナ内の要素を並べ替え、中間位置に要素を追加しないようにすることができます.要素を中間位置に挿入する必要がある場合は、入力フェーズでlistを使用することを考慮し、入力が完了するとlistの内容をvectorにコピーします.
どのコンテナを使用するべきか分からない場合は、vectorとlistの共通の操作のみをプログラムで使用できます.反復器を使用し、下付きの操作を使用せず、ランダムなアクセスを避けることができます.これにより、必要に応じてvectorやlistを選択するのに便利です.
一般的に、各コンテナはヘッダファイルに定義され、ファイル名はタイプ名と同じです.すなわち、dequeはヘッダファイルdequeに定義され、listはヘッダファイルlistに定義され、これに類する.コンテナはテンプレートクラスとして定義されます.
シーケンスコンテナは、ほとんど任意のタイプの要素を保存できます.特に、エレメントのタイプが別のコンテナであるコンテナを定義できます.このコンテナの定義は、他のコンテナタイプとまったく同じです.カッコで要素タイプを指定します(この場合、別のコンテナタイプ).
標準ライブラリでは、シーケンスコンテナに加えて、stack、queue、priorityの3つのシーケンスコンテナアダプタが定義されています.queue.アダプタ(adaptor)は、標準ライブラリの一般的な概念です.コンテナ、反復器、関数にはアダプタがあります.本質的に、1つのアダプタは、あるものの行為を別のもののように見せるメカニズムです.1つのコンテナアダプタは、既存のコンテナタイプを受け入れ、異なるタイプのように動作させます.
次は、他の記事のcopyのテストコードです.詳細は、対応するreferenceを参照してください.
#include "deque.hpp"
#include
#include
#include
// https://msdn.microsoft.com/en-us/library/22a9t119.aspx
int test_deque_2()
{
{ // deque::at: Returns a reference to the element at a specified location in the deque.
using namespace std;
deque c1;
c1.push_back(10);
c1.push_back(20);
const int& i = c1.at(0);
int& j = c1.at(1);
cout << "The first element is " << i << endl;
cout << "The second element is " << j << endl;
}
{ // deque::back: Returns a reference to the last element of the deque.
using namespace std;
deque c1;
c1.push_back(10);
c1.push_back(11);
int& i = c1.back();
const int& ii = c1.front();
cout << "The last integer of c1 is " << i << endl; // 11
i--;
cout << "The next-to-last integer of c1 is " << ii << endl; // 10
cout << "The last integer of c1 is " << c1.back() << endl; // 10
}
{ // deque::clear: Erases all the elements of a deque.
using namespace std;
deque c1;
c1.push_back(10);
c1.push_back(20);
c1.push_back(30);
cout << "The size of the deque is initially " << c1.size() << endl;
c1.clear();
cout << "The size of the deque after clearing is " << c1.size() << endl;
}
{ // deque::const_reference: A type that provides a reference to a const element stored in a deque for reading and performing const operations
using namespace std;
deque c1;
c1.push_back(10);
c1.push_back(20);
const deque c2 = c1;
const int &i = c2.front();
const int &j = c2.back();
cout << "The first element is " << i << endl;
cout << "The second element is " << j << endl;
// The following line would cause an error as c2 is const
// c2.push_back( 30 );
}
{ // deque::crbegin: Returns a const iterator to the first element in a reversed deque
using namespace std;
deque v1;
deque ::iterator v1_Iter;
deque ::const_reverse_iterator v1_rIter;
v1.push_back(1);
v1.push_back(2);
v1_Iter = v1.begin();
cout << "The first element of deque is "
<< *v1_Iter << "." << endl;
v1_rIter = v1.crbegin();
cout << "The first element of the reversed deque is "
<< *v1_rIter << "." << endl;
}
{ // deque::emplace: Inserts an element constructed in place into the deque at a specified position.
using namespace std;
deque v1;
deque ::iterator Iter;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
cout << "v1 =";
for (Iter = v1.begin(); Iter != v1.end(); Iter++)
cout << " " << *Iter;
cout << endl;
// initialize a deque of deques by moving v1
deque < deque > vv1;
vv1.emplace(vv1.begin(), move(v1));
if (vv1.size() != 0 && vv1[0].size() != 0) {
cout << "vv1[0] =";
for (Iter = vv1[0].begin(); Iter != vv1[0].end(); Iter++)
cout << " " << *Iter;
cout << endl;
}
}
return 0;
}
/
// reference: http://www.cplusplus.com/reference/deque/deque/
int test_deque_1()
{
{ // deque::deque: Construct deque container
unsigned int i;
// constructors used in the same order as described above:
std::deque first; // empty deque of ints
std::deque second(4, 100); // four ints with value 100
std::deque third(second.begin(), second.end()); // iterating through second
std::deque fourth(third); // a copy of third
// the iterator constructor can be used to copy arrays:
int myints[] = { 16, 2, 77, 29 };
std::deque fifth(myints, myints + sizeof(myints) / sizeof(int));
std::cout << "The contents of fifth are:";
for (std::deque::iterator it = fifth.begin(); it != fifth.end(); ++it)
std::cout << ' ' << *it; // 16 2 77 29
std::cout << '
';
}
{ // deque::assign: Assigns new contents to the deque container,
// replacing its current contents, and modifying its size accordingly.
std::deque first;
std::deque second;
std::deque third;
first.assign(7, 100); // 7 ints with a value of 100
std::deque::iterator it;
it = first.begin() + 1;
second.assign(it, first.end() - 1); // the 5 central values of first
int myints[] = { 1776, 7, 4 };
third.assign(myints, myints + 3); // assigning from array.
std::cout << "Size of first: " << int(first.size()) << '
'; // 7
std::cout << "Size of second: " << int(second.size()) << '
'; // 5
std::cout << "Size of third: " << int(third.size()) << '
'; // 3
}
{ // deque::at: Returns a reference to the element at position n in the deque container object.
std::deque mydeque(10); // 10 zero-initialized unsigneds
// assign some values:
for (unsigned i = 0; i < mydeque.size(); i++)
mydeque.at(i) = i;
std::cout << "mydeque contains:";
for (unsigned i = 0; i < mydeque.size(); i++)
std::cout << ' ' << mydeque.at(i); // 0 1 2 3 4 5 6 7 8 9
std::cout << '
';
}
{ // deque::back: Returns a reference to the last element in the container.
// deque::push_back: Adds a new element at the end of the deque container,
// after its current last element. The content of val is copied (or moved) to the new element
std::deque mydeque;
mydeque.push_back(10);
while (mydeque.back() != 0)
mydeque.push_back(mydeque.back() - 1);
std::cout << "mydeque contains:";
for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // deque::begin: Return iterator to beginning
// deque::end: Return iterator to end
std::deque mydeque;
for (int i = 1; i <= 5; i++) mydeque.push_back(i);
std::cout << "mydeque contains:";
std::deque::iterator it = mydeque.begin();
while (it != mydeque.end())
std::cout << ' ' << *it++;
std::cout << '
';
}
{ // deque::cbegin: c++11, Return const_iterator to beginning
// deque::cend: c++11, Return const_iterator to end
std::deque mydeque = { 10, 20, 30, 40, 50 };
std::cout << "mydeque contains:";
for (auto it = mydeque.cbegin(); it != mydeque.cend(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // deque::clear: Clear content
unsigned int i;
std::deque mydeque;
mydeque.push_back(100);
mydeque.push_back(200);
mydeque.push_back(300);
std::cout << "mydeque contains:";
for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
mydeque.clear();
mydeque.push_back(1101);
mydeque.push_back(2202);
std::cout << "mydeque contains:";
for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // deque::crbegin: c++11, Return const_reverse_iterator to reverse beginning
// deque::crend: c++11, Return const_reverse_iterator to reverse end
std::deque mydeque = { 1, 2, 3, 4, 5 };
std::cout << "mydeque backwards:";
for (auto rit = mydeque.crbegin(); rit != mydeque.crend(); ++rit)
std::cout << ' ' << *rit;
std::cout << '
';
}
{ // deque::emplace: c++11, Construct and insert element
std::deque mydeque = { 10, 20, 30 };
auto it = mydeque.emplace(mydeque.begin() + 1, 100);
mydeque.emplace(it, 200);
mydeque.emplace(mydeque.end(), 300);
std::cout << "mydeque contains:";
for (auto& x : mydeque)
std::cout << ' ' << x;
std::cout << '
';
}
{ // deque::emplace_back: c++11, Construct and insert element at the end
std::deque mydeque = { 10, 20, 30 };
mydeque.emplace_back(100);
mydeque.emplace_back(200);
std::cout << "mydeque contains:";
for (auto& x : mydeque)
std::cout << ' ' << x;
std::cout << '
';
}
{ // deque::emplace_front: c++11, Construct and insert element at beginning
std::deque mydeque = { 10, 20, 30 };
mydeque.emplace_front(111);
mydeque.emplace_front(222);
std::cout << "mydeque contains:";
for (auto& x : mydeque)
std::cout << ' ' << x;
std::cout << '
';
}
{ // deque::empty: Test whether container is empty
std::deque mydeque;
int sum(0);
for (int i = 1; i <= 10; i++) mydeque.push_back(i);
while (!mydeque.empty()) {
sum += mydeque.front();
mydeque.pop_front();
}
std::cout << "total: " << sum << '
';
}
{ // deque::erase: Erase elements
std::deque mydeque;
// set some values (from 1 to 10)
for (int i = 1; i <= 10; i++) mydeque.push_back(i);
// erase the 6th element
mydeque.erase(mydeque.begin() + 5);
// erase the first 3 elements:
mydeque.erase(mydeque.begin(), mydeque.begin() + 3);
std::cout << "mydeque contains:";
for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // deque::front: Access first element, Returns a reference to the first element in the deque containe
// deque::push_front: Inserts a new element at the beginning of the deque container,
// right before its current first element. The content of val is copied (or moved) to the inserted element
std::deque mydeque;
mydeque.push_front(77);
mydeque.push_back(20);
mydeque.front() -= mydeque.back();
std::cout << "mydeque.front() is now " << mydeque.front() << '
';
}
{ // deque::get_allocator: Returns a copy of the allocator object associated with the deque object
std::deque mydeque;
int * p;
unsigned int i;
// allocate an array with space for 5 elements using deque's allocator:
p = mydeque.get_allocator().allocate(5);
// construct values in-place on the array:
for (i = 0; i < 5; i++) mydeque.get_allocator().construct(&p[i], i);
std::cout << "The allocated array contains:";
for (i = 0; i < 5; i++) std::cout << ' ' << p[i];
std::cout << '
';
// destroy and deallocate:
for (i = 0; i < 5; i++) mydeque.get_allocator().destroy(&p[i]);
mydeque.get_allocator().deallocate(p, 5);
}
{ // deque::insert: Insert elements
std::deque mydeque;
// set some initial values:
for (int i = 1; i < 6; i++) mydeque.push_back(i); // 1 2 3 4 5
std::deque::iterator it = mydeque.begin();
++it;
it = mydeque.insert(it, 10); // 1 10 2 3 4 5
// "it" now points to the newly inserted 10
mydeque.insert(it, 2, 20); // 1 20 20 10 2 3 4 5
// "it" no longer valid!
it = mydeque.begin() + 2;
std::vector myvector(2, 30);
mydeque.insert(it, myvector.begin(), myvector.end());
// 1 20 30 30 20 10 2 3 4 5
std::cout << "mydeque contains:";
for (it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // deque::max_size: Return maximum size
unsigned int i;
std::deque mydeque;
std::cout << "Enter number of elements: ";
i = 100; //std::cin >> i;
if (i < mydeque.max_size()) mydeque.resize(i);
else std::cout << "That size exceeds the limit.
";
fprintf(stderr, "max size: %d
", mydeque.max_size());
}
{ // deque::operator=: Assigns new contents to the container, replacing its current contents, and modifying its size accordingly
std::deque first(3); // deque with 3 zero-initialized ints
std::deque second(5); // deque with 5 zero-initialized ints
second = first;
first = std::deque();
std::cout << "Size of first: " << int(first.size()) << '
';
std::cout << "Size of second: " << int(second.size()) << '
';
}
{ // deque::operator[]: Returns a reference to the element at position n in the deque container
std::deque mydeque(10); // 10 zero-initialized elements
std::deque::size_type sz = mydeque.size();
// assign some values:
for (unsigned i = 0; i < sz; i++) mydeque[i] = i;
// reverse order of elements using operator[]:
for (unsigned i = 0; i < sz / 2; i++) {
int temp;
temp = mydeque[sz - 1 - i];
mydeque[sz - 1 - i] = mydeque[i];
mydeque[i] = temp;
}
// print content:
std::cout << "mydeque contains:";
for (unsigned i = 0; i < sz; i++)
std::cout << ' ' << mydeque[i];
std::cout << '
';
}
{ // deque::pop_back: Removes the last element in the deque container, effectively reducing the container size by one
std::deque mydeque;
int sum(0);
mydeque.push_back(10);
mydeque.push_back(20);
mydeque.push_back(30);
while (!mydeque.empty()) {
sum += mydeque.back();
mydeque.pop_back();
}
std::cout << "The elements of mydeque add up to " << sum << '
';
}
{ // deque::pop_front: Removes the first element in the deque container, effectively reducing its size by one.
std::deque mydeque;
mydeque.push_back(100);
mydeque.push_back(200);
mydeque.push_back(300);
std::cout << "Popping out the elements in mydeque:";
while (!mydeque.empty()) {
std::cout << ' ' << mydeque.front();
mydeque.pop_front();
}
std::cout << "
The final size of mydeque is " << int(mydeque.size()) << '
';
}
{ // deque::rbegin: Returns a reverse iterator pointing to the last element in the container
// deque::rend: Returns a reverse iterator pointing to the theoretical element preceding the first element in the deque container
std::deque mydeque(5); // 5 default-constructed ints
std::deque::reverse_iterator rit = mydeque.rbegin();
int i = 0;
for (rit = mydeque.rbegin(); rit != mydeque.rend(); ++rit)
*rit = ++i;
std::cout << "mydeque contains:";
for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // deque::resize: Resizes the container so that it contains n elements
std::deque mydeque;
std::deque::iterator it;
// set some initial content:
for (int i = 1; i < 10; ++i) mydeque.push_back(i);
mydeque.resize(5);
mydeque.resize(8, 100);
mydeque.resize(12);
std::cout << "mydeque contains:";
for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // deque::shrink_to_fit: c++11, Requests the container to reduce its memory usage to fit its size.
// deque::size: Returns the number of elements in the deque container
std::deque mydeque(100);
std::cout << "1. size of mydeque: " << mydeque.size() << '
';
mydeque.resize(10);
std::cout << "2. size of mydeque: " << mydeque.size() << '
';
mydeque.shrink_to_fit();
fprintf(stderr, "3. size of mydeque: %d
", mydeque.size());
}
{ // deque::swap: Exchanges the content of the container by the content of x,
// which is another deque object containing elements of the same type. Sizes may differ.
unsigned int i;
std::deque foo(3, 100); // three ints with a value of 100
std::deque bar(5, 200); // five ints with a value of 200
foo.swap(bar);
std::cout << "foo contains:";
for (std::deque::iterator it = foo.begin(); it != foo.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
std::cout << "bar contains:";
for (std::deque::iterator it = bar.begin(); it != bar.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
{ // relational operators: compare
std::deque foo(3, 100); // three ints with a value of 100
std::deque bar(2, 200); // two ints with a value of 200
if (foo == bar) std::cout << "foo and bar are equal
";
if (foo != bar) std::cout << "foo and bar are not equal
";
if (foo< bar) std::cout << "foo is less than bar
";
if (foo> bar) std::cout << "foo is greater than bar
";
if (foo <= bar) std::cout << "foo is less than or equal to bar
";
if (foo >= bar) std::cout << "foo is greater than or equal to bar
";
}
{ // std::swap: The contents of container x are exchanged with those of y.
// Both container objects must be of the same type (same template parameters), although sizes may differ
unsigned int i;
std::deque foo(3, 100); // three ints with a value of 100
std::deque bar(5, 200); // five ints with a value of 200
swap(foo, bar);
std::cout << "foo contains:";
for (std::deque::iterator it = foo.begin(); it != foo.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
std::cout << "bar contains:";
for (std::deque::iterator it = bar.begin(); it != bar.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
}
return 0;
} GitHub: https://github.com/fengbingchun/Messy_Test