deque,queue,priority_queue

std::deque,queue,priority_queue

deque†

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

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

インクルード†

#include <deque>

先頭への要素の追加，削除(push_front,pop_front)†

• push_front(val) : コンテナの先頭に要素を追加

  void push_front(const T& val);

• pop_front() : コンテナの先頭要素を削除

  void pop_front();

vectorとdeque,どちらを使うべきか？†

dequeは名前からキューであるように思えるが，実際には任意の位置への値の挿入，ランダムアクセスも サポートしていてvectorとよく似ている． しかし，両コンテナは以下のように操作によってパフォーマンスが異なる．

• 要素アクセス時間 : vector < deque
• コンテナ両端への要素の追加にかかる時間 : deque < vector
• コンテナ中間への要素の追加にかかる時間 : あまり変わらない？

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

queue†

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

インクルード†

#include <queue>

初期化(コンストラクタ)†

explicit queue(const Container& ctnr = Container());

メンバ関数†

• 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();

  使用例

  #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†

queueコンテナアダプタの標準の基底はdequeであるが， 別のコンテナを基底に指定することもできる． 別のコンテナを使用したい場合は，

list<int> l(10, 1);
queue<int, list<int> > q(l);

のようにする．

priority_queue†

優先順位付きのqueue． クラスのテンプレート仕様は，

template < class T, class Container = vector<T>,
           class Compare = less<typename Container::value_type> > class priority_queue;

となっており， 定義時にデータ型，基底コンテナ(デフォルトはvector)，優先度を判定する比較関数オブジェクトを指定することができる．

インクルード†

#include <queue>

初期化(コンストラクタ)†

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());

メンバ関数†

• 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();

  使用例

  #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

クラスオブジェクトの優先度付きキュー†

intやdoubleなどの組込オブジェクトでは優先順位が既に規定されている． 自身が作成したクラスについてpriority_queueを用いたい場合は， operator<を定義すればよい． 例

#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