c++のstack、queue、priorityについてQueueの紹介
8313 ワード
c++には、いくつかのシーケンスコンテナに加えて、標準ライブラリにはstack、queue、priorityの3つのコンテナアダプタが定義されています.queue.アダプタは、標準ライブラリの一般的な概念です.コンテナ、反復器、関数は本質的にアダプタです.本質的に、1つのアダプタは、あるものの行為を別のもののように見せるメカニズムです.1つのコンテナアダプタは、既存のコンテナタイプを受け入れ、異なるタイプのように動作させます.たとえば、stackアダプタは、arrayとrorward_listを除くシーケンスコンテナを受け入れ、stackのように動作させます.
次は、すべてのコンテナアダプタでサポートされている操作とタイプです.
size_type現在のタイプの最大オブジェクトのサイズを保存するのに十分なタイプ
value_type要素タイプ
container_type実装アダプタの下位コンテナタイプ
A a; aという空のアダプタを作成
A a(c); コンテナcのコピー付きaというアダプタを作成します.
リレーショナル演算子各アダプタは、すべてのリレーショナル演算子をサポートします:==、!=、、和>=これらの演算子は、下位コンテナの比較結果を返します.
a.empty()aに収容と要素が含まれている場合falseを返し、そうでない場合trueを返す
a.size()はa中の要素の個数を返す
swap(a,b)はaとbの内容を交換し、aとbは同じタイプでなければならない.下地容器のタイプも同じでなければならない.
a.swap(b)
アダプタの構造には、デフォルトの構造関数で空のオブジェクトを作成する方法と、パラメータとしてコンテナを受信してコピー初期化する方法の2つがあります.
例:deque myDeque;
............//いくつかの操作を経てmyDequeにすでにいくつかの要素があると仮定します.
stack myStack(myDeque);//myDequeの要素をmyStackにコピーする
デフォルトでは、stackとqueueはdequeに基づいて実装され、priority_queueはvector上で実現される.
もちろん、アダプタを作成するときに、名前付きシーケンスコンテナを2番目のタイプパラメータとして使用することで、デフォルトのコンテナタイプを再ロードすることもできます.
例:stack>str_stk1;//vectorで実現される空のスタック、すなわちこのときのスタックのデータ格納はvectorを最下位とする
stack > str_stk 2(vec)/vecはint型データが格納されたvectorコンテナであり、str_stk 2がvecをコピーして初期化する
上はc++primerの関連解釈と結びつけていくつかの小さなマットを行い、次は正式にテーマに入ります.
1、stackスタック
stackタイプは、ヘッダファイルに定義されたデータ構造であり、使用時にヘッダファイルを自分で作成したcppファイルに含めるだけでよい.
スタックを定義します:stack stk; //value_typeはスタック内の要素タイプを指し、int、stringなどであってもよい
スタックの操作は次のとおりです.
stk.pop()スタックトップ要素を削除しますが、スタックトップの要素は戻りません.
stk.top()はスタックトップの要素を返しますが、スタックトップ要素はポップアップされません.
push(item)は、コピーまたは移動によってitem要素のコピーをスタックの上部に押し込む.
stk.emplace(arg)はargをstkに配置し、pushに相当する役割を果たす.
size()はスタック内の要素の数を返します.
Empty()はスタックが空であるか否かを判断し、スタックが空である場合falseを返し、そうでない場合trueを返す
swap(stk 1)はstkとstk 1の要素を交換し、この操作は本当に彼らの要素を交換することはなく、ただ2つの容器の内部データ構造を交換し、ポインタの思想類比で理解することができる.
swap(stk 1,stk 2)この関数は非メンバーバージョンの関数であり、機能はメンバーバージョンのswapと同じである.
次のプログラムはstackの使い方の1つの展示です.
1、queueキュー
Queueキューはc++標準ライブラリの重要なデータ構造であり、その主な特性は先進的な先出であり、私たちの日常生活の列に並んで買い物をすることに相当し、先着者は先にサービスされ、後着者は列の尾に並ぶことである.
まずqueueはヘッダファイルに定義され、使用時にヘッダファイルを含めます.
キューを定義します:queue q;
q.pop()queueのキューヘッダ要素を削除
q.front()はキューのキューヘッダ要素を返しますが、削除しません.
q.back()はキューのキューの末尾要素を返しますが、要素は削除されません.
q.push(arg)要素argをキューのキューの末尾に挿入する
q.emplace(arg)は要素argをキューの末尾に配置し、pushと同様に作用する.
q.size()は、キュー内の要素の数を返します.
q.empty()キューが空の場合trueを返します.そうでない場合falseを返します.
q.swap(q 1)はqとq 1の要素を交換し、方法はstackと同様にコピー形式で交換するのではなく、最下位のデータ構造を交換するだけだ.
swap(q,q 1)非メンバー関数、メンバー関数swapと同様
次のプログラムはqueueの小さなテストです.
3、priority_queue優先キュー
キューの延長として、優先キューはヘッダファイルに含まれる有用なデータ構造でもあります.
優先キューは、2つのキューで作成された重要なデータ構造です.log(n)の効率で1つのキューの最大値または最小値(最大値と最小値は、作成した優先キューの性質によって決定される)を検索することができます.これは、primアルゴリズムが優先キューと結合すると良い効果が得られる場合が多いなど、多くの場合に役立ちます.
priority_Queueのテンプレートライフには3つのパラメータがあります:priority_queue,
ここでtypeはデータのタイプであり、containerは優先キューを実現する下位コンテナであり、functionは要素間の比較方式であり、containerはvector、dequeなどの配列形式で実現しなければならないコンテナであり、
list.c++標準ライブラリでは、デフォルトではvectorをコンテナとし、operatorを使用します.
デフォルトの優先キューを定義する:priority_queue temp;
temp.pop()priority_を削除Queueのキューヘッダ要素
temp.トップ()はpriority_を返します.Queue優先キュー内のキューヘッダ要素ですが、要素は削除されません.
temp.push(arg)優先キューに要素argを挿入
temp.Emplace(arg)は要素argを優先キューに配置し、pushと同じ役割を果たす.
temp.size()は、優先キュー内の要素の数を返します.
temp.Empty()優先キューが空の場合trueを返します.そうでない場合falseを返します.
temp.swap(temp 1)はtempとtemp 1の要素を交換し、本当にコピー形式で交換するわけではありません.ただ、最下位のデータ構造を交換します.
swap(temp,temp 1)非メンバー関数、メンバー関数swapと同様
次に、システムが提供するデータ型を使用した優先キューの例を示します.
このプログラムでは、デフォルトのパラメータを使用して大きなスタックを構築する例
小さなトップスタックを作成するには、3つのパラメータを持ち込む必要があります.
上記の優先キューの宣言を変更するだけで、以下のプログラムが得られます.
次に、リロードの簡単な例を示します.
次に、上記の例を修正し、シミュレーション関数の例を示します.
上記の例では、優先キュー内の3番目のパラメータを1つの関数オブジェクトに置き換えて、優先キュー内のデータ比較の根拠とします.
次に、関数オブジェクトの知識を補足します.
c++では、他の演算子と同様に関数呼び出し演算子()を扱うことができる.この演算子はリロードすることもできます.()演算子は任意のタイプを返し、任意の数のパラメータを使用できますが、代入演算子と同様に、この演算子はメンバー関数としてのみ再ロードできます.関数呼び出し演算子定義を含むオブジェクトを関数オブジェクトと呼びます.関数オブジェクトもオブジェクトですが、それらの動作は関数のように表現されています.関数オブジェクトが呼び出されると、そのパラメータは関数呼び出し演算子のパラメータです.
次は、すべてのコンテナアダプタでサポートされている操作とタイプです.
size_type現在のタイプの最大オブジェクトのサイズを保存するのに十分なタイプ
value_type要素タイプ
container_type実装アダプタの下位コンテナタイプ
A a; aという空のアダプタを作成
A a(c); コンテナcのコピー付きaというアダプタを作成します.
リレーショナル演算子各アダプタは、すべてのリレーショナル演算子をサポートします:==、!=、、和>=これらの演算子は、下位コンテナの比較結果を返します.
a.empty()aに収容と要素が含まれている場合falseを返し、そうでない場合trueを返す
a.size()はa中の要素の個数を返す
swap(a,b)はaとbの内容を交換し、aとbは同じタイプでなければならない.下地容器のタイプも同じでなければならない.
a.swap(b)
アダプタの構造には、デフォルトの構造関数で空のオブジェクトを作成する方法と、パラメータとしてコンテナを受信してコピー初期化する方法の2つがあります.
例:deque myDeque;
............//いくつかの操作を経てmyDequeにすでにいくつかの要素があると仮定します.
stack myStack(myDeque);//myDequeの要素をmyStackにコピーする
デフォルトでは、stackとqueueはdequeに基づいて実装され、priority_queueはvector上で実現される.
もちろん、アダプタを作成するときに、名前付きシーケンスコンテナを2番目のタイプパラメータとして使用することで、デフォルトのコンテナタイプを再ロードすることもできます.
例:stack>str_stk1;//vectorで実現される空のスタック、すなわちこのときのスタックのデータ格納はvectorを最下位とする
stack > str_stk 2(vec)/vecはint型データが格納されたvectorコンテナであり、str_stk 2がvecをコピーして初期化する
上はc++primerの関連解釈と結びつけていくつかの小さなマットを行い、次は正式にテーマに入ります.
1、stackスタック
stackタイプは、ヘッダファイルに定義されたデータ構造であり、使用時にヘッダファイルを自分で作成したcppファイルに含めるだけでよい.
スタックを定義します:stack stk; //value_typeはスタック内の要素タイプを指し、int、stringなどであってもよい
スタックの操作は次のとおりです.
stk.pop()スタックトップ要素を削除しますが、スタックトップの要素は戻りません.
stk.top()はスタックトップの要素を返しますが、スタックトップ要素はポップアップされません.
push(item)は、コピーまたは移動によってitem要素のコピーをスタックの上部に押し込む.
stk.emplace(arg)はargをstkに配置し、pushに相当する役割を果たす.
size()はスタック内の要素の数を返します.
Empty()はスタックが空であるか否かを判断し、スタックが空である場合falseを返し、そうでない場合trueを返す
swap(stk 1)はstkとstk 1の要素を交換し、この操作は本当に彼らの要素を交換することはなく、ただ2つの容器の内部データ構造を交換し、ポインタの思想類比で理解することができる.
swap(stk 1,stk 2)この関数は非メンバーバージョンの関数であり、機能はメンバーバージョンのswapと同じである.
次のプログラムはstackの使い方の1つの展示です.
int main()
{
stack stk1; //
stack stk2;
stk1.push(2); //
stk1.push(9);
stk1.emplace(3);
stk1.emplace(39);
stk2.push(3);
stk2.push(4);
stk2.swap(stk1); //
while(!stk1.empty()) // ，
{
cout << stk1.top() << endl; //
stk1.pop(); //
}
while(stk2.size()) // 0 ，
{
cout << stk2.top() << endl;
stk2.pop();
}
return 0;
} 1、queueキュー
Queueキューはc++標準ライブラリの重要なデータ構造であり、その主な特性は先進的な先出であり、私たちの日常生活の列に並んで買い物をすることに相当し、先着者は先にサービスされ、後着者は列の尾に並ぶことである.
まずqueueはヘッダファイルに定義され、使用時にヘッダファイルを含めます.
キューを定義します:queue q;
q.pop()queueのキューヘッダ要素を削除
q.front()はキューのキューヘッダ要素を返しますが、削除しません.
q.back()はキューのキューの末尾要素を返しますが、要素は削除されません.
q.push(arg)要素argをキューのキューの末尾に挿入する
q.emplace(arg)は要素argをキューの末尾に配置し、pushと同様に作用する.
q.size()は、キュー内の要素の数を返します.
q.empty()キューが空の場合trueを返します.そうでない場合falseを返します.
q.swap(q 1)はqとq 1の要素を交換し、方法はstackと同様にコピー形式で交換するのではなく、最下位のデータ構造を交換するだけだ.
swap(q,q 1)非メンバー関数、メンバー関数swapと同様
次のプログラムはqueueの小さなテストです.
#include
using namespace std;
#include
int main()
{
queue q; //
for(int i=0;i<10;i++)
{
q.push(i); // i
}
q.emplace(32); // 32
cout << q.size() << endl; //
while(!q.empty()) // ，
{
cout << q.front() << endl; //
q.pop(); //
}
return 0;
} 3、priority_queue優先キュー
キューの延長として、優先キューはヘッダファイルに含まれる有用なデータ構造でもあります.
優先キューは、2つのキューで作成された重要なデータ構造です.log(n)の効率で1つのキューの最大値または最小値(最大値と最小値は、作成した優先キューの性質によって決定される)を検索することができます.これは、primアルゴリズムが優先キューと結合すると良い効果が得られる場合が多いなど、多くの場合に役立ちます.
priority_Queueのテンプレートライフには3つのパラメータがあります:priority_queue,
ここでtypeはデータのタイプであり、containerは優先キューを実現する下位コンテナであり、functionは要素間の比較方式であり、containerはvector、dequeなどの配列形式で実現しなければならないコンテナであり、
list.c++標準ライブラリでは、デフォルトではvectorをコンテナとし、operatorを使用します.
デフォルトの優先キューを定義する:priority_queue temp;
temp.pop()priority_を削除Queueのキューヘッダ要素
temp.トップ()はpriority_を返します.Queue優先キュー内のキューヘッダ要素ですが、要素は削除されません.
temp.push(arg)優先キューに要素argを挿入
temp.Emplace(arg)は要素argを優先キューに配置し、pushと同じ役割を果たす.
temp.size()は、優先キュー内の要素の数を返します.
temp.Empty()優先キューが空の場合trueを返します.そうでない場合falseを返します.
temp.swap(temp 1)はtempとtemp 1の要素を交換し、本当にコピー形式で交換するわけではありません.ただ、最下位のデータ構造を交換します.
swap(temp,temp 1)非メンバー関数、メンバー関数swapと同様
次に、システムが提供するデータ型を使用した優先キューの例を示します.
このプログラムでは、デフォルトのパラメータを使用して大きなスタックを構築する例
#include
#include
using namespace std;
#include
int main()
{
priority_queue,greater > myQueue; // ,
uniform_int_distribution u(0,100); // 0 100
default_random_engine e; //
int value;
for(int i=0;i<10;i++)
{
value=u(e);
cout << value << " ";
myQueue.push(value); //
}
cout << endl;
while(!myQueue.empty()) //
{
cout << myQueue.top() << " "; //
myQueue.pop();
}
cout << endl;
return 0;
} 小さなトップスタックを作成するには、3つのパラメータを持ち込む必要があります.
上記の優先キューの宣言を変更するだけで、以下のプログラムが得られます.
#include
int main()
{
priority_queue myQueue; // （ ）
uniform_int_distribution u(0,100); // 0 100
default_random_engine e; //
int value;
for(int i=0;i<10;i++)
{
value=u(e);
cout << value << " ";
myQueue.push(value); //
}
cout << endl;
while(!myQueue.empty()) //
{
cout << myQueue.top() << " "; //
myQueue.pop();
}
cout << endl;
return 0;
} 次に、リロードの簡単な例を示します.
#include
#include
using namespace std;
#include
class node
{
public:
node(int x=0,int y=0):m_x(x),m_y(y){}
friend bool operator(const node &n1,const node &n2) // >
{
return n1.m_x>n2.m_x;
}
friend ostream &operator<,greater > myQueue;
uniform_int_distribution u(0,100);
default_random_engine e;
int value1,value2;
for(int i=0;i<10;i++)
{
value1=u(e);
value2=u(e);
cout << "(" << value1 << ","<< value2 << ")";
myQueue.push(node(value1,value2));
}
cout << endl;
while(!myQueue.empty())
{
cout << myQueue.top() << " ";
myQueue.pop();
}
cout << endl;
return 0;
} 次に、上記の例を修正し、シミュレーション関数の例を示します.
#include
#include
using namespace std;
#include
class node
{
public:
node(int x = 0, int y = 0) :m_x(x), m_y(y) {}
int get_x()const { return m_x; }
friend ostream &operator<n2.get_x();
}
};
int main()
{
priority_queue, cmp> myQueue;
uniform_int_distribution u(0, 100);
default_random_engine e;
int value1, value2;
for (int i = 0; i<10; i++)
{
value1 = u(e);
value2 = u(e);
cout << "(" << value1 << "," << value2 << ")";
myQueue.push(node(value1, value2));
}
cout << endl;
while (!myQueue.empty())
{
cout << myQueue.top() << " ";
myQueue.pop();
}
cout << endl;
return 0;
} 上記の例では、優先キュー内の3番目のパラメータを1つの関数オブジェクトに置き換えて、優先キュー内のデータ比較の根拠とします.
次に、関数オブジェクトの知識を補足します.
c++では、他の演算子と同様に関数呼び出し演算子()を扱うことができる.この演算子はリロードすることもできます.()演算子は任意のタイプを返し、任意の数のパラメータを使用できますが、代入演算子と同様に、この演算子はメンバー関数としてのみ再ロードできます.関数呼び出し演算子定義を含むオブジェクトを関数オブジェクトと呼びます.関数オブジェクトもオブジェクトですが、それらの動作は関数のように表現されています.関数オブジェクトが呼び出されると、そのパラメータは関数呼び出し演算子のパラメータです.