This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[patch] : finish adding move symantics to <algorithm>
- From: chris jefferson <caj at cs dot york dot ac dot uk>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Mon, 30 May 2005 11:51:53 +0100
- Subject: [patch] : finish adding move symantics to <algorithm>
This patch finishes adding move symantics to <algorithm>, in particular
to the sort functions and inplace_merge, as they all use each other and
the same internal functions.
This one is slightly more intrusive than the others, and in particular
introduces different algorithms for sorting moveable and non-moveable types.
Bootstrapped on powerpc-apple-darwin8.1.0
Chris
2005-05-30 Chris Jefferson <chris@bubblescope.net>
* include/bits/stl_algo.h (__stable_partition_adaptive,
__merge_sort_loop, __merge_backward, __rotate_adaptive,
__merge_adaptive) : Make rvalref aware.
(__unguarded_linear_insert) : Remove unnecessary parameter, make
rvalref aware.
(__unguarded_nocopy_partition, __unguarded_mid_partition,
__introsort_partition, __move_merge) : New helper functions.
(__insertion_sort) : Make rvalref aware, adapt to new
__unguarded_linear_insert.
(__unguarded_insertion_sort) : Adapt to new __unguarded_linear_insert.
(__introsort_loop, nth_element) : Use __introsort_partition.
* include/bits/stl_algobase.h (__move, __move_backward) : New.
* include/bits/stl_tempbuf.h (_M_initalize_buffer) : Removed from
_Temporary_buffer into own class, make rvalref aware.
(_Temporary_buffer::_Temporary_buffer) : Use new _M_initalize_buffer,
remove old workaround.
* include/bits/stl_uninitalized.h (__uninitalized_fill_n) : New.
* testsuite/25_algorithms/inplace_merge/moveable.cc : New.
* testsuite/25_algorithms/nth_element/moveable.cc : New.
* testsuite/25_algorithms/partial_sort/moveable.cc : New.
* testsuite/25_algorithms/partition/moveable.cc : Add stable_partition
test.
* testsuite/25_algorithms/sort/moveable.cc : New.
* testsuite/25_algorithms/sort.cc : Move to...
* testsuite/25_algorithms/sort/sort.cc : ...here.
* testsuite/25_algorithms/stable_sort/moveable.cc : New.
* testsuite/performance/25_algorithms/sort.cc : New.
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_algo.h libstdc++-v3/include/bits/stl_algo.h
--- libstdc++-v3.so_7.clean/include/bits/stl_algo.h 2005-05-25 13:38:47.000000000 +0100
+++ libstdc++-v3/include/bits/stl_algo.h 2005-05-28 12:18:24.000000000 +0100
@@ -1811,15 +1811,15 @@
for ( ; __first != __last ; ++__first)
if (__pred(*__first))
{
- *__result1 = *__first;
+ *__result1 = __gnu_cxx::__move(*__first);
++__result1;
}
else
{
- *__result2 = *__first;
+ *__result2 = __gnu_cxx::__move(*__first);
++__result2;
}
- std::copy(__buffer, __result2, __result1);
+ std::__move(__buffer, __result2, __result1);
return __result1;
}
else
@@ -1929,20 +1929,109 @@
* This is a helper function for the sort routine.
* @endif
*/
- template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
- void
- __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
- _Compare __comp)
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline void
+ __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
+ typename iterator_traits<_RandomAccessIterator>::value_type
+ __val(__gnu_cxx::__move(*__last));
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, *__next))
{
- *__last = *__next;
+ *__last = __gnu_cxx::__move(*__next);
__last = __next;
--__next;
}
- *__last = __val;
+ *__last = __gnu_cxx::__move(__val);
+ }
+
+ /**
+ * @if maint
+ * This is a helper function. It assumes __pivot is not in the range
+ * [__first, __last).
+ * @endif
+ */
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline _RandomAccessIterator
+ __unguarded_nocopy_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last,
+ _RandomAccessIterator __pivot, _Compare __comp)
+ {
+ while (true)
+ {
+ while (__comp(*__first, *__pivot))
+ ++__first;
+ --__last;
+ while (__comp(*__pivot, *__last))
+ --__last;
+ if (!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ }
+ }
+
+ /**
+ * @if maint
+ * This is a helper function for the sort routine
+ * @endif
+ */
+ template<typename _RandomAccessIterator, typename _Compare>
+ _RandomAccessIterator
+ __unguarded_mid_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last,
+ _RandomAccessIterator __pivot, _Compare __comp)
+ {
+ while (true)
+ {
+ while (__comp(*__first, *__pivot))
+ ++__first;
+ --__last;
+ while (__comp(*__pivot, *__last))
+ --__last;
+ if (__first == __pivot)
+ {
+ if(__last == __pivot)
+ return __first;
+ ++__first;
+ while(__comp(*__first, *__pivot))
+ ++__first;
+ if(!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ break;
+ }
+
+ if (__last == __pivot)
+ {
+ --__last;
+ while(__comp(*__pivot, *__last))
+ --__last;
+ if(!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ break;
+ }
+ std::iter_swap(__first, __last);
+ ++__first;
+ }
+
+ while (true)
+ {
+ while (__comp(*__first, *__pivot))
+ ++__first;
+ --__last;
+ while (__comp(*__pivot, *__last))
+ --__last;
+
+ if (!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ }
}
/**
@@ -1959,15 +2048,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(__gnu_cxx::__move(*__i));
+ std::__move_backward(__first, __i, __i + 1);
+ *__first = __gnu_cxx::__move(__val);
}
else
- std::__unguarded_linear_insert(__i, __val, __comp);
+ std::__unguarded_linear_insert(__i, __comp);
}
}
@@ -1985,7 +2074,7 @@
_ValueType;
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
- std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
+ std::__unguarded_linear_insert(__i, __comp);
}
/**
@@ -2200,6 +2289,65 @@
__gnu_cxx::__ops::less());
}
+
+
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline typename __enable_if<_RandomAccessIterator,
+ !(__gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
+ ::value_type>::value)>::__type
+ __introsort_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last, _Compare __comp)
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+
+ return
+ std::__unguarded_partition(__first, __last,
+ _ValueType(std::__median(*__first,
+ *(__first
+ + (__last
+ - __first)
+ / 2),
+ *(__last - 1),
+ __comp)),
+ __comp);
+ }
+
+template<typename _RandomAccessIterator, typename _Compare>
+ inline typename __enable_if<_RandomAccessIterator,
+ __gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
+ ::value_type>::value>::__type
+ __introsort_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last, _Compare __comp)
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ _RandomAccessIterator __cut, __pivot(__first + (__last - __first)/2);
+ const _ValueType &__a = *__first;
+ const _ValueType &__b = *__pivot;
+ const _ValueType &__c = *(__last - 1);
+
+ if (__comp(__a, __b))
+ if (__comp(__b, __c))
+ __cut = __unguarded_mid_partition(__first, __last, __pivot,
+ __comp);
+ else if (__comp(__a, __c))
+ __cut = __unguarded_nocopy_partition(__first, __last - 1,
+ __last - 1, __comp);
+ else
+ __cut = __unguarded_nocopy_partition(__first + 1, __last,
+ __first, __comp);
+ else if (__comp(__a, __c))
+ __cut = __unguarded_nocopy_partition(__first + 1, __last, __first,
+ __comp);
+ else if (__comp(__b, __c))
+ __cut = __unguarded_nocopy_partition(__first, __last - 1,
+ __last - 1, __comp);
+ else
+ __cut = __unguarded_mid_partition(__first, __last, __pivot, __comp);
+ return __cut;
+ }
+
/**
* @if maint
* This is a helper function for the sort routine.
@@ -2223,20 +2371,12 @@
}
--__depth_limit;
_RandomAccessIterator __cut =
- std::__unguarded_partition(__first, __last,
- _ValueType(std::__median(*__first,
- *(__first
- + (__last
- - __first)
- / 2),
- *(__last - 1),
- __comp)),
- __comp);
+ std::__introsort_partition(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
-
+
/**
* @brief Sort the elements of a sequence using a predicate for comparison.
* @param first An iterator.
@@ -2589,6 +2729,46 @@
__result));
}
+ // Varient of std::merge which moves rather than copies input
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator, typename _Compare>
+ _OutputIterator
+ __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result, _Compare __comp)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+ __glibcxx_function_requires(_SameTypeConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
+ typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+ __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+
+ while (__first1 != __last1 && __first2 != __last2)
+ {
+ if (__comp(*__first2, *__first1))
+ {
+ *__result = __gnu_cxx::__move(*__first2);
+ ++__first2;
+ }
+ else
+ {
+ *__result = __gnu_cxx::__move(*__first1);
+ ++__first1;
+ }
+ ++__result;
+ }
+ return std::__move(__first2, __last2, std::__move(__first1, __last1,
+ __result));
+ }
+
/**
* @brief Merges two sorted ranges.
* @param first1 An iterator.
@@ -2631,18 +2811,16 @@
while (__last - __first >= __two_step)
{
- __result = std::merge(__first, __first + __step_size,
- __first + __step_size, __first + __two_step,
- __result,
- __comp);
+ __result = std::__move_merge(__first, __first + __step_size,
+ __first + __step_size,
+ __first + __two_step, __result,
+ __comp);
__first += __two_step;
}
__step_size = std::min(_Distance(__last - __first), __step_size);
- std::merge(__first, __first + __step_size,
- __first + __step_size, __last,
- __result,
- __comp);
+ std::__move_merge(__first, __first + __step_size,
+ __first + __step_size, __last, __result, __comp);
}
enum { _S_chunk_size = 7 };
@@ -2703,25 +2881,25 @@
_Compare __comp)
{
if (__first1 == __last1)
- return std::copy_backward(__first2, __last2, __result);
+ return std::__move_backward(__first2, __last2, __result);
if (__first2 == __last2)
- return std::copy_backward(__first1, __last1, __result);
+ return std::__move_backward(__first1, __last1, __result);
--__last1;
--__last2;
while (true)
{
if (__comp(*__last2, *__last1))
{
- *--__result = *__last1;
+ *--__result = __gnu_cxx::__move(*__last1);
if (__first1 == __last1)
- return std::copy_backward(__first2, ++__last2, __result);
+ return std::__move_backward(__first2, ++__last2, __result);
--__last1;
}
else
{
- *--__result = *__last2;
+ *--__result = __gnu_cxx::__move(*__last2);
if (__first2 == __last2)
- return std::copy_backward(__first1, ++__last1, __result);
+ return std::__move_backward(__first1, ++__last1, __result);
--__last2;
}
}
@@ -2745,15 +2923,15 @@
_BidirectionalIterator2 __buffer_end;
if (__len1 > __len2 && __len2 <= __buffer_size)
{
- __buffer_end = std::copy(__middle, __last, __buffer);
- std::copy_backward(__first, __middle, __last);
- return std::copy(__buffer, __buffer_end, __first);
+ __buffer_end = std::__move(__middle, __last, __buffer);
+ std::__move_backward(__first, __middle, __last);
+ return std::__move(__buffer, __buffer_end, __first);
}
else if (__len1 <= __buffer_size)
{
- __buffer_end = std::copy(__first, __middle, __buffer);
- std::copy(__middle, __last, __first);
- return std::copy_backward(__buffer, __buffer_end, __last);
+ __buffer_end = std::__move(__first, __middle, __buffer);
+ std::__move(__middle, __last, __first);
+ return std::__move_backward(__buffer, __buffer_end, __last);
}
else
{
@@ -2780,12 +2958,13 @@
{
if (__len1 <= __len2 && __len1 <= __buffer_size)
{
- _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
- std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
+ _Pointer __buffer_end = std::__move(__first, __middle, __buffer);
+ std::__move_merge(__buffer, __buffer_end, __middle, __last,
+ __first, __comp);
}
else if (__len2 <= __buffer_size)
{
- _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
+ _Pointer __buffer_end = std::__move(__middle, __last, __buffer);
std::__merge_backward(__first, __middle, __buffer, __buffer_end,
__last, __comp);
}
@@ -3051,14 +3230,7 @@
while (__last - __first > 3)
{
_RandomAccessIterator __cut =
- std::__unguarded_partition(__first, __last,
- _ValueType(std::__median(*__first,
- *(__first
- + (__last
- - __first)
- / 2),
- *(__last - 1),
- __comp)), __comp);
+ __introsort_partition(__first, __last, __comp);
if (__cut <= __nth)
__first = __cut;
else
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_algobase.h libstdc++-v3/include/bits/stl_algobase.h
--- libstdc++-v3.so_7.clean/include/bits/stl_algobase.h 2005-05-25 13:38:47.000000000 +0100
+++ libstdc++-v3/include/bits/stl_algobase.h 2005-05-25 17:09:55.000000000 +0100
@@ -381,6 +381,33 @@
return std::__copy_normal<__in, __out>::copy_n(__first, __last,
__result);
}
+
+ template<typename _InputIterator, typename _OutputIterator>
+ inline typename __enable_if<_OutputIterator,
+ __gnu_cxx::__is_moveable<
+ typename iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_OutputIterator>::value_type>
+ ::__value>::__type
+ __move(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ {
+ for(; __first != __last; ++__result, ++__first)
+ *__result = __gnu_cxx::__move(*__first);
+ return __result;
+ }
+
+ template<typename _InputIterator, typename _OutputIterator>
+ inline typename __enable_if<_OutputIterator,
+ !(__gnu_cxx::__is_moveable<
+ typename iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_OutputIterator>::value_type>
+ ::__value)>::__type
+ __move(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ { return std::copy(__first, __last, __result); }
+
template<bool, typename>
struct __copy_backward
@@ -512,6 +539,34 @@
__result);
}
+ template<typename _InputIterator, typename _OutputIterator>
+ inline
+ typename __enable_if<_OutputIterator,
+ __gnu_cxx::__is_moveable<
+ typename iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_OutputIterator>::value_type>
+ ::__value>::__type
+ __move_backward(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ {
+ while (__first != __last)
+ *--__result = __gnu_cxx::__move(*--__last);
+ return __result;
+ }
+
+ template<typename _InputIterator, typename _OutputIterator>
+ inline
+ typename __enable_if<_OutputIterator,
+ !(__gnu_cxx::__is_moveable<
+ typename iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_OutputIterator>::value_type>
+ ::__value)>::__type
+ __move_backward(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ { return std::copy_backward(__first, __last, __result); }
+
template<bool>
struct __fill
{
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_tempbuf.h libstdc++-v3/include/bits/stl_tempbuf.h
--- libstdc++-v3.so_7.clean/include/bits/stl_tempbuf.h 2005-02-01 16:07:12.000000000 +0000
+++ libstdc++-v3/include/bits/stl_tempbuf.h 2005-05-27 17:43:59.000000000 +0100
@@ -65,6 +65,36 @@
namespace std
{
+
+ template<bool __moveable, bool __trivial>
+ struct __initialize_temporary_buffer
+ {
+ template<typename _Tp>
+ static void
+ __fun(const _Tp& val, _Tp* _M_buffer, ptrdiff_t _M_len)
+ { std::uninitialized_fill_n(_M_buffer, _M_len, val); }
+ };
+
+ // We can't normally assume the existance of a default constructor, but
+ // all the moveable types have one.
+ template<>
+ struct __initialize_temporary_buffer<true, false>
+ {
+ template<typename _Tp>
+ static void
+ __fun(const _Tp& val, _Tp* _M_buffer, ptrdiff_t _M_len)
+ { std::__uninitialized_fill_n(_M_buffer, _M_len); }
+ };
+
+ template<bool __moveable>
+ struct __initialize_temporary_buffer<__moveable, true>
+ {
+ template<typename _Tp>
+ static void
+ __fun(const _Tp& val, _Tp* _M_buffer, ptrdiff_t _M_len)
+ { }
+ };
+
/**
* @if maint
* This class is used in two places: stl_algo.h and ext/memory,
@@ -89,13 +119,6 @@
size_type _M_len;
pointer _M_buffer;
- void
- _M_initialize_buffer(const _Tp&, __true_type) { }
-
- void
- _M_initialize_buffer(const _Tp& val, __false_type)
- { std::uninitialized_fill_n(_M_buffer, _M_len, val); }
-
public:
/// As per Table mumble.
size_type
@@ -144,9 +167,6 @@
: _M_original_len(std::distance(__first, __last)),
_M_len(0), _M_buffer(0)
{
- // Workaround for a __type_traits bug in the pre-7.3 compiler.
- typedef typename std::__is_scalar<_Tp>::__type _Trivial;
-
try
{
pair<pointer, size_type> __p(get_temporary_buffer<
@@ -154,7 +174,9 @@
_M_buffer = __p.first;
_M_len = __p.second;
if (_M_len > 0)
- _M_initialize_buffer(*__first, _Trivial());
+ __initialize_temporary_buffer<__gnu_cxx::__is_moveable<_Tp>::value,
+ std::__is_scalar<_Tp>::__value>::
+ __fun(*__first,_M_buffer, _M_len);
}
catch(...)
{
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_uninitialized.h libstdc++-v3/include/bits/stl_uninitialized.h
--- libstdc++-v3.so_7.clean/include/bits/stl_uninitialized.h 2005-02-01 16:07:14.000000000 +0000
+++ libstdc++-v3/include/bits/stl_uninitialized.h 2005-05-25 00:25:20.000000000 +0100
@@ -218,6 +218,25 @@
std::__uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}
+ // Specialised version of uninitialized_fill_n for default construction.
+ template<typename _ForwardIterator, typename _Size>
+ inline void
+ __uninitialized_fill_n(_ForwardIterator __first, _Size __n)
+ {
+ typedef typename iterator_traits<_ForwardIterator>::value_type _Tp;
+ _ForwardIterator __cur = __first;
+ try
+ {
+ for (; __n > 0; --__n, ++__cur)
+ std::_Construct(&*__cur);
+ }
+ catch(...)
+ {
+ std::_Destroy(__first, __cur);
+ __throw_exception_again;
+ }
+ }
+
// Extensions: versions of uninitialized_copy, uninitialized_fill,
// and uninitialized_fill_n that take an allocator parameter.
// We dispatch back to the standard versions when we're given the
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/inplace_merge/moveable.cc libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/inplace_merge/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable.cc 2005-05-24 22:32:52.000000000 +0100
@@ -0,0 +1,52 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.4 [lib.alg.merge]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::bidirectional_iterator_wrapper;
+using std::inplace_merge;
+using __gnu_test::rvalstruct;
+
+typedef test_container<rvalstruct, bidirectional_iterator_wrapper> container;
+
+void
+test1()
+{
+ int intarray[]={0,2,4,1,3,5};
+ rvalstruct array[6];
+ std::copy(intarray, intarray + 6, array);
+ container con(array, array + 6);
+ inplace_merge(con.begin(), con.it(3), con.end());
+ for(int i = 0; i < 6; ++i)
+ VERIFY(array[i].val == i && array[i].valid);
+}
+
+int
+main()
+{
+ test1();
+ return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/nth_element/moveable.cc libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/nth_element/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc 2005-05-24 22:51:23.000000000 +0100
@@ -0,0 +1,73 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.2 [lib.alg.nth.element]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using std::nth_element;
+using __gnu_test::rvalstruct;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+void
+test1()
+{
+ int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array, array + 7);
+ nth_element(con.begin(), con.it(3), con.end());
+ for(int i = 0; i < 3; ++i)
+ VERIFY(array[i].val < 3);
+ for(int i = 4; i < 7; ++i)
+ VERIFY(array[i].val > 3);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+void
+test2()
+{
+ int intarray[] = {0, 6, 1, 5, 2, 4, 3};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array,array + 7);
+ nth_element(con.begin(), con.it(3), con.end());
+ for(int i = 0; i < 3; ++i)
+ VERIFY(array[i].val < 3);
+ for(int i = 4; i < 7; ++i)
+ VERIFY(array[i].val > 3);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+int
+main()
+{
+ test1();
+ test2();
+ return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/partial_sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/partial_sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/partial_sort/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partial_sort/moveable.cc 2005-05-22 12:00:46.000000000 +0100
@@ -0,0 +1,67 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.3 [lib.partial.sort]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::partial_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+void
+test1()
+{
+ int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array, array + 7);
+ partial_sort(con.begin(), con.it(3), con.end());
+ VERIFY(array[0].val == 0 && array[1].val == 1 && array[2].val == 2);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+void
+test2()
+{
+ int intarray[] = {0, 6, 1, 5, 2, 4, 3};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array,array + 7);
+ partial_sort(con.begin(), con.it(3), con.end());
+ VERIFY(array[0].val == 0 && array[1].val == 1 && array[2].val == 2);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+int
+main()
+{
+ test1();
+ test2();
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/partition/moveable.cc libstdc++-v3/testsuite/25_algorithms/partition/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/partition/moveable.cc 2005-05-20 16:08:39.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partition/moveable.cc 2005-05-22 19:45:01.000000000 +0100
@@ -73,9 +73,24 @@
for (const rvalstruct* i = barray+N/2; i < barray + N; ++i) VERIFY(!pred(*i));
}
+// 25.2.12 stable_partition()
+void
+test02()
+{
+ using std::stable_partition;
+
+ rvalstruct s1[N];
+ std::copy(A, A + N, s1);
+ Fcontainer fcon(s1, s1 + N);
+ stable_partition(fcon.begin(), fcon.end(), Pred());
+ for(int i = 0; i < N; ++i)
+ VERIFY(s1[i].valid && s1[i].val == B[i]);
+}
+
int
main()
{
test01();
+ test02();
return 0;
}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort/moveable.cc 2005-05-22 12:41:24.000000000 +0100
@@ -0,0 +1,61 @@
+// Copyright (C) 2001 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1 algorithms, sort()
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+bool test __attribute__((unused)) = true;
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::partial_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+
+const int A[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7,
+ 17, 8, 18, 9, 19};
+const int N = sizeof(A) / sizeof(int);
+
+// 25.3.1.1 sort()
+void
+test01()
+{
+ rvalstruct s1[N];
+ std::copy(A, A + N, s1);
+ Container con(s1, s1 + N);
+ std::sort(con.begin(), con.end());
+ VERIFY(s1[0].valid);
+ for(int i = 1; i < N; ++i)
+ VERIFY(s1[i].val>s1[i-1].val && s1[i].valid);
+}
+
+int
+main()
+{
+ test01();
+ return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/sort.cc libstdc++-v3/testsuite/25_algorithms/sort/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/sort.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort/sort.cc 2005-05-23 15:16:24.000000000 +0100
@@ -0,0 +1,171 @@
+// Copyright (C) 2001 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1 algorithms, sort()
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
+const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
+const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
+const int N = sizeof(A) / sizeof(int);
+const int logN = 3; // ln(N) rounded up
+const int P = 7;
+
+// comparison predicate for stable_sort: order by rightmost digit
+struct CompLast
+{
+ bool
+ operator()(const int x, const int y)
+ { return x % 10 < y % 10; }
+};
+
+// This functor has the equivalent functionality of std::geater<>,
+// but there is no dependency on <functional> and it also tracks the
+// number of invocations since creation.
+class Gt
+{
+public:
+ static int count() { return itsCount; }
+ static void reset() { itsCount = 0; }
+
+ bool
+ operator()(const int& x, const int& y)
+ {
+ ++itsCount;
+ return x > y;
+ }
+
+private:
+ static int itsCount;
+};
+
+int Gt::itsCount = 0;
+
+
+// 25.3.1.1 sort()
+void
+test01()
+{
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ std::sort(s1, s1 + N);
+ VERIFY(std::equal(s1, s1 + N, A));
+
+ Gt gt;
+ gt.reset();
+ std::sort(s1, s1 + N, gt);
+ VERIFY(std::equal(s1, s1 + N, C));
+}
+
+// 25.3.1.2 stable_sort()
+void
+test02()
+{
+ int s1[N];
+ std::copy(A, A + N, s1);
+ VERIFY(std::equal(s1, s1 + N, A));
+
+ std::stable_sort(s1, s1 + N, CompLast());
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ std::stable_sort(s1, s1 + N);
+ VERIFY(std::equal(s1, s1 + N, A));
+
+ Gt gt;
+ gt.reset();
+ std::stable_sort(s1, s1 + N, gt);
+ VERIFY(std::equal(s1, s1 + N, C));
+ VERIFY(gt.count() <= N * logN * logN);
+}
+
+// 25.3.1.3 partial_sort()
+void
+test03()
+{
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ std::partial_sort(s1, s1 + P, s1 + N);
+ VERIFY(std::equal(s1, s1 + P, A));
+
+ Gt gt;
+ gt.reset();
+ std::partial_sort(s1, s1 + P, s1 + N, gt);
+ VERIFY(std::equal(s1, s1 + P, C));
+}
+
+// 25.3.1.4 partial_sort_copy()
+void
+test04()
+{
+ using std::partial_sort_copy;
+
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ int s2[2*N];
+
+ partial_sort_copy(s1, s1 + N, s2, s2 + P);
+ VERIFY(std::equal(s2, s2 + P, A));
+
+ Gt gt;
+ gt.reset();
+ partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
+ VERIFY(std::equal(s2, s2 + P, C));
+
+ VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
+}
+
+// 25.3.2 nth_element()
+void
+test05()
+{
+ using std::nth_element;
+
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ int* pn = s1 + (N / 2) - 1;
+ nth_element(s1, pn, s1 + N);
+ for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
+
+ CompLast pred;
+ nth_element(s1, pn, s1 + N, pred);
+ for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+
+ return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort.cc libstdc++-v3/testsuite/25_algorithms/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort.cc 2003-09-23 21:02:52.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort.cc 1970-01-01 01:00:00.000000000 +0100
@@ -1,171 +0,0 @@
-// Copyright (C) 2001 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library. This library is free
-// software; you can redistribute it and/or modify it under the
-// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 2, or (at your option)
-// any later version.
-
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-// GNU General Public License for more details.
-
-// You should have received a copy of the GNU General Public License along
-// with this library; see the file COPYING. If not, write to the Free
-// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-// 25.3.1 algorithms, sort()
-
-#include <algorithm>
-#include <testsuite_hooks.h>
-
-bool test __attribute__((unused)) = true;
-
-const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
-const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
-const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
-const int N = sizeof(A) / sizeof(int);
-const int logN = 3; // ln(N) rounded up
-const int P = 7;
-
-// comparison predicate for stable_sort: order by rightmost digit
-struct CompLast
-{
- bool
- operator()(const int x, const int y)
- { return x % 10 < y % 10; }
-};
-
-// This functor has the equivalent functionality of std::geater<>,
-// but there is no dependency on <functional> and it also tracks the
-// number of invocations since creation.
-class Gt
-{
-public:
- static int count() { return itsCount; }
- static void reset() { itsCount = 0; }
-
- bool
- operator()(const int& x, const int& y)
- {
- ++itsCount;
- return x > y;
- }
-
-private:
- static int itsCount;
-};
-
-int Gt::itsCount = 0;
-
-
-// 25.3.1.1 sort()
-void
-test01()
-{
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- std::sort(s1, s1 + N);
- VERIFY(std::equal(s1, s1 + N, A));
-
- Gt gt;
- gt.reset();
- std::sort(s1, s1 + N, gt);
- VERIFY(std::equal(s1, s1 + N, C));
-}
-
-// 25.3.1.2 stable_sort()
-void
-test02()
-{
- int s1[N];
- std::copy(A, A + N, s1);
- VERIFY(std::equal(s1, s1 + N, A));
-
- std::stable_sort(s1, s1 + N, CompLast());
- VERIFY(std::equal(s1, s1 + N, B));
-
- std::stable_sort(s1, s1 + N);
- VERIFY(std::equal(s1, s1 + N, A));
-
- Gt gt;
- gt.reset();
- std::stable_sort(s1, s1 + N, gt);
- VERIFY(std::equal(s1, s1 + N, C));
- VERIFY(gt.count() <= N * logN * logN);
-}
-
-// 25.3.1.3 partial_sort()
-void
-test03()
-{
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- std::partial_sort(s1, s1 + P, s1 + N);
- VERIFY(std::equal(s1, s1 + P, A));
-
- Gt gt;
- gt.reset();
- std::partial_sort(s1, s1 + P, s1 + N, gt);
- VERIFY(std::equal(s1, s1 + P, C));
-}
-
-// 25.3.1.4 partial_sort_copy()
-void
-test04()
-{
- using std::partial_sort_copy;
-
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- int s2[2*N];
-
- partial_sort_copy(s1, s1 + N, s2, s2 + P);
- VERIFY(std::equal(s2, s2 + P, A));
-
- Gt gt;
- gt.reset();
- partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
- VERIFY(std::equal(s2, s2 + P, C));
-
- VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
-}
-
-// 25.3.2 nth_element()
-void
-test05()
-{
- using std::nth_element;
-
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- int* pn = s1 + (N / 2) - 1;
- nth_element(s1, pn, s1 + N);
- for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
-
- CompLast pred;
- nth_element(s1, pn, s1 + N, pred);
- for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
-}
-
-int
-main()
-{
- test01();
- test02();
- test03();
- test04();
- test05();
-
- return 0;
-}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/stable_sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/stable_sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/stable_sort/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/stable_sort/moveable.cc 2005-05-24 09:51:16.000000000 +0100
@@ -0,0 +1,54 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.2 [lib.stable.sort]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::stable_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+
+
+void
+test1()
+{
+ int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array, array + 7);
+ stable_sort(con.begin(), con.end());
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].val == i && array[i].valid);
+}
+
+
+int
+main()
+{
+ test1();
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/performance/25_algorithms/sort.cc libstdc++-v3/testsuite/performance/25_algorithms/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/performance/25_algorithms/sort.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/performance/25_algorithms/sort.cc 2005-05-28 11:28:50.000000000 +0100
@@ -0,0 +1,227 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+
+#define DISABLE_ITERATOR_DEBUG
+
+#include<vector>
+#include<algorithm>
+#include<stdio.h>
+#include<string>
+#include<sstream>
+
+#include<testsuite_performance.h>
+#include<testsuite_iterators.h>
+
+using namespace std;
+using namespace __gnu_test;
+
+// Used to stop move symantics
+struct vec_wrap
+{
+ vector<int> v;
+
+ explicit vec_wrap(vector<int> in_vec) : v(in_vec)
+ { }
+
+ vec_wrap()
+ { }
+};
+
+bool inline
+operator<(const vec_wrap& lhs, const vec_wrap& rhs)
+{ return lhs.v == rhs.v; }
+
+
+// Used to perform the move symantics algorithm on an int
+struct int_wrap
+{
+ int i;
+
+ explicit int_wrap(int in_val) : i(in_val)
+ { }
+
+ int_wrap(__gnu_cxx::__rvalref<int_wrap> in) : i(in.__ref.i)
+ { }
+
+ void
+ operator=(int in)
+ { i = in; }
+
+ void
+ operator=(__gnu_cxx::__rvalref<int_wrap> in)
+ { i = in.__ref.i; }
+
+ int_wrap()
+ { }
+};
+
+struct ptr_wrap
+{
+ vector<int>* ptr;
+ ptr_wrap(vector<int>* in_ptr) : ptr(in_ptr)
+ { }
+};
+
+bool inline
+operator<(ptr_wrap lhs, ptr_wrap rhs)
+{ return *(lhs.ptr) < *(rhs.ptr); }
+
+bool inline
+operator<(const int_wrap& lhs, const int_wrap& rhs)
+{ return lhs.i < rhs.i; }
+
+namespace __gnu_cxx
+{
+ template<>
+ struct __is_moveable<int_wrap>
+ { static const bool value = true; };
+}
+
+struct
+dereference_compare
+{
+ template<typename T>
+ bool operator()(T lhs, T rhs)
+ { return *lhs < *rhs; }
+};
+
+template<typename T>
+void sort_and_output(T& vec, std::string description)
+{
+ time_counter time;
+ resource_counter resource;
+ start_counters(time, resource);
+ std::sort(vec.begin(), vec.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, description.c_str(), time, resource);
+ clear_counters(time, resource);
+
+}
+
+void
+test1(int vec_length, vector<int> sort_vec, string vec_description)
+{
+ vector<vector<int> > moveable_vecs;
+ for(int i = 0; i < sort_vec.size(); i++)
+ {
+ vector<int> vec(vec_length, sort_vec[i]);
+ moveable_vecs.push_back(vec);
+ }
+ ostringstream outputline;
+ outputline << "moveable vector - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(moveable_vecs, outputline.str());
+}
+
+
+void
+test2(int vec_length, vector<int> sort_vec, string vec_description )
+{
+ vector<vec_wrap> unmoveable_vecs;
+ for(int i = 0; i < sort_vec.size(); i++)
+ {
+ vector<int> vec(vec_length, sort_vec[i]);
+ vec_wrap wrap(vec);
+ unmoveable_vecs.push_back(wrap);
+ }
+ ostringstream outputline;
+ outputline << "unmoveable vector - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(unmoveable_vecs, outputline.str());
+}
+
+
+void
+test3(int vec_length, vector<int> sort_vec, string vec_description)
+{
+ vector<vector<int> > primary_vec;
+ vector<ptr_wrap> ptr_vec;
+ for(int i = 0; i < sort_vec.size(); i++)
+ {
+ vector<int> vec(vec_length, sort_vec[i]);
+ primary_vec.push_back(vec);
+ }
+ for(int i = 0; i < sort_vec.size(); i++)
+ ptr_vec.push_back(&primary_vec[i]);
+ ostringstream outputline;
+ outputline << "pointers to vector - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(ptr_vec, outputline.str());
+}
+
+
+void
+test4(vector<int> sort_vec, string vec_description)
+{
+ ostringstream outputline;
+ outputline << "ints - length " << sort_vec.size() << ":" << vec_description;
+ sort_and_output(sort_vec, outputline.str());
+}
+
+void
+test5(vector<int> sort_vec, string vec_description)
+{
+ vector<int_wrap> moveable_int_vec(sort_vec.size());
+ copy(sort_vec.begin(), sort_vec.end(), moveable_int_vec.begin());
+ ostringstream outputline;
+ outputline << "moveable ints - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(moveable_int_vec, outputline.str());
+}
+
+int
+main(void)
+{
+ for(int length = 100000; length < 1000001; length*=10)
+ {
+ vector<int> sort_vec;
+ int val = 1000;
+ for(int i = 0; i < length; ++i)
+ {
+ val = (val * 88888) % 1000003;
+ sort_vec.push_back(val);
+ }
+ test1(1000000/length, sort_vec, "random vector");
+ test2(1000000/length, sort_vec, "random vector");
+ test3(1000000/length, sort_vec, "random vector");
+
+ }
+
+ for(int length = 1000000; length < 10000001; length*=10)
+ {
+ vector<int> sort_vec;
+ int val = 1000;
+ for(int i = 0; i < length; ++i)
+ {
+ val = (val * 88888) % 1000003;
+ sort_vec.push_back(val);
+ }
+ test4(sort_vec, "random vector");
+ test5(sort_vec, "random vector");
+ }
+}