Definiowanie funkcji porównania dla sterty Fibonacci w boostu

Question

Potrzebuję używać sterty Fibonacciego w moim projekcie i próbuję użyć go z biblioteki boost. Ale nie mogę dowiedzieć się, jak skonfigurować funkcję porównywania zdefiniowaną przez użytkownika dla dowolnego typu danych. Muszę skonstruować stertę min dla węzła struktury zdefiniowaną następująco:

struct node 
{ 
    int id; 
    int weight; 
    struct node* next; 
       /* dist is a global array of integers */ 
    bool operator > (struct node b)         //Boost generates a Max-heap. What I need is a min-heap. 
      {return dist[id] < dist[b.id] ? 1:0 ;}    //That's why "<" is used for "operator >". 
    bool operator < (struct node b) 
      {return dist[id] > dist[b.id] ? 1:0 ;} 
    bool operator >=(struct node b) 
      {return dist[id] <= dist[b.id] ? 1:0 ;} 
    bool operator <=(struct node b) 
      {return dist[id] >= dist[b.id] ? 1:0 ;} 

    node() 
    { 
      id=0; 
      weight=0; 
      next=NULL; 
    } 

}; 

Sprawdziłem dokumentację i była klasa porównania. Ale nie zawierało żadnego elementu. Proszę mi powiedzieć, jak skonfigurować funkcję porównywania zdefiniowaną przez użytkownika. Z góry dziękuję.

Answer 1

fibonacci_heap wykonuje porównanie funktor, który jest skutecznie struct lub class z operatora wywołania funkcji - operator(). Mam zamiar uprościć node struct, ale powinieneś być w stanie korzystać z tego z niewielkimi modyfikacjami:

struct node 
{ 
    int id; 

    node(int i) 
     : id(i) 
    { } 
}; 

Teraz musimy zdefiniować klasę, która porównuje node s. Będzie to miało operator() że trwa 2 węzły przez const odniesienia, i zwracają bool:

struct compare_node 
{ 
    bool operator()(const node& n1, const node& n2) const 
    { 
     return n1.id > n2.id; 
    } 
}; 

Możemy zadeklarować naszą sterty następująco:

boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>> heap; 

pełny przykład:

#include <boost/heap/fibonacci_heap.hpp> 

#include <iostream> 

struct node 
{ 
    int id; 

    node(int i) 
     : id(i) 
    { } 
}; 

struct compare_node 
{ 
    bool operator()(const node& n1, const node& n2) const 
    { 
     return n1.id > n2.id; 
    } 
}; 

int main() 
{ 
    boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>> heap; 
    heap.push(node(3)); 
    heap.push(node(2)); 
    heap.push(node(1)); 

    for(const node& n : heap) { 
     std::cout << n.id << "\n"; 
    } 
}