std::priority_queue

C++

よく嵌るのでメモ。

  • 大きなものから出てくる
  • 比較関数の実装法は頭に入れておく 
priority_queue<Hoge> pq;

のように使うHogeクラス では、デフォルトでは比較に std::less<Hoge> が使われるので operator< の実装が必要。

class Hoge {
  ...
  bool operator<(const Hoge &a) const;
};

二つのconst を忘れると悲惨なことになります。


比較関数の部分を分離しようとすると、「型」が必要なので普通の関数でなくファンクタクラスが必要。

struct Compare : public binary_function<Hoge,Hoge,bool> {
  bool operator()(const Hoge &a, const Hoge &b) {
    ...
  }
};
priority_queue<Hoge, vector<Hoge>, Compare> pq;

使うコンテナを明示的に書かなきゃいけなくなるのが気持ち悪い。

コンストラクタの引数の方を使って

priority_queue<Hoge> pq( Compare() );

と書きたいのだが、そうすると関数宣言に間違われるので一時変数に格納するか以下のように書く。

priority_queue<Hoge> pq( (Compare()) );

すると、そんなコンストラクタ無いよというエラーが出る。 ← いまここ


以下、使用例としてダイクストラ法のテンプレっぽいもの。
小さなものから取り出したいので比較関数の定義に注意が必要。

#include <vector>
#include <queue>
#include <functional>
using namespace std;
const int NONE = -1;

struct S {
  int node, cost, prev;
  S(int n, int c, int p): node(n), cost(c), prev(p) {}
  bool operator>(const S &s) const {
    return cost > s.cost;
  }
};

class G {
  int n;
  vector<vector<int> > cost;
  vector<int> minc;
  vector<int> prev;
public:
  G(int n): n(n), cost(n,vector<int>(n,NONE)), minc(n,NONE), prev(n) {}

  void dijkstra(int start) {
    minc.assign(n,NONE);
    priority_queue<S, vector<S>, greater<S> > pq;
    pq.push(S(start,0,NONE));
    while (!pq.empty()) {
      S s = pq.top();
      pq.pop();
      if (minc[s.node] != NONE) { continue; }
      minc[s.node] = s.cost;
      prev[s.node] = s.prev;
      for (int i = 0; i < n; ++i) {
        if (minc[i] == NONE && cost[s.node][i] != NONE) {
          pq.push(S(i, s.cost+cost[s.node][i], s.node));
        }
      }
    }
  }

  void input();
  void output();
};