Приоритетная очередь STL для пользовательского класса

У меня много проблем с тем, чтобы моя очередь приоритетов распознавала, по какому параметру она должна сортироваться. Я перегрузил оператор меньше чем в своем пользовательском классе, но, похоже, он его не использует. Вот соответствующий код:

Узел.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() возвращает целое число

main.cpp

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

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


c++ stl comparator priority-queue
person bmalicoat    schedule 09.10.2009    source источник
comment
Вы должны быть в классе искусственного интеллекта Chai :) /   -  person Polaris878    schedule 09.10.2009
comment
Хорошие детективные способности ;)   -  person bmalicoat    schedule 09.10.2009

Ответы (2)


arrow_upward
22
arrow_downward

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.

РЕДАКТИРОВАТЬ: теперь, когда С++ 11 здесь, вам больше не нужно наследовать от std::binary_function (что означает, что вам не нужно #include функционал)

person rlbond    schedule 09.10.2009
comment
Из любопытства: зачем определять структуру с оператором(), а не просто функцию? - person Laurence Gonsalves; 09.10.2009
comment
Вы должны. Вы не можете специализировать шаблоны с помощью функций, только типов (исключая особые обстоятельства). Функциональные объекты являются очень важной частью программирования STL. Отличная книга для чтения — Effective STL Скотта Мейера. В ней объясняется все о STL и лучших способах ее использования. - person rlbond; 09.10.2009
comment
Кроме того, я должен указать, что std::less<T> также является функциональным объектом (т.е. структурой с operator()) - person rlbond; 21.12.2009
comment
Вы забыли точку с запятой после структуры. - person d33tah; 03.03.2013
comment
Почему это использует '.' и не '->'? - person bunnybare; 10.11.2014

arrow_upward
14
arrow_downward

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

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

bool operator<(const Node &aNode) const;

После этого, если у вас возникнут проблемы с вызовом функции getTotalCost(), вполне вероятно, что она тоже не является константой. Отметьте его как 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();
}
person GManNickG    schedule 09.10.2009
comment
На самом деле, я должен не согласиться с определением operator< вне класса в некоторых случаях. Если ясно, что он должен делать, я не думаю, что это действительно большая проблема, чтобы определить его как члена. Кроме того, он позволяет использовать Boost.Operators. - person rlbond; 09.10.2009