From 1f4dcbf7cd8c60457ab9b156017db6e39293657b Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Thu, 14 Feb 2019 14:10:19 +0000 Subject: [PATCH] LWG 2537 fix priority_queue constructors to establish invariant This change is safe to make now (in stage 4), because the constructors are currently incorrect and unusable (unless the supplied container already contains a heap, in which case the new make_heap calls are redundant but harmless). * doc/xml/manual/intro.xml: Document LWG 2537 status. * include/bits/stl_queue.h (priority_queue(const Compare&, const Container&, const Alloc&)) (priority_queue(const Compare&, Container&&, const Alloc&)): Call make_heap. * testsuite/23_containers/priority_queue/dr2537.cc: New test. From-SVN: r268878 --- libstdc++-v3/ChangeLog | 7 +++ libstdc++-v3/doc/xml/manual/intro.xml | 8 +++ libstdc++-v3/include/bits/stl_queue.h | 8 ++- .../23_containers/priority_queue/dr2537.cc | 50 +++++++++++++++++++ 4 files changed, 71 insertions(+), 2 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 8cedc38c1a4..8186974196e 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,12 @@ 2019-02-14 Jonathan Wakely + * doc/xml/manual/intro.xml: Document LWG 2537 status. + * include/bits/stl_queue.h + (priority_queue(const Compare&, const Container&, const Alloc&)) + (priority_queue(const Compare&, Container&&, const Alloc&)): Call + make_heap. + * testsuite/23_containers/priority_queue/dr2537.cc: New test. + * doc/xml/manual/intro.xml: Document LWG 2566 status. * include/bits/stl_queue.h (queue, priority_queue): Add static assertions to enforce LWG 2566 requirement on value_type. diff --git a/libstdc++-v3/doc/xml/manual/intro.xml b/libstdc++-v3/doc/xml/manual/intro.xml index 2a3231f4eb4..656e32b00aa 100644 --- a/libstdc++-v3/doc/xml/manual/intro.xml +++ b/libstdc++-v3/doc/xml/manual/intro.xml @@ -1127,6 +1127,14 @@ requirements of the license of GCC. Add static assertions to enforce the requirement. + 2566: + Constructors for priority_queue taking allocators + should call make_heap + + + Call make_heap. + + 2583: There is no way to supply an allocator for basic_string(str, pos) diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h index 1eb56810edc..dd1d5d9727a 100644 --- a/libstdc++-v3/include/bits/stl_queue.h +++ b/libstdc++-v3/include/bits/stl_queue.h @@ -520,14 +520,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION priority_queue(const _Compare& __x, const _Alloc& __a) : c(__a), comp(__x) { } + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 2537. Constructors [...] taking allocators should call make_heap template> priority_queue(const _Compare& __x, const _Sequence& __c, const _Alloc& __a) - : c(__c, __a), comp(__x) { } + : c(__c, __a), comp(__x) + { std::make_heap(c.begin(), c.end(), comp); } template> priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a) - : c(std::move(__c), __a), comp(__x) { } + : c(std::move(__c), __a), comp(__x) + { std::make_heap(c.begin(), c.end(), comp); } template> priority_queue(const priority_queue& __q, const _Alloc& __a) diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc b/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc new file mode 100644 index 00000000000..ecb51780ee5 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc @@ -0,0 +1,50 @@ +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include + +struct Q : std::priority_queue +{ + using priority_queue::priority_queue; + + bool is_heap() const + { return std::is_heap(c.begin(), c.end()); } +}; + +void +test01() +{ + const Q::value_compare cmp; + const Q::container_type c{ 2, 3, 5, 7, 11, 13, 17, 19, 23 }; + const Q::container_type::allocator_type a; + + Q q1(cmp, c, a); + VERIFY( q1.is_heap() ); + + auto c2 = c; + Q q2(cmp, std::move(c2), a); + VERIFY( q2.is_heap() ); +} + +int +main() +{ + test01(); +} -- 2.30.2