diff options
Diffstat (limited to 'gcc-4.6/libstdc++-v3/include/bits/stl_algo.h')
| -rw-r--r-- | gcc-4.6/libstdc++-v3/include/bits/stl_algo.h | 263 |
1 files changed, 170 insertions, 93 deletions
diff --git a/gcc-4.6/libstdc++-v3/include/bits/stl_algo.h b/gcc-4.6/libstdc++-v3/include/bits/stl_algo.h index 6c2be06..1d6026a 100644 --- a/gcc-4.6/libstdc++-v3/include/bits/stl_algo.h +++ b/gcc-4.6/libstdc++-v3/include/bits/stl_algo.h @@ -2751,20 +2751,76 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // merge - /// This is a helper function for the merge routines. + /// This is a helper function for the __merge_adaptive routines. + template<typename _InputIterator1, typename _InputIterator2, + typename _OutputIterator> + void + __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result) + { + while (__first1 != __last1 && __first2 != __last2) + { + if (*__first2 < *__first1) + { + *__result = _GLIBCXX_MOVE(*__first2); + ++__first2; + } + else + { + *__result = _GLIBCXX_MOVE(*__first1); + ++__first1; + } + ++__result; + } + if (__first1 != __last1) + _GLIBCXX_MOVE3(__first1, __last1, __result); + } + + /// This is a helper function for the __merge_adaptive routines. + template<typename _InputIterator1, typename _InputIterator2, + typename _OutputIterator, typename _Compare> + void + __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result, _Compare __comp) + { + while (__first1 != __last1 && __first2 != __last2) + { + if (__comp(*__first2, *__first1)) + { + *__result = _GLIBCXX_MOVE(*__first2); + ++__first2; + } + else + { + *__result = _GLIBCXX_MOVE(*__first1); + ++__first1; + } + ++__result; + } + if (__first1 != __last1) + _GLIBCXX_MOVE3(__first1, __last1, __result); + } + + /// This is a helper function for the __merge_adaptive routines. template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, typename _BidirectionalIterator3> - _BidirectionalIterator3 - __move_merge_backward(_BidirectionalIterator1 __first1, - _BidirectionalIterator1 __last1, - _BidirectionalIterator2 __first2, - _BidirectionalIterator2 __last2, - _BidirectionalIterator3 __result) + void + __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, + _BidirectionalIterator1 __last1, + _BidirectionalIterator2 __first2, + _BidirectionalIterator2 __last2, + _BidirectionalIterator3 __result) { if (__first1 == __last1) - return _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); - if (__first2 == __last2) - return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result); + { + _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); + return; + } + else if (__first2 == __last2) + return; + --__last1; --__last2; while (true) @@ -2773,34 +2829,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { *--__result = _GLIBCXX_MOVE(*__last1); if (__first1 == __last1) - return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); + { + _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); + return; + } --__last1; } else { *--__result = _GLIBCXX_MOVE(*__last2); if (__first2 == __last2) - return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result); + return; --__last2; } } } - /// This is a helper function for the merge routines. + /// This is a helper function for the __merge_adaptive routines. template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, typename _BidirectionalIterator3, typename _Compare> - _BidirectionalIterator3 - __move_merge_backward(_BidirectionalIterator1 __first1, - _BidirectionalIterator1 __last1, - _BidirectionalIterator2 __first2, - _BidirectionalIterator2 __last2, - _BidirectionalIterator3 __result, - _Compare __comp) + void + __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, + _BidirectionalIterator1 __last1, + _BidirectionalIterator2 __first2, + _BidirectionalIterator2 __last2, + _BidirectionalIterator3 __result, + _Compare __comp) { if (__first1 == __last1) - return _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); - if (__first2 == __last2) - return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result); + { + _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); + return; + } + else if (__first2 == __last2) + return; + --__last1; --__last2; while (true) @@ -2809,75 +2872,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { *--__result = _GLIBCXX_MOVE(*__last1); if (__first1 == __last1) - return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); + { + _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); + return; + } --__last1; } else { *--__result = _GLIBCXX_MOVE(*__last2); if (__first2 == __last2) - return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result); + return; --__last2; } } } /// This is a helper function for the merge routines. - template<typename _InputIterator1, typename _InputIterator2, - typename _OutputIterator> - _OutputIterator - __move_merge(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _OutputIterator __result) - { - while (__first1 != __last1 && __first2 != __last2) - { - if (*__first2 < *__first1) - { - *__result = _GLIBCXX_MOVE(*__first2); - ++__first2; - } - else - { - *__result = _GLIBCXX_MOVE(*__first1); - ++__first1; - } - ++__result; - } - return _GLIBCXX_MOVE3(__first2, __last2, - _GLIBCXX_MOVE3(__first1, __last1, - __result)); - } - - /// This is a helper function for the merge routines. - template<typename _InputIterator1, typename _InputIterator2, - typename _OutputIterator, typename _Compare> - _OutputIterator - __move_merge(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _OutputIterator __result, _Compare __comp) - { - while (__first1 != __last1 && __first2 != __last2) - { - if (__comp(*__first2, *__first1)) - { - *__result = _GLIBCXX_MOVE(*__first2); - ++__first2; - } - else - { - *__result = _GLIBCXX_MOVE(*__first1); - ++__first1; - } - ++__result; - } - return _GLIBCXX_MOVE3(__first2, __last2, - _GLIBCXX_MOVE3(__first1, __last1, - __result)); - } - - - /// This is a helper function for the merge routines. template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, typename _Distance> _BidirectionalIterator1 @@ -2891,15 +2902,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _BidirectionalIterator2 __buffer_end; if (__len1 > __len2 && __len2 <= __buffer_size) { - __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); - _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); - return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); + if (__len2) + { + __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); + _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); + return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); + } + else + return __first; } else if (__len1 <= __buffer_size) { - __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); - _GLIBCXX_MOVE3(__middle, __last, __first); - return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); + if (__len1) + { + __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); + _GLIBCXX_MOVE3(__middle, __last, __first); + return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); + } + else + return __last; } else { @@ -2922,13 +2943,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); - std::__move_merge(__buffer, __buffer_end, __middle, __last, __first); + std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, + __first); } else if (__len2 <= __buffer_size) { _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); - std::__move_merge_backward(__first, __middle, __buffer, - __buffer_end, __last); + std::__move_merge_adaptive_backward(__first, __middle, __buffer, + __buffer_end, __last); } else { @@ -2978,14 +3000,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); - std::__move_merge(__buffer, __buffer_end, __middle, __last, - __first, __comp); + std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, + __first, __comp); } else if (__len2 <= __buffer_size) { _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); - std::__move_merge_backward(__first, __middle, __buffer, __buffer_end, - __last, __comp); + std::__move_merge_adaptive_backward(__first, __middle, __buffer, + __buffer_end, __last, __comp); } else { @@ -3222,6 +3244,61 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __CheckedCompare(__comp)); } + + /// This is a helper function for the __merge_sort_loop routines. + template<typename _InputIterator1, typename _InputIterator2, + typename _OutputIterator> + _OutputIterator + __move_merge(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result) + { + while (__first1 != __last1 && __first2 != __last2) + { + if (*__first2 < *__first1) + { + *__result = _GLIBCXX_MOVE(*__first2); + ++__first2; + } + else + { + *__result = _GLIBCXX_MOVE(*__first1); + ++__first1; + } + ++__result; + } + return _GLIBCXX_MOVE3(__first2, __last2, + _GLIBCXX_MOVE3(__first1, __last1, + __result)); + } + + /// This is a helper function for the __merge_sort_loop routines. + template<typename _InputIterator1, typename _InputIterator2, + typename _OutputIterator, typename _Compare> + _OutputIterator + __move_merge(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result, _Compare __comp) + { + while (__first1 != __last1 && __first2 != __last2) + { + if (__comp(*__first2, *__first1)) + { + *__result = _GLIBCXX_MOVE(*__first2); + ++__first2; + } + else + { + *__result = _GLIBCXX_MOVE(*__first1); + ++__first1; + } + ++__result; + } + return _GLIBCXX_MOVE3(__first2, __last2, + _GLIBCXX_MOVE3(__first1, __last1, + __result)); + } + template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Distance> void |