diff --git a/libcxx/docs/Status/Cxx2bIssues.csv b/libcxx/docs/Status/Cxx2bIssues.csv --- a/libcxx/docs/Status/Cxx2bIssues.csv +++ b/libcxx/docs/Status/Cxx2bIssues.csv @@ -67,13 +67,13 @@ `3430 `__,"``std::fstream`` & co. should be constructible from string_view","June 2021","","" `3462 `__,"ยง[formatter.requirements]: Formatter requirements forbid use of ``fc.arg()``","June 2021","","" `3481 `__,"``viewable_range`` mishandles lvalue move-only views","June 2021","","" -`3506 `__,"Missing allocator-extended constructors for ``priority_queue``","June 2021","","" +`3506 `__,"Missing allocator-extended constructors for ``priority_queue``","June 2021","|Complete|","14.0" `3517 `__,"``join_view::iterator``'s ``iter_swap`` is underconstrained","June 2021","","" `3518 `__,"Exception requirements on char trait operations unclear","June 2021","","" `3519 `__,"Incomplete synopses for classes","June 2021","","" `3520 `__,"``iter_move`` and ``iter_swap`` are inconsistent for ``transform_view::iterator``","June 2021","","" `3521 `__,"Overly strict requirements on ``qsort`` and ``bsearch``","June 2021","","" -`3522 `__,"Missing requirement on ``InputIterator`` template parameter for ``priority_queue`` constructors","June 2021","","" +`3522 `__,"Missing requirement on ``InputIterator`` template parameter for ``priority_queue`` constructors","June 2021","|Complete|","14.0" `3523 `__,"``iota_view::sentinel`` is not always ``iota_view``'s sentinel","June 2021","","" `3526 `__,"Return types of ``uses_allocator_construction_args`` unspecified","June 2021","","" `3527 `__,"``uses_allocator_construction_args`` handles rvalue pairs of rvalue references incorrectly","June 2021","","" diff --git a/libcxx/docs/Status/RangesIssues.csv b/libcxx/docs/Status/RangesIssues.csv --- a/libcxx/docs/Status/RangesIssues.csv +++ b/libcxx/docs/Status/RangesIssues.csv @@ -1,4 +1,4 @@ -"Number","Name","Status","Assignee" +"Number","Name","Status","First released version" `P0896R4 `__,,, `P1035R7 `__,Input Range Adaptors,, `P1207R4 `__,Movability Of Single-Pass Iterators,, @@ -67,7 +67,7 @@ `LWG3505 `__, split_view::outer-iterator::operator++ misspecified,, `LWG3517 `__,"join_view::iterator's iter_swap is underconstrained",, `LWG3520 `__,"iter_move and iter_swap are inconsistent for transform_view::iterator",, -`LWG3522 `__,"Missing requirement on InputIterator template parameter for priority_queue constructors",, +`LWG3522 `__,"Missing requirement on InputIterator template parameter for priority_queue constructors","|Complete|","14.0" `LWG3523 `__,"iota_view::sentinel is not always iota_view's sentinel",, `LWG3532 `__,"split_view::inner-iterator::operator++(int) should depend on Base",, `LWG3533 `__,"Make base() const & consistent across iterator wrappers that supports input_iterators",, diff --git a/libcxx/include/queue b/libcxx/include/queue --- a/libcxx/include/queue +++ b/libcxx/include/queue @@ -115,27 +115,39 @@ priority_queue() : priority_queue(Compare()) {} // C++20 explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {} priority_queue(const Compare& x, const Container&); - explicit priority_queue(const Compare& x = Compare(), Container&&= Container()); // before C++20 + explicit priority_queue(const Compare& x = Compare(), Container&& = Container()); // before C++20 priority_queue(const Compare& x, Container&&); // C++20 template priority_queue(InputIterator first, InputIterator last, const Compare& comp = Compare()); template priority_queue(InputIterator first, InputIterator last, - const Compare& comp, const container_type& c); + const Compare& comp, const Container& c); template priority_queue(InputIterator first, InputIterator last, - const Compare& comp, container_type&& c); + const Compare& comp, Container&& c); template explicit priority_queue(const Alloc& a); template priority_queue(const Compare& comp, const Alloc& a); template - priority_queue(const Compare& comp, const container_type& c, + priority_queue(const Compare& comp, const Container& c, const Alloc& a); template - priority_queue(const Compare& comp, container_type&& c, + priority_queue(const Compare& comp, Container&& c, const Alloc& a); + template + priority_queue(InputIterator first, InputIterator last, + const Alloc& a); + template + priority_queue(InputIterator first, InputIterator last, + const Compare& comp, const Alloc& a); + template + priority_queue(InputIterator first, InputIterator last, + const Compare& comp, const Container& c, const Alloc& a); + template + priority_queue(InputIterator first, InputIterator last, + const Compare& comp, Container&& c, const Alloc& a); template priority_queue(const priority_queue& q, const Alloc& a); template @@ -160,15 +172,30 @@ -> priority_queue; // C++17 template::value_type>, - class Container = vector::value_type>> + class Compare = less>, + class Container = vector>> priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container()) - -> priority_queue::value_type, Container, Compare>; // C++17 + -> priority_queue, Container, Compare>; // C++17 template priority_queue(Compare, Container, Allocator) -> priority_queue; // C++17 +template +priority_queue(InputIterator, InputIterator, Allocator) + -> priority_queue, + vector, Allocator>, + less>>; + +template +priority_queue(InputIterator, InputIterator, Compare, Allocator) + -> priority_queue, + vector, Allocator>, Compare>; + +template +priority_queue(InputIterator, InputIterator, Compare, Container, Allocator) + -> priority_queue; + template void swap(priority_queue& x, priority_queue& y) @@ -464,16 +491,16 @@ _LIBCPP_INLINE_VISIBILITY priority_queue(const value_compare& __comp, container_type&& __c); #endif - template + template ::value> > _LIBCPP_INLINE_VISIBILITY priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare()); - template + template ::value> > _LIBCPP_INLINE_VISIBILITY priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c); #ifndef _LIBCPP_CXX03_LANG - template + template ::value> > _LIBCPP_INLINE_VISIBILITY priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c); @@ -507,6 +534,31 @@ _EnableIf::value>* = 0); #endif // _LIBCPP_CXX03_LANG + template ::value> > + _LIBCPP_INLINE_VISIBILITY + priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a, + _EnableIf::value>* = 0); + + template ::value> > + _LIBCPP_INLINE_VISIBILITY + priority_queue(_InputIter __f, _InputIter __l, + const value_compare& __comp, const _Alloc& __a, + _EnableIf::value>* = 0); + + template ::value> > + _LIBCPP_INLINE_VISIBILITY + priority_queue(_InputIter __f, _InputIter __l, + const value_compare& __comp, const container_type& __c, const _Alloc& __a, + _EnableIf::value>* = 0); + +#ifndef _LIBCPP_CXX03_LANG + template ::value> > + _LIBCPP_INLINE_VISIBILITY + priority_queue(_InputIter __f, _InputIter __l, + const value_compare& __comp, container_type&& __c, const _Alloc& __a, + _EnableIf::value>* = 0); +#endif // _LIBCPP_CXX03_LANG + _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY bool empty() const {return c.empty();} _LIBCPP_INLINE_VISIBILITY @@ -560,6 +612,33 @@ > priority_queue(_Compare, _Container, _Alloc) -> priority_queue; + +template::value>, + class = _EnableIf<__is_allocator<_Allocator>::value> +> +priority_queue(_InputIterator, _InputIterator, _Allocator) + -> priority_queue<__iter_value_type<_InputIterator>, + vector<__iter_value_type<_InputIterator>, _Allocator>, + less<__iter_value_type<_InputIterator>>>; + +template::value>, + class = _EnableIf::value>, + class = _EnableIf<__is_allocator<_Allocator>::value> +> +priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator) + -> priority_queue<__iter_value_type<_InputIterator>, + vector<__iter_value_type<_InputIterator>, _Allocator>, _Compare>; + +template::value>, + class = _EnableIf::value>, + class = _EnableIf::value>, + class = _EnableIf::value> +> +priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc) + -> priority_queue; #endif template @@ -587,7 +666,7 @@ #endif // _LIBCPP_CXX03_LANG template -template +template inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp) @@ -598,7 +677,7 @@ } template -template +template inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, @@ -613,7 +692,7 @@ #ifndef _LIBCPP_CXX03_LANG template -template +template inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, @@ -669,7 +748,6 @@ : c(__q.c, __a), comp(__q.comp) { - _VSTD::make_heap(c.begin(), c.end(), comp); } #ifndef _LIBCPP_CXX03_LANG @@ -695,11 +773,65 @@ _EnableIf::value>*) : c(_VSTD::move(__q.c), __a), comp(_VSTD::move(__q.comp)) +{ +} + +#endif // _LIBCPP_CXX03_LANG + +template +template +inline +priority_queue<_Tp, _Container, _Compare>::priority_queue( + _InputIter __f, _InputIter __l, const _Alloc& __a, + _EnableIf::value>*) + : c(__f, __l, __a), + comp() { _VSTD::make_heap(c.begin(), c.end(), comp); } -#endif // _LIBCPP_CXX03_LANG +template +template +inline +priority_queue<_Tp, _Container, _Compare>::priority_queue( + _InputIter __f, _InputIter __l, + const value_compare& __comp, const _Alloc& __a, + _EnableIf::value>*) + : c(__f, __l, __a), + comp(__comp) +{ + _VSTD::make_heap(c.begin(), c.end(), comp); +} + +template +template +inline +priority_queue<_Tp, _Container, _Compare>::priority_queue( + _InputIter __f, _InputIter __l, + const value_compare& __comp, const container_type& __c, const _Alloc& __a, + _EnableIf::value>*) + : c(__c, __a), + comp(__comp) +{ + c.insert(c.end(), __f, __l); + _VSTD::make_heap(c.begin(), c.end(), comp); +} + +#ifndef _LIBCPP_CXX03_LANG +template +template +inline +priority_queue<_Tp, _Container, _Compare>::priority_queue( + _InputIter __f, _InputIter __l, const value_compare& __comp, + container_type&& __c, const _Alloc& __a, + _EnableIf::value>*) + : c(_VSTD::move(__c), __a), + comp(__comp) +{ + c.insert(c.end(), __f, __l); + _VSTD::make_heap(c.begin(), c.end(), comp); +} +#endif // _LIBCPP_CXX03_LANG template inline diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_alloc.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_alloc.pass.cpp @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template +// priority_queue(InputIterator first, InputIterator last, const Alloc& a); + +#include +#include +#include + +#include "test_macros.h" +#include "test_allocator.h" + +template > +struct PQ : std::priority_queue { + typedef std::priority_queue base; + + template + explicit PQ(It first, It last, const Alloc& a) : base(first, last, a) {} + + using base::c; +}; + +int main(int, char**) +{ + int a[] = {3, 5, 2, 0, 6, 8, 1}; + typedef test_allocator Alloc; + PQ > q(a, a+7, Alloc(2)); + assert(q.size() == 7); + assert(q.top() == 8); + assert(q.c.get_allocator() == Alloc(2)); + + return 0; +} diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_alloc.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_alloc.pass.cpp @@ -0,0 +1,42 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template +// priority_queue(InputIterator first, InputIterator last, const Compare& comp, const Alloc& a); + +#include +#include +#include +#include + +#include "test_macros.h" +#include "test_allocator.h" + +template > +struct PQ : std::priority_queue { + typedef std::priority_queue base; + + template + explicit PQ(It first, It last, const Comp& compare, const Alloc& a) : base(first, last, compare, a) {} + + using base::c; +}; + +int main(int, char**) +{ + int a[] = {3, 5, 2, 0, 6, 8, 1}; + typedef test_allocator Alloc; + PQ, std::greater > q(a, a+7, std::greater(), Alloc(2)); + assert(q.size() == 7); + assert(q.top() == 0); + assert(q.c.get_allocator() == Alloc(2)); + + return 0; +} diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp @@ -0,0 +1,42 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template +// priority_queue(InputIterator first, InputIterator last, +// const Compare& comp, const Container& c, const Alloc& a); + +#include +#include + +#include "test_macros.h" +#include "test_allocator.h" + +template > +struct PQ : std::priority_queue { + typedef std::priority_queue base; + + template + explicit PQ(It first, It last, const Comp& compare, const Cont& v, const Alloc& a) : base(first, last, compare, v, a) {} + + using base::c; +}; + +int main(int, char**) +{ + typedef test_allocator Alloc; + int a[] = {3, 5, 2, 0, 6, 8, 1}; + std::vector v(a, a+3); + PQ > q(a+3, a+7, std::less(), v, Alloc(2)); + assert(q.size() == 7); + assert(q.top() == 8); + assert(q.c.get_allocator() == Alloc(2)); + + return 0; +} diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_rcont_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_rcont_alloc.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_rcont_alloc.pass.cpp @@ -0,0 +1,46 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03 + +// + +// template +// priority_queue(InputIterator first, InputIterator last, +// const Compare& comp, Container&& c, const Alloc& a); + +#include +#include + +#include "test_macros.h" +#include "test_allocator.h" +#include "MoveOnly.h" + +template > +struct PQ : std::priority_queue { + typedef std::priority_queue base; + + template + explicit PQ(It first, It last, const Comp& compare, Cont&& v, const Alloc& a) : base(first, last, compare, std::move(v), a) {} + + using base::c; +}; + +int main(int, char**) +{ + using Alloc = test_allocator; + int a[] = {3, 5, 2, 0, 6, 8, 1}; + PQ> q( + a+3, a+7, std::less(), + std::vector(a, a+3), Alloc(2)); + assert(q.size() == 7); + assert(q.top() == MoveOnly(8)); + assert(q.c.get_allocator() == Alloc(2)); + + return 0; +} diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/ctor_iter_constraint.compile.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/ctor_iter_constraint.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/ctor_iter_constraint.compile.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03 + +// + +// template +// priority_queue(InputIterator first, InputIterator last, const Compare& = Compare()); +// template +// priority_queue(InputIterator first, InputIterator last, const Compare&, const Container&); +// template +// priority_queue(InputIterator first, InputIterator last, const Compare&, Container&&); +// template +// priority_queue(InputIterator first, InputIterator last, const Alloc&); +// template +// priority_queue(InputIterator first, InputIterator last, const Compare&, const Alloc&); +// template +// priority_queue(InputIterator first, InputIterator last, const Compare&, const Container&, const Alloc&); +// template +// priority_queue(InputIterator first, InputIterator last, const Compare&, Container&&, const Alloc&); + +#include +#include +#include + +// Sanity-check that std::vector is constructible from two ints... +static_assert( std::is_constructible, int*, int*>::value, ""); +static_assert( std::is_constructible, int , int >::value, ""); + +// ...but std::priority_queue is not. +static_assert( std::is_constructible, int*, int*>::value, ""); +static_assert(!std::is_constructible, int , int >::value, ""); + +static_assert( std::is_constructible, int*, int*, std::less>::value, ""); +static_assert(!std::is_constructible, int , int , std::less>::value, ""); + +static_assert( std::is_constructible, int*, int*, std::less, std::vector>::value, ""); +static_assert(!std::is_constructible, int , int , std::less, std::vector>::value, ""); + +static_assert( std::is_constructible, int*, int*, std::less, std::vector&>::value, ""); +static_assert(!std::is_constructible, int , int , std::less, std::vector&>::value, ""); + +static_assert( std::is_constructible, int*, int*, std::allocator>::value, ""); +static_assert(!std::is_constructible, int , int , std::allocator>::value, ""); + +static_assert( std::is_constructible, int*, int*, std::less, std::allocator>::value, ""); +static_assert(!std::is_constructible, int , int , std::less, std::allocator>::value, ""); + +static_assert( std::is_constructible, int*, int*, std::less, std::vector, std::allocator>::value, ""); +static_assert(!std::is_constructible, int , int , std::less, std::vector, std::allocator>::value, ""); + +static_assert( std::is_constructible, int*, int*, std::less, std::vector&, std::allocator>::value, ""); +static_assert(!std::is_constructible, int , int , std::less, std::vector&, std::allocator>::value, ""); diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp --- a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp +++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp @@ -143,6 +143,7 @@ { typedef short T; + typedef signed char ConvertibleToT; typedef std::greater Comp; typedef test_allocator Alloc; typedef std::deque Cont; @@ -173,6 +174,70 @@ std::priority_queue pri(std::move(source), ConvertibleToAlloc(2)); static_assert(std::is_same_v>); } + + { + Cont cont; + std::priority_queue pri(Comp(), cont, Alloc(2)); + static_assert(std::is_same_v>); + } + + { + Cont cont; + std::priority_queue pri(Comp(), cont, ConvertibleToAlloc(2)); + static_assert(std::is_same_v>); + } + + { + Cont cont; + std::priority_queue pri(Comp(), std::move(cont), Alloc(2)); + static_assert(std::is_same_v>); + } + + { + Cont cont; + std::priority_queue pri(Comp(), std::move(cont), ConvertibleToAlloc(2)); + static_assert(std::is_same_v>); + } + + { + T a[2] = {}; + std::priority_queue pri(a, a+2, Alloc(2)); + static_assert(std::is_same_v>>); + } + + { + T a[2] = {}; + std::priority_queue pri(a, a+2, Comp(), Alloc(2)); + static_assert(std::is_same_v, Comp>>); + } + + { + Cont cont; + ConvertibleToT a[2] = {}; + std::priority_queue pri(a, a+2, Comp(), cont, Alloc(2)); + static_assert(std::is_same_v>); + } + + { + Cont cont; + ConvertibleToT a[2] = {}; + std::priority_queue pri(a, a+2, Comp(), cont, ConvertibleToAlloc(2)); + static_assert(std::is_same_v>); + } + + { + Cont cont; + ConvertibleToT a[2] = {}; + std::priority_queue pri(a, a+2, Comp(), std::move(cont), Alloc(2)); + static_assert(std::is_same_v>); + } + + { + Cont cont; + ConvertibleToT a[2] = {}; + std::priority_queue pri(a, a+2, Comp(), std::move(cont), ConvertibleToAlloc(2)); + static_assert(std::is_same_v>); + } } return 0;