Kolejka priorytetowa STL i przeciążanie za pomocą wskaźników

Question

To jest mój pierwszy raz przy użyciu kolejki priorytetowej. Próbuję zaimplementować algorytm Dijkstry do szkoły i doszedłem do wniosku, że potrzebuję sterty min. Teraz moje węzły są wskaźnikami i chcę porównać ich wagę, ale nie sądzę, że mogę przeciążać> i < za pomocą wskaźników? Czy jest sposób, w jaki mogę to osiągnąć?

Code tak daleko:

priority_queue<Node*, vector<Node*>, node_comparison> minHeap; 

A potem mam struct porównywania ciężarów węzła

struct node_comparison 
{ 
    bool operator<(const Node* a, const Node* b) const 
    { 
    return a->totalWeight < b->totalWeight; 
    } 
}; 

Jednak mówi, że nie ma zbyt wielu parametrów dla tej funkcji operatora. Próbowałem dowiedzieć się, jak od pewnego czasu mogę zarządzać kolejką priorytetową minowych stert z moimi węzłami i dalej utknąć. Jakieś pomysły?

Answer 1

Jeśli dobrze rozumiem pytanie, wierzę, co rzeczywiście chcesz to zrobić node_comparisonfunktor (dokładniej binarny predykat):

struct node_comparison 
{ 
    bool operator() (const Node* a, const Node* b) const 
    { 
     return a->totalWeight < b->totalWeight; 
    } 
}; 

funktora to klasa, której obiekty zapewniają szybkość rozpuszczania przeciążenie operatora połączeń (operator()), a zatem mogą być wywoływane z tej samej składni byłoby użyć do wywoływania funkcji:

Node* p1 = ...; 
Node* p2 = ...; 
node_comparison comp; 
bool res = comp(p1, p2) // <== Invokes your overload of operator() 

Wewnętrznie std::priority_queue stwórz twój predykat mniej więcej tak, jak to zrobiłem w powyższym fragmencie kodu, i wywołaj go w ten sposób, aby dokonać porównań między jego elementami.

---

Zaletą funktorów ponad regularnych funkcji jest to, że mogą one posiadać państwu informacje (coś, czego prawdopodobnie nie będzie potrzebne w tej chwili, ale często okazuje się być pożądane):

#include <cmath> 

struct my_comparator 
{ 
    my_comparator(int x) : _x(x) { } 

    bool operator() (int n, int m) const 
    { 
     return abs(n - _x) < abs(m - _x); 
    } 

    int _x; 
}; 

Powyższy predykat, na przykład, porównuje liczby całkowite w zależności od tego, jak dalece są od innej liczby całkowitej podanej w czasie budowy. W ten sposób może on być wykorzystany:

#include <queue> 
#include <iostream> 

void foo(int pivot) 
{ 
    my_comparator mc(pivot); 
    std::priority_queue<int, std::deque<int>, my_comparator> pq(mc); 

    pq.push(9); 
    pq.push(2); 
    pq.push(17); 

    while (!pq.empty()) 
    { 
     std::cout << pq.top(); 
     pq.pop(); 
    } 
} 

int main() 
{ 
    foo(7); 

    std::cout << std::endl; 

    foo(10); 
} 

Answer 2

Będziesz potrzebować Twój porównanie funktor wdrożyć bool operator()(....), nie bool operator<(....):

struct node_comparison 
{ 
    bool operator()(const Node* a, const Node* b) const 
    { 
    return a->totalWeight < b->totalWeight; 
    } 
};