Hàng đợi ưu tiên STL trên lớp tùy chỉnh

Question

Tôi đang gặp rất nhiều sự cố khi nhận hàng đợi ưu tiên của mình để nhận ra thông số cần sắp xếp. Tôi đã quá tải các nhà điều hành ít hơn trong lớp tùy chỉnh của tôi, nhưng nó dường như không sử dụng nó. Dưới đây là các mã có liên quan:

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() trả về một int

main.cpp

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

gì Tôi đang thiếu và/hoặc làm sai?

Answer 1

less<vector<Node*>::value_type> Phương tiện mà so sánh của bạn so sánh con trỏ với nhau, có nghĩa là vector của bạn sẽ được sắp xếp theo cách bố trí trong bộ nhớ của các nút.

Bạn muốn làm một cái gì đó như thế này:

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

Lưu ý rằng bạn cần phải const-đúng định nghĩa của bạn về totalCost.

EDIT: Bây giờ C++ 11 là ở đây, bạn không cần phải kế thừa từ std :: binary_function nữa (có nghĩa là bạn không cần phải #include chức năng)

Answer 2

Bạn cần thực hiện tham số const, bởi vì hiện tại bạn đang cung cấp tham chiếu không phải trả phí, có nghĩa là bạn có thể sửa đổi đối tượng mà bạn đang so sánh. (Mà bạn không, và có lẽ không nên).

Bạn không phải là chính xác. operator< của bạn không làm thay đổi đến Node, do đó chức năng nên được const:

bool operator<(const Node &aNode) const; 

Sau đó, nếu bạn gặp khó khăn khi gọi getTotalCost() chức năng, nó có khả năng rằng nó không phải là const là tốt. Đánh dấu nó là const nếu chưa:

int getTotalCost(void) const; 

Mã của bạn bây giờ là (nhiều hơn) chính xác.

Trên một mặt lưu ý, các nhà khai thác nhị phân thường được thực hiện bên ngoài lớp:

class Node 
{ 
public: 
    // ... 

    int getTotalCost(void) const; 

    // ... 
}; 

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