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

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-10-27 (木) 15:09:17