std::deque,queue,priority_queue deque†両端キュー(double-ended queue).値をコンテナの両端から格納できる.さらに中間に値を挿入する,[]でのランダムアクセスも可能. メンバ関数はほぼvectorと同じであり, 先頭への要素の追加,削除用関数があることが異なる. インクルード†#include <deque> 先頭への要素の追加,削除(push_front,pop_front)†
vectorとdeque,どちらを使うべきか?†dequeは名前からキューであるように思えるが,実際には任意の位置への値の挿入,ランダムアクセスも サポートしていてvectorとよく似ている. しかし,両コンテナは以下のように操作によってパフォーマンスが異なる.
一般的には要素アクセス速度が速いvectorを使えばよいが,両端への要素追加が頻繁に起こる場合はdequeを使えばよい. また,dequeはメモリ上の非連続領域を用いる場合もあるらしい(処理系依存?)ので, 従来の配列との互換性が必要な場合はvectorを用いた方がよい. queue†FIFO(First In First Out)方式のキューとして値を格納する. dequeを基底としたコンテナアダプタ. インクルード†#include <queue> 初期化(コンストラクタ)†explicit queue(const Container& ctnr = Container()); メンバ関数†
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()); メンバ関数†
クラスオブジェクトの優先度付きキュー†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 |