Index: include/bits/stl_algo.h =================================================================== --- include/bits/stl_algo.h (revision 151016) +++ include/bits/stl_algo.h (working copy) @@ -136,6 +136,54 @@ return __b; } + /// Swaps the median value of *__a, *__b and *__c to *__a + template + void + __move_median_to_front(_Iterator __a, _Iterator __b, _Iterator __c) + { + // concept requirements + typedef typename iterator_traits<_Iterator>::value_type _Tp; + __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) + 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 + void + __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c, + _Compare __comp) + { + // concept requirements + typedef typename iterator_traits<_Iterator>::value_type _Tp; + __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, + _Tp, _Tp>) + 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 +2106,40 @@ } /// This is a helper function for the sort routine. - template + template 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 + template 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 +2153,15 @@ 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 +2175,15 @@ 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 +2197,7 @@ _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 +2210,7 @@ _ValueType; for (_RandomAccessIterator __i = __first; __i != __last; ++__i) - std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp); + std::__unguarded_linear_insert(__i, __comp); } /** @@ -2202,7 +2254,7 @@ template _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Tp __pivot) + _RandomAccessIterator __last, const _Tp& __pivot) { while (true) { @@ -2223,7 +2275,7 @@ _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Tp __pivot, _Compare __comp) + const _Tp& __pivot, _Compare __comp) { while (true) { @@ -2239,6 +2291,29 @@ } } + /// This is a helper function... + template + _RandomAccessIterator + __unguarded_partition_pivot(_RandomAccessIterator __first, + _RandomAccessIterator __last) + { + _RandomAccessIterator __mid = __first + (__last - __first) / 2; + __move_median_first(__first, __mid, (__last - 1)); + return __unguarded_partition(__first + 1, __last, *__first); + } + + + /// This is a helper function... + template + _RandomAccessIterator + __unguarded_partition_pivot(_RandomAccessIterator __first, + _RandomAccessIterator __last, _Compare __comp) + { + _RandomAccessIterator __mid = __first + (__last - __first) / 2; + __move_median_first(__first, __mid, (__last - 1), __comp); + return __unguarded_partition(__first, __last - 1, *(__last - 1), __comp); + } + /// This is a helper function for the sort routine. template void @@ -2246,9 +2321,6 @@ _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 +2330,7 @@ } --__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 +2343,6 @@ _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 +2352,7 @@ } --__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 +2403,7 @@ } --__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 +2432,7 @@ } --__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 Index: ChangeLog =================================================================== --- ChangeLog (revision 151016) +++ ChangeLog (working copy) @@ -1,3 +1,18 @@ +2009-08-23 Chris Jefferson + include/stl_algo.h (__move_median_to_front): Add new method + to ease sorting move-only types. + (__unguarded_linear_insert) : Assume always inserting value + at __last. + (__insertion_sort, __unguarded_insertion_sort) : Update for + move-only types. + (__unguarded_partition) : Take pivot by reference. + (__unguarded_partition_pivot) : Add new method for sorting + move-only types. + (__introsort_loop, __introselect) : Use + __unguarded_partition_pivot. + testsuite/25_algorithms/nth_element/moveable.cc : Enable. + + 2009-08-22 Ralf Wildenhues * doc/xml/manual/build_hacking.xml: Use tools from Autoconf Index: testsuite/25_algorithms/nth_element/moveable.cc =================================================================== --- testsuite/25_algorithms/nth_element/moveable.cc (revision 151016) +++ testsuite/25_algorithms/nth_element/moveable.cc (working copy) @@ -1,4 +1,3 @@ -// { dg-require-rvalref "" } // { dg-options "-std=gnu++0x" } // Copyright (C) 2005, 2007, 2009 Free Software Foundation, Inc.