diff options
Diffstat (limited to 'libstdc++-v3/include/bits/stl_algo.h')
-rw-r--r-- | libstdc++-v3/include/bits/stl_algo.h | 169 |
1 files changed, 105 insertions, 64 deletions
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 6418ebf6db4..a745295e9b0 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -136,6 +136,56 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __b; } + /// Swaps the median value of *__a, *__b and *__c to *__a + template<typename _Iterator> + void + __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c) + { + // concept requirements + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_Iterator>::value_type>) + + if (*__a < *__b) + { + if (*__b < *__c) + std::iter_swap(__a, __b); + else if (*__a < *__c) + std::iter_swap(__a, __c); + } + else if (*__a < *__c) + return; + else if (*__b < *__c) + std::iter_swap(__a, __c); + else + std::iter_swap(__a, __b); + } + + /// Swaps the median value of *__a, *__b and *__c under __comp to *__a + template<typename _Iterator, typename _Compare> + void + __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c, + _Compare __comp) + { + // concept requirements + __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, + typename iterator_traits<_Iterator>::value_type, + typename iterator_traits<_Iterator>::value_type>) + + if (__comp(*__a, *__b)) + { + if (__comp(*__b, *__c)) + std::iter_swap(__a, __b); + else if (__comp(*__a, *__c)) + std::iter_swap(__a, __c); + } + else if (__comp(*__a, *__c)) + return; + else if (__comp(*__b, *__c)) + std::iter_swap(__a, __c); + else + std::iter_swap(__a, __b); + } + // for_each /// This is an overload used by find() for the Input Iterator case. @@ -2058,36 +2108,40 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /// This is a helper function for the sort routine. - template<typename _RandomAccessIterator, typename _Tp> + template<typename _RandomAccessIterator> void - __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val) + __unguarded_linear_insert(_RandomAccessIterator __last) { + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__last); _RandomAccessIterator __next = __last; --__next; while (__val < *__next) { - *__last = *__next; + *__last = _GLIBCXX_MOVE(*__next); __last = __next; --__next; } - *__last = __val; + *__last = _GLIBCXX_MOVE(__val); } /// This is a helper function for the sort routine. - template<typename _RandomAccessIterator, typename _Tp, typename _Compare> + template<typename _RandomAccessIterator, typename _Compare> void - __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, + __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp) { + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__last); _RandomAccessIterator __next = __last; --__next; while (__comp(__val, *__next)) { - *__last = *__next; + *__last = _GLIBCXX_MOVE(*__next); __last = __next; --__next; } - *__last = __val; + *__last = _GLIBCXX_MOVE(__val); } /// This is a helper function for the sort routine. @@ -2101,15 +2155,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std) for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) { - typename iterator_traits<_RandomAccessIterator>::value_type - __val = *__i; - if (__val < *__first) + if (*__i < *__first) { - std::copy_backward(__first, __i, __i + 1); - *__first = __val; + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__i); + _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); + *__first = _GLIBCXX_MOVE(__val); } else - std::__unguarded_linear_insert(__i, __val); + std::__unguarded_linear_insert(__i); } } @@ -2123,15 +2177,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std) for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) { - typename iterator_traits<_RandomAccessIterator>::value_type - __val = *__i; - if (__comp(__val, *__first)) + if (__comp(*__i, *__first)) { - std::copy_backward(__first, __i, __i + 1); - *__first = __val; + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__i); + _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); + *__first = _GLIBCXX_MOVE(__val); } else - std::__unguarded_linear_insert(__i, __val, __comp); + std::__unguarded_linear_insert(__i, __comp); } } @@ -2145,7 +2199,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType; for (_RandomAccessIterator __i = __first; __i != __last; ++__i) - std::__unguarded_linear_insert(__i, _ValueType(*__i)); + std::__unguarded_linear_insert(__i); } /// This is a helper function for the sort routine. @@ -2158,7 +2212,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType; for (_RandomAccessIterator __i = __first; __i != __last; ++__i) - std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp); + std::__unguarded_linear_insert(__i, __comp); } /** @@ -2202,7 +2256,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template<typename _RandomAccessIterator, typename _Tp> _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Tp __pivot) + _RandomAccessIterator __last, const _Tp& __pivot) { while (true) { @@ -2223,7 +2277,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Tp __pivot, _Compare __comp) + const _Tp& __pivot, _Compare __comp) { while (true) { @@ -2239,6 +2293,29 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } + /// This is a helper function... + template<typename _RandomAccessIterator> + inline _RandomAccessIterator + __unguarded_partition_pivot(_RandomAccessIterator __first, + _RandomAccessIterator __last) + { + _RandomAccessIterator __mid = __first + (__last - __first) / 2; + std::__move_median_first(__first, __mid, (__last - 1)); + return std::__unguarded_partition(__first + 1, __last, *__first); + } + + + /// This is a helper function... + template<typename _RandomAccessIterator, typename _Compare> + inline _RandomAccessIterator + __unguarded_partition_pivot(_RandomAccessIterator __first, + _RandomAccessIterator __last, _Compare __comp) + { + _RandomAccessIterator __mid = __first + (__last - __first) / 2; + std::__move_median_first(__first, __mid, (__last - 1), __comp); + return std::__unguarded_partition(__first + 1, __last, *__first, __comp); + } + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Size> void @@ -2246,9 +2323,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _RandomAccessIterator __last, _Size __depth_limit) { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - while (__last - __first > int(_S_threshold)) { if (__depth_limit == 0) @@ -2258,14 +2332,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - - 1)))); + std::__unguarded_partition_pivot(__first, __last); std::__introsort_loop(__cut, __last, __depth_limit); __last = __cut; } @@ -2278,9 +2345,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp) { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - while (__last - __first > int(_S_threshold)) { if (__depth_limit == 0) @@ -2290,15 +2354,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - 1), - __comp)), - __comp); + std::__unguarded_partition_pivot(__first, __last, __comp); std::__introsort_loop(__cut, __last, __depth_limit, __comp); __last = __cut; } @@ -2349,14 +2405,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - - 1)))); + std::__unguarded_partition_pivot(__first, __last); if (__cut <= __nth) __first = __cut; else @@ -2385,15 +2434,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - 1), - __comp)), - __comp); + std::__unguarded_partition_pivot(__first, __last, __comp); if (__cut <= __nth) __first = __cut; else |