Priority queue comparator on object with const member

Question

I'm trying to implement a priority queue which uses an object which has a const member that is used to define the priority of objects in the queue. The following is a stripped down version of what I'm using

#include <vector>
#include <queue>

class Event {
public:
    Event(float _time) : time(_time) {};
    const float time;
};

struct EventComp {
public:
    bool operator()(const Event& a, const Event& b) const {
      return a.time < b.time;
    }
};

class EventQueue {
private:
    std::priority_queue<Event, std::vector<Event>, EventComp> events;
};


int main(int argc, char *argv[])
{
    EventQueue q;
}

When I try to compile (using g++ -std=c++11), I get the following error messages, which I don't quite understand.

g++ -std=c++11 events.cpp -o events
In file included from /usr/include/c++/4.8/queue:62:0,
                 from events.cpp:2:
/usr/include/c++/4.8/bits/stl_heap.h: In instantiation of ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Event*, std::vector<Event> >; _Distance = long int; _Tp = Event; _Compare = EventComp]’:
/usr/include/c++/4.8/bits/stl_heap.h:448:15:   required from ‘void std::make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Event*, std::vector<Event> >; _Compare = EventComp]’
/usr/include/c++/4.8/bits/stl_queue.h:411:48:   required from ‘std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&) [with _Tp = Event; _Sequence = std::vector<Event>; _Compare = EventComp]’
events.cpp:15:7:   required from here
/usr/include/c++/4.8/bits/stl_heap.h:315:29: error: use of deleted function ‘Event& Event::operator=(Event&&)’
    *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
                             ^
events.cpp:4:7: note: ‘Event& Event::operator=(Event&&)’ is implicitly deleted because the default definition would be ill-formed:
 class Event {
       ^
events.cpp:4:7: error: non-static const member ‘const float Event::time’, can’t use default assignment operator
In file included from /usr/include/c++/4.8/queue:62:0,
                 from events.cpp:2:
/usr/include/c++/4.8/bits/stl_heap.h:321:29: error: use of deleted function ‘Event& Event::operator=(Event&&)’
    *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
                             ^

I assume that some part of the internal structure of the priority_queue needs the move assignment operator to insert elements, but the const member seems to prevent that operator from being defined. I tried using the rule of five, but it didn't seem to work out. What do I need to add to the class definitions to get this working?

edit: I'm aware that I can remove the const qualifier from the member variable, make it private, and add an accessor member function to get the value of the variable, but I would rather have it public and const, so I'm interested in solutions which keep the member variable as it is in the example (if that is even possible).

Ryter

FWIW its works on clang – Haldane

to narrow down the problem see if vector<Event> compiles – Pugh

A number of vector and priority_queue operations requires MoveAssignable. In your case with a const data member there's pretty much no way to give it sensible assignment semantics. Make time non-const and if you want to avoid modifications, make it private and provide a getter instead. – Heldentenor

A more inefficient alternative, if you insist on keeping the const, is to add a level of indirection by using a priority_queue of, e.g., unique_ptr<Event>, and adjusting your comparator accordingly. – Heldentenor

Answer 1

The default constructor of std::priority_queue<Event, ...> requires Event to be MoveAssignable because it calls std::make_heap (which has this requirement). Event is not MoveAssignable because of the const float time data member. If you remove the const qualifier from this data member, your code should compile.

I'm aware that I can remove the const qualifier from the member variable, make it private, and add an accessor member function to get the value of the variable, but I would rather have it public and const, so I'm interested in solutions which keep the member variable as it is in the example (if that is even possible).

Ultimately, to use this std::lib facility, Event will have to be MoveAssignable. This requirement can be met with either a move assignment operator, or a copy assignment operator. Either or both of these can be supplied by you, or the compiler. But when you have a const data member, the compiler supplied special member will be implicitly deleted.

Go ahead and supply your own copy and/or move assignment operator if you desire:

class Event {
public:
    Event(float _time) : time(_time) {};
    const float time;

    Event(Event&&) = default;
    Event& operator=(Event&&);  // Supply this
};

I do not have a good guess as to what you might want the move (or copy) assignment operator to do, since you have stated that once constructed, you do not want time to ever change. That is a design decision which you must work out (and has more to do with software design in general, than C++ syntax).

---

<aside>

In the comments of the question POW notes that the code in the question compiles with clang (more accurately, with libc++). The reason for this is a nearly conforming extension in libc++:

The standard specifies this priority_queue constructor:

explicit priority_queue(const Compare& x = Compare(),
                        Container&& c = Container());

which calls std::make_heap with the container c. But the standard also gives leeway to implementors to replace member function signatures with default values, with equivalent overloads. libc++ replaces this single signature with the following three:

priority_queue();
explicit priority_queue(const Compare& x);
explicit priority_queue(const Compare& x, Container&& c);

And only the 3rd needs to call std::make_heap. Thus the default constructor in libc++ places fewer requirements on the value_type.

I said nearly conforming. The part that is not completely conforming is that the default constructor is not declared explicit. This was a conscious design decision on the part of the implementor to make priority_queue easier to use.

</aside>

General

Hmm, are you sure making the default ctor of the container adaptors explicit wasn't a defect? The container default ctors used to be explicit too until fixed in a DR. – Heldentenor

OTOH, they have no initializer_list constructors, which is I guess why LWG 2193 skipped them. – Heldentenor

@T.C.: I'm sure it is a defect. It just hasn't been reported yet. ;-) – General