Boost logo

Boost Users :

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):

To wit, with 1.49 beta 1:

     #include <boost/heap/binomial_heap.hpp>

     using namespace boost::heap;

     struct cmp {
         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);

     # ifdef CALL_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

   boost_1_49_0_beta1/boost/heap/binomial_heap.hpp: ...
   heap.cpp:21: instantiated from here
          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&)


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at