Coda di priorità STL e sovraccarico con puntatori

Question

Questa è la prima volta che utilizzo una coda di priorità. Sto cercando di implementare l'algoritmo di Dijkstra per la scuola e ho pensato di aver bisogno di un mucchio minimo per farlo. In questo momento i miei nodi sono puntatori e voglio confrontare il loro peso, ma non penso di poter sovraccaricare> e < con i puntatori? C'è un modo per farlo?

Codice fino a questo punto:

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

E poi ho una struct per confrontare i pesi del nodo

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

Tuttavia dice che ci sono troppi parametri per questa funzione dell'operatore. Ho cercato di capire come riuscire a gestire una coda di priorità heap minima con i miei nodi per un po 'di tempo e rimanere bloccati. Qualche idea?

Answer 1

Se ho capito bene la tua domanda, credo che quello che realmente vuole è quello di rendere node_comparison un funtore (più precisamente, un predicato binario):

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

un funtore è una classe i cui oggetti di fornire un overload dell'operatore di chiamata (operator()) e, quindi, può essere invocato con la stessa sintassi si usa per invocare una funzione:

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

Internamente, std::priority_queue istanzia il tuo predicato più o meno come ho fatto nel frammento di codice sopra, e lo invoco in questo modo per eseguire confronti tra i suoi elementi.

---

Il vantaggio di funtori oltre funzioni regolari è che essi potrebbero contenere stato informazioni (qualcosa che probabilmente non sarà necessario per il momento, ma che spesso si rivela auspicabile):

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

Il predicato precedente, ad esempio, confronta gli interi in base alla distanza da un altro intero fornito in fase di costruzione. Ecco come potrebbe essere utilizzato:

#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

Si avrebbe bisogno il vostro funtore confronto per attuare bool operator()(....), non bool operator<(....):

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