自定义类的STL优先级队列

Question

我在使用优先级队列来识别它应该排序的参数时遇到了很多麻烦.我在我的自定义类中重载了less运算符但它似乎没有使用它.这是相关的代码:

Node.h

class Node
{   
public:
    Node(...);
    ~Node();
    bool operator<(Node &aNode);
...
}

Node.cpp

#include "Node.h"
bool Node::operator<(Node &aNode)
{
    return (this->getTotalCost() < aNode.getTotalCost());
}

getTotalCost()返回一个int

main.cpp中

priority_queue<Node*, vector<Node*>,less<vector<Node*>::value_type> > nodesToCheck;

我错过了什么和/或做错了什么？

Answer 1

less<vector<Node*>::value_type>意味着比较器将指针相互比较,这意味着您的向量将按节点内存中的布局进行排序.

你想做这样的事情:

#include <functional>
struct DereferenceCompareNode : public std::binary_function<Node*, Node*, bool>
{
    bool operator()(const Node* lhs, const Node* rhs) const
    {
        return lhs->getTotalCost() < rhs->getTotalCost();
    }
};

// later...
priority_queue<Node*, vector<Node*>, DereferenceCompareNode> nodesToCheck;

请注意,您需要在定义中使用const-correct totalCost.

编辑:既然C++ 11在这里,你不再需要从std :: binary_function继承(这意味着你不需要#include功能)

Answer 2

你需要制作你的参数const,因为到目前为止你给它一个非成本参考,这意味着你可以修改你正在比较的对象.(你不是,也可能不应该).

你不是正确的.您operator<没有对Node进行修改,因此该函数应该是const:

bool operator<(const Node &aNode) const;

在那之后,如果你在调用getTotalCost()函数时遇到问题,那么它很可能也不是const.如果它还没有,请将其标记为const:

int getTotalCost(void) const;

您的代码现在(更多)const-correct.

另外,二元运算符通常在类外实现:

class Node
{
public:
    // ...

    int getTotalCost(void) const;

    // ...
};

bool operator<(const Node& lhs, const Node& rhs)
{
    return lhs.getTotalCost() < rhs.getTotalCost();
}