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

  使用例

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

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

  使用例

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  #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<を定義すればよい． 例

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43

#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