c++ - 自定义类上的 STL 优先级队列

Question

我很难让我的优先级队列识别它应该排序的参数。我在自定义类中重载了小于运算符，但它似乎没有使用它。以下是相关代码：

节点.h

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

节点.cpp

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

getTotalCost() 返回一个整数

主文件

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;

请注意，您的totalCost.

编辑：现在 C++11 就在这里，您不再需要从 std::binary_function 继承（这意味着您不需要#include 功能）

Answer 2

您需要创建您的参数const，因为到目前为止您正在给它一个非成本参考，这意味着您可能会修改您正在比较的对象。（你不是，而且可能不应该）。

你不是正确的。您operator<没有对节点进行修改，因此函数应该是 const：

bool operator<(const Node &aNode) const;

之后，如果您在调用该getTotalCost()函数时遇到问题，很可能它也不是 const。如果还没有，则将其标记为 const：

int getTotalCost(void) const;

您的代码现在（更多）是 const 正确的。

附带说明一下，二元运算符通常在类之外实现：

class Node
{
public:
    // ...

    int getTotalCost(void) const;

    // ...
};

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