Comparators in std::priority_queue

Question

Is there a reason that the std::priority_queue's constructor accepts a comparator by constant reference? What if the comparator goes out of scope?

I was thinking about this in the context of possibly moving the comparator as @LightnessRacesInOrbit pointed out!

I am sorry if there has already been a post about this. I have not been able to find it!

Answer 1

I have never actually thought about this before, and the const-ref indeed is a bit misleading. However, the function signature was thought up before move semantics came along and it became vogue to accept everything by value. Indeed, the comparator is copied!

[C++14: 23.6.4.1/4]: Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls c.insert(c.end(), first, last); and finally calls make_heap(c.begin(), c.end(), comp).

Lambdas are not copy-assignable, but they are copy-constructible, so there is no problem here.

[C++14: 5.1.2/20]: The closure type associated with a lambda-expression has a deleted (8.4.3) default constructor and a deleted copy assignment operator. It has an implicitly-declared copy constructor (12.8) and may have an implicitly-declared move constructor (12.8). [..]

Does this prevent move-construction of the comparator itself? Yes, it does. I'm going to assume that this convention, of taking the comparator by const-ref then copying it, stems from the STL days, way before move semantics. I imagine it wasn't seriously considered to add overloads to take the comparator by value because that adds complexity and you shouldn't have a complex, move-enhancible comparator in the first place (give them state, sure, but not too much). Still, this may be worth raising with the committee if you can come up with a solid use case for moving a comparator.

Answer 2

It doesn't go out of scope -- it is copy constructed into the container. The description on cppreference.com states:

explicit priority_queue( const Compare& compare = Compare(),
                         const Container& cont = Container() );

Copy-constructs the underlying container c with the contents of cont. Copy-constructs the comparison functor comp with the contents of compare. Calls std::make_heap(c.begin(), c.end(), comp). This is also the default constructor.

There are various other forms of the constructor, but in all cases the internal comparator is either copy- or move-constructed from the one supplied.