Boost Min-Queue using custom value comparator

Question

I want to implement a shortest path search on a sparse graph (which is not a boost graph and probably cannot converted into one efficiently) and so I naturally sticked to implementing Dijkstras algorithm using a priority queue. Since my graph is a custom one, I needed to implement the distance comparison as a function object and hand it to the queue:

#include <boost/heap/fibonacci_heap.hpp>
#include <iostream>
#include <climits>

#define BIG (INT_MAX / 2)

struct node_compare {
  std::vector<int> dist;

  void set(int node, int d) {
    dist[node] = d;
  }

  node_compare(int dim) : dist(dim, BIG) {};

  /* this is a 'greater than' because boost implements max-heaps */
  bool operator()(const int& n1, const int& n2) const { 
    std::cout << "Comparing " << n1 << " < " << n2 << " = " << dist[n1] << " > " << dist[n2] << std::endl;
    return dist[n1] > dist[n2];
  }

};

typedef boost::heap::fibonacci_heap<int,  boost::heap::compare<node_compare>> priority_queue;

int main(int argc, char** argv) {
  /* comparator implementation, based on distances */
  node_compare cmp(5);

  priority_queue pq(cmp);

  cmp.set(3, 10);

  for (int i = 0; i < 5; i++)
    pq.push(i);

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

What strikes me is that somehow the priority queue seems to construct its own instance of node_compare, although I provide an instance in the constructor. This should not even be possible, since node_compare does not have a default constructor...

I know this seems a little bit like a "please find that bug for me"-kind of question, but I really don't know whether I miss some important piece of C++ semantics or boost logic here.

Answer 1

The heap does indeed store its own instance of node_compare but does not default construct it but copy constructs it from the object you pass in the constructor.

So in the line priority_queue pq(cmp); the queue copies the cmp object using the automatically generated copy constructor of the node_compare class.

If you call cmp.set(3, 10); before creating the priority_queue it should be set in the comparator of the queue, too.

I'm afraid you can't change the comparator once you created the heap. The heap object has a value_comp() member function which returns a const reference to the comparator, so you can't change the returned comparator. I think you can not change the comparator since that would invalidate the data structure in the heap.

But you can store a reference to the distance vector inside the comparator:

struct node_compare {
    const std::vector<int> &dist_;

    node_compare(const std::vector<int> &dist) : dist(dist) {};

    bool operator()(const int& n1, const int& n2) const { 
        return dist_[n1] > dist_[n2];
    }
};

You only have to be carefull that you don't change the passed distance vector after you added elements to your heap.