STL优先级队列和指针重载 [英] STL priority queue and overloading with pointers
问题描述
这是我第一次使用优先级队列.我正在尝试为学校实现Dijkstra的算法,所以我认为我需要一个最小的堆才能做到这一点.现在我的节点是指针,我想比较它们的权重,但是我认为我不能重载>和<.有指针吗?有什么办法可以做到这一点?
This is my first time using a priority queue. I'm trying to implement Dijkstra's algorithm for school and I figured I need a min heap to do this. Right now my nodes are pointers and I want to compare their weight, but I don't think I can overload > and < with pointers? Is there a way I could accomplish this?
到目前为止的代码:
priority_queue<Node*, vector<Node*>, node_comparison> minHeap;
然后我有一个结构来比较节点的权重
And then I have a struct to compare the node's weights
struct node_comparison
{
bool operator<( const Node* a, const Node* b ) const
{
return a->totalWeight < b->totalWeight;
}
};
但是,该操作符函数的参数过多.我一直试图弄清楚我现在如何可以管理与节点的最小堆优先级队列,并保持不动.有什么想法吗?
However it says there are too many parameters for this operator function. I've been trying to figure out how I could manage a min heap priority queue with my nodes for a while now and keep getting stuck. Any ideas?
推荐答案
如果我正确理解了您的问题,我相信您真正想要的是将node_comparison
用作 functor (更具体地说,是二进制谓词):
If I understand your question correctly, I believe what you actually want is to make node_comparison
a functor (more specifically, a binary predicate):
struct node_comparison
{
bool operator () ( const Node* a, const Node* b ) const
{
return a->totalWeight < b->totalWeight;
}
};
函子是一个类,其对象提供了调用操作符(operator ()
)的重载,因此可以使用与调用函数时相同的语法进行调用:
A functor is a class whose objects provide an overload of the call operator (operator ()
) and, therefore, can be invoked with the same syntax you would use for invoking a function:
Node* p1 = ...;
Node* p2 = ...;
node_comparison comp;
bool res = comp(p1, p2) // <== Invokes your overload of operator ()
在内部,std::priority_queue
会像我在上面的代码片段中那样实例化您的谓词,并以这种方式调用它以在其元素之间进行比较.
Internally, std::priority_queue
will instantiate your predicate more or less like I did in the code snippet above, and invoke it that way to perform comparisons between its elements.
与常规函数相比,函子的优势在于它们可以保存 state 信息(您暂时可能不需要某些东西,但通常证明是合乎需要的):
The advantage of functors over regular functions is that they could hold state information (something you probably won't need for the moment, but which often turns out to be desirable):
#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;
};
例如,上述谓词根据整数与构造时提供的另一个整数的距离来比较整数.这是可以使用的方式:
The above predicate, for instance, compares integers based on how distant they are from another integer provided at construction time. This is how it could be used:
#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);
}
这篇关于STL优先级队列和指针重载的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!