diff options
Diffstat (limited to 'contrib/libc++/include/algorithm')
| -rw-r--r-- | contrib/libc++/include/algorithm | 354 |
1 files changed, 220 insertions, 134 deletions
diff --git a/contrib/libc++/include/algorithm b/contrib/libc++/include/algorithm index 367489f..02cbc81 100644 --- a/contrib/libc++/include/algorithm +++ b/contrib/libc++/include/algorithm @@ -281,11 +281,12 @@ template <class ForwardIterator, class OutputIterator> template <class RandomAccessIterator> void - random_shuffle(RandomAccessIterator first, RandomAccessIterator last); + random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14 template <class RandomAccessIterator, class RandomNumberGenerator> void - random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); + random_shuffle(RandomAccessIterator first, RandomAccessIterator last, + RandomNumberGenerator& rand); // deprecated in C++14 template<class RandomAccessIterator, class UniformRandomNumberGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, @@ -528,19 +529,19 @@ template <class ForwardIterator, class Compare> template <class T> const T& - min(const T& a, const T& b); + min(const T& a, const T& b); // constexpr in C++14 template <class T, class Compare> const T& - min(const T& a, const T& b, Compare comp); + min(const T& a, const T& b, Compare comp); // constexpr in C++14 template<class T> T - min(initializer_list<T> t); + min(initializer_list<T> t); // constexpr in C++14 template<class T, class Compare> T - min(initializer_list<T> t, Compare comp); + min(initializer_list<T> t, Compare comp); // constexpr in C++14 template <class ForwardIterator> ForwardIterator @@ -552,19 +553,19 @@ template <class ForwardIterator, class Compare> template <class T> const T& - max(const T& a, const T& b); + max(const T& a, const T& b); // constexpr in C++14 template <class T, class Compare> const T& - max(const T& a, const T& b, Compare comp); + max(const T& a, const T& b, Compare comp); // constexpr in C++14 template<class T> T - max(initializer_list<T> t); + max(initializer_list<T> t); // constexpr in C++14 template<class T, class Compare> T - max(initializer_list<T> t, Compare comp); + max(initializer_list<T> t, Compare comp); // constexpr in C++14 template<class ForwardIterator> pair<ForwardIterator, ForwardIterator> @@ -576,19 +577,19 @@ template<class ForwardIterator, class Compare> template<class T> pair<const T&, const T&> - minmax(const T& a, const T& b); + minmax(const T& a, const T& b); // constexpr in C++14 template<class T, class Compare> pair<const T&, const T&> - minmax(const T& a, const T& b, Compare comp); + minmax(const T& a, const T& b, Compare comp); // constexpr in C++14 template<class T> pair<T, T> - minmax(initializer_list<T> t); + minmax(initializer_list<T> t); // constexpr in C++14 template<class T, class Compare> pair<T, T> - minmax(initializer_list<T> t, Compare comp); + minmax(initializer_list<T> t, Compare comp); // constexpr in C++14 template <class InputIterator1, class InputIterator2> bool @@ -637,12 +638,17 @@ template <class BidirectionalIterator, class Compare> #include <__undef_min_max> +#include <__debug> + #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD +// I'd like to replace these with _VSTD::equal_to<void>, but can't because: +// * That only works with C++14 and later, and +// * We haven't included <functional> here. template <class _T1, class _T2 = _T1> struct __equal_to { @@ -655,46 +661,59 @@ struct __equal_to template <class _T1> struct __equal_to<_T1, _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} }; template <class _T1> struct __equal_to<const _T1, _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} }; template <class _T1> struct __equal_to<_T1, const _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} }; template <class _T1, class _T2 = _T1> struct __less { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} }; template <class _T1> struct __less<_T1, _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} }; template <class _T1> struct __less<const _T1, _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} }; template <class _T1> struct __less<_T1, const _T1> { - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} }; template <class _Predicate> @@ -958,7 +977,7 @@ __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, } template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_RandomAccessIterator1 +_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) @@ -1024,8 +1043,8 @@ find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, // find_first_of template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_ForwardIterator1 -find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, +_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1 +__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) { for (; __first1 != __last1; ++__first1) @@ -1035,6 +1054,16 @@ find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, return __last1; } + +template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator1 +find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) +{ + return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred); +} + template <class _ForwardIterator1, class _ForwardIterator2> inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator1 @@ -1043,7 +1072,7 @@ find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, { typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::find_first_of(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); + return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } // adjacent_find @@ -1111,7 +1140,7 @@ pair<_InputIterator1, _InputIterator2> mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { - for (; __first1 != __last1; ++__first1, ++__first2) + for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) break; return pair<_InputIterator1, _InputIterator2>(__first1, __first2); @@ -1135,7 +1164,7 @@ mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred) { - for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) break; return pair<_InputIterator1, _InputIterator2>(__first1, __first2); @@ -1160,7 +1189,7 @@ inline _LIBCPP_INLINE_VISIBILITY bool equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { - for (; __first1 != __last1; ++__first1, ++__first2) + for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) return false; return true; @@ -1184,7 +1213,7 @@ __equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag ) { - for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) return false; return __first1 == __last1 && __first2 == __last2; @@ -1238,7 +1267,7 @@ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred) { // shorten sequences as much as possible by lopping of any equal parts - for (; __first1 != __last1; ++__first1, ++__first2) + for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) goto __not_done; return true; @@ -1298,7 +1327,7 @@ __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, forward_iterator_tag, forward_iterator_tag ) { // shorten sequences as much as possible by lopping of any equal parts - for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) goto __not_done; return __first1 == __last1 && __first2 == __last2; @@ -1423,7 +1452,7 @@ __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, } template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_RandomAccessIterator1 +_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) @@ -1716,7 +1745,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) *__result = *__first; return __result; } @@ -1845,7 +1874,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) *__result = _VSTD::move(*__first); return __result; } @@ -1921,7 +1950,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) *__result = __op(*__first); return __result; } @@ -1932,7 +1961,7 @@ _OutputIterator transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _OutputIterator __result, _BinaryOperation __binary_op) { - for (; __first1 != __last1; ++__first1, ++__first2, ++__result) + for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result) *__result = __binary_op(*__first1, *__first2); return __result; } @@ -1969,7 +1998,7 @@ _OutputIterator replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __old_value, const _Tp& __new_value) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) if (*__first == __old_value) *__result = __new_value; else @@ -1985,7 +2014,7 @@ _OutputIterator replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred, const _Tp& __new_value) { - for (; __first != __last; ++__first, ++__result) + for (; __first != __last; ++__first, (void) ++__result) if (__pred(*__first)) *__result = __new_value; else @@ -2000,7 +2029,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) { - for (; __n > 0; ++__first, --__n) + for (; __n > 0; ++__first, (void) --__n) *__first = __value_; return __first; } @@ -2074,7 +2103,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator generate_n(_OutputIterator __first, _Size __n, _Generator __gen) { - for (; __n > 0; ++__first, --__n) + for (; __n > 0; ++__first, (void) --__n) *__first = __gen(); return __first; } @@ -2505,9 +2534,9 @@ rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterato // min_element template <class _ForwardIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator -min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +__min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { if (__first != __last) { @@ -2519,19 +2548,27 @@ min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) return __first; } +template <class _ForwardIterator, class _Compare> +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator +min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +{ + return __min_element(__first, __last, __comp); +} + template <class _ForwardIterator> inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::min_element(__first, __last, + return __min_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); } // min template <class _Tp, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) { @@ -2539,7 +2576,7 @@ min(const _Tp& __a, const _Tp& __b, _Compare __comp) } template <class _Tp> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& min(const _Tp& __a, const _Tp& __b) { @@ -2549,19 +2586,19 @@ min(const _Tp& __a, const _Tp& __b) #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS template<class _Tp, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp min(initializer_list<_Tp> __t, _Compare __comp) { - return *_VSTD::min_element(__t.begin(), __t.end(), __comp); + return *__min_element(__t.begin(), __t.end(), __comp); } template<class _Tp> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp min(initializer_list<_Tp> __t) { - return *_VSTD::min_element(__t.begin(), __t.end()); + return *__min_element(__t.begin(), __t.end(), __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -2569,9 +2606,9 @@ min(initializer_list<_Tp> __t) // max_element template <class _ForwardIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator -max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +__max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { if (__first != __last) { @@ -2583,19 +2620,28 @@ max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) return __first; } + +template <class _ForwardIterator, class _Compare> +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator +max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +{ + return __max_element(__first, __last, __comp); +} + template <class _ForwardIterator> inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::max_element(__first, __last, + return __max_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); } // max template <class _Tp, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) { @@ -2603,7 +2649,7 @@ max(const _Tp& __a, const _Tp& __b, _Compare __comp) } template <class _Tp> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 const _Tp& max(const _Tp& __a, const _Tp& __b) { @@ -2613,19 +2659,19 @@ max(const _Tp& __a, const _Tp& __b) #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS template<class _Tp, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp max(initializer_list<_Tp> __t, _Compare __comp) { - return *_VSTD::max_element(__t.begin(), __t.end(), __comp); + return *__max_element(__t.begin(), __t.end(), __comp); } template<class _Tp> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp max(initializer_list<_Tp> __t) { - return *_VSTD::max_element(__t.begin(), __t.end()); + return *__max_element(__t.begin(), __t.end(), __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -2684,13 +2730,14 @@ inline _LIBCPP_INLINE_VISIBILITY std::pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); + return _VSTD::minmax_element(__first, __last, + __less<typename iterator_traits<_ForwardIterator>::value_type>()); } // minmax template<class _Tp, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<const _Tp&, const _Tp&> minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) { @@ -2699,7 +2746,7 @@ minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) } template<class _Tp> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<const _Tp&, const _Tp&> minmax(const _Tp& __a, const _Tp& __b) { @@ -2708,24 +2755,49 @@ minmax(const _Tp& __a, const _Tp& __b) #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS -template<class _Tp> -inline _LIBCPP_INLINE_VISIBILITY +template<class _Tp, class _Compare> +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Tp, _Tp> -minmax(initializer_list<_Tp> __t) +minmax(initializer_list<_Tp> __t, _Compare __comp) { - pair<const _Tp*, const _Tp*> __p = - _VSTD::minmax_element(__t.begin(), __t.end()); - return pair<_Tp, _Tp>(*__p.first, *__p.second); + typedef typename initializer_list<_Tp>::const_iterator _Iter; + _Iter __first = __t.begin(); + _Iter __last = __t.end(); + std::pair<_Tp, _Tp> __result ( *__first, *__first ); + + ++__first; + if (__t.size() % 2 == 0) + { + if (__comp(*__first, __result.first)) + __result.first = *__first; + else + __result.second = *__first; + ++__first; + } + + while (__first != __last) + { + _Tp __prev = *__first++; + if (__comp(__prev, *__first)) { + if (__comp(__prev, __result.first)) __result.first = __prev; + if (__comp(__result.second, *__first)) __result.second = *__first; + } + else { + if (__comp(*__first, __result.first)) __result.first = *__first; + if (__comp(__result.second, __prev)) __result.second = __prev; + } + + __first++; + } + return __result; } -template<class _Tp, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY +template<class _Tp> +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Tp, _Tp> -minmax(initializer_list<_Tp> __t, _Compare __comp) +minmax(initializer_list<_Tp> __t) { - pair<const _Tp*, const _Tp*> __p = - _VSTD::minmax_element(__t.begin(), __t.end(), __comp); - return pair<_Tp, _Tp>(*__p.first, *__p.second); + return _VSTD::minmax(__t, __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -4300,7 +4372,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator if (__len1 <= __len2) { value_type* __p = __buff; - for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p) + for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p) ::new(__p) value_type(_VSTD::move(*__i)); __merge<_Compare>(move_iterator<value_type*>(__buff), move_iterator<value_type*>(__p), @@ -4311,7 +4383,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator else { value_type* __p = __buff; - for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p) + for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p) ::new(__p) value_type(_VSTD::move(*__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator<value_type*> _Rv; @@ -4336,7 +4408,7 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, if (__len2 == 0) return; // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 - for (; true; ++__first, --__len1) + for (; true; ++__first, (void) --__len1) { if (__len1 == 0) return; @@ -4724,49 +4796,8 @@ is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) template <class _Compare, class _RandomAccessIterator> void -__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - if (__len > 1) - { - difference_type __p = 0; - _RandomAccessIterator __pp = __first; - difference_type __c = 2; - _RandomAccessIterator __cp = __first + __c; - if (__c == __len || __comp(*__cp, *(__cp - 1))) - { - --__c; - --__cp; - } - if (__comp(*__pp, *__cp)) - { - value_type __t(_VSTD::move(*__pp)); - do - { - *__pp = _VSTD::move(*__cp); - __pp = __cp; - __p = __c; - __c = (__p + 1) * 2; - if (__c > __len) - break; - __cp = __first + __c; - if (__c == __len || __comp(*__cp, *(__cp - 1))) - { - --__c; - --__cp; - } - } while (__comp(__t, *__cp)); - *__pp = _VSTD::move(__t); - } - } -} - -template <class _Compare, class _RandomAccessIterator> -void -__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) +__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; @@ -4799,10 +4830,10 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); - __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first); + __sift_up<_Comp_ref>(__first, __last, __c, __last - __first); #else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; - __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first); + __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); #endif // _LIBCPP_DEBUG } @@ -4817,6 +4848,60 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) // pop_heap template <class _Compare, class _RandomAccessIterator> +void +__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len, + _RandomAccessIterator __start) +{ + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; + // left-child of __start is at 2 * __start + 1 + // right-child of __start is at 2 * __start + 2 + difference_type __child = __start - __first; + + if (__len < 2 || (__len - 2) / 2 < __child) + return; + + __child = 2 * __child + 1; + _RandomAccessIterator __child_i = __first + __child; + + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { + // right-child exists and is greater than left-child + ++__child_i; + ++__child; + } + + // check if we are in heap-order + if (__comp(*__child_i, *__start)) + // we are, __start is larger than it's largest child + return; + + value_type __top(_VSTD::move(*__start)); + do + { + // we are not in heap-order, swap the parent with it's largest child + *__start = _VSTD::move(*__child_i); + __start = __child_i; + + if ((__len - 2) / 2 < __child) + break; + + // recompute the child based off of the updated parent + __child = 2 * __child + 1; + __child_i = __first + __child; + + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { + // right-child exists and is greater than left-child + ++__child_i; + ++__child; + } + + // check if we are in heap-order + } while (!__comp(*__child_i, __top)); + *__start = _VSTD::move(__top); +} + +template <class _Compare, class _RandomAccessIterator> inline _LIBCPP_INLINE_VISIBILITY void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, @@ -4825,7 +4910,7 @@ __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare if (__len > 1) { swap(*__first, *--__last); - __push_heap_front<_Compare>(__first, __last, __comp, __len-1); + __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); } } @@ -4862,10 +4947,11 @@ __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compar difference_type __n = __last - __first; if (__n > 1) { - __last = __first; - ++__last; - for (difference_type __i = 1; __i < __n;) - __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i); + // start from the first parent, there is no need to consider children + for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) + { + __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); + } } } @@ -4940,7 +5026,7 @@ __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _R if (__comp(*__i, *__first)) { swap(*__i, *__first); - __push_heap_front<_Compare>(__first, __middle, __comp, __len); + __sift_down<_Compare>(__first, __middle, __comp, __len, __first); } } __sort_heap<_Compare>(__first, __middle, __comp); @@ -4981,15 +5067,15 @@ __partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __r = __result_first; if (__r != __result_last) { - typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0; - for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len) + for (; __first != __last && __r != __result_last; (void) ++__first, ++__r) *__r = *__first; __make_heap<_Compare>(__result_first, __r, __comp); + typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; for (; __first != __last; ++__first) if (__comp(*__first, *__result_first)) { *__result_first = *__first; - __push_heap_front<_Compare>(__result_first, __r, __comp, __len); + __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); } __sort_heap<_Compare>(__result_first, __r, __comp); } @@ -5503,7 +5589,7 @@ bool __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) { - for (; __first2 != __last2; ++__first1, ++__first2) + for (; __first2 != __last2; ++__first1, (void) ++__first2) { if (__first1 == __last1 || __comp(*__first1, *__first2)) return true; |
