std::deque,queue,priority_queue

-----
#contents
-----

*deque [#nf3cbe70]
両端キュー(double-ended queue)．値をコンテナの両端から格納できる．さらに中間に値を挿入する，[]でのランダムアクセスも可能．

メンバ関数はほぼvectorと同じであり，
先頭への要素の追加，削除用関数があることが異なる．

***インクルード [#h89f568a]
 #include <deque>

***先頭への要素の追加，削除(push_front,pop_front) [#lfccecbd]
-push_front(val) : コンテナの先頭に要素を追加
 void push_front(const T& val);
-pop_front() : コンテナの先頭要素を削除
 void pop_front();

***vectorとdeque,どちらを使うべきか？ [#q7021b67]
dequeは名前からキューであるように思えるが，実際には任意の位置への値の挿入，ランダムアクセスも
サポートしていてvectorとよく似ている．
しかし，両コンテナは以下のように操作によってパフォーマンスが異なる．
-要素アクセス時間 : vector < deque
-コンテナ両端への要素の追加にかかる時間 : deque < vector
-コンテナ中間への要素の追加にかかる時間 : あまり変わらない？

一般的には要素アクセス速度が速いvectorを使えばよいが，両端への要素追加が頻繁に起こる場合はdequeを使えばよい．
また，dequeはメモリ上の非連続領域を用いる場合もあるらしい(処理系依存？)ので，
従来の配列との互換性が必要な場合はvectorを用いた方がよい．



*queue [#g62b3c8c]
FIFO(First In First Out)方式のキューとして値を格納する．
dequeを基底としたコンテナアダプタ．

***インクルード [#he9d4889]
 #include <queue>

***初期化(コンストラクタ) [#j0d0f7ec]
 explicit queue(const Container& ctnr = Container());

***メンバ関数 [#lf020290]
-front() : コンテナの最初の要素にアクセスする関数
 value_type& front();
 const value_type& front() const;
-back() : コンテナの最後の要素にアクセスする関数
 value_type& back();
 const value_type& back() const;
-size() : コンテナのサイズを返す関数
 size_type size() const;
-empty() : コンテナが空だったらtrueを返す関数．
 bool empty () const;
-push(val) : コンテナの最後に要素を追加
 void push(const T& val);
-pop() : コンテナの最初の要素を削除
 void pop();
使用例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
	queue<int> x;

	for(int i = 0; i < 5; ++i){
		x.push(i);
		cout << x.back() << " ";
	}
	cout << endl;

	for(int i = 0; i < 5; ++i){
		cout << x.front() << " ";
		x.pop();
	}
	cout << endl;

	return 0;
}
}}
実行結果
 0 1 2 3 4
 0 1 2 3 4

***deque以外のコンテナを用いたqueue [#af9693e5]
queueコンテナアダプタの標準の基底はdequeであるが，
別のコンテナを基底に指定することもできる．
別のコンテナを使用したい場合は，
 list<int> l(10, 1);
 queue<int, list<int> > q(l);
のようにする．


*priority_queue [#x2df3f89]
優先順位付きのqueue．
クラスのテンプレート仕様は，
 template < class T, class Container = vector<T>,
            class Compare = less<typename Container::value_type> > class priority_queue;
となっており，
定義時にデータ型，基底コンテナ(デフォルトはvector)，優先度を判定する比較関数オブジェクトを指定することができる．

***インクルード [#k9c98188]
 #include <queue>

***初期化(コンストラクタ) [#yf909b8a]
 explicit priority_queue(const Compare& x = Compare(),
                           const Container& y = Container());
 template <class InputIterator>
  priority_queue(InputIterator first, InputIterator last,
                   const Compare& x = Compare(),
                   const Container& y = Container());

***メンバ関数 [#p979d734]
-top() : 優先度が最も高い要素への参照を返す関数
 const value_type& top() const;
-size() : コンテナのサイズを返す関数
 size_type size() const;
-empty() : コンテナが空だったらtrueを返す関数．
 bool empty () const;
-push(val) : キューに要素を追加
 void push(const T& val);
-pop() : キューの最初の要素を削除
 void pop();
使用例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
	string s[] = {"b", "d", "a", "c", "e"};

	priority_queue<string> x(s, s+5);
	while(!x.empty()){
		cout << x.top();
		x.pop();
	}
	cout << endl;

	priority_queue<string, vector<string>, greater<string> > y(s, s+5);
	while(!y.empty()){
		cout << y.top();
		y.pop();
	}
	cout << endl;

	return 0;
}
}}
実行結果
 edcba
 abcde

***クラスオブジェクトの優先度付きキュー [#u41dab8e]
intやdoubleなどの組込オブジェクトでは優先順位が既に規定されている．
自身が作成したクラスについてpriority_queueを用いたい場合は，
operator<を定義すればよい．
例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;

class rxPriorityData
{
	int m_iPriority;
	double m_fValue;
public:
	rxPriorityData() : m_iPriority(0),m_fValue(0.0) {}
	rxPriorityData(int priority, double value) : m_iPriority(priority),m_fValue(value) {}

	int GetPriority(void) const { return m_iPriority; }
	friend std::ostream &operator<<(std::ostream &out, rxPriorityData& a);
};

inline bool operator<(rxPriorityData a, rxPriorityData b)
{
	return a.GetPriority() < b.GetPriority();
}

inline std::ostream &operator<<(std::ostream &out, rxPriorityData& a)
{
	return out << a.m_fValue << " ";
}

int main(void)
{
	rxPriorityData p[] = { rxPriorityData(2, 30.0), 
						   rxPriorityData(5, 10.0), 
						   rxPriorityData(3, 25.0), 
						   rxPriorityData(4, 35.0), 
						   rxPriorityData(1, 15.0) };

	priority_queue<rxPriorityData> z(p, p+5);
	while(!z.empty()){
		cout << z.top();
		z.pop();
	}
	cout << endl;

	return 0;
}
}}
実行結果
 10 35 25 30 15
トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS