STL-Prioritätswarteschlange für benutzerdefinierte Klasse

Question

Ich habe große Schwierigkeiten, meine Prioritätswarteschlange zu erkennen, nach welchem ​​Parameter sie sortiert werden soll. Ich habe den "less than" -Operator in meiner benutzerdefinierten Klasse überladen, scheint ihn aber nicht zu verwenden. Hier ist der relevante Code:

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() gibt ein int

main.cpp

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

Was vermisse ich und/oder mache ich falsch?

Answer 1

less<vector<Node*>::value_type> bedeutet, dass Ihr Komparator die Zeiger zueinander werden, was bedeutet, Ihren Vektor vergleicht durch das Layout im Speicher sortiert werden der Knoten.

Sie wollen, so etwas tun:

#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; 

Beachten Sie, dass Sie benötigen const-correct in Ihrer Definition von totalCost sein.

EDIT: Nun, da C++ 11 ist hier, Sie brauchen nicht mehr von std :: binary_function erben (was bedeutet, Sie müssen funktional nicht # include)

Answer 2

Sie müssen Ihren Parameter const eingeben, da Sie ab sofort eine nicht kostenpflichtige Referenz angeben, was bedeutet, dass Sie das Objekt, mit dem Sie vergleichen, ändern können. (Was Sie nicht sind und wahrscheinlich nicht sollten).

Sie sind nicht const-correct. Ihre operator< nicht Veränderungen an den Knoten, so dass die Funktion const sein sollte:

bool operator<(const Node &aNode) const; 

Danach, wenn Sie Schwierigkeiten haben, den Aufruf der getTotalCost() Funktion, ist es wahrscheinlich, dass es nicht so gut ist konst. Markiere es als const wenn es nicht schon ist:

int getTotalCost(void) const; 

Dein Code ist jetzt (mehr) const-correct.

Auf einer Seite zur Kenntnis, sind binäre Operatoren in der Regel außerhalb der Klasse implementiert:

class Node 
{ 
public: 
    // ... 

    int getTotalCost(void) const; 

    // ... 
}; 

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