c++ - STL优先级队列和指针重载

Question

这是我第一次使用优先队列。我正在尝试为学校实现 Dijkstra 算法，我认为我需要一个最小堆来执行此操作。现在我的节点是指针，我想比较它们的权重，但我认为我不能用指针重载 > 和 <？有什么办法可以做到这一点吗？

到目前为止的代码:

priority_queue<Node*, vector<Node*>, node_comparison> minHeap;

然后我有一个结构来比较节点的权重

struct node_comparison 
{
   bool operator<( const Node* a, const Node* b ) const 
   {
    return a->totalWeight < b->totalWeight;
   }
};

但是它说这个运算符函数的参数太多了。一段时间以来，我一直在尝试弄清楚如何用我的节点管理一个最小堆优先级队列，但一直卡住。有什么想法吗？

Answer 1

如果我正确理解你的问题，我相信你真正想要的是使 node_comparison 成为一个 functor(更具体地说，一个二元谓词):

struct node_comparison 
{
    bool operator () ( const Node* a, const Node* b ) const 
    {
        return a->totalWeight < b->totalWeight;
    }
};

仿函数是一个类，其对象提供调用运算符 (operator ()) 的重载，因此可以使用与调用函数相同的语法来调用:

Node* p1 = ...;
Node* p2 = ...;
node_comparison comp;
bool res = comp(p1, p2) // <== Invokes your overload of operator ()

在内部，std::priority_queue 将或多或少像我在上面的代码片段中所做的那样实例化您的谓词，并以这种方式调用它以执行其元素之间的比较。

---

与常规函数相比，仿函数的优势在于它们可以保存状态信息(目前您可能不需要，但通常会被证明是可取的):

#include <cmath>

struct my_comparator
{
    my_comparator(int x) : _x(x) { }

    bool operator () (int n, int m) const
    {
        return abs(n - _x) < abs(m - _x);
    }

    int _x;
};

例如，上面的谓词根据整数与构造时提供的另一个整数的距离来比较整数。这就是它的使用方式:

#include <queue>
#include <iostream>

void foo(int pivot)
{
    my_comparator mc(pivot);
    std::priority_queue<int, std::deque<int>, my_comparator> pq(mc);

    pq.push(9);
    pq.push(2);
    pq.push(17);

    while (!pq.empty())
    {
        std::cout << pq.top();
        pq.pop();
    }
}

int main()
{
    foo(7);

    std::cout << std::endl;

    foo(10);
}