boostorg / heap

Boost.Heap
https://boost.org/libs/heap
18 stars 39 forks source link

Relax `MutablePriorityQueue` concept to not require that `value_type` be default constructable. #22

Open kalaxy opened 4 years ago

kalaxy commented 4 years ago

The MutablePriorityQueue concept currently requires that value_type be default constructable. I don't think that is required by an actual queue implementation. It would be great if we could relax that requirement.

kalaxy commented 4 years ago

Here is a small example case. Everything seems to work fine in the queue, when the element isn't default constructable, but when trying the concept check I get a compiler error.

#include <boost/heap/skew_heap.hpp>

struct Int {
    Int( int i ) : _i(i) {};
    Int& operator=(int i) {
        _i = i;
        return *this;
    }
    friend bool operator<(Int const &lhs, Int const &rhs) {
        return lhs._i < rhs._i;
    }
    int _i;
};

int main() {
    using PQ = boost::heap::skew_heap<Int, boost::heap::mutable_<true>>;

    PQ pq;
    auto handle = pq.push(1);

    pq.update(handle, 2);

    *handle = 3;
    pq.update(handle);

    pq.pop();

    // Uncommenting this causes a compile error.
    // BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<PQ>));
}