diff options
Diffstat (limited to 'contrib/libc++/include/algorithm')
| -rw-r--r-- | contrib/libc++/include/algorithm | 170 |
1 files changed, 93 insertions, 77 deletions
diff --git a/contrib/libc++/include/algorithm b/contrib/libc++/include/algorithm index 61b0143..7b0c53e 100644 --- a/contrib/libc++/include/algorithm +++ b/contrib/libc++/include/algorithm @@ -521,11 +521,11 @@ template <class RandomAccessIterator, class Compare> template <class ForwardIterator> ForwardIterator - min_element(ForwardIterator first, ForwardIterator last); + min_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14 template <class ForwardIterator, class Compare> ForwardIterator - min_element(ForwardIterator first, ForwardIterator last, Compare comp); + min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14 template <class T> const T& @@ -545,11 +545,11 @@ template<class T, class Compare> template <class ForwardIterator> ForwardIterator - max_element(ForwardIterator first, ForwardIterator last); + max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14 template <class ForwardIterator, class Compare> ForwardIterator - max_element(ForwardIterator first, ForwardIterator last, Compare comp); + max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14 template <class T> const T& @@ -569,11 +569,11 @@ template<class T, class Compare> template<class ForwardIterator> pair<ForwardIterator, ForwardIterator> - minmax_element(ForwardIterator first, ForwardIterator last); + minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14 template<class ForwardIterator, class Compare> pair<ForwardIterator, ForwardIterator> - minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); + minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14 template<class T> pair<const T&, const T&> @@ -1672,7 +1672,8 @@ search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) { return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type> - (__first, __last, __count, __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); + (__first, __last, __convert_to_integral(__count), __value_, __pred, + typename iterator_traits<_ForwardIterator>::iterator_category()); } template <class _ForwardIterator, class _Size, class _Tp> @@ -1681,7 +1682,8 @@ _ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::search_n(__first, __last, __count, __value_, __equal_to<__v, _Tp>()); + return _VSTD::search_n(__first, __last, __convert_to_integral(__count), + __value_, __equal_to<__v, _Tp>()); } // copy @@ -1761,7 +1763,8 @@ typename enable_if __copy(_Tp* __first, _Tp* __last, _Up* __result) { const size_t __n = static_cast<size_t>(__last - __first); - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + if (__n > 0) + _VSTD::memmove(__result, __first, __n * sizeof(_Up)); return __result + __n; } @@ -1796,8 +1799,11 @@ typename enable_if __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) { const size_t __n = static_cast<size_t>(__last - __first); - __result -= __n; - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + if (__n > 0) + { + __result -= __n; + _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + } return __result; } @@ -1839,8 +1845,10 @@ typename enable_if !__is_random_access_iterator<_InputIterator>::value, _OutputIterator >::type -copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) +copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) { + typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize; + _IntegralSize __n = __orig_n; if (__n > 0) { *__result = *__first; @@ -1862,8 +1870,10 @@ typename enable_if __is_random_access_iterator<_InputIterator>::value, _OutputIterator >::type -copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) +copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) { + typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize; + _IntegralSize __n = __orig_n; return _VSTD::copy(__first, __first + __n, __result); } @@ -1890,7 +1900,8 @@ typename enable_if __move(_Tp* __first, _Tp* __last, _Up* __result) { const size_t __n = static_cast<size_t>(__last - __first); - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + if (__n > 0) + _VSTD::memmove(__result, __first, __n * sizeof(_Up)); return __result + __n; } @@ -1925,8 +1936,11 @@ typename enable_if __move_backward(_Tp* __first, _Tp* __last, _Up* __result) { const size_t __n = static_cast<size_t>(__last - __first); - __result -= __n; - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + if (__n > 0) + { + __result -= __n; + _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + } return __result; } @@ -2055,7 +2069,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) { - return _VSTD::__fill_n(__first, __n, __value_); + return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_); } // fill @@ -2101,8 +2115,10 @@ generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen) template <class _OutputIterator, class _Size, class _Generator> inline _LIBCPP_INLINE_VISIBILITY _OutputIterator -generate_n(_OutputIterator __first, _Size __n, _Generator __gen) +generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen) { + typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize; + _IntegralSize __n = __orig_n; for (; __n > 0; ++__first, (void) --__n) *__first = __gen(); return __first; @@ -2536,7 +2552,7 @@ rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterato template <class _ForwardIterator, class _Compare> 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) { @@ -2548,20 +2564,12 @@ __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 +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last) { - return __min_element(__first, __last, + return _VSTD::min_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); } @@ -2590,7 +2598,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp min(initializer_list<_Tp> __t, _Compare __comp) { - return *__min_element(__t.begin(), __t.end(), __comp); + return *_VSTD::min_element(__t.begin(), __t.end(), __comp); } template<class _Tp> @@ -2598,7 +2606,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp min(initializer_list<_Tp> __t) { - return *__min_element(__t.begin(), __t.end(), __less<_Tp>()); + return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -2608,7 +2616,7 @@ min(initializer_list<_Tp> __t) template <class _ForwardIterator, class _Compare> 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) { @@ -2621,20 +2629,12 @@ __max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp } -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 +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last) { - return __max_element(__first, __last, + return _VSTD::max_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); } @@ -2663,7 +2663,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp max(initializer_list<_Tp> __t, _Compare __comp) { - return *__max_element(__t.begin(), __t.end(), __comp); + return *_VSTD::max_element(__t.begin(), __t.end(), __comp); } template<class _Tp> @@ -2671,7 +2671,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp max(initializer_list<_Tp> __t) { - return *__max_element(__t.begin(), __t.end(), __less<_Tp>()); + return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>()); } #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -2679,6 +2679,7 @@ max(initializer_list<_Tp> __t) // minmax_element template <class _ForwardIterator, class _Compare> +_LIBCPP_CONSTEXPR_AFTER_CXX11 std::pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { @@ -2726,7 +2727,7 @@ minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __com } template <class _ForwardIterator> -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 std::pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last) { @@ -2763,7 +2764,7 @@ minmax(initializer_list<_Tp> __t, _Compare __comp) typedef typename initializer_list<_Tp>::const_iterator _Iter; _Iter __first = __t.begin(); _Iter __last = __t.end(); - std::pair<_Tp, _Tp> __result ( *__first, *__first ); + std::pair<_Tp, _Tp> __result(*__first, *__first); ++__first; if (__t.size() % 2 == 0) @@ -2778,13 +2779,13 @@ minmax(initializer_list<_Tp> __t, _Compare __comp) 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; + if (__comp(*__first, __prev)) { + if ( __comp(*__first, __result.first)) __result.first = *__first; + if (!__comp(__prev, __result.second)) __result.second = __prev; } else { - if (__comp(*__first, __result.first)) __result.first = *__first; - if (__comp(__result.second, __prev)) __result.second = __prev; + if ( __comp(__prev, __result.first)) __result.first = __prev; + if (!__comp(*__first, __result.second)) __result.second = *__first; } __first++; @@ -3148,6 +3149,9 @@ is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) for (; __first != __last; ++__first) if (!__pred(*__first)) break; + if ( __first == __last ) + return true; + ++__first; for (; __first != __last; ++__first) if (__pred(*__first)) return false; @@ -4357,6 +4361,34 @@ merge(_InputIterator1 __first1, _InputIterator1 __last1, // inplace_merge +template <class _Compare, class _InputIterator1, class _InputIterator2, + class _OutputIterator> +void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result, _Compare __comp) +{ + for (; __first1 != __last1; ++__result) + { + if (__first2 == __last2) + { + _VSTD::move(__first1, __last1, __result); + return; + } + + if (__comp(*__first2, *__first1)) + { + *__result = _VSTD::move(*__first2); + ++__first2; + } + else + { + *__result = _VSTD::move(*__first1); + ++__first1; + } + } + // __first2 through __last2 are already in the right spot. +} + template <class _Compare, class _BidirectionalIterator> void __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, @@ -4372,11 +4404,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator value_type* __p = __buff; 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), - move_iterator<_BidirectionalIterator>(__middle), - move_iterator<_BidirectionalIterator>(__last), - __first, __comp); + __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp); } else { @@ -4385,9 +4413,9 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator ::new(__p) value_type(_VSTD::move(*__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator<value_type*> _Rv; - __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)), - move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)), - _RBi(__last), __negate<_Compare>(__comp)); + __half_inplace_merge(_Rv(__p), _Rv(__buff), + _RBi(__middle), _RBi(__first), + _RBi(__last), __negate<_Compare>(__comp)); } } @@ -4404,6 +4432,9 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, // if __middle == __last, we're done if (__len2 == 0) return; + if (__len1 <= __buff_size || __len2 <= __buff_size) + return __buffered_inplace_merge<_Compare> + (__first, __middle, __last, __comp, __len1, __len2, __buff); // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 for (; true; ++__first, (void) --__len1) { @@ -4412,11 +4443,6 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, if (__comp(*__middle, *__first)) break; } - if (__len1 <= __buff_size || __len2 <= __buff_size) - { - __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff); - return; - } // __first < __middle < __last // *__first > *__middle // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that @@ -4481,12 +4507,6 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, } } -template <class _Tp> -struct __inplace_merge_switch -{ - static const unsigned value = is_trivially_copy_assignable<_Tp>::value; -}; - template <class _BidirectionalIterator, class _Compare> inline _LIBCPP_INLINE_VISIBILITY void @@ -4498,13 +4518,9 @@ inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _ difference_type __len1 = _VSTD::distance(__first, __middle); difference_type __len2 = _VSTD::distance(__middle, __last); difference_type __buf_size = _VSTD::min(__len1, __len2); - pair<value_type*, ptrdiff_t> __buf(0, 0); - unique_ptr<value_type, __return_temporary_buffer> __h; - if (__inplace_merge_switch<value_type>::value && __buf_size > 8) - { - __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); - __h.reset(__buf.first); - } + pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); + unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first); + #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); |
