[Boost-users] [heap] Boost heap and default constructors for comparators

Subject: [Boost-users] [heap] Boost heap and default constructors for comparators
From: Evan Driscoll (driscoll_at_[hidden])
Date: 2012-02-16 18:39:00

The Boost heap library (at least binomial and fibonacci heaps) requires 
a default constructor of its comparator in order to call 'pop()' on a heap.

I ran into this because I was trying to use a std::binary_negate<> 
wrapper around another comparator: this has no default constructor. So 
it's pretty easy to work around; I just have to provide a custom version 
of binary_negate.

However, is this intentional? Should it be fixed?

The problem is a little strange; it only surfaces if you call the 
'pop()' function of the heap. If you look at the error location, 
binomial_heap.hpp:831, it is

   // private constructor, just used in pop()
   explicit binomial_heap(node_list_type & child_list, size_type size):
       super_t(value_compare())

To wit, with 1.49 beta 1:

     #include <boost/heap/binomial_heap.hpp>

     using namespace boost::heap;

     struct cmp {
     # ifdef MAKE_DEFAULT_CONSTRUCTOR
         cmp() {}
     # endif
         cmp(int a) {}

         bool operator() (int a, int b) const { return a < b; }
     };

     int main() {
         cmp c(1);
         binomial_heap<int, compare<cmp> > h(c);

         h.push(1);
     # ifdef CALL_POP
         h.pop();
     # endif
     }

Compiling with CALL_POP undefined works. Adding -DCALL_POP then causes a 
compiler error (the following from GCC 4.3.2, but also witnessed with 
MSVC10):

   boost_1_49_0_beta1/boost/heap/binomial_heap.hpp: ...
   heap.cpp:21:   instantiated from here
   boost_1_49_0_beta1/boost/heap/binomial_heap.hpp:831:
          error: no matching function for call to ‘cmp::cmp()’
   heap.cpp:9: note: candidates are: cmp::cmp(int)
   heap.cpp:5: note:                 cmp::cmp(const cmp&)

Adding -DMAKE_DEFAULT_CONSTRUCTOR works again.