C++ Logo

STD-PROPOSALS

Advanced search

Subject: Re: [std-proposals] priority_queue doesn't work with move-only types
From: Arthur O'Dwyer (arthur.j.odwyer_at_[hidden])
Date: 2021-02-21 09:41:20


On Sun, Feb 21, 2021 at 10:04 AM Bo Persson via Std-Proposals <
std-proposals_at_[hidden]> wrote:
> The reason for not having top-and-pop methods is that copying out the
> element might throw. And if it is already popped at that point, it is
lost.

That's a common misconception.
You can see that it's not the real rationale because, as Phil already
pointed out, std::stack and std::queue *do* allow moving-out-of the top
element, which equally well might throw and result in the element's value
being "lost." The only way to avoid data loss on throw is for the element
type to provide the *strong exception guarantee*; that's up to the designer
of the element type. The designer of the container can't affect that
decision for better or worse.
If your element type's special members might throw, then pop() is not the
only "data-losing" operation: all the container adaptors also provide a
move-enabled `push(T&&)`. If you pass an rvalue element into `push`, and
its move-constructor throws, then you have "lost" that element's data just
as surely as if it had thrown during `pop`.
https://godbolt.org/z/fb6raT

In fact, priority_queue is special in that it does throwing operations on
its elements as part of normal "heap maintenance." I have a blog post about
the fun situations you can get into when rebalancing the heap throws an
exception:
https://quuxplusone.github.io/blog/2019/02/24/container-adaptor-invariants/
and turned it into a 60-minute conference talk a couple years ago:
https://www.youtube.com/watch?v=b9ZYM0d6htg
In short, the STL's whole "adaptor" idea is kind of broken when it comes to
exception-safety, because we don't require strong exception guarantees out
of the building blocks (containers, comparators) and therefore they can't
safely be composed together to form larger invariants. (I personally
consider this "bad, but the cure would be even worse, at this point.")

The philosophy to keep in mind when "transferring ownership" of elements
(whether it's an rvalue into `v.push_back(...)`, or an owning pointer into
`shared_ptr<T>(...)`) is that the ownership is transferred *at the moment
of the call*. If `push_back` throws an exception, well, it's up to the
vector to clean up that element. If allocating the shared_ptr's control
block throws an exception, well, it's up to shared_ptr to call `delete` on
that raw owning pointer that was passed in.
And vice versa: in the unlikely case that `extract_top()` threw an
exception during the move-from operation, it would be appropriate for the
queue to clean up the moved-from element and probably even to restore the
heap invariant before returning.

> On 2021-02-21 at 13:38, Phil Endecott via Std-Proposals wrote:
> > std::priority_queue doesn't work with move-only types, because
> > it only has a const top() method.
> >
> > This is in contrast to std::queue and std::stack, which have both
> > const and non-const front() or top() methods.
> >[...]
> > The rationale for not having a non-const top() method is that
> > allowing the top element to be modified allows the priority
> > queue's heap constraint to be broken - which is reasonable.
> > Of course in this particular case it is safe as the moved-from
> > top element is immediately popped.
> >
> > One possible solution would be to provide a combined top-and-pop
> > method.

This sounds reasonable to me. If you wanted to get LEWG really excited, you
might suggest that this new method be implemented as
    value_type extract_top() {
        value_type result = std::*move_if_noexcept*(c.front());
        pop();
        return result;
    }
Library folks love functions that fundamentally change their behavior based
on the noexceptness of the component operations. ;)

There might be some clever way to achieve your goal by piggybacking on the
`reemplace_top` operation (which I've blogged but never written a paper
for):
https://quuxplusone.github.io/blog/2018/04/27/pq-replace-top/
https://reviews.llvm.org/D57734
perhaps by providing an `exchange_top` operation
    T value = pq.exchange_top(nullptr);
The problem with that, of course, is that it would fill up your priority
queue with nullptrs. :P
So the idea needs some work; but maybe you can figure something out.

–Arthur



STD-PROPOSALS list run by std-proposals-owner@lists.isocpp.org

Standard Proposals Archives on Google Groups