STL优先队列使用自定义类

Question

我在使用优先队列时遇到了很多麻烦，无法让它识别应该按哪个参数进行排序。我已经在自定义类中重载了小于运算符，但似乎没有使用它。以下是相关代码：

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;

我错过了什么？或者我做错了什么？

- bmalicoat

---

你一定是在Chai的AI课上学习 :)（翻译为程序相关内容）请参考以下链接：https://dev59.com/0UnSa4cB1Zd3GeqPPqTT - Polaris878

好的侦探技能 ;) - bmalicoat

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 时需要保持const正确。

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

- rlbond

---

出于好奇，为什么要使用operator()定义结构体而不是普通函数？ - Laurence Gonsalves

你必须这样做。你不能使用函数来专门化模板，只能使用类型（除非有特殊情况）。函数对象是STL编程的重要组成部分。一个很好的阅读材料是Scott Meyer的《Effective STL》。它解释了关于STL的所有内容以及利用它的最佳方式。 - rlbond

另外，我应该指出std::less<T>也是一个函数对象（即具有operator()的结构体）。 - rlbond

你在 struct 后面忘记加分号了。 - d33tah

为什么这里使用 '.' 而不是 '->'？ - bunnybare

Answer 2

你需要将参数声明为const，因为现在你正在使用非const引用，这意味着你可能会修改与之比较的对象（但你并没有，也应该不应该这么做）。

你没有使用const正确。你的operator<不会对Node进行修改，所以该函数应该声明为const：

bool operator<(const Node &aNode) const;

接下来，如果你在调用getTotalCost()函数时遇到了问题，很可能它也不是const的。 如果它还没有被标记为const，请将其标记为const：

int getTotalCost(void) const;

你的代码现在更符合常量正确性。

此外，二元操作符通常在类外实现：

class Node
{
public:
    // ...

    int getTotalCost(void) const;

    // ...
};

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

- GManNickG

---

实际上，我不同意在某些情况下类之外定义 operator< 的定义。如果它很清楚应该做什么，我认为把它定义成成员函数并不是什么大问题。此外，它还可以使用 Boost.Operators 功能模块。 - rlbond