STL priority_queue 对 <int, struct> 错误

Question

在网格中寻找最短路径并努力正确设置优先级队列。

struct position{
    int row;
    int col;
    position* parent;
    position(int a, int b):row(a),col(b), parent(nullptr){}
};

vector<position>vec;


priority_queue<pair<int, position>, vector<pair<int, position>>, greater<pair<int, position>>>pq;

int distance = 0;
position *t = new p(0,0);

pq.push(make_pair(distance, t));

出现此错误：

no matching function for call to ‘std::priority_queue, std::vector >, std::greater > >::push(std::pair)’
     pq.push(make_pair(distance, t));

Answer 1

此处优先级队列声明与您尝试推送的内容不匹配。

声明应该类似于

priority_queue<pair<obj1,obj2>pq;

obj1/obj2 可以是 int 或 pair<obj,obj>

这样的声明后你可以使用

pq.push(make_pair(obj1,obj2))

Answer 2

您的代码中存在两个主要问题。

首先，您的 priority_queue 是 std::pair<int, position>，但您正试图推入 std::pair<int, position*>。

其次，std::greater<T>依赖于底层类型T的>运算符。在您的例子中，它是 std::pair<int, position>，其 > 运算符取决于 position 的 < 运算符（参见 this reference）。您需要为 position 提供 <，或者，您可以使用自定义比较函子类型。

Answer 3

您需要编写一个仿函数（或使用 lambda）来比较距离 - 位置对，std::greater 不会自动为您完成。试试这个片段：

struct position {
    int row;
    int col;
    position* parent;
    position(int a, int b) :row(a), col(b), parent(nullptr) {}
};

typedef std::pair<int, position> dist_pos_t;

class compare
{
public:
    bool operator()(const dist_pos_t& lhs, const dist_pos_t& rhs)
    {
        return rhs.first < lhs.first;
    }

};
std::priority_queue<dist_pos_t, std::vector<dist_pos_t>, compare >pq;

int main() {
    int distance = 0;
    position *t = new position(0, 0);
    pq.push(std::make_pair(distance, *t));
}

STL priority_queue 对 <int, struct> 错误

STL priority_queue of pairs<int, struct> error

c++

struct

priority-queue