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; 

什麼我是否錯過和/或做錯了？

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; 

請注意，您需要爲const，正確的在你的totalCost定義。

編輯：現在，C++ 11是在這裏，你不需要從的std :: binary_function繼承了（這意味着你不需要＃包括功能）

Answer 2

您需要製作參數const，因爲截至目前您正在給它一個非成本參考，這意味着您可能會修改您正在比較的對象。 （你不是，也許不應該）。

你不是const正確的。您operator<不作修改的節點，所以函數應該是const：

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(); 
}