[libc++] Implement the resolution of LWG3506 in all language modes.

[• Quuxplusone]

Summary

LWG3506 "Missing allocator-extended constructors for priority_queue"
makes the following changes:
- New allocator-extended constructors for priority_queue.
- New deduction guides targeting those constructors.

Also, do a drive-by fix in the allocator-extended move constructor:
there's no need to do a `make_heap` after moving from `__q.c` into
our own `c`, because that container was already heapified when it
was part of `__q`. [priqueue.cons.alloc] actually specifies the
behavior and does *not* mention calling `make_heap`. I think this
was just a copy-paste thinko. It dates back to the initial import
of libc++.

[ldionne]

libcxx/include/queue

175–176

Maybe we can get rid of the typename here?

537

I'm not sure I understand why we're constraining those constructors with is_cpp17_input_iterator?

I understand it's just generally a bad idea to have unconstrained template parameters, but that seems to be what the spec has?

554

Doesn't this work even in C++03 mode with the rvalue references extension?

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp

22

Why are you creating this derived type?

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp

20

This would need to be updated.

[ldionne]

libcxx/include/queue

537

Never mind this, I just saw your other patch.

[• Quuxplusone]

Update tests: my sneaky inheritance of constructors didn't work in C++03 mode, so revert to something much closer to the existing approach in other priority_queue tests.
"13.0" is now "14.0".

[• Quuxplusone]

libcxx/include/queue

554

Yes, but I haven't been reckless enough yet to break our historical tradition that guards all actual container move-constructors and move-assignments under _LIBCPP_CXX03_LANG. I think we should break those all at once.

Note particularly the priority_queue(const Comp&, Container&&, const Alloc&) on line 528, which is already guarded like this.

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp

22

I'd been doing it in order to get at q.c.get_allocator() on line 35.
However, it turns out that using priority_queue::priority_queue; is a C++11ism, unsupported in C++03 mode, so I'll either have to do the more verbose inheritance from e.g. libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_alloc.pass.cpp or else think of a different way to get at the allocator.

[ldionne]

libcxx/include/queue

554

Oh, thanks, I had not realized there was such a tradition.

[• Quuxplusone]

Fix shadowing warning in new tests by s/comp/compare/g.

[ldionne]

LGTM, but can you please add SFINAE tests for the constructors that you added? I'd like to catch in case we had forgotten to constrain them properly (right now I don't think we would).

libcxx/docs/Status/Cxx2bIssues.csv

 "","","","",""
 `2774 <https://wg21.link/LWG2774>`__,"``std::function`` construction vs assignment","June 2021","",""
 `2818 <https://wg21.link/LWG2818>`__,"``::std::`` everywhere rule needs tweaking","June 2021","",""
 `2997 <https://wg21.link/LWG2997>`__,"LWG 491 and the specification of ``{forward_,}list::unique``","June 2021","",""
 `3410 <https://wg21.link/LWG3410>`__,"``lexicographical_compare_three_way`` is overspecified","June 2021","",""
 `3430 <https://wg21.link/LWG3430>`__,"``std::fstream`` & co. should be constructible from string_view","June 2021","",""
 `3462 <https://wg21.link/LWG3462>`__,"§[formatter.requirements]: Formatter requirements forbid use of ``fc.arg()``","June 2021","",""
 `3481 <https://wg21.link/LWG3481>`__,"``viewable_range`` mishandles lvalue move-only views","June 2021","",""
-`3506 <https://wg21.link/LWG3506>`__,"Missing allocator-extended constructors for ``priority_queue``","June 2021","",""
+`3506 <https://wg21.link/LWG3506>`__,"Missing allocator-extended constructors for ``priority_queue``","June 2021","|Complete|","14.0"
 `3517 <https://wg21.link/LWG3517>`__,"``join_view::iterator``'s ``iter_swap`` is underconstrained","June 2021","",""
 `3518 <https://wg21.link/LWG3518>`__,"Exception requirements on char trait operations unclear","June 2021","",""
 `3519 <https://wg21.link/LWG3519>`__,"Incomplete synopses for <random> classes","June 2021","",""
 `3520 <https://wg21.link/LWG3520>`__,"``iter_move`` and ``iter_swap`` are inconsistent for ``transform_view::iterator``","June 2021","",""
 `3521 <https://wg21.link/LWG3521>`__,"Overly strict requirements on ``qsort`` and ``bsearch``","June 2021","",""
-`3522 <https://wg21.link/LWG3522>`__,"Missing requirement on ``InputIterator`` template parameter for ``priority_queue`` constructors","June 2021","",""
+`3522 <https://wg21.link/LWG3522>`__,"Missing requirement on ``InputIterator`` template parameter for ``priority_queue`` constructors","June 2021","|Complete|","14.0"
 `3523 <https://wg21.link/LWG3523>`__,"``iota_view::sentinel`` is not always ``iota_view``'s sentinel","June 2021","",""
 `3526 <https://wg21.link/LWG3526>`__,"Return types of ``uses_allocator_construction_args`` unspecified","June 2021","",""
 `3527 <https://wg21.link/LWG3527>`__,"``uses_allocator_construction_args`` handles rvalue pairs of rvalue references incorrectly","June 2021","",""
 `3528 <https://wg21.link/LWG3528>`__,"``make_from_tuple`` can perform (the equivalent of) a C-style cast","June 2021","",""
 `3529 <https://wg21.link/LWG3529>`__,"``priority_queue(first, last)`` should construct ``c`` with ``(first, last)``","June 2021","",""
 `3530 <https://wg21.link/LWG3530>`__,"``BUILTIN-PTR-MEOW`` should not opt the type out of syntactic checks","June 2021","",""
 `3532 <https://wg21.link/LWG3532>`__,"``split_view<V, P>::inner-iterator<true>::operator++(int)`` should depend on ``Base``","June 2021","",""
 `3533 <https://wg21.link/LWG3533>`__,"Make ``base() const &`` consistent across iterator wrappers that supports ``input_iterators``","June 2021","",""

libcxx/docs/Status/RangesIssues.csv

-"Number","Name","Status","Assignee"
+"Number","Name","Status","First released version"
 `P0896R4 <https://wg21.link/P0896R4>`__,<ranges>,,
 `P1035R7 <https://wg21.link/P1035R7>`__,Input Range Adaptors,,
 `P1207R4 <https://wg21.link/P1207R4>`__,Movability Of Single-Pass Iterators,,
 `P1243R4 <https://wg21.link/P1243R4>`__,Rangify New Algorithms,,
 `P1248R1 <https://wg21.link/P1248R1>`__,Fixing Relations,,
 `P1252R2 <https://wg21.link/P1252R2>`__,Ranges Design Cleanup,,
 `P1391R4 <https://wg21.link/P1391R4>`__,Range Constructor For string_view,,
 `P1456R1 <https://wg21.link/P1456R1>`__,Move-Only Views,,

 `LWG3397 <https://wg21.link/lwg3397>`__, ranges::basic_istream_view::iterator should not provide iterator_category,,
 `LWG3398 <https://wg21.link/lwg3398>`__, tuple_element_t is also wrong for const subrange,,
 `LWG3474 <https://wg21.link/lwg3474>`__, Nesting join_views is broken because of CTAD,,
 `LWG3481 <https://wg21.link/LWG3481>`__,"viewable_range mishandles lvalue move-only views",,
 `LWG3500 <https://wg21.link/lwg3500>`__, join_view::iterator::operator->() is bogus,,
 `LWG3505 <https://wg21.link/lwg3505>`__, split_view::outer-iterator::operator++ misspecified,,
 `LWG3517 <https://wg21.link/LWG3517>`__,"join_view::iterator's iter_swap is underconstrained",,
 `LWG3520 <https://wg21.link/LWG3520>`__,"iter_move and iter_swap are inconsistent for transform_view::iterator",,
-`LWG3522 <https://wg21.link/LWG3522>`__,"Missing requirement on InputIterator template parameter for priority_queue constructors",,
+`LWG3522 <https://wg21.link/LWG3522>`__,"Missing requirement on InputIterator template parameter for priority_queue constructors","|Complete|","14.0"
 `LWG3523 <https://wg21.link/LWG3523>`__,"iota_view::sentinel is not always iota_view's sentinel",,
 `LWG3532 <https://wg21.link/LWG3532>`__,"split_view<V, P>::inner-iterator<true>::operator++(int) should depend on Base",,
 `LWG3533 <https://wg21.link/LWG3533>`__,"Make base() const & consistent across iterator wrappers that supports input_iterators",,
 `LWG3541 <https://wg21.link/LWG3541>`__,"indirectly_readable_traits should be SFINAE-friendly for all types",,
 `LWG3543 <https://wg21.link/LWG3543>`__,"Definition of when counted_iterators refer to the same sequence isn't quite right",,
 `LWG3546 <https://wg21.link/LWG3546>`__,"common_iterator's postfix-proxy is not quite right",,
 `LWG3549 <https://wg21.link/LWG3549>`__,"view_interface is overspecified to derive from view_base",,
 `LWG3551 <https://wg21.link/LWG3551>`__,"borrowed_{iterator,subrange}_t are overspecified",,
 `LWG3553 <https://wg21.link/LWG3553>`__,"Useless constraint in split_view::outer-iterator::value_type::begin()",,
 `LWG3555 <https://wg21.link/LWG3555>`__,"{transform,elements}_view::iterator::iterator_concept should consider const-qualification of the underlying range",,

libcxx/include/queue

 protected:
     container_type c;
     Compare comp;
 
 public:
     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 <class InputIterator>
         priority_queue(InputIterator first, InputIterator last,
                        const Compare& comp = Compare());
     template <class InputIterator>
         priority_queue(InputIterator first, InputIterator last,
-                       const Compare& comp, const container_type& c);
+                       const Compare& comp, const Container& c);
     template <class InputIterator>
         priority_queue(InputIterator first, InputIterator last,
-                       const Compare& comp, container_type&& c);
+                       const Compare& comp, Container&& c);
     template <class Alloc>
         explicit priority_queue(const Alloc& a);
     template <class Alloc>
         priority_queue(const Compare& comp, const Alloc& a);
     template <class Alloc>
-        priority_queue(const Compare& comp, const container_type& c,
+        priority_queue(const Compare& comp, const Container& c,
                        const Alloc& a);
     template <class Alloc>
-        priority_queue(const Compare& comp, container_type&& c,
+        priority_queue(const Compare& comp, Container&& c,
                        const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Compare& comp, const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Compare& comp, const Container& c, const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Compare& comp, Container&& c, const Alloc& a);
     template <class Alloc>
         priority_queue(const priority_queue& q, const Alloc& a);
     template <class Alloc>
         priority_queue(priority_queue&& q, const Alloc& a);
 
     bool            empty() const;
     size_type       size() const;
     const_reference top() const;
 
     void push(const value_type& v);
     void push(value_type&& v);
     template <class... Args> void emplace(Args&&... args);
     void pop();
 
     void swap(priority_queue& q)
         noexcept(is_nothrow_swappable_v<Container> &&
                  is_nothrow_swappable_v<Comp>)
 };
 
 template <class Compare, class Container>
 priority_queue(Compare, Container)
     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 
 template<class InputIterator,
-         class Compare = less<typename iterator_traits<InputIterator>::value_type>,
-         class Container = vector<typename iterator_traits<InputIterator>::value_type>>
+         class Compare = less<iter-value-type<InputIterator>>,
+         class Container = vector<iter-value-type<InputIterator>>>
 priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
-    -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>; // C++17
+    -> priority_queue<iter-value-type<InputIterator>, Container, Compare>; // C++17
 
 template<class Compare, class Container, class Allocator>
 priority_queue(Compare, Container, Allocator)
     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 
+template<class InputIterator, class Allocator>
+priority_queue(InputIterator, InputIterator, Allocator)
+    -> priority_queue<iter-value-type<InputIterator>,
+                      vector<iter-value-type<InputIterator>, Allocator>,
+                      less<iter-value-type<InputIterator>>>;
+
+template<class InputIterator, class Compare, class Allocator>
+priority_queue(InputIterator, InputIterator, Compare, Allocator)
+    -> priority_queue<iter-value-type<InputIterator>,
+                      vector<iter-value-type<InputIterator>, Allocator>, Compare>;
+
+template<class InputIterator, class Compare, class Container, class Allocator>
+priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
+    -> priority_queue<typename Container::value_type, Container, Compare>;
+
 template <class T, class Container, class Compare>
   void swap(priority_queue<T, Container, Compare>& x,
             priority_queue<T, Container, Compare>& y)
             noexcept(noexcept(x.swap(y)));
 
 }  // std
 
 */
#endif // _LIBCPP_CXX03_LANG
     explicit priority_queue(const value_compare& __comp)
         : c(), comp(__comp) {}
     _LIBCPP_INLINE_VISIBILITY
     priority_queue(const value_compare& __comp, const container_type& __c);
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     priority_queue(const value_compare& __comp, container_type&& __c);
 #endif
-    template <class _InputIter>
+    template <class _InputIter, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
         _LIBCPP_INLINE_VISIBILITY
         priority_queue(_InputIter __f, _InputIter __l,
                        const value_compare& __comp = value_compare());
-    template <class _InputIter>
+    template <class _InputIter, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
         _LIBCPP_INLINE_VISIBILITY
         priority_queue(_InputIter __f, _InputIter __l,
                        const value_compare& __comp, const container_type& __c);
 #ifndef _LIBCPP_CXX03_LANG
-    template <class _InputIter>
+    template <class _InputIter, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
         _LIBCPP_INLINE_VISIBILITY
         priority_queue(_InputIter __f, _InputIter __l,
                        const value_compare& __comp, container_type&& __c);
 #endif // _LIBCPP_CXX03_LANG
     template <class _Alloc>
         _LIBCPP_INLINE_VISIBILITY
         explicit priority_queue(const _Alloc& __a,
                        _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
template <class _Alloc>
                        const _Alloc& __a,
                        _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
     template <class _Alloc>
         _LIBCPP_INLINE_VISIBILITY
         priority_queue(priority_queue&& __q, const _Alloc& __a,
                        _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
 #endif // _LIBCPP_CXX03_LANG
 
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l,
+                       const value_compare& __comp, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l,
+                       const value_compare& __comp, const container_type& __c, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+
+#ifndef _LIBCPP_CXX03_LANG
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l,
+                       const value_compare& __comp, container_type&& __c, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+#endif  // _LIBCPP_CXX03_LANG
+
     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
     bool            empty() const {return c.empty();}
     _LIBCPP_INLINE_VISIBILITY
     size_type       size() const  {return c.size();}
     _LIBCPP_INLINE_VISIBILITY
     const_reference top() const   {return c.front();}
 
     _LIBCPP_INLINE_VISIBILITY
template<class _Compare,
          class _Container,
          class _Alloc,
          class = _EnableIf<!__is_allocator<_Compare>::value>,
          class = _EnableIf<!__is_allocator<_Container>::value>,
          class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
 >
 priority_queue(_Compare, _Container, _Alloc)
     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
+
+template<class _InputIterator, class _Allocator,
+         class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::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<class _InputIterator, class _Compare, class _Allocator,
+         class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::value>,
+         class = _EnableIf<!__is_allocator<_Compare>::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<class _InputIterator, class _Compare, class _Container, class _Alloc,
+         class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::value>,
+         class = _EnableIf<!__is_allocator<_Compare>::value>,
+         class = _EnableIf<!__is_allocator<_Container>::value>,
+         class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
+>
+priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
+    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 #endif
 
 template <class _Tp, class _Container, class _Compare>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
                                                           const container_type& __c)
     : c(__c),
       comp(__comp)
: c(_VSTD::move(__c)),
       comp(__comp)
 {
     _VSTD::make_heap(c.begin(), c.end(), comp);
 }
 
 #endif // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Container, class _Compare>
-template <class _InputIter>
+template <class _InputIter, class>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
                                                           const value_compare& __comp)
     : c(__f, __l),
       comp(__comp)
 {
     _VSTD::make_heap(c.begin(), c.end(), comp);
 }
 
 template <class _Tp, class _Container, class _Compare>
-template <class _InputIter>
+template <class _InputIter, class>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
                                                           const value_compare& __comp,
                                                           const container_type& __c)
     : c(__c),
       comp(__comp)
 {
     c.insert(c.end(), __f, __l);
     _VSTD::make_heap(c.begin(), c.end(), comp);
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Container, class _Compare>
-template <class _InputIter>
+template <class _InputIter, class>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
                                                           const value_compare& __comp,
                                                           container_type&& __c)
     : c(_VSTD::move(__c)),
       comp(__comp)
 {
     c.insert(c.end(), __f, __l);

 template <class _Alloc>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
                                                           const _Alloc& __a,
                        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
     : c(__q.c, __a),
       comp(__q.comp)
 {
-    _VSTD::make_heap(c.begin(), c.end(), comp);
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Container, class _Compare>
 template <class _Alloc>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,

 template <class _Alloc>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
                                                           const _Alloc& __a,
                        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
     : c(_VSTD::move(__q.c), __a),
       comp(_VSTD::move(__q.comp))
 {
+}
+
+#endif  // _LIBCPP_CXX03_LANG
+
+template <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
+    : c(__f, __l, __a),
+      comp()
+{
+    _VSTD::make_heap(c.begin(), c.end(), comp);
+}
+
+template <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l,
+        const value_compare& __comp, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
+    : c(__f, __l, __a),
+      comp(__comp)
+{
     _VSTD::make_heap(c.begin(), c.end(), comp);
 }
 
-#endif // _LIBCPP_CXX03_LANG
+template <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l,
+        const value_compare& __comp, const container_type& __c, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::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 <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l, const value_compare& __comp,
+        container_type&& __c, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::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 <class _Tp, class _Container, class _Compare>
 inline
 void
 priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
 {
     c.push_back(__v);
     _VSTD::push_heap(c.begin(), c.end(), comp);

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_alloc.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+#include <cstddef>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    typedef std::priority_queue<T, Cont, Comp> base;
+
+    template<class It, class Alloc>
+    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<int> Alloc;
+    PQ<int, std::vector<int, Alloc> > q(a, a+7, Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == 8);
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_alloc.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare& comp, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+#include <functional>
+#include <cstddef>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    typedef std::priority_queue<T, Cont, Comp> base;
+
+    template<class It, class Alloc>
+    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<int> Alloc;
+    PQ<int, std::vector<int, Alloc>, std::greater<int> > q(a, a+7, std::greater<int>(), Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == 0);
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last,
+//                  const Compare& comp, const Container& c, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    typedef std::priority_queue<T, Cont, Comp> base;
+
+    template<class It, class Alloc>
+    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<int> Alloc;
+    int a[] = {3, 5, 2, 0, 6, 8, 1};
+    std::vector<int, Alloc> v(a, a+3);
+    PQ<int, std::vector<int, Alloc> > q(a+3, a+7, std::less<int>(), v, Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == 8);
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_rcont_alloc.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last,
+//                  const Compare& comp, Container&& c, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+#include "MoveOnly.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    typedef std::priority_queue<T, Cont, Comp> base;
+
+    template<class It, class Alloc>
+    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<MoveOnly>;
+    int a[] = {3, 5, 2, 0, 6, 8, 1};
+    PQ<MoveOnly, std::vector<MoveOnly, Alloc>> q(
+        a+3, a+7, std::less<MoveOnly>(),
+        std::vector<MoveOnly, Alloc>(a, a+3), Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == MoveOnly(8));
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/ctor_iter_constraint.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare& = Compare());
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare&, const Container&);
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare&, Container&&);
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Alloc&);
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare&, const Alloc&);
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare&, const Container&, const Alloc&);
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare&, Container&&, const Alloc&);
+
+#include <queue>
+#include <type_traits>
+#include <vector>
+
+// Sanity-check that std::vector is constructible from two ints...
+static_assert( std::is_constructible<std::vector<int>,         int*, int*>::value, "");
+static_assert( std::is_constructible<std::vector<int>,         int , int >::value, "");
+
+// ...but std::priority_queue is not.
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int >::value, "");
+
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*, std::less<int>>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int , std::less<int>>::value, "");
+
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*, std::less<int>, std::vector<int>>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int , std::less<int>, std::vector<int>>::value, "");
+
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*, std::less<int>, std::vector<int>&>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int , std::less<int>, std::vector<int>&>::value, "");
+
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*, std::allocator<int>>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int , std::allocator<int>>::value, "");
+
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*, std::less<int>, std::allocator<int>>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int , std::less<int>, std::allocator<int>>::value, "");
+
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*, std::less<int>, std::vector<int>, std::allocator<int>>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int , std::less<int>, std::vector<int>, std::allocator<int>>::value, "");
+
+static_assert( std::is_constructible<std::priority_queue<int>, int*, int*, std::less<int>, std::vector<int>&, std::allocator<int>>::value, "");
+static_assert(!std::is_constructible<std::priority_queue<int>, int , int , std::less<int>, std::vector<int>&, std::allocator<int>>::value, "");

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp

 
 // template<class Compare, class Container>
 // priority_queue(Compare, Container)
 //     -> priority_queue<typename Container::value_type, Container, Compare>;
 //
 // template<class InputIterator,
 //          class Compare = less<typename iterator_traits<InputIterator>::value_type>,
 //          class Container = vector<typename iterator_traits<InputIterator>::value_type>>
 // priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
 //     -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>;
 //
 // template<class Compare, class Container, class Allocator>
 // priority_queue(Compare, Container, Allocator)
 //     -> priority_queue<typename Container::value_type, Container, Compare>;
 
 
 #include <queue>
assert(pri.size() == 0);
         Cont cont;
         std::priority_queue pri(comp, std::move(cont), ConvertibleToAlloc(2));
         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
         }
     }
 
     {
         typedef short T;
+        typedef signed char ConvertibleToT;
         typedef std::greater<T> Comp;
         typedef test_allocator<T> Alloc;
         typedef std::deque<T, Alloc> Cont;
         typedef test_allocator<int> ConvertibleToAlloc;
         static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
                       !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
 
         {
assert(pri.size() == 0);
         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
         }
 
         {
         std::priority_queue<T, Cont, Comp> source;
         std::priority_queue pri(std::move(source), ConvertibleToAlloc(2));
         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
         }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), cont, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), cont, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), std::move(cont), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), std::move(cont), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>>>);
+        }
+
+        {
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>, Comp>>);
+        }
+
+        {
+        Cont cont;
+        ConvertibleToT a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), cont, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        ConvertibleToT a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), cont, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        ConvertibleToT a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), std::move(cont), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        ConvertibleToT a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), std::move(cont), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
     }
 
     return 0;
 }