[libc++] Implement the resolutions of LWG3506 and LWG3522.
Implement the changes in all language modes.
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.
LWG3522: "Missing requirement on InputIterator template parameter
for priority_queue constructors". The iterator parameter should be
constrained to actually be an iterator type. `priority_queue{1,2}`
should be SFINAE-friendly ill-formed.
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++.
Differential Revision: https://reviews.llvm.org/D106824
Differential Revision: https://reviews.llvm.org/D106827
NOKEYCHECK=True
GitOrigin-RevId: 3894a8a4768fd6fa9bf18303a0db1687c7c687b3
diff --git a/include/queue b/include/queue
index 42470e3..276fff9 100644
--- a/include/queue
+++ b/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 <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>
@@ -160,15 +172,30 @@
-> 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)
@@ -464,16 +491,16 @@
_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);
@@ -507,6 +534,31 @@
_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
@@ -560,6 +612,33 @@
>
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>
@@ -587,7 +666,7 @@
#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)
@@ -598,7 +677,7 @@
}
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,
@@ -613,7 +692,7 @@
#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,
@@ -669,7 +748,6 @@
: c(__q.c, __a),
comp(__q.comp)
{
- _VSTD::make_heap(c.begin(), c.end(), comp);
}
#ifndef _LIBCPP_CXX03_LANG
@@ -696,10 +774,64 @@
: 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);
}
-#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 _Alloc& __a,
+ _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
+ : c(__f, __l, __a),
+ comp(__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 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