Очередь приоритетов STL для пользовательских классов - PullRequest
Новая
       15

Очередь приоритетов STL для пользовательских классов

14 голосов
/ 09 октября 2009

У меня много проблем с тем, чтобы моя очередь с приоритетом распознала, по какому параметру она должна быть отсортирована. Я перегрузил оператор 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;

Что я пропускаю и / или делаю неправильно?

Ответы [ 2 ]

22 голосов
/ 09 октября 2009

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)

14 голосов
/ 09 октября 2009

Вам нужно сделать свой параметр const, потому что на данный момент вы даете ему бесплатную ссылку, что означает, что вы можете изменить объект, с которым сравниваете. (Которым вы не являетесь, и, вероятно, не должны).

Ты не в порядке. Ваш operator< не вносит изменений в узел, поэтому функция должна быть постоянной: 

bool operator<(const Node &aNode) const;

После этого, если у вас возникли проблемы с вызовом функции getTotalCost(), вполне вероятно, что она также не является константой. Отметьте это как 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();
}
...