This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[v3] Remove algos code duplication
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Sun, 25 Mar 2012 21:28:57 +0200
- Subject: [v3] Remove algos code duplication
Hi
Here is a patch proposal to remove the duplication of the
implementation details of many algos thanks to usage of lambdas in C++
11 mode. This is what has been experimented in libstdcxx_so_7 branch but
abandonned, lambdas are the real answer to this problem.
2012-03-22 François Dumont <fdumont@gcc.gnu.org>
* include/bits/stl_algo.h: Hide in C++ 11 mode implementation
details made useless thanks to usage of lambdas.
(__find_if_not): Remove.
* include/bits/stl_heap.h: Likewise.
Tested undex linux x86_64 with
make check
and
make CXXFLAGS=-std=gnu++11 check
There are some errors building the testsuite entirely in C++11 mode but
none coming from this patch.
Are you interested ?
François
Index: include/bits/stl_heap.h
===================================================================
--- include/bits/stl_heap.h (revision 185750)
+++ include/bits/stl_heap.h (working copy)
@@ -68,6 +68,7 @@
* @ingroup sorting_algorithms
*/
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator, typename _Distance>
_Distance
__is_heap_until(_RandomAccessIterator __first, _Distance __n)
@@ -82,6 +83,7 @@
}
return __n;
}
+#endif
template<typename _RandomAccessIterator, typename _Distance,
typename _Compare>
@@ -105,8 +107,21 @@
template<typename _RandomAccessIterator, typename _Distance>
inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
- { return std::__is_heap_until(__first, __n) == __n; }
+ {
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+#endif
+ return std::__is_heap_until(__first, __n
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ ) == __n;
+ }
+
template<typename _RandomAccessIterator, typename _Compare,
typename _Distance>
inline bool
@@ -127,6 +142,7 @@
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
// + is_heap and is_heap_until in C++0x.
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
void
__push_heap(_RandomAccessIterator __first,
@@ -141,7 +157,25 @@
}
*(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
}
+#endif
+ template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
+ typename _Compare>
+ void
+ __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
+ _Distance __topIndex, _Tp __value, _Compare __comp)
+ {
+ _Distance __parent = (__holeIndex - 1) / 2;
+ while (__holeIndex > __topIndex
+ && __comp(*(__first + __parent), __value))
+ {
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
+ __holeIndex = __parent;
+ __parent = (__holeIndex - 1) / 2;
+ }
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
+ }
+
/**
* @brief Push an element onto a heap.
* @param __first Start of heap.
@@ -170,26 +204,14 @@
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value));
+ _DistanceType(0), _GLIBCXX_MOVE(__value)
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs, const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
}
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
- typename _Compare>
- void
- __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __topIndex, _Tp __value, _Compare __comp)
- {
- _Distance __parent = (__holeIndex - 1) / 2;
- while (__holeIndex > __topIndex
- && __comp(*(__first + __parent), __value))
- {
- *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
- __holeIndex = __parent;
- __parent = (__holeIndex - 1) / 2;
- }
- *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
- }
-
/**
* @brief Push an element onto a heap using comparison functor.
* @param __first Start of heap.
@@ -223,6 +245,7 @@
_DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
@@ -248,7 +271,37 @@
std::__push_heap(__first, __holeIndex, __topIndex,
_GLIBCXX_MOVE(__value));
}
+#endif
+ template<typename _RandomAccessIterator, typename _Distance,
+ typename _Tp, typename _Compare>
+ void
+ __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
+ _Distance __len, _Tp __value, _Compare __comp)
+ {
+ const _Distance __topIndex = __holeIndex;
+ _Distance __secondChild = __holeIndex;
+ while (__secondChild < (__len - 1) / 2)
+ {
+ __secondChild = 2 * (__secondChild + 1);
+ if (__comp(*(__first + __secondChild),
+ *(__first + (__secondChild - 1))))
+ __secondChild--;
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
+ __holeIndex = __secondChild;
+ }
+ if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
+ {
+ __secondChild = 2 * (__secondChild + 1);
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
+ + (__secondChild - 1)));
+ __holeIndex = __secondChild - 1;
+ }
+ std::__push_heap(__first, __holeIndex, __topIndex,
+ _GLIBCXX_MOVE(__value), __comp);
+ }
+
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
@@ -265,7 +318,25 @@
_DistanceType(__last - __first),
_GLIBCXX_MOVE(__value));
}
+#endif
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline void
+ __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _RandomAccessIterator __result, _Compare __comp)
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
+
+ _ValueType __value = _GLIBCXX_MOVE(*__result);
+ *__result = _GLIBCXX_MOVE(*__first);
+ std::__adjust_heap(__first, _DistanceType(0),
+ _DistanceType(__last - __first),
+ _GLIBCXX_MOVE(__value), __comp);
+ }
+
/**
* @brief Pop an element off a heap.
* @param __first Start of heap.
@@ -293,54 +364,14 @@
__glibcxx_requires_heap(__first, __last);
--__last;
- std::__pop_heap(__first, __last, __last);
+ std::__pop_heap(__first, __last, __last
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs, const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
}
- template<typename _RandomAccessIterator, typename _Distance,
- typename _Tp, typename _Compare>
- void
- __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __len, _Tp __value, _Compare __comp)
- {
- const _Distance __topIndex = __holeIndex;
- _Distance __secondChild = __holeIndex;
- while (__secondChild < (__len - 1) / 2)
- {
- __secondChild = 2 * (__secondChild + 1);
- if (__comp(*(__first + __secondChild),
- *(__first + (__secondChild - 1))))
- __secondChild--;
- *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
- __holeIndex = __secondChild;
- }
- if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
- {
- __secondChild = 2 * (__secondChild + 1);
- *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
- + (__secondChild - 1)));
- __holeIndex = __secondChild - 1;
- }
- std::__push_heap(__first, __holeIndex, __topIndex,
- _GLIBCXX_MOVE(__value), __comp);
- }
-
- template<typename _RandomAccessIterator, typename _Compare>
- inline void
- __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result, _Compare __comp)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
-
- _ValueType __value = _GLIBCXX_MOVE(*__result);
- *__result = _GLIBCXX_MOVE(*__first);
- std::__adjust_heap(__first, _DistanceType(0),
- _DistanceType(__last - __first),
- _GLIBCXX_MOVE(__value), __comp);
- }
-
/**
* @brief Pop an element off a heap using comparison functor.
* @param __first Start of heap.
@@ -399,7 +430,13 @@
while (true)
{
_ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
- std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
+ std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value)
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
if (__parent == 0)
return;
__parent--;
@@ -459,18 +496,25 @@
void
sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIterator>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap(__first, __last);
while (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last);
+ std::__pop_heap(__first, __last, __last
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs, const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
}
}
@@ -517,15 +561,20 @@
inline _RandomAccessIterator
is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIterator>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
- return __first + std::__is_heap_until(__first, std::distance(__first,
- __last));
+ return __first + std::__is_heap_until(__first,
+ std::distance(__first, __last),
+ [](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; });
}
/**
@@ -549,8 +598,8 @@
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
- return __first + std::__is_heap_until(__first, std::distance(__first,
- __last),
+ return __first + std::__is_heap_until(__first,
+ std::distance(__first, __last),
__comp);
}
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 185750)
+++ include/bits/stl_algo.h (working copy)
@@ -74,6 +74,7 @@
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// Swaps the median value of *__a, *__b and *__c to *__a
template<typename _Iterator>
void
@@ -97,6 +98,7 @@
else
std::iter_swap(__a, __b);
}
+#endif
/// Swaps the median value of *__a, *__b and *__c under __comp to *__a
template<typename _Iterator, typename _Compare>
@@ -126,6 +128,7 @@
// for_each
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is an overload used by find() for the Input Iterator case.
template<typename _InputIterator, typename _Tp>
inline _InputIterator
@@ -136,6 +139,7 @@
++__first;
return __first;
}
+#endif
/// This is an overload used by find_if() for the Input Iterator case.
template<typename _InputIterator, typename _Predicate>
@@ -148,6 +152,7 @@
return __first;
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is an overload used by find() for the RAI case.
template<typename _RandomAccessIterator, typename _Tp>
_RandomAccessIterator
@@ -195,6 +200,7 @@
return __last;
}
}
+#endif
/// This is an overload used by find_if() for the RAI case.
template<typename _RandomAccessIterator, typename _Predicate>
@@ -244,67 +250,6 @@
}
}
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
- /// This is an overload used by find_if_not() for the Input Iterator case.
- template<typename _InputIterator, typename _Predicate>
- inline _InputIterator
- __find_if_not(_InputIterator __first, _InputIterator __last,
- _Predicate __pred, input_iterator_tag)
- {
- while (__first != __last && bool(__pred(*__first)))
- ++__first;
- return __first;
- }
-
- /// This is an overload used by find_if_not() for the RAI case.
- template<typename _RandomAccessIterator, typename _Predicate>
- _RandomAccessIterator
- __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Predicate __pred, random_access_iterator_tag)
- {
- typename iterator_traits<_RandomAccessIterator>::difference_type
- __trip_count = (__last - __first) >> 2;
-
- for (; __trip_count > 0; --__trip_count)
- {
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
-
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
-
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
-
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- }
-
- switch (__last - __first)
- {
- case 3:
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- case 2:
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- case 1:
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- case 0:
- default:
- return __last;
- }
- }
-#endif
-
// set_difference
// set_intersection
// set_symmetric_difference
@@ -318,6 +263,7 @@
// count_if
// search
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/**
* This is an uglified
* search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
@@ -399,6 +345,7 @@
__tailSize -= __remainder;
}
}
+#endif
// search_n
@@ -493,6 +440,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
// find_end for forward iterators.
template<typename _ForwardIterator1, typename _ForwardIterator2>
_ForwardIterator1
@@ -520,6 +468,7 @@
}
}
}
+#endif
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
@@ -551,6 +500,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
// find_end for bidirectional iterators (much faster).
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
_BidirectionalIterator1
@@ -585,6 +535,7 @@
return __result;
}
}
+#endif
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _BinaryPredicate>
@@ -652,18 +603,24 @@
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
+ typedef typename iterator_traits<_ForwardIterator1>::value_type _ValType1;
+ typedef typename iterator_traits<_ForwardIterator2>::value_type _ValType2;
+
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_ForwardIterator1>::value_type,
- typename iterator_traits<_ForwardIterator2>::value_type>)
+ __glibcxx_function_requires(_EqualOpConcept<_ValType1, _ValType2>)
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
return std::__find_end(__first1, __last1, __first2, __last2,
std::__iterator_category(__first1),
- std::__iterator_category(__first2));
+ std::__iterator_category(__first2)
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValType1& __v1, const _ValType2& __v2)
+ { return __v1 == __v2; }
+#endif
+ );
}
/**
@@ -784,13 +741,17 @@
find_if_not(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
{
+ typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
+
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
- typename iterator_traits<_InputIterator>::value_type>)
+ _ValueType>)
__glibcxx_requires_valid_range(__first, __last);
- return std::__find_if_not(__first, __last, __pred,
- std::__iterator_category(__first));
+ return std::__find_if(__first, __last,
+ [&__pred](const _ValueType& __x)
+ { return !bool(__pred(__x)); },
+ std::__iterator_category(__first));
}
/**
@@ -1242,6 +1203,7 @@
return ++__dest;
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/**
* This is an uglified unique_copy(_InputIterator, _InputIterator,
* _OutputIterator)
@@ -1306,6 +1268,7 @@
*++__result = *__first;
return ++__result;
}
+#endif
/**
* This is an uglified
@@ -1906,6 +1869,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the sort routines.
template<typename _RandomAccessIterator>
void
@@ -1918,6 +1882,7 @@
if (*__i < *__first)
std::__pop_heap(__first, __middle, __i);
}
+#endif
/// This is a helper function for the sort routines.
template<typename _RandomAccessIterator, typename _Compare>
@@ -1991,7 +1956,13 @@
std::__adjust_heap(__result_first, _DistanceType(0),
_DistanceType(__result_real_last
- __result_first),
- _InputValueType(*__first));
+ _InputValueType(*__first)
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _OutputValueType& __lhs,
+ const _OutputValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
++__first;
}
std::sort_heap(__result_first, __result_real_last);
@@ -2069,6 +2040,7 @@
return __result_real_last;
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator>
void
@@ -2086,6 +2058,7 @@
}
*__last = _GLIBCXX_MOVE(__val);
}
+#endif
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
@@ -2106,6 +2079,7 @@
*__last = _GLIBCXX_MOVE(__val);
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator>
void
@@ -2128,6 +2102,7 @@
std::__unguarded_linear_insert(__i);
}
}
+#endif
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
@@ -2151,6 +2126,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator>
inline void
@@ -2163,6 +2139,7 @@
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i);
}
+#endif
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
@@ -2183,6 +2160,7 @@
*/
enum { _S_threshold = 16 };
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator>
void
@@ -2197,6 +2175,7 @@
else
std::__insertion_sort(__first, __last);
}
+#endif
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
@@ -2214,6 +2193,7 @@
std::__insertion_sort(__first, __last, __comp);
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Tp>
_RandomAccessIterator
@@ -2233,6 +2213,7 @@
++__first;
}
}
+#endif
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
@@ -2255,6 +2236,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function...
template<typename _RandomAccessIterator>
inline _RandomAccessIterator
@@ -2265,6 +2247,7 @@
std::__move_median_first(__first, __mid, (__last - 1));
return std::__unguarded_partition(__first + 1, __last, *__first);
}
+#endif
/// This is a helper function...
@@ -2278,6 +2261,7 @@
return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size>
void
@@ -2299,6 +2283,7 @@
__last = __cut;
}
}
+#endif
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
@@ -2324,6 +2309,7 @@
// sort
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator, typename _Size>
void
__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
@@ -2352,6 +2338,7 @@
}
std::__insertion_sort(__first, __last);
}
+#endif
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
@@ -2730,6 +2717,7 @@
// merge
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the __merge_adaptive routines.
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
@@ -2755,6 +2743,7 @@
if (__first1 != __last1)
_GLIBCXX_MOVE3(__first1, __last1, __result);
}
+#endif
/// This is a helper function for the __merge_adaptive routines.
template<typename _InputIterator1, typename _InputIterator2,
@@ -2782,6 +2771,7 @@
_GLIBCXX_MOVE3(__first1, __last1, __result);
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the __merge_adaptive routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _BidirectionalIterator3>
@@ -2823,6 +2813,7 @@
}
}
}
+#endif
/// This is a helper function for the __merge_adaptive routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
@@ -2909,6 +2900,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
typename _Pointer>
@@ -2964,6 +2956,7 @@
__len2 - __len22, __buffer, __buffer_size);
}
}
+#endif
/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
@@ -3023,6 +3016,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance>
void
@@ -3065,6 +3059,7 @@
std::__merge_without_buffer(__new_middle, __second_cut, __last,
__len1 - __len11, __len2 - __len22);
}
+#endif
/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
@@ -3158,10 +3153,22 @@
_Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
__last);
if (__buf.begin() == 0)
- std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
+ std::__merge_without_buffer(__first, __middle, __last, __len1, __len2
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ , [](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
else
std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
- __buf.begin(), _DistanceType(__buf.size()));
+ __buf.begin(), _DistanceType(__buf.size())
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ , [](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+);
}
/**
@@ -3224,6 +3231,7 @@
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the __merge_sort_loop routines.
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
@@ -3250,6 +3258,7 @@
_GLIBCXX_MOVE3(__first1, __last1,
__result));
}
+#endif
/// This is a helper function for the __merge_sort_loop routines.
template<typename _InputIterator1, typename _InputIterator2,
@@ -3278,6 +3287,7 @@
__result));
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
typename _Distance>
void
@@ -3300,6 +3310,7 @@
std::__move_merge(__first, __first + __step_size,
__first + __step_size, __last, __result);
}
+#endif
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
typename _Distance, typename _Compare>
@@ -3325,6 +3336,7 @@
__first + __step_size, __last, __result, __comp);
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator, typename _Distance>
void
__chunk_insertion_sort(_RandomAccessIterator __first,
@@ -3338,6 +3350,7 @@
}
std::__insertion_sort(__first, __last);
}
+#endif
template<typename _RandomAccessIterator, typename _Distance,
typename _Compare>
@@ -3356,6 +3369,7 @@
enum { _S_chunk_size = 7 };
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator, typename _Pointer>
void
__merge_sort_with_buffer(_RandomAccessIterator __first,
@@ -3379,6 +3393,7 @@
__step_size *= 2;
}
}
+#endif
template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
void
@@ -3406,6 +3421,7 @@
}
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
template<typename _RandomAccessIterator, typename _Pointer,
typename _Distance>
void
@@ -3432,6 +3448,7 @@
_Distance(__last - __middle),
__buffer, __buffer_size);
}
+#endif
template<typename _RandomAccessIterator, typename _Pointer,
typename _Distance, typename _Compare>
@@ -3462,6 +3479,7 @@
__comp);
}
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
/// This is a helper function for the stable sorting routines.
template<typename _RandomAccessIterator>
void
@@ -3480,6 +3498,7 @@
__middle - __first,
__last - __middle);
}
+#endif
/// This is a helper function for the stable sorting routines.
template<typename _RandomAccessIterator, typename _Compare>
@@ -4414,13 +4433,21 @@
find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
{
+ typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
+
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_InputIterator>::value_type, _Tp>)
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
return std::__find(__first, __last, __val,
std::__iterator_category(__first));
+#else
+ return std::__find_if(__first, __last,
+ [&__val](const _ValueType& __x)
+ { return __x == __val; },
+ std::__iterator_category(__first));
+#endif
}
/**
@@ -4817,10 +4844,11 @@
search_n(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count, const _Tp& __val)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
+
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
if (__count <= 0)
@@ -4828,6 +4856,10 @@
if (__count == 1)
return _GLIBCXX_STD_A::find(__first, __last, __val);
return std::__search_n(__first, __last, __count, __val,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ [](const _ValueType& __x, const _Tp& __v)
+ { return __x == __v; },
+#endif
std::__iterator_category(__first));
}
@@ -5098,17 +5130,22 @@
unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result)
{
+ typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
+
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- typename iterator_traits<_InputIterator>::value_type>)
- __glibcxx_function_requires(_EqualityComparableConcept<
- typename iterator_traits<_InputIterator>::value_type>)
+ _ValueType>)
+ __glibcxx_function_requires(_EqualityComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
if (__first == __last)
return __result;
return std::__unique_copy(__first, __last, __result,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ [](const _ValueType& __x, const _ValueType& __y)
+ { return __x == __y; },
+#endif
std::__iterator_category(__first),
std::__iterator_category(__result));
}
@@ -5278,7 +5315,12 @@
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
- std::__heap_select(__first, __middle, __last);
+ std::__heap_select(__first, __middle, __last
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs, const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
std::sort_heap(__first, __middle);
}
@@ -5357,7 +5399,12 @@
return;
std::__introselect(__first, __nth, __last,
- std::__lg(__last - __first) * 2);
+ std::__lg(__last - __first) * 2
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs, const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
}
/**
@@ -5431,8 +5478,20 @@
if (__first != __last)
{
std::__introsort_loop(__first, __last,
- std::__lg(__last - __first) * 2);
- std::__final_insertion_sort(__first, __last);
+ std::__lg(__last - __first) * 2
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
+ std::__final_insertion_sort(__first, __last
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
}
}
@@ -5635,10 +5694,22 @@
_Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
__last);
if (__buf.begin() == 0)
- std::__inplace_stable_sort(__first, __last);
+ std::__inplace_stable_sort(__first, __last
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
- _DistanceType(__buf.size()));
+ _DistanceType(__buf.size())
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ,[](const _ValueType& __lhs,
+ const _ValueType& __rhs)
+ { return __lhs < __rhs; }
+#endif
+ );
}
/**