On Wed, 18 Dec 2024, Jonathan Wakely wrote:
> We don't know what state an arbitrary sequence container will be in
> after moving from it, so a moved-from std::priority_queue needs to clear
> the moved-from container to ensure it doesn't contain elements that are
> in an invalid order for the queue. An alternative would be to call
> std::make_heap again to re-establish the rvalue queue's invariant, but
> that could potentially cause an exception to be thrown. Just clearing it
> so the sequence is empty seems safer and more likely to match user
> expectations.
LGTM. I guess we need to do the same in flat_map/set..
>
> libstdc++-v3/ChangeLog:
>
> PR libstdc++/118088
> * include/bits/stl_queue.h (priority_queue(priority_queue&&)):
> Clear the source object after moving from it.
> (priority_queue(priority_queue&&, const Alloc&)): Likewise.
> (operator=(priority_queue&&)): Likewise.
> * testsuite/23_containers/priority_queue/118088.cc: New test.
> ---
>
> Tested x86_64-linux.
>
> libstdc++-v3/include/bits/stl_queue.h | 26 +++++-
> .../23_containers/priority_queue/118088.cc | 83 +++++++++++++++++++
> 2 files changed, 106 insertions(+), 3 deletions(-)
> create mode 100644
> libstdc++-v3/testsuite/23_containers/priority_queue/118088.cc
>
> diff --git a/libstdc++-v3/include/bits/stl_queue.h
> b/libstdc++-v3/include/bits/stl_queue.h
> index ada354b911d..53a9a47a2d2 100644
> --- a/libstdc++-v3/include/bits/stl_queue.h
> +++ b/libstdc++-v3/include/bits/stl_queue.h
> @@ -564,6 +564,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> : c(std::move(__s)), comp(__x)
> { std::make_heap(c.begin(), c.end(), comp); }
>
> + priority_queue(const priority_queue&) = default;
> + priority_queue& operator=(const priority_queue&) = default;
> +
> + priority_queue(priority_queue&& __q)
> + noexcept(__and_<is_nothrow_move_constructible<_Sequence>,
> + is_nothrow_move_constructible<_Compare>>::value)
> + : c(std::move(__q.c)), comp(std::move(__q.comp))
> + { __q.c.clear(); }
> +
> + priority_queue&
> + operator=(priority_queue&& __q)
> + noexcept(__and_<is_nothrow_move_assignable<_Sequence>,
> + is_nothrow_move_assignable<_Compare>>::value)
> + {
> + c = std::move(__q.c);
> + __q.c.clear();
> + comp = std::move(__q.comp);
> + return *this;
> + }
> +
> template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
> explicit
> priority_queue(const _Alloc& __a)
> @@ -592,7 +612,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
> template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
> priority_queue(priority_queue&& __q, const _Alloc& __a)
> - : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
> + : c(std::move(__q.c), __a), comp(std::move(__q.comp))
> + { __q.c.clear(); }
> #endif
>
> /**
> @@ -607,8 +628,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> * the copy according to @a __x.
> *
> * For more information on function objects, see the
> - * documentation on @link functors functor base
> - * classes@endlink.
> + * documentation on @link functors functor base classes@endlink.
> */
> #if __cplusplus < 201103L
> template<typename _InputIterator>
> diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/118088.cc
> b/libstdc++-v3/testsuite/23_containers/priority_queue/118088.cc
> new file mode 100644
> index 00000000000..b59175d8786
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/priority_queue/118088.cc
> @@ -0,0 +1,83 @@
> +// { dg-do run { target c++11 } }
> +
> +#include <queue>
> +#include <vector>
> +#include <testsuite_hooks.h>
> +
> +template<typename T, typename Seq>
> +bool
> +check(std::priority_queue<T, Seq>& p)
> +{
> + if (!p.empty())
> + {
> + T prev = p.top();
> + p.pop();
> + while (!p.empty())
> + {
> + if ( prev < p.top() )
> + return false;
> + prev = p.top();
> + p.pop();
> + }
> + }
> + return true;
> +}
> +
> +// A vector-like type that has a non-empty moved-from state.
> +struct Vector : std::vector<int>
> +{
> + using Base = std::vector<int>;
> +
> + using Base::Base;
> +
> + Vector(const Vector&) = default;
> + Vector& operator=(const Vector&) = default;
> +
> + Vector(Vector&& v) : Base(static_cast<const Base&>(v))
> + {
> + invalidate_heap(v);
> + }
> +
> + Vector(Vector&& v, const std::allocator<int>&)
> + : Base(static_cast<const Base&>(v))
> + {
> + invalidate_heap(v);
> + }
> +
> + Vector&
> + operator=(Vector&& v)
> + {
> + static_cast<Base&>(*this) = static_cast<const Base&>(v);
> + invalidate_heap(v);
> + return *this;
> + }
> +
> + void invalidate_heap(Base& v) { v = {1,2,3}; }
> +};
> +
> +void
> +test_moves()
> +{
> + std::priority_queue<int, Vector> p;
> + p.push(1);
> + p.push(3);
> + p.push(5);
> + p.push(2);
> + p.push(2);
> + p.push(2);
> + p.push(2);
> + std::priority_queue<int, Vector> p2 = std::move(p);
> + VERIFY( check(p) );
> +
> + // Allocator-extended move constructor:
> + std::priority_queue<int, Vector> p3(std::move(p2), std::allocator<int>());
> + VERIFY( check(p2) );
> +
> + p2 = std::move(p3);
> + VERIFY( check(p3) );
> +}
> +
> +int main()
> +{
> + test_moves();
> +}
> --
> 2.47.1
>
>
