将 priority_queue 的 int 与自定义比较一起使用

Question

我有从 1 到 n 的数字，以及大小为 n 的优先级数组 P。我想声明一个使用 P 作为优先级的优先级队列。

我不想定义一个包含数字及其优先级的新类型对象，我想使用一个 int 对象的优先级队列并将依赖于 P 的自定义比较对象传递给std::priority_queue。我尝试了以下但它不起作用：

std::priority_queue<int, vector<int>, [P](int i, int j){ return P[i]<P[j]; }> PQ;

我还尝试用 bool operator(int i, int j) {P[i] < P[j]} 成员和构造函数定义 class，我可以将 P 传递给它，但这也没有用。

我应该如何声明我的优先队列？

以下似乎有效：

class MyLess{
 public:
  MyLess(const int* p) {p_ = p;}
  bool operator()(const int &lhs, const int &rhs) const { return p_[lhs] < p_[rhs]; }

 private:
  const int* p_;
};
...
std::priority_queue<int, vector<int>, MyLess> PQ(P);

Answer 1

选项 #1

#include <functional>
// ...
std::priority_queue<int
                  , std::vector<int>
                  , std::function<bool(int,int)>
                  >
                  PQ([P] (int i, int j) { return P[i] < P[j]; });

选项#2

auto cmp = [P] (int i, int j) { return P[i] < P[j]; };

std::priority_queue<int, std::vector<int>, decltype(cmp)> PQ(cmp);

将 priority_queue 的 int 与自定义比较一起使用

Using a priority_queue of int with custom compare

c++

c++11

priority-queue

选项 #1

选项#2