This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Remove algo logic duplication Round 3
- 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: Mon, 23 Sep 2013 22:07:11 +0200
- Subject: Remove algo logic duplication Round 3
- Authentication-results: sourceware.org; auth=none
Hi
Here is a new version of the patch. Marc idea to use template
operators indeed simplified the code, it avoids some binding operations.
I also review the name of helper functions so there are much fewer of
them and so that you only need to know what kind of operation you need
to know what function you must use, much cleaner I think.
I also get rid of the attempt to move as much code as possible
into __detail namespace to limit the patch. Moving code to __detail
namespace might be part of a future patch if it is considered of
interest or necessary for any other purpose.
I have also added a number of test case using std::vector<bool> but
as said Marc, even if big, this is a safe patch cause not detectable
from a user code point of view.
I follow each one opinion on previous mail thread but I think this
solution is still the most transparent ones for users in both C++03 and
C++11 modes. In addition to removing code logic duplication it also a
good enhancement to the debug mode as most of internal algo usages are
not performing the debug check again.
So, what do I do think about it ?
François
Index: include/Makefile.in
===================================================================
--- include/Makefile.in (revision 202818)
+++ include/Makefile.in (working copy)
@@ -388,6 +388,7 @@
${bits_srcdir}/ostream_insert.h \
${bits_srcdir}/parse_numbers.h \
${bits_srcdir}/postypes.h \
+ ${bits_srcdir}/predefined_ops.h \
${bits_srcdir}/ptr_traits.h \
${bits_srcdir}/random.h \
${bits_srcdir}/random.tcc \
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 202818)
+++ include/bits/stl_algo.h (working copy)
@@ -60,10 +60,10 @@
#include <bits/algorithmfwd.h>
#include <bits/stl_heap.h>
#include <bits/stl_tempbuf.h> // for _Temporary_buffer
+#include <bits/predefined_ops.h>
#if __cplusplus >= 201103L
#include <random> // for std::uniform_int_distribution
-#include <functional> // for std::bind
#endif
// See concept_check.h for the __glibcxx_*_requires macros.
@@ -72,129 +72,39 @@
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
- /// Swaps the median value of *__a, *__b and *__c to *__a
- template<typename _Iterator>
- void
- __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
- {
- // concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_Iterator>::value_type>)
-
- if (*__a < *__b)
- {
- if (*__b < *__c)
- std::iter_swap(__a, __b);
- else if (*__a < *__c)
- std::iter_swap(__a, __c);
- }
- else if (*__a < *__c)
- return;
- else if (*__b < *__c)
- std::iter_swap(__a, __c);
- else
- std::iter_swap(__a, __b);
- }
-
/// Swaps the median value of *__a, *__b and *__c under __comp to *__a
template<typename _Iterator, typename _Compare>
void
__move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
_Compare __comp)
{
- // concept requirements
- __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
- typename iterator_traits<_Iterator>::value_type,
- typename iterator_traits<_Iterator>::value_type>)
-
- if (__comp(*__a, *__b))
+ if (__comp(__a, __b))
{
- if (__comp(*__b, *__c))
+ if (__comp(__b, __c))
std::iter_swap(__a, __b);
- else if (__comp(*__a, *__c))
+ else if (__comp(__a, __c))
std::iter_swap(__a, __c);
}
- else if (__comp(*__a, *__c))
+ else if (__comp(__a, __c))
return;
- else if (__comp(*__b, *__c))
+ 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.
- template<typename _InputIterator, typename _Tp>
- inline _InputIterator
- __find(_InputIterator __first, _InputIterator __last,
- const _Tp& __val, input_iterator_tag)
- {
- while (__first != __last && !(*__first == __val))
- ++__first;
- return __first;
- }
-
- /// This is an overload used by find_if() for the Input Iterator case.
+ /// This is an overload used by find algos for the Input Iterator case.
template<typename _InputIterator, typename _Predicate>
inline _InputIterator
__find_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred, input_iterator_tag)
{
- while (__first != __last && !bool(__pred(*__first)))
+ while (__first != __last && !__pred(__first))
++__first;
return __first;
}
- /// This is an overload used by find() for the RAI case.
- template<typename _RandomAccessIterator, typename _Tp>
- _RandomAccessIterator
- __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
- const _Tp& __val, random_access_iterator_tag)
- {
- typename iterator_traits<_RandomAccessIterator>::difference_type
- __trip_count = (__last - __first) >> 2;
-
- for (; __trip_count > 0; --__trip_count)
- {
- if (*__first == __val)
- return __first;
- ++__first;
-
- if (*__first == __val)
- return __first;
- ++__first;
-
- if (*__first == __val)
- return __first;
- ++__first;
-
- if (*__first == __val)
- return __first;
- ++__first;
- }
-
- switch (__last - __first)
- {
- case 3:
- if (*__first == __val)
- return __first;
- ++__first;
- case 2:
- if (*__first == __val)
- return __first;
- ++__first;
- case 1:
- if (*__first == __val)
- return __first;
- ++__first;
- case 0:
- default:
- return __last;
- }
- }
-
- /// This is an overload used by find_if() for the RAI case.
+ /// This is an overload used by find algos for the RAI case.
template<typename _RandomAccessIterator, typename _Predicate>
_RandomAccessIterator
__find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
@@ -205,19 +115,19 @@
for (; __trip_count > 0; --__trip_count)
{
- if (__pred(*__first))
+ if (__pred(__first))
return __first;
++__first;
- if (__pred(*__first))
+ if (__pred(__first))
return __first;
++__first;
- if (__pred(*__first))
+ if (__pred(__first))
return __first;
++__first;
- if (__pred(*__first))
+ if (__pred(__first))
return __first;
++__first;
}
@@ -225,15 +135,15 @@
switch (__last - __first)
{
case 3:
- if (__pred(*__first))
+ if (__pred(__first))
return __first;
++__first;
case 2:
- if (__pred(*__first))
+ if (__pred(__first))
return __first;
++__first;
case 1:
- if (__pred(*__first))
+ if (__pred(__first))
return __first;
++__first;
case 0:
@@ -242,73 +152,23 @@
}
}
- /// 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)
+ template<typename _Iterator, typename _Predicate>
+ inline _Iterator
+ __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
{
- while (__first != __last && bool(__pred(*__first)))
- ++__first;
- return __first;
+ return __find_if(__first, __last, __pred,
+ std::__iterator_category(__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;
- }
- }
-
/// Provided for stable_partition to use.
template<typename _InputIterator, typename _Predicate>
inline _InputIterator
__find_if_not(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
{
- return std::__find_if_not(__first, __last, __pred,
- std::__iterator_category(__first));
+ return std::__find_if(__first, __last,
+ __gnu_cxx::__ops::__negate(__pred),
+ std::__iterator_category(__first));
}
/// Like find_if_not(), but uses and updates a count of the
@@ -319,7 +179,7 @@
__find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
{
for (; __len; --__len, ++__first)
- if (!bool(__pred(*__first)))
+ if (!__pred(__first))
break;
return __first;
}
@@ -337,98 +197,73 @@
// count_if
// search
- /**
- * This is an uglified
- * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
- * overloaded for forward iterators.
- */
- template<typename _ForwardIterator, typename _Integer, typename _Tp>
- _ForwardIterator
- __search_n(_ForwardIterator __first, _ForwardIterator __last,
- _Integer __count, const _Tp& __val,
- std::forward_iterator_tag)
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ _ForwardIterator1
+ __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+ _BinaryPredicate __predicate)
{
- __first = _GLIBCXX_STD_A::find(__first, __last, __val);
- while (__first != __last)
- {
- typename iterator_traits<_ForwardIterator>::difference_type
- __n = __count;
- _ForwardIterator __i = __first;
- ++__i;
- while (__i != __last && __n != 1 && *__i == __val)
- {
- ++__i;
- --__n;
- }
- if (__n == 1)
- return __first;
- if (__i == __last)
- return __last;
- __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
- }
- return __last;
- }
+ // Test for empty ranges
+ if (__first1 == __last1 || __first2 == __last2)
+ return __first1;
- /**
- * This is an uglified
- * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
- * overloaded for random access iterators.
- */
- template<typename _RandomAccessIter, typename _Integer, typename _Tp>
- _RandomAccessIter
- __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
- _Integer __count, const _Tp& __val,
- std::random_access_iterator_tag)
- {
-
- typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
- _DistanceType;
+ // Test for a pattern of length 1.
+ _ForwardIterator2 __p1(__first2);
+ if (++__p1 == __last2)
+ return std::__find_if(__first1, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
- _DistanceType __tailSize = __last - __first;
- _DistanceType __remainder = __count;
+ // General case.
+ _ForwardIterator2 __p;
+ _ForwardIterator1 __current = __first1;
- while (__remainder <= __tailSize) // the main loop...
+ for (;;)
{
- __first += __remainder;
- __tailSize -= __remainder;
- // __first here is always pointing to one past the last element of
- // next possible match.
- _RandomAccessIter __backTrack = __first;
- while (*--__backTrack == __val)
+ __first1 =
+ std::__find_if(__first1, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
+
+ if (__first1 == __last1)
+ return __last1;
+
+ __p = __p1;
+ __current = __first1;
+ if (++__current == __last1)
+ return __last1;
+
+ while (__predicate(__current, __p))
{
- if (--__remainder == 0)
- return (__first - __count); // Success
+ if (++__p == __last2)
+ return __first1;
+ if (++__current == __last1)
+ return __last1;
}
- __remainder = __count + 1 - (__first - __backTrack);
+ ++__first1;
}
- return __last; // Failure
+ return __first1;
}
// search_n
/**
- * This is an uglified
- * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
- * _BinaryPredicate)
- * overloaded for forward iterators.
+ * This is an helper function for search_n overloaded for forward iterators.
*/
- template<typename _ForwardIterator, typename _Integer, typename _Tp,
- typename _BinaryPredicate>
+ template<typename _ForwardIterator, typename _Integer,
+ typename _UnaryPredicate>
_ForwardIterator
- __search_n(_ForwardIterator __first, _ForwardIterator __last,
- _Integer __count, const _Tp& __val,
- _BinaryPredicate __binary_pred, std::forward_iterator_tag)
+ __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
+ _Integer __count, _UnaryPredicate __unary_pred,
+ std::forward_iterator_tag)
{
- while (__first != __last && !bool(__binary_pred(*__first, __val)))
- ++__first;
-
+ __first = std::__find_if(__first, __last, __unary_pred);
while (__first != __last)
{
typename iterator_traits<_ForwardIterator>::difference_type
__n = __count;
_ForwardIterator __i = __first;
++__i;
- while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
+ while (__i != __last && __n != 1 && __unary_pred(__i))
{
++__i;
--__n;
@@ -437,28 +272,23 @@
return __first;
if (__i == __last)
return __last;
- __first = ++__i;
- while (__first != __last
- && !bool(__binary_pred(*__first, __val)))
- ++__first;
+ __first
+ = std::__find_if(++__i, __last, __unary_pred);
}
return __last;
}
/**
- * This is an uglified
- * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
- * _BinaryPredicate)
- * overloaded for random access iterators.
+ * This is an helper function for search_n overloaded for random access
+ * iterators.
*/
- template<typename _RandomAccessIter, typename _Integer, typename _Tp,
- typename _BinaryPredicate>
+ template<typename _RandomAccessIter, typename _Integer,
+ typename _UnaryPredicate>
_RandomAccessIter
- __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
- _Integer __count, const _Tp& __val,
- _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
+ __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
+ _Integer __count, _UnaryPredicate __unary_pred,
+ std::random_access_iterator_tag)
{
-
typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
_DistanceType;
@@ -472,7 +302,7 @@
// __first here is always pointing to one past the last element of
// next possible match.
_RandomAccessIter __backTrack = __first;
- while (__binary_pred(*--__backTrack, __val))
+ while (__unary_pred(--__backTrack))
{
if (--__remainder == 0)
return (__first - __count); // Success
@@ -482,34 +312,24 @@
return __last; // Failure
}
- // find_end for forward iterators.
- template<typename _ForwardIterator1, typename _ForwardIterator2>
- _ForwardIterator1
- __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2,
- forward_iterator_tag, forward_iterator_tag)
+ template<typename _ForwardIterator, typename _Integer,
+ typename _UnaryPredicate>
+ _ForwardIterator
+ __search_n(_ForwardIterator __first, _ForwardIterator __last,
+ _Integer __count,
+ _UnaryPredicate __unary_pred)
{
- if (__first2 == __last2)
- return __last1;
- else
- {
- _ForwardIterator1 __result = __last1;
- while (1)
- {
- _ForwardIterator1 __new_result
- = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
- if (__new_result == __last1)
- return __result;
- else
- {
- __result = __new_result;
- __first1 = __new_result;
- ++__first1;
- }
- }
- }
+ if (__count <= 0)
+ return __first;
+
+ if (__count == 1)
+ return std::__find_if(__first, __last, __unary_pred);
+
+ return std::__search_n_aux(__first, __last, __count, __unary_pred,
+ std::__iterator_category(__first));
}
+ // find_end for forward iterators.
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
_ForwardIterator1
@@ -520,61 +340,24 @@
{
if (__first2 == __last2)
return __last1;
- else
+
+ _ForwardIterator1 __result = __last1;
+ while (1)
{
- _ForwardIterator1 __result = __last1;
- while (1)
+ _ForwardIterator1 __new_result
+ = std::__search(__first1, __last1, __first2, __last2, __comp);
+ if (__new_result == __last1)
+ return __result;
+ else
{
- _ForwardIterator1 __new_result
- = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
- __last2, __comp);
- if (__new_result == __last1)
- return __result;
- else
- {
- __result = __new_result;
- __first1 = __new_result;
- ++__first1;
- }
+ __result = __new_result;
+ __first1 = __new_result;
+ ++__first1;
}
}
}
// find_end for bidirectional iterators (much faster).
- template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
- _BidirectionalIterator1
- __find_end(_BidirectionalIterator1 __first1,
- _BidirectionalIterator1 __last1,
- _BidirectionalIterator2 __first2,
- _BidirectionalIterator2 __last2,
- bidirectional_iterator_tag, bidirectional_iterator_tag)
- {
- // concept requirements
- __glibcxx_function_requires(_BidirectionalIteratorConcept<
- _BidirectionalIterator1>)
- __glibcxx_function_requires(_BidirectionalIteratorConcept<
- _BidirectionalIterator2>)
-
- typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
- typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
-
- _RevIterator1 __rlast1(__first1);
- _RevIterator2 __rlast2(__first2);
- _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
- __rlast1,
- _RevIterator2(__last2),
- __rlast2);
-
- if (__rresult == __rlast1)
- return __last1;
- else
- {
- _BidirectionalIterator1 __result = __rresult.base();
- std::advance(__result, -std::distance(__first2, __last2));
- return __result;
- }
- }
-
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _BinaryPredicate>
_BidirectionalIterator1
@@ -596,9 +379,9 @@
_RevIterator1 __rlast1(__first1);
_RevIterator2 __rlast2(__first2);
- _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
- _RevIterator2(__last2), __rlast2,
- __comp);
+ _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
+ _RevIterator2(__last2), __rlast2,
+ __comp);
if (__rresult == __rlast1)
return __last1;
@@ -627,7 +410,7 @@
* [__first2,__last2) and returns an iterator to the __first
* element of the sub-sequence, or @p __last1 if the sub-sequence
* is not found. The sub-sequence will be the last such
- * subsequence contained in [__first,__last1).
+ * subsequence contained in [__first1,__last1).
*
* Because the sub-sequence must lie completely within the range @p
* [__first1,__last1) it must start at a position less than @p
@@ -652,7 +435,8 @@
return std::__find_end(__first1, __last1, __first2, __last2,
std::__iterator_category(__first1),
- std::__iterator_category(__first2));
+ std::__iterator_category(__first2),
+ __gnu_cxx::__ops::__iter_equal_to_iter());
}
/**
@@ -702,7 +486,7 @@
return std::__find_end(__first1, __last1, __first2, __last2,
std::__iterator_category(__first1),
std::__iterator_category(__first2),
- __comp);
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
#if __cplusplus >= 201103L
@@ -778,7 +562,8 @@
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- return std::__find_if_not(__first, __last, __pred);
+ return std::__find_if_not(__first, __last,
+ __gnu_cxx::__ops::__pred_iter(__pred));
}
/**
@@ -847,6 +632,20 @@
}
#endif
+ template<typename _InputIterator, typename _OutputIterator,
+ typename _Predicate>
+ _OutputIterator
+ __remove_copy_if(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result, _Predicate __pred)
+ {
+ for (; __first != __last; ++__first)
+ if (!__pred(__first))
+ {
+ *__result = *__first;
+ ++__result;
+ }
+ return __result;
+ }
/**
* @brief Copy a sequence, removing elements of a given value.
@@ -875,13 +674,8 @@
typename iterator_traits<_InputIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- for (; __first != __last; ++__first)
- if (!(*__first == __value))
- {
- *__result = *__first;
- ++__result;
- }
- return __result;
+ return std::__remove_copy_if(__first, __last, __result,
+ __gnu_cxx::__ops::__iter_equals_val(__value));
}
/**
@@ -913,13 +707,8 @@
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- for (; __first != __last; ++__first)
- if (!bool(__pred(*__first)))
- {
- *__result = *__first;
- ++__result;
- }
- return __result;
+ return std::__remove_copy_if(__first, __last, __result,
+ __gnu_cxx::__ops::__pred_iter(__pred));
}
#if __cplusplus >= 201103L
@@ -961,7 +750,6 @@
return __result;
}
-
template<typename _InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
__copy_n(_InputIterator __first, _Size __n,
@@ -1063,6 +851,25 @@
}
#endif
+ template<typename _ForwardIterator, typename _Predicate>
+ _ForwardIterator
+ __remove_if(_ForwardIterator __first, _ForwardIterator __last,
+ _Predicate __pred)
+ {
+ __first = std::__find_if(__first, __last, __pred);
+ if (__first == __last)
+ return __first;
+ _ForwardIterator __result = __first;
+ ++__first;
+ for (; __first != __last; ++__first)
+ if (!__pred(__first))
+ {
+ *__result = _GLIBCXX_MOVE(*__first);
+ ++__result;
+ }
+ return __result;
+ }
+
/**
* @brief Remove elements from a sequence.
* @ingroup mutating_algorithms
@@ -1092,18 +899,8 @@
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- __first = _GLIBCXX_STD_A::find(__first, __last, __value);
- if(__first == __last)
- return __first;
- _ForwardIterator __result = __first;
- ++__first;
- for(; __first != __last; ++__first)
- if(!(*__first == __value))
- {
- *__result = _GLIBCXX_MOVE(*__first);
- ++__result;
- }
- return __result;
+ return std::__remove_if(__first, __last,
+ __gnu_cxx::__ops::__iter_equals_val(__value));
}
/**
@@ -1135,18 +932,44 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
- if(__first == __last)
- return __first;
- _ForwardIterator __result = __first;
+ return std::__remove_if(__first, __last,
+ __gnu_cxx::__ops::__pred_iter(__pred));
+ }
+
+ template<typename _ForwardIterator, typename _BinaryPredicate>
+ _ForwardIterator
+ __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
+ _BinaryPredicate __binary_pred)
+ {
+ if (__first == __last)
+ return __last;
+ _ForwardIterator __next = __first;
+ while (++__next != __last)
+ {
+ if (__binary_pred(__first, __next))
+ return __first;
+ __first = __next;
+ }
+ return __last;
+ }
+
+ template<typename _ForwardIterator, typename _BinaryPredicate>
+ _ForwardIterator
+ __unique(_ForwardIterator __first, _ForwardIterator __last,
+ _BinaryPredicate __binary_pred)
+ {
+ // Skip the beginning, if already unique.
+ __first = std::__adjacent_find(__first, __last, __binary_pred);
+ if (__first == __last)
+ return __last;
+
+ // Do the real copy work.
+ _ForwardIterator __dest = __first;
++__first;
- for(; __first != __last; ++__first)
- if(!bool(__pred(*__first)))
- {
- *__result = _GLIBCXX_MOVE(*__first);
- ++__result;
- }
- return __result;
+ while (++__first != __last)
+ if (!__binary_pred(__dest, __first))
+ *++__dest = _GLIBCXX_MOVE(*__first);
+ return ++__dest;
}
/**
@@ -1174,18 +997,8 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- // Skip the beginning, if already unique.
- __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
- if (__first == __last)
- return __last;
-
- // Do the real copy work.
- _ForwardIterator __dest = __first;
- ++__first;
- while (++__first != __last)
- if (!(*__dest == *__first))
- *++__dest = _GLIBCXX_MOVE(*__first);
- return ++__dest;
+ return std::__unique(__first, __last,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
}
/**
@@ -1216,86 +1029,11 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- // Skip the beginning, if already unique.
- __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
- if (__first == __last)
- return __last;
-
- // Do the real copy work.
- _ForwardIterator __dest = __first;
- ++__first;
- while (++__first != __last)
- if (!bool(__binary_pred(*__dest, *__first)))
- *++__dest = _GLIBCXX_MOVE(*__first);
- return ++__dest;
+ return std::__unique(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
}
/**
- * This is an uglified unique_copy(_InputIterator, _InputIterator,
- * _OutputIterator)
- * overloaded for forward iterators and output iterator as result.
- */
- template<typename _ForwardIterator, typename _OutputIterator>
- _OutputIterator
- __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
- _OutputIterator __result,
- forward_iterator_tag, output_iterator_tag)
- {
- // concept requirements -- taken care of in dispatching function
- _ForwardIterator __next = __first;
- *__result = *__first;
- while (++__next != __last)
- if (!(*__first == *__next))
- {
- __first = __next;
- *++__result = *__first;
- }
- return ++__result;
- }
-
- /**
- * This is an uglified unique_copy(_InputIterator, _InputIterator,
- * _OutputIterator)
- * overloaded for input iterators and output iterator as result.
- */
- template<typename _InputIterator, typename _OutputIterator>
- _OutputIterator
- __unique_copy(_InputIterator __first, _InputIterator __last,
- _OutputIterator __result,
- input_iterator_tag, output_iterator_tag)
- {
- // concept requirements -- taken care of in dispatching function
- typename iterator_traits<_InputIterator>::value_type __value = *__first;
- *__result = __value;
- while (++__first != __last)
- if (!(__value == *__first))
- {
- __value = *__first;
- *++__result = __value;
- }
- return ++__result;
- }
-
- /**
- * This is an uglified unique_copy(_InputIterator, _InputIterator,
- * _OutputIterator)
- * overloaded for input iterators and forward iterator as result.
- */
- template<typename _InputIterator, typename _ForwardIterator>
- _ForwardIterator
- __unique_copy(_InputIterator __first, _InputIterator __last,
- _ForwardIterator __result,
- input_iterator_tag, forward_iterator_tag)
- {
- // concept requirements -- taken care of in dispatching function
- *__result = *__first;
- while (++__first != __last)
- if (!(*__result == *__first))
- *++__result = *__first;
- return ++__result;
- }
-
- /**
* This is an uglified
* unique_copy(_InputIterator, _InputIterator, _OutputIterator,
* _BinaryPredicate)
@@ -1316,7 +1054,7 @@
_ForwardIterator __next = __first;
*__result = *__first;
while (++__next != __last)
- if (!bool(__binary_pred(*__first, *__next)))
+ if (!__binary_pred(__first, __next))
{
__first = __next;
*++__result = *__first;
@@ -1343,9 +1081,12 @@
typename iterator_traits<_InputIterator>::value_type>)
typename iterator_traits<_InputIterator>::value_type __value = *__first;
+ __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
+ __rebound_pred
+ = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
*__result = __value;
while (++__first != __last)
- if (!bool(__binary_pred(__value, *__first)))
+ if (!__rebound_pred(__first, __value))
{
__value = *__first;
*++__result = __value;
@@ -1370,10 +1111,9 @@
__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
typename iterator_traits<_ForwardIterator>::value_type,
typename iterator_traits<_InputIterator>::value_type>)
-
*__result = *__first;
while (++__first != __last)
- if (!bool(__binary_pred(*__result, *__first)))
+ if (!__binary_pred(__result, __first))
*++__result = *__first;
return ++__result;
}
@@ -1800,10 +1540,10 @@
}
/// This is a helper function...
- /// Requires __first != __last and !__pred(*__first)
+ /// Requires __first != __last and !__pred(__first)
/// and __len == distance(__first, __last).
///
- /// !__pred(*__first) allows us to guarantee that we don't
+ /// !__pred(__first) allows us to guarantee that we don't
/// move-assign an element onto itself.
template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
typename _Distance>
@@ -1818,14 +1558,14 @@
{
_ForwardIterator __result1 = __first;
_Pointer __result2 = __buffer;
- // The precondition guarantees that !__pred(*__first), so
+ // The precondition guarantees that !__pred(__first), so
// move that element to the buffer before starting the loop.
// This ensures that we only call __pred once per element.
*__result2 = _GLIBCXX_MOVE(*__first);
++__result2;
++__first;
for (; __first != __last; ++__first)
- if (__pred(*__first))
+ if (__pred(__first))
{
*__result1 = _GLIBCXX_MOVE(*__first);
++__result1;
@@ -1862,6 +1602,34 @@
}
}
+ template<typename _ForwardIterator, typename _Predicate>
+ _ForwardIterator
+ __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
+ _Predicate __pred)
+ {
+ __first = std::__find_if_not(__first, __last, __pred);
+
+ if (__first == __last)
+ return __first;
+
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_ForwardIterator>::difference_type
+ _DistanceType;
+
+ _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
+ if (__buf.size() > 0)
+ return
+ std::__stable_partition_adaptive(__first, __last, __pred,
+ _DistanceType(__buf.requested_size()),
+ __buf.begin(),
+ _DistanceType(__buf.size()));
+ else
+ return
+ std::__inplace_stable_partition(__first, __pred,
+ _DistanceType(__buf.requested_size()));
+ }
+
/**
* @brief Move elements for which a predicate is true to the beginning
* of a sequence, preserving relative ordering.
@@ -1891,60 +1659,62 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- __first = std::__find_if_not(__first, __last, __pred);
-
- if (__first == __last)
- return __first;
- else
- {
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
-
- _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
- __last);
- if (__buf.size() > 0)
- return
- std::__stable_partition_adaptive(__first, __last, __pred,
- _DistanceType(__buf.requested_size()),
- __buf.begin(),
- _DistanceType(__buf.size()));
- else
- return
- std::__inplace_stable_partition(__first, __pred,
- _DistanceType(__buf.requested_size()));
- }
+ return std::__stable_partition(__first, __last,
+ __gnu_cxx::__ops::__pred_iter(__pred));
}
/// This is a helper function for the sort routines.
- template<typename _RandomAccessIterator>
- void
- __heap_select(_RandomAccessIterator __first,
- _RandomAccessIterator __middle,
- _RandomAccessIterator __last)
- {
- std::make_heap(__first, __middle);
- for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
- if (*__i < *__first)
- std::__pop_heap(__first, __middle, __i);
- }
-
- /// This is a helper function for the sort routines.
template<typename _RandomAccessIterator, typename _Compare>
void
__heap_select(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last, _Compare __comp)
{
- std::make_heap(__first, __middle, __comp);
+ std::__make_heap(__first, __middle, __comp);
for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
- if (__comp(*__i, *__first))
+ if (__comp(__i, __first))
std::__pop_heap(__first, __middle, __i, __comp);
}
// partial_sort
+ template<typename _InputIterator, typename _RandomAccessIterator,
+ typename _Compare>
+ _RandomAccessIterator
+ __partial_sort_copy(_InputIterator __first, _InputIterator __last,
+ _RandomAccessIterator __result_first,
+ _RandomAccessIterator __result_last,
+ _Compare __comp)
+ {
+ typedef typename iterator_traits<_InputIterator>::value_type
+ _InputValueType;
+ typedef iterator_traits<_RandomAccessIterator> _RItTraits;
+ typedef typename _RItTraits::difference_type _DistanceType;
+
+ if (__result_first == __result_last)
+ return __result_last;
+ _RandomAccessIterator __result_real_last = __result_first;
+ while (__first != __last && __result_real_last != __result_last)
+ {
+ *__result_real_last = *__first;
+ ++__result_real_last;
+ ++__first;
+ }
+
+ std::__make_heap(__result_first, __result_real_last, __comp);
+ while (__first != __last)
+ {
+ if (__comp(__first, __result_first))
+ std::__adjust_heap(__result_first, _DistanceType(0),
+ _DistanceType(__result_real_last
+ - __result_first),
+ _InputValueType(*__first), __comp);
+ ++__first;
+ }
+ std::__sort_heap(__result_first, __result_real_last, __comp);
+ return __result_real_last;
+ }
+
/**
* @brief Copy the smallest elements of a sequence.
* @ingroup sorting_algorithms
@@ -1986,27 +1756,9 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_valid_range(__result_first, __result_last);
- if (__result_first == __result_last)
- return __result_last;
- _RandomAccessIterator __result_real_last = __result_first;
- while(__first != __last && __result_real_last != __result_last)
- {
- *__result_real_last = *__first;
- ++__result_real_last;
- ++__first;
- }
- std::make_heap(__result_first, __result_real_last);
- while (__first != __last)
- {
- if (*__first < *__result_first)
- std::__adjust_heap(__result_first, _DistanceType(0),
- _DistanceType(__result_real_last
- - __result_first),
- _InputValueType(*__first));
- ++__first;
- }
- std::sort_heap(__result_first, __result_real_last);
- return __result_real_last;
+ return std::__partial_sort_copy(__first, __last,
+ __result_first, __result_last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -2029,7 +1781,8 @@
* @p __comp(*j,*i) is false.
* The value returned is @p __result_first+N.
*/
- template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
+ template<typename _InputIterator, typename _RandomAccessIterator,
+ typename _Compare>
_RandomAccessIterator
partial_sort_copy(_InputIterator __first, _InputIterator __last,
_RandomAccessIterator __result_first,
@@ -2056,49 +1809,12 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_valid_range(__result_first, __result_last);
- if (__result_first == __result_last)
- return __result_last;
- _RandomAccessIterator __result_real_last = __result_first;
- while(__first != __last && __result_real_last != __result_last)
- {
- *__result_real_last = *__first;
- ++__result_real_last;
- ++__first;
- }
- std::make_heap(__result_first, __result_real_last, __comp);
- while (__first != __last)
- {
- if (__comp(*__first, *__result_first))
- std::__adjust_heap(__result_first, _DistanceType(0),
- _DistanceType(__result_real_last
- - __result_first),
- _InputValueType(*__first),
- __comp);
- ++__first;
- }
- std::sort_heap(__result_first, __result_real_last, __comp);
- return __result_real_last;
+ return std::__partial_sort_copy(__first, __last,
+ __result_first, __result_last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
/// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator>
- void
- __unguarded_linear_insert(_RandomAccessIterator __last)
- {
- typename iterator_traits<_RandomAccessIterator>::value_type
- __val = _GLIBCXX_MOVE(*__last);
- _RandomAccessIterator __next = __last;
- --__next;
- while (__val < *__next)
- {
- *__last = _GLIBCXX_MOVE(*__next);
- __last = __next;
- --__next;
- }
- *__last = _GLIBCXX_MOVE(__val);
- }
-
- /// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
void
__unguarded_linear_insert(_RandomAccessIterator __last,
@@ -2108,7 +1824,7 @@
__val = _GLIBCXX_MOVE(*__last);
_RandomAccessIterator __next = __last;
--__next;
- while (__comp(__val, *__next))
+ while (__comp(__val, __next))
{
*__last = _GLIBCXX_MOVE(*__next);
__last = __next;
@@ -2118,29 +1834,6 @@
}
/// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator>
- void
- __insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last)
- {
- if (__first == __last)
- return;
-
- for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
- {
- if (*__i < *__first)
- {
- 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);
- }
- }
-
- /// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
void
__insertion_sort(_RandomAccessIterator __first,
@@ -2150,7 +1843,7 @@
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
- if (__comp(*__i, *__first))
+ if (__comp(__i, __first))
{
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__i);
@@ -2158,34 +1851,20 @@
*__first = _GLIBCXX_MOVE(__val);
}
else
- std::__unguarded_linear_insert(__i, __comp);
+ std::__unguarded_linear_insert(__i,
+ __gnu_cxx::__ops::__val_comp_iter(__comp));
}
}
/// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator>
- inline void
- __unguarded_insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
- for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
- std::__unguarded_linear_insert(__i);
- }
-
- /// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
inline void
__unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
- std::__unguarded_linear_insert(__i, __comp);
+ std::__unguarded_linear_insert(__i,
+ __gnu_cxx::__ops::__val_comp_iter(__comp));
}
/**
@@ -2195,21 +1874,6 @@
enum { _S_threshold = 16 };
/// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator>
- void
- __final_insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last)
- {
- if (__last - __first > int(_S_threshold))
- {
- std::__insertion_sort(__first, __first + int(_S_threshold));
- std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
- }
- else
- std::__insertion_sort(__first, __last);
- }
-
- /// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
void
__final_insertion_sort(_RandomAccessIterator __first,
@@ -2226,38 +1890,18 @@
}
/// This is a helper function...
- template<typename _RandomAccessIterator, typename _Tp>
+ template<typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
- _RandomAccessIterator __last, const _Tp& __pivot)
- {
- while (true)
- {
- while (*__first < __pivot)
- ++__first;
- --__last;
- while (__pivot < *__last)
- --__last;
- if (!(__first < __last))
- return __first;
- std::iter_swap(__first, __last);
- ++__first;
- }
- }
-
- /// This is a helper function...
- template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
- _RandomAccessIterator
- __unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
- const _Tp& __pivot, _Compare __comp)
+ _RandomAccessIterator __pivot, _Compare __comp)
{
while (true)
{
- while (__comp(*__first, __pivot))
+ while (__comp(__first, __pivot))
++__first;
--__last;
- while (__comp(__pivot, *__last))
+ while (__comp(__pivot, __last))
--__last;
if (!(__first < __last))
return __first;
@@ -2267,18 +1911,6 @@
}
/// This is a helper function...
- template<typename _RandomAccessIterator>
- inline _RandomAccessIterator
- __unguarded_partition_pivot(_RandomAccessIterator __first,
- _RandomAccessIterator __last)
- {
- _RandomAccessIterator __mid = __first + (__last - __first) / 2;
- std::__move_median_first(__first, __mid, (__last - 1));
- return std::__unguarded_partition(__first + 1, __last, *__first);
- }
-
-
- /// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
@@ -2286,29 +1918,18 @@
{
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
std::__move_median_first(__first, __mid, (__last - 1), __comp);
- return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
+ return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}
- /// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator, typename _Size>
- void
- __introsort_loop(_RandomAccessIterator __first,
- _RandomAccessIterator __last,
- _Size __depth_limit)
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline void
+ __partial_sort(_RandomAccessIterator __first,
+ _RandomAccessIterator __middle,
+ _RandomAccessIterator __last,
+ _Compare __comp)
{
- while (__last - __first > int(_S_threshold))
- {
- if (__depth_limit == 0)
- {
- _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
- return;
- }
- --__depth_limit;
- _RandomAccessIterator __cut =
- std::__unguarded_partition_pivot(__first, __last);
- std::__introsort_loop(__cut, __last, __depth_limit);
- __last = __cut;
- }
+ std::__heap_select(__first, __middle, __last, __comp);
+ std::__sort_heap(__first, __middle, __comp);
}
/// This is a helper function for the sort routine.
@@ -2322,7 +1943,7 @@
{
if (__depth_limit == 0)
{
- _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
+ std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
@@ -2335,33 +1956,18 @@
// sort
- template<typename _RandomAccessIterator, typename _Size>
- void
- __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
- _RandomAccessIterator __last, _Size __depth_limit)
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline void
+ __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
- while (__last - __first > 3)
+ if (__first != __last)
{
- if (__depth_limit == 0)
- {
- std::__heap_select(__first, __nth + 1, __last);
-
- // Place the nth largest element in its final position.
- std::iter_swap(__first, __nth);
- return;
- }
- --__depth_limit;
- _RandomAccessIterator __cut =
- std::__unguarded_partition_pivot(__first, __last);
- if (__cut <= __nth)
- __first = __cut;
- else
- __last = __cut;
+ std::__introsort_loop(__first, __last,
+ std::__lg(__last - __first) * 2,
+ __comp);
+ std::__final_insertion_sort(__first, __last, __comp);
}
- std::__insertion_sort(__first, __last);
}
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
@@ -2370,9 +1976,6 @@
_RandomAccessIterator __last, _Size __depth_limit,
_Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
while (__last - __first > 3)
{
if (__depth_limit == 0)
@@ -2420,8 +2023,6 @@
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
@@ -2430,6 +2031,18 @@
__glibcxx_requires_partitioned_lower_pred(__first, __last,
__val, __comp);
+ return std::__lower_bound(__first, __last, __val,
+ __gnu_cxx::__ops::__iter_comp_val(__comp));
+ }
+
+ template<typename _ForwardIterator, typename _Tp, typename _Compare>
+ _ForwardIterator
+ __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val, _Compare __comp)
+ {
+ typedef typename iterator_traits<_ForwardIterator>::difference_type
+ _DistanceType;
+
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
@@ -2437,14 +2050,14 @@
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
- if (__comp(*__middle, __val))
+ if (__comp(__val, __middle))
+ __len = __half;
+ else
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
- else
- __len = __half;
}
return __first;
}
@@ -2467,31 +2080,14 @@
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
__glibcxx_requires_partitioned_upper(__first, __last, __val);
- _DistanceType __len = std::distance(__first, __last);
-
- while (__len > 0)
- {
- _DistanceType __half = __len >> 1;
- _ForwardIterator __middle = __first;
- std::advance(__middle, __half);
- if (__val < *__middle)
- __len = __half;
- else
- {
- __first = __middle;
- ++__first;
- __len = __len - __half - 1;
- }
- }
- return __first;
+ return std::__upper_bound(__first, __last, __val,
+ __gnu_cxx::__ops::__val_less_iter());
}
/**
@@ -2516,8 +2112,6 @@
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
@@ -2526,6 +2120,20 @@
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
+ return std::__upper_bound(__first, __last, __val,
+ __gnu_cxx::__ops::__val_comp_iter(__comp));
+ }
+
+ template<typename _ForwardIterator, typename _Tp,
+ typename _CompareItTp, typename _CompareTpIt>
+ pair<_ForwardIterator, _ForwardIterator>
+ __equal_range(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val,
+ _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
+ {
+ typedef typename iterator_traits<_ForwardIterator>::difference_type
+ _DistanceType;
+
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
@@ -2533,16 +2141,25 @@
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
- if (__comp(__val, *__middle))
- __len = __half;
- else
+ if (__comp_it_val(__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
+ else if (__comp_val_it(__val, __middle))
+ __len = __half;
+ else
+ {
+ _ForwardIterator __left
+ = std::__lower_bound(__first, __middle, __val, __comp_it_val);
+ std::advance(__first, __len);
+ _ForwardIterator __right
+ = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
+ return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
+ }
}
- return __first;
+ return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
}
/**
@@ -2569,42 +2186,17 @@
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
- __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+ __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
__glibcxx_requires_partitioned_lower(__first, __last, __val);
__glibcxx_requires_partitioned_upper(__first, __last, __val);
- _DistanceType __len = std::distance(__first, __last);
-
- while (__len > 0)
- {
- _DistanceType __half = __len >> 1;
- _ForwardIterator __middle = __first;
- std::advance(__middle, __half);
- if (*__middle < __val)
- {
- __first = __middle;
- ++__first;
- __len = __len - __half - 1;
- }
- else if (__val < *__middle)
- __len = __half;
- else
- {
- _ForwardIterator __left = std::lower_bound(__first, __middle,
- __val);
- std::advance(__first, __len);
- _ForwardIterator __right = std::upper_bound(++__middle, __first,
- __val);
- return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
- }
- }
- return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
+ return std::__equal_range(__first, __last, __val,
+ __gnu_cxx::__ops::__iter_less_val(),
+ __gnu_cxx::__ops::__val_less_iter());
}
/**
@@ -2631,8 +2223,6 @@
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
@@ -2645,32 +2235,9 @@
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
- _DistanceType __len = std::distance(__first, __last);
-
- while (__len > 0)
- {
- _DistanceType __half = __len >> 1;
- _ForwardIterator __middle = __first;
- std::advance(__middle, __half);
- if (__comp(*__middle, __val))
- {
- __first = __middle;
- ++__first;
- __len = __len - __half - 1;
- }
- else if (__comp(__val, *__middle))
- __len = __half;
- else
- {
- _ForwardIterator __left = std::lower_bound(__first, __middle,
- __val, __comp);
- std::advance(__first, __len);
- _ForwardIterator __right = std::upper_bound(++__middle, __first,
- __val, __comp);
- return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
- }
- }
- return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
+ return std::__equal_range(__first, __last, __val,
+ __gnu_cxx::__ops::__iter_comp_val(__comp),
+ __gnu_cxx::__ops::__val_comp_iter(__comp));
}
/**
@@ -2699,7 +2266,9 @@
__glibcxx_requires_partitioned_lower(__first, __last, __val);
__glibcxx_requires_partitioned_upper(__first, __last, __val);
- _ForwardIterator __i = std::lower_bound(__first, __last, __val);
+ _ForwardIterator __i
+ = std::__lower_bound(__first, __last, __val,
+ __gnu_cxx::__ops::__iter_less_val());
return __i != __last && !(__val < *__i);
}
@@ -2735,7 +2304,9 @@
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
- _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
+ _ForwardIterator __i
+ = std::__lower_bound(__first, __last, __val,
+ __gnu_cxx::__ops::__iter_comp_val(__comp));
return __i != __last && !bool(__comp(__val, *__i));
}
@@ -2743,32 +2314,6 @@
/// 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,
@@ -2777,7 +2322,7 @@
{
while (__first1 != __last1 && __first2 != __last2)
{
- if (__comp(*__first2, *__first1))
+ if (__comp(__first2, __first1))
{
*__result = _GLIBCXX_MOVE(*__first2);
++__first2;
@@ -2795,48 +2340,6 @@
/// This is a helper function for the __merge_adaptive routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
- typename _BidirectionalIterator3>
- void
- __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
- _BidirectionalIterator1 __last1,
- _BidirectionalIterator2 __first2,
- _BidirectionalIterator2 __last2,
- _BidirectionalIterator3 __result)
- {
- if (__first1 == __last1)
- {
- _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
- return;
- }
- else if (__first2 == __last2)
- return;
-
- --__last1;
- --__last2;
- while (true)
- {
- if (*__last2 < *__last1)
- {
- *--__result = _GLIBCXX_MOVE(*__last1);
- if (__first1 == __last1)
- {
- _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
- return;
- }
- --__last1;
- }
- else
- {
- *--__result = _GLIBCXX_MOVE(*__last2);
- if (__first2 == __last2)
- return;
- --__last2;
- }
- }
- }
-
- /// This is a helper function for the __merge_adaptive routines.
- template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _BidirectionalIterator3, typename _Compare>
void
__move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
@@ -2858,7 +2361,7 @@
--__last2;
while (true)
{
- if (__comp(*__last2, *__last1))
+ if (__comp(__last2, __last1))
{
*--__result = _GLIBCXX_MOVE(*__last1);
if (__first1 == __last1)
@@ -2921,62 +2424,6 @@
}
/// This is a helper function for the merge routines.
- template<typename _BidirectionalIterator, typename _Distance,
- typename _Pointer>
- void
- __merge_adaptive(_BidirectionalIterator __first,
- _BidirectionalIterator __middle,
- _BidirectionalIterator __last,
- _Distance __len1, _Distance __len2,
- _Pointer __buffer, _Distance __buffer_size)
- {
- if (__len1 <= __len2 && __len1 <= __buffer_size)
- {
- _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
- 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_adaptive_backward(__first, __middle, __buffer,
- __buffer_end, __last);
- }
- else
- {
- _BidirectionalIterator __first_cut = __first;
- _BidirectionalIterator __second_cut = __middle;
- _Distance __len11 = 0;
- _Distance __len22 = 0;
- if (__len1 > __len2)
- {
- __len11 = __len1 / 2;
- std::advance(__first_cut, __len11);
- __second_cut = std::lower_bound(__middle, __last,
- *__first_cut);
- __len22 = std::distance(__middle, __second_cut);
- }
- else
- {
- __len22 = __len2 / 2;
- std::advance(__second_cut, __len22);
- __first_cut = std::upper_bound(__first, __middle,
- *__second_cut);
- __len11 = std::distance(__first, __first_cut);
- }
- _BidirectionalIterator __new_middle =
- std::__rotate_adaptive(__first_cut, __middle, __second_cut,
- __len1 - __len11, __len22, __buffer,
- __buffer_size);
- std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
- __len22, __buffer, __buffer_size);
- std::__merge_adaptive(__new_middle, __second_cut, __last,
- __len1 - __len11,
- __len2 - __len22, __buffer, __buffer_size);
- }
- }
-
- /// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
typename _Pointer, typename _Compare>
void
@@ -2990,14 +2437,14 @@
if (__len1 <= __len2 && __len1 <= __buffer_size)
{
_Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
- std::__move_merge_adaptive(__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_adaptive_backward(__first, __middle, __buffer,
- __buffer_end, __last, __comp);
+ std::__move_merge_adaptive_backward
+ (__first, __middle, __buffer, __buffer_end, __last, __comp);
}
else
{
@@ -3009,75 +2456,34 @@
{
__len11 = __len1 / 2;
std::advance(__first_cut, __len11);
- __second_cut = std::lower_bound(__middle, __last, *__first_cut,
- __comp);
+ __second_cut
+ = std::__lower_bound(__middle, __last, *__first_cut,
+ __gnu_cxx::__ops::__iter_comp_val(__comp));
__len22 = std::distance(__middle, __second_cut);
}
else
{
__len22 = __len2 / 2;
std::advance(__second_cut, __len22);
- __first_cut = std::upper_bound(__first, __middle, *__second_cut,
- __comp);
+ __first_cut
+ = std::__upper_bound(__first, __middle, *__second_cut,
+ __gnu_cxx::__ops::__val_comp_iter(__comp));
__len11 = std::distance(__first, __first_cut);
}
- _BidirectionalIterator __new_middle =
- std::__rotate_adaptive(__first_cut, __middle, __second_cut,
- __len1 - __len11, __len22, __buffer,
- __buffer_size);
- std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
- __len22, __buffer, __buffer_size, __comp);
+ _BidirectionalIterator __new_middle
+ = std::__rotate_adaptive(__first_cut, __middle,
+ __second_cut, __len1 - __len11,
+ __len22, __buffer, __buffer_size);
+ std::__merge_adaptive(__first, __first_cut, __new_middle,
+ __len11, __len22,
+ __buffer, __buffer_size, __comp);
std::__merge_adaptive(__new_middle, __second_cut, __last,
- __len1 - __len11,
- __len2 - __len22, __buffer,
- __buffer_size, __comp);
+ __len1 - __len11, __len2 - __len22,
+ __buffer, __buffer_size, __comp);
}
}
/// This is a helper function for the merge routines.
- template<typename _BidirectionalIterator, typename _Distance>
- void
- __merge_without_buffer(_BidirectionalIterator __first,
- _BidirectionalIterator __middle,
- _BidirectionalIterator __last,
- _Distance __len1, _Distance __len2)
- {
- if (__len1 == 0 || __len2 == 0)
- return;
- if (__len1 + __len2 == 2)
- {
- if (*__middle < *__first)
- std::iter_swap(__first, __middle);
- return;
- }
- _BidirectionalIterator __first_cut = __first;
- _BidirectionalIterator __second_cut = __middle;
- _Distance __len11 = 0;
- _Distance __len22 = 0;
- if (__len1 > __len2)
- {
- __len11 = __len1 / 2;
- std::advance(__first_cut, __len11);
- __second_cut = std::lower_bound(__middle, __last, *__first_cut);
- __len22 = std::distance(__middle, __second_cut);
- }
- else
- {
- __len22 = __len2 / 2;
- std::advance(__second_cut, __len22);
- __first_cut = std::upper_bound(__first, __middle, *__second_cut);
- __len11 = std::distance(__first, __first_cut);
- }
- std::rotate(__first_cut, __middle, __second_cut);
- _BidirectionalIterator __new_middle = __first_cut;
- std::advance(__new_middle, std::distance(__middle, __second_cut));
- std::__merge_without_buffer(__first, __first_cut, __new_middle,
- __len11, __len22);
- std::__merge_without_buffer(__new_middle, __second_cut, __last,
- __len1 - __len11, __len2 - __len22);
- }
-
- /// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
typename _Compare>
void
@@ -3091,7 +2497,7 @@
return;
if (__len1 + __len2 == 2)
{
- if (__comp(*__middle, *__first))
+ if (__comp(__middle, __first))
std::iter_swap(__first, __middle);
return;
}
@@ -3103,16 +2509,18 @@
{
__len11 = __len1 / 2;
std::advance(__first_cut, __len11);
- __second_cut = std::lower_bound(__middle, __last, *__first_cut,
- __comp);
+ __second_cut
+ = std::__lower_bound(__middle, __last, *__first_cut,
+ __gnu_cxx::__ops::__iter_comp_val(__comp));
__len22 = std::distance(__middle, __second_cut);
}
else
{
__len22 = __len2 / 2;
std::advance(__second_cut, __len22);
- __first_cut = std::upper_bound(__first, __middle, *__second_cut,
- __comp);
+ __first_cut
+ = std::__upper_bound(__first, __middle, *__second_cut,
+ __gnu_cxx::__ops::__val_comp_iter(__comp));
__len11 = std::distance(__first, __first_cut);
}
std::rotate(__first_cut, __middle, __second_cut);
@@ -3124,6 +2532,36 @@
__len1 - __len11, __len2 - __len22, __comp);
}
+ template<typename _BidirectionalIterator, typename _Compare>
+ void
+ __inplace_merge(_BidirectionalIterator __first,
+ _BidirectionalIterator __middle,
+ _BidirectionalIterator __last,
+ _Compare __comp)
+ {
+ typedef typename iterator_traits<_BidirectionalIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_BidirectionalIterator>::difference_type
+ _DistanceType;
+
+ if (__first == __middle || __middle == __last)
+ return;
+
+ const _DistanceType __len1 = std::distance(__first, __middle);
+ const _DistanceType __len2 = std::distance(__middle, __last);
+
+ typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
+ _TmpBuf __buf(__first, __last);
+
+ if (__buf.begin() == 0)
+ std::__merge_without_buffer
+ (__first, __middle, __last, __len1, __len2, __comp);
+ else
+ std::__merge_adaptive
+ (__first, __middle, __last, __len1, __len2, __buf.begin(),
+ _DistanceType(__buf.size()), __comp);
+ }
+
/**
* @brief Merges two sorted ranges in place.
* @ingroup sorting_algorithms
@@ -3148,31 +2586,16 @@
_BidirectionalIterator __middle,
_BidirectionalIterator __last)
{
- typedef typename iterator_traits<_BidirectionalIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_BidirectionalIterator>::difference_type
- _DistanceType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
_BidirectionalIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_sorted(__first, __middle);
__glibcxx_requires_sorted(__middle, __last);
- if (__first == __middle || __middle == __last)
- return;
-
- _DistanceType __len1 = std::distance(__first, __middle);
- _DistanceType __len2 = std::distance(__middle, __last);
-
- _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
- __last);
- if (__buf.begin() == 0)
- std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
- else
- std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
- __buf.begin(), _DistanceType(__buf.size()));
+ std::__inplace_merge(__first, __middle, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -3204,75 +2627,31 @@
_BidirectionalIterator __last,
_Compare __comp)
{
- typedef typename iterator_traits<_BidirectionalIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_BidirectionalIterator>::difference_type
- _DistanceType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
_BidirectionalIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType, _ValueType>)
+ typename iterator_traits<_BidirectionalIterator>::value_type,
+ typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_sorted_pred(__first, __middle, __comp);
__glibcxx_requires_sorted_pred(__middle, __last, __comp);
- if (__first == __middle || __middle == __last)
- return;
-
- const _DistanceType __len1 = std::distance(__first, __middle);
- const _DistanceType __len2 = std::distance(__middle, __last);
-
- _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
- __last);
- if (__buf.begin() == 0)
- std::__merge_without_buffer(__first, __middle, __last, __len1,
- __len2, __comp);
- else
- std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
- __buf.begin(), _DistanceType(__buf.size()),
- __comp);
+ std::__inplace_merge(__first, __middle, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
/// This is a helper function for the __merge_sort_loop routines.
- template<typename _InputIterator1, typename _InputIterator2,
- typename _OutputIterator>
+ template<typename _InputIterator, typename _OutputIterator,
+ typename _Compare>
_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,
+ __move_merge(_InputIterator __first1, _InputIterator __last1,
+ _InputIterator __first2, _InputIterator __last2,
_OutputIterator __result, _Compare __comp)
{
while (__first1 != __last1 && __first2 != __last2)
{
- if (__comp(*__first2, *__first1))
+ if (__comp(__first2, __first1))
{
*__result = _GLIBCXX_MOVE(*__first2);
++__first2;
@@ -3290,29 +2669,6 @@
}
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
- typename _Distance>
- void
- __merge_sort_loop(_RandomAccessIterator1 __first,
- _RandomAccessIterator1 __last,
- _RandomAccessIterator2 __result,
- _Distance __step_size)
- {
- const _Distance __two_step = 2 * __step_size;
-
- while (__last - __first >= __two_step)
- {
- __result = std::__move_merge(__first, __first + __step_size,
- __first + __step_size,
- __first + __two_step, __result);
- __first += __two_step;
- }
-
- __step_size = std::min(_Distance(__last - __first), __step_size);
- std::__move_merge(__first, __first + __step_size,
- __first + __step_size, __last, __result);
- }
-
- template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
typename _Distance, typename _Compare>
void
__merge_sort_loop(_RandomAccessIterator1 __first,
@@ -3332,24 +2688,10 @@
}
__step_size = std::min(_Distance(__last - __first), __step_size);
- std::__move_merge(__first,__first + __step_size,
+ std::__move_merge(__first, __first + __step_size,
__first + __step_size, __last, __result, __comp);
}
- template<typename _RandomAccessIterator, typename _Distance>
- void
- __chunk_insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last,
- _Distance __chunk_size)
- {
- while (__last - __first >= __chunk_size)
- {
- std::__insertion_sort(__first, __first + __chunk_size);
- __first += __chunk_size;
- }
- std::__insertion_sort(__first, __last);
- }
-
template<typename _RandomAccessIterator, typename _Distance,
typename _Compare>
void
@@ -3367,30 +2709,6 @@
enum { _S_chunk_size = 7 };
- template<typename _RandomAccessIterator, typename _Pointer>
- void
- __merge_sort_with_buffer(_RandomAccessIterator __first,
- _RandomAccessIterator __last,
- _Pointer __buffer)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _Distance;
-
- const _Distance __len = __last - __first;
- const _Pointer __buffer_last = __buffer + __len;
-
- _Distance __step_size = _S_chunk_size;
- std::__chunk_insertion_sort(__first, __last, __step_size);
-
- while (__step_size < __len)
- {
- std::__merge_sort_loop(__first, __last, __buffer, __step_size);
- __step_size *= 2;
- std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
- __step_size *= 2;
- }
- }
-
template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
void
__merge_sort_with_buffer(_RandomAccessIterator __first,
@@ -3408,43 +2726,16 @@
while (__step_size < __len)
{
- std::__merge_sort_loop(__first, __last, __buffer,
- __step_size, __comp);
+ std::__merge_sort_loop(__first, __last, __buffer, __step_size,
+ __comp);
__step_size *= 2;
- std::__merge_sort_loop(__buffer, __buffer_last, __first,
- __step_size, __comp);
+ std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size,
+ __comp);
__step_size *= 2;
}
}
template<typename _RandomAccessIterator, typename _Pointer,
- typename _Distance>
- void
- __stable_sort_adaptive(_RandomAccessIterator __first,
- _RandomAccessIterator __last,
- _Pointer __buffer, _Distance __buffer_size)
- {
- const _Distance __len = (__last - __first + 1) / 2;
- const _RandomAccessIterator __middle = __first + __len;
- if (__len > __buffer_size)
- {
- std::__stable_sort_adaptive(__first, __middle,
- __buffer, __buffer_size);
- std::__stable_sort_adaptive(__middle, __last,
- __buffer, __buffer_size);
- }
- else
- {
- std::__merge_sort_with_buffer(__first, __middle, __buffer);
- std::__merge_sort_with_buffer(__middle, __last, __buffer);
- }
- std::__merge_adaptive(__first, __middle, __last,
- _Distance(__middle - __first),
- _Distance(__last - __middle),
- __buffer, __buffer_size);
- }
-
- template<typename _RandomAccessIterator, typename _Pointer,
typename _Distance, typename _Compare>
void
__stable_sort_adaptive(_RandomAccessIterator __first,
@@ -3474,25 +2765,6 @@
}
/// This is a helper function for the stable sorting routines.
- template<typename _RandomAccessIterator>
- void
- __inplace_stable_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last)
- {
- if (__last - __first < 15)
- {
- std::__insertion_sort(__first, __last);
- return;
- }
- _RandomAccessIterator __middle = __first + (__last - __first) / 2;
- std::__inplace_stable_sort(__first, __middle);
- std::__inplace_stable_sort(__middle, __last);
- std::__merge_without_buffer(__first, __middle, __last,
- __middle - __first,
- __last - __middle);
- }
-
- /// This is a helper function for the stable sorting routines.
template<typename _RandomAccessIterator, typename _Compare>
void
__inplace_stable_sort(_RandomAccessIterator __first,
@@ -3519,6 +2791,24 @@
// that their input ranges are sorted and the postcondition that their output
// ranges are sorted.
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _Compare>
+ bool
+ __includes(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _Compare __comp)
+ {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (__comp(__first2, __first1))
+ return false;
+ else if (__comp(__first1, __first2))
+ ++__first1;
+ else
+ ++__first1, ++__first2;
+
+ return __first2 == __last2;
+ }
+
/**
* @brief Determines whether all elements of a sequence exists in a range.
* @param __first1 Start of search range.
@@ -3542,28 +2832,20 @@
includes(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set(__first1, __last1, __first2);
__glibcxx_requires_sorted_set(__first2, __last2, __first1);
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first2 < *__first1)
- return false;
- else if(*__first1 < *__first2)
- ++__first1;
- else
- ++__first1, ++__first2;
-
- return __first2 == __last2;
+ return std::__includes(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -3594,30 +2876,20 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_Compare __comp)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType1, _ValueType2>)
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
- while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first2, *__first1))
- return false;
- else if(__comp(*__first1, *__first2))
- ++__first1;
- else
- ++__first1, ++__first2;
-
- return __first2 == __last2;
+ return std::__includes(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
// nth_element
@@ -3630,30 +2902,11 @@
// min_element
// max_element
- /**
- * @brief Permute range into the next @e dictionary ordering.
- * @ingroup sorting_algorithms
- * @param __first Start of range.
- * @param __last End of range.
- * @return False if wrapped to first permutation, true otherwise.
- *
- * Treats all permutations of the range as a set of @e dictionary sorted
- * sequences. Permutes the current sequence into the next one of this set.
- * Returns true if there are more sequences to generate. If the sequence
- * is the largest of the set, the smallest is generated and false returned.
- */
- template<typename _BidirectionalIterator>
+ template<typename _BidirectionalIterator, typename _Compare>
bool
- next_permutation(_BidirectionalIterator __first,
- _BidirectionalIterator __last)
+ __next_permutation(_BidirectionalIterator __first,
+ _BidirectionalIterator __last, _Compare __comp)
{
- // concept requirements
- __glibcxx_function_requires(_BidirectionalIteratorConcept<
- _BidirectionalIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_BidirectionalIterator>::value_type>)
- __glibcxx_requires_valid_range(__first, __last);
-
if (__first == __last)
return false;
_BidirectionalIterator __i = __first;
@@ -3667,24 +2920,54 @@
{
_BidirectionalIterator __ii = __i;
--__i;
- if (*__i < *__ii)
+ if (__comp(__i, __ii))
{
_BidirectionalIterator __j = __last;
- while (!(*__i < *--__j))
+ while (!__comp(__i, --__j))
{}
std::iter_swap(__i, __j);
- std::reverse(__ii, __last);
+ std::__reverse(__ii, __last,
+ std::__iterator_category(__first));
return true;
}
if (__i == __first)
{
- std::reverse(__first, __last);
+ std::__reverse(__first, __last,
+ std::__iterator_category(__first));
return false;
}
}
}
/**
+ * @brief Permute range into the next @e dictionary ordering.
+ * @ingroup sorting_algorithms
+ * @param __first Start of range.
+ * @param __last End of range.
+ * @return False if wrapped to first permutation, true otherwise.
+ *
+ * Treats all permutations of the range as a set of @e dictionary sorted
+ * sequences. Permutes the current sequence into the next one of this set.
+ * Returns true if there are more sequences to generate. If the sequence
+ * is the largest of the set, the smallest is generated and false returned.
+ */
+ template<typename _BidirectionalIterator>
+ bool
+ next_permutation(_BidirectionalIterator __first,
+ _BidirectionalIterator __last)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_BidirectionalIteratorConcept<
+ _BidirectionalIterator>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_BidirectionalIterator>::value_type>)
+ __glibcxx_requires_valid_range(__first, __last);
+
+ return std::__next_permutation
+ (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
+ }
+
+ /**
* @brief Permute range into the next @e dictionary ordering using
* comparison functor.
* @ingroup sorting_algorithms
@@ -3712,6 +2995,15 @@
typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
+ return std::__next_permutation
+ (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ }
+
+ template<typename _BidirectionalIterator, typename _Compare>
+ bool
+ __prev_permutation(_BidirectionalIterator __first,
+ _BidirectionalIterator __last, _Compare __comp)
+ {
if (__first == __last)
return false;
_BidirectionalIterator __i = __first;
@@ -3725,18 +3017,20 @@
{
_BidirectionalIterator __ii = __i;
--__i;
- if (__comp(*__i, *__ii))
+ if (__comp(__ii, __i))
{
_BidirectionalIterator __j = __last;
- while (!bool(__comp(*__i, *--__j)))
+ while (!__comp(--__j, __i))
{}
std::iter_swap(__i, __j);
- std::reverse(__ii, __last);
+ std::__reverse(__ii, __last,
+ std::__iterator_category(__first));
return true;
}
if (__i == __first)
{
- std::reverse(__first, __last);
+ std::__reverse(__first, __last,
+ std::__iterator_category(__first));
return false;
}
}
@@ -3767,34 +3061,8 @@
typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return false;
- _BidirectionalIterator __i = __first;
- ++__i;
- if (__i == __last)
- return false;
- __i = __last;
- --__i;
-
- for(;;)
- {
- _BidirectionalIterator __ii = __i;
- --__i;
- if (*__ii < *__i)
- {
- _BidirectionalIterator __j = __last;
- while (!(*--__j < *__i))
- {}
- std::iter_swap(__i, __j);
- std::reverse(__ii, __last);
- return true;
- }
- if (__i == __first)
- {
- std::reverse(__first, __last);
- return false;
- }
- }
+ return std::__prev_permutation(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -3825,39 +3093,28 @@
typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return false;
- _BidirectionalIterator __i = __first;
- ++__i;
- if (__i == __last)
- return false;
- __i = __last;
- --__i;
-
- for(;;)
- {
- _BidirectionalIterator __ii = __i;
- --__i;
- if (__comp(*__ii, *__i))
- {
- _BidirectionalIterator __j = __last;
- while (!bool(__comp(*--__j, *__i)))
- {}
- std::iter_swap(__i, __j);
- std::reverse(__ii, __last);
- return true;
- }
- if (__i == __first)
- {
- std::reverse(__first, __last);
- return false;
- }
- }
+ return std::__prev_permutation(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
// replace
// replace_if
+ template<typename _InputIterator, typename _OutputIterator,
+ typename _Predicate, typename _Tp>
+ _OutputIterator
+ __replace_copy_if(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result,
+ _Predicate __pred, const _Tp& __new_value)
+ {
+ for (; __first != __last; ++__first, ++__result)
+ if (__pred(__first))
+ *__result = __new_value;
+ else
+ *__result = *__first;
+ return __result;
+ }
+
/**
* @brief Copy a sequence, replacing each element of one value with another
* value.
@@ -3886,12 +3143,9 @@
typename iterator_traits<_InputIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- for (; __first != __last; ++__first, ++__result)
- if (*__first == __old_value)
- *__result = __new_value;
- else
- *__result = *__first;
- return __result;
+ return std::__replace_copy_if(__first, __last, __result,
+ __gnu_cxx::__ops::__iter_equals_val(__old_value),
+ __new_value);
}
/**
@@ -3924,15 +3178,23 @@
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- for (; __first != __last; ++__first, ++__result)
- if (__pred(*__first))
- *__result = __new_value;
- else
- *__result = *__first;
- return __result;
+ return std::__replace_copy_if(__first, __last, __result,
+ __gnu_cxx::__ops::__pred_iter(__pred),
+ __new_value);
}
-#if __cplusplus >= 201103L
+ template<typename _InputIterator, typename _Predicate>
+ typename iterator_traits<_InputIterator>::difference_type
+ __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
+ {
+ typename iterator_traits<_InputIterator>::difference_type __n = 0;
+ for (; __first != __last; ++__first)
+ if (__pred(__first))
+ ++__n;
+ return __n;
+ }
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
/**
* @brief Determines whether the elements of a sequence are sorted.
* @ingroup sorting_algorithms
@@ -3960,6 +3222,21 @@
_Compare __comp)
{ return std::is_sorted_until(__first, __last, __comp) == __last; }
+ template<typename _ForwardIterator, typename _Compare>
+ _ForwardIterator
+ __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
+ _Compare __comp)
+ {
+ if (__first == __last)
+ return __last;
+
+ _ForwardIterator __next = __first;
+ for (++__next; __next != __last; __first = __next, ++__next)
+ if (__comp(__next, __first))
+ return __next;
+ return __next;
+ }
+
/**
* @brief Determines the end of a sorted sequence.
* @ingroup sorting_algorithms
@@ -3978,14 +3255,8 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __last;
-
- _ForwardIterator __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next)
- if (*__next < *__first)
- return __next;
- return __next;
+ return std::__is_sorted_until(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -4009,14 +3280,8 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __last;
-
- _ForwardIterator __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next)
- if (__comp(*__next, *__first))
- return __next;
- return __next;
+ return std::__is_sorted_until(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
/**
@@ -4055,34 +3320,18 @@
: pair<const _Tp&, const _Tp&>(__a, __b);
}
- /**
- * @brief Return a pair of iterators pointing to the minimum and maximum
- * elements in a range.
- * @ingroup sorting_algorithms
- * @param __first Start of range.
- * @param __last End of range.
- * @return make_pair(m, M), where m is the first iterator i in
- * [__first, __last) such that no other element in the range is
- * smaller, and where M is the last iterator i in [__first, __last)
- * such that no other element in the range is larger.
- */
- template<typename _ForwardIterator>
+ template<typename _ForwardIterator, typename _Compare>
pair<_ForwardIterator, _ForwardIterator>
- minmax_element(_ForwardIterator __first, _ForwardIterator __last)
+ __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
+ _Compare __comp)
{
- // concept requirements
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_ForwardIterator>::value_type>)
- __glibcxx_requires_valid_range(__first, __last);
-
_ForwardIterator __next = __first;
if (__first == __last
|| ++__next == __last)
return std::make_pair(__first, __first);
_ForwardIterator __min, __max;
- if (*__next < *__first)
+ if (__comp(__next, __first))
{
__min = __next;
__max = __first;
@@ -4101,25 +3350,25 @@
__next = __first;
if (++__next == __last)
{
- if (*__first < *__min)
+ if (__comp(__first, __min))
__min = __first;
- else if (!(*__first < *__max))
+ else if (!__comp(__first, __max))
__max = __first;
break;
}
- if (*__next < *__first)
+ if (__comp(__next, __first))
{
- if (*__next < *__min)
+ if (__comp(__next, __min))
__min = __next;
- if (!(*__first < *__max))
+ if (!__comp(__first, __max))
__max = __first;
}
else
{
- if (*__first < *__min)
+ if (__comp(__first, __min))
__min = __first;
- if (!(*__next < *__max))
+ if (!__comp(__next, __max))
__max = __next;
}
@@ -4136,6 +3385,31 @@
* @ingroup sorting_algorithms
* @param __first Start of range.
* @param __last End of range.
+ * @return make_pair(m, M), where m is the first iterator i in
+ * [__first, __last) such that no other element in the range is
+ * smaller, and where M is the last iterator i in [__first, __last)
+ * such that no other element in the range is larger.
+ */
+ template<typename _ForwardIterator>
+ pair<_ForwardIterator, _ForwardIterator>
+ minmax_element(_ForwardIterator __first, _ForwardIterator __last)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_ForwardIterator>::value_type>)
+ __glibcxx_requires_valid_range(__first, __last);
+
+ return std::__minmax_element(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
+ }
+
+ /**
+ * @brief Return a pair of iterators pointing to the minimum and maximum
+ * elements in a range.
+ * @ingroup sorting_algorithms
+ * @param __first Start of range.
+ * @param __last End of range.
* @param __comp Comparison functor.
* @return make_pair(m, M), where m is the first iterator i in
* [__first, __last) such that no other element in the range is
@@ -4154,58 +3428,8 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- _ForwardIterator __next = __first;
- if (__first == __last
- || ++__next == __last)
- return std::make_pair(__first, __first);
-
- _ForwardIterator __min, __max;
- if (__comp(*__next, *__first))
- {
- __min = __next;
- __max = __first;
- }
- else
- {
- __min = __first;
- __max = __next;
- }
-
- __first = __next;
- ++__first;
-
- while (__first != __last)
- {
- __next = __first;
- if (++__next == __last)
- {
- if (__comp(*__first, *__min))
- __min = __first;
- else if (!__comp(*__first, *__max))
- __max = __first;
- break;
- }
-
- if (__comp(*__next, *__first))
- {
- if (__comp(*__next, *__min))
- __min = __next;
- if (!__comp(*__first, *__max))
- __max = __first;
- }
- else
- {
- if (__comp(*__first, *__min))
- __min = __first;
- if (!__comp(*__next, *__max))
- __max = __next;
- }
-
- __first = __next;
- ++__first;
- }
-
- return std::make_pair(__min, __max);
+ return std::__minmax_element(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
// N2722 + DR 915.
@@ -4247,27 +3471,16 @@
return std::make_pair(*__p.first, *__p.second);
}
- /**
- * @brief Checks whether a permutaion of the second sequence is equal
- * to the first sequence.
- * @ingroup non_mutating_algorithms
- * @param __first1 Start of first range.
- * @param __last1 End of first range.
- * @param __first2 Start of second range.
- * @return true if there exists a permutation of the elements in the range
- * [__first2, __first2 + (__last1 - __first1)), beginning with
- * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
- * returns true; otherwise, returns false.
- */
- template<typename _ForwardIterator1, typename _ForwardIterator2>
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
bool
- is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2)
+ __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _BinaryPredicate __pred)
{
// Efficiently compare identical prefixes: O(N) if sequences
// have the same elements in the same order.
for (; __first1 != __last1; ++__first1, ++__first2)
- if (!(*__first1 == *__first2))
+ if (!__pred(__first1, __first2))
break;
if (__first1 == __last1)
@@ -4279,12 +3492,17 @@
std::advance(__last2, std::distance(__first1, __last1));
for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
{
- if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
+ if (__scan != std::__find_if(__first1, __scan,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
continue; // We've seen this one before.
-
- auto __matches = std::count(__first2, __last2, *__scan);
- if (0 == __matches
- || std::count(__scan, __last1, *__scan) != __matches)
+
+ auto __matches
+ = std::__count_if(__first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
+ if (0 == __matches ||
+ std::__count_if(__scan, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
+ != __matches)
return false;
}
return true;
@@ -4297,6 +3515,35 @@
* @param __first1 Start of first range.
* @param __last1 End of first range.
* @param __first2 Start of second range.
+ * @return true if there exists a permutation of the elements in the range
+ * [__first2, __first2 + (__last1 - __first1)), beginning with
+ * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
+ * returns true; otherwise, returns false.
+ */
+ template<typename _ForwardIterator1, typename _ForwardIterator2>
+ bool
+ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2)
+ {
+ // 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_requires_valid_range(__first1, __last1);
+
+ return std::__is_permutation(__first1, __last1, __first2,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
+ }
+
+ /**
+ * @brief Checks whether a permutation of the second sequence is equal
+ * to the first sequence.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 Start of first range.
+ * @param __last1 End of first range.
+ * @param __first2 Start of second range.
* @param __pred A binary predicate.
* @return true if there exists a permutation of the elements in
* the range [__first2, __first2 + (__last1 - __first1)),
@@ -4310,38 +3557,79 @@
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _BinaryPredicate __pred)
{
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
+ __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
+ typename iterator_traits<_ForwardIterator1>::value_type,
+ typename iterator_traits<_ForwardIterator2>::value_type>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+
+ return std::__is_permutation(__first1, __last1, __first2,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred));
+ }
+
+#if __cplusplus > 201103L
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ bool
+ __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+ _BinaryPredicate __pred)
+ {
+ using _Cat1
+ = typename iterator_traits<_ForwardIterator1>::iterator_category;
+ using _Cat2
+ = typename iterator_traits<_ForwardIterator2>::iterator_category;
+ using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
+ using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
+ constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
+ if (__ra_iters)
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 != __d2)
+ return false;
+ }
+
// Efficiently compare identical prefixes: O(N) if sequences
// have the same elements in the same order.
for (; __first1 != __last1; ++__first1, ++__first2)
- if (!bool(__pred(*__first1, *__first2)))
+ if (!__pred(__first1, __first2))
break;
- if (__first1 == __last1)
- return true;
+ if (__ra_iters)
+ {
+ if (__first1 == __last1)
+ return true;
+ }
+ else
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 == 0 && __d2 == 0)
+ return true;
+ if (__d1 != __d2)
+ return false;
+ }
- // Establish __last2 assuming equal ranges by iterating over the
- // rest of the list.
- _ForwardIterator2 __last2 = __first2;
- std::advance(__last2, std::distance(__first1, __last1));
for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
{
- using std::placeholders::_1;
-
- if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
- std::bind(__pred, _1, *__scan)))
+ if (__scan != std::__find_if(__first1, __scan,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
continue; // We've seen this one before.
-
- auto __matches = std::count_if(__first2, __last2,
- std::bind(__pred, _1, *__scan));
+
+ auto __matches = std::__count_if(__first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
if (0 == __matches
- || std::count_if(__scan, __last1,
- std::bind(__pred, _1, *__scan)) != __matches)
+ || std::__count_if(__scan, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
+ != __matches)
return false;
}
return true;
}
-#if __cplusplus > 201103L
/**
* @brief Checks whether a permutaion of the second sequence is equal
* to the first sequence.
@@ -4360,43 +3648,12 @@
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
- using _Cat1
- = typename iterator_traits<_ForwardIterator1>::iterator_category;
- using _Cat2
- = typename iterator_traits<_ForwardIterator2>::iterator_category;
- using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
- using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
- if (_It1_is_RA() && _It2_is_RA())
- {
- auto __d1 = std::distance(__first1, __last1);
- auto __d2 = std::distance(__first2, __last2);
- if (__d1 != __d2)
- return false;
- }
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
- // Efficiently compare identical prefixes: O(N) if sequences
- // have the same elements in the same order.
- for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
- if (!(*__first1 == *__first2))
- break;
-
- if (__first1 == __last1 && __first2 == __last2)
- return true;
-
- if (std::distance(__first1, __last1) != std::distance(__first2, __last2))
- return false;
-
- for (auto __scan = __first1; __scan != __last1; ++__scan)
- {
- if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
- continue; // We've seen this one before.
-
- auto __matches = std::count(__first2, __last2, *__scan);
- if (0 == __matches
- || std::count(__scan, __last1, *__scan) != __matches)
- return false;
- }
- return true;
+ return
+ std::__is_permutation(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
}
/**
@@ -4420,58 +3677,11 @@
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate __pred)
{
- using _Cat1
- = typename iterator_traits<_ForwardIterator1>::iterator_category;
- using _Cat2
- = typename iterator_traits<_ForwardIterator2>::iterator_category;
- using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
- using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
- constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
- if (__ra_iters)
- {
- auto __d1 = std::distance(__first1, __last1);
- auto __d2 = std::distance(__first2, __last2);
- if (__d1 != __d2)
- return false;
- }
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
- // Efficiently compare identical prefixes: O(N) if sequences
- // have the same elements in the same order.
- for (; __first1 != __last1; ++__first1, ++__first2)
- if (!bool(__pred(*__first1, *__first2)))
- break;
-
- if (__ra_iters)
- {
- if (__first1 == __last1)
- return true;
- }
- else
- {
- auto __d1 = std::distance(__first1, __last1);
- auto __d2 = std::distance(__first2, __last2);
- if (__d1 == 0 && __d2 == 0)
- return true;
- if (__d1 != __d2)
- return false;
- }
-
- for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
- {
- using std::placeholders::_1;
-
- if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
- std::bind(__pred, _1, *__scan)))
- continue; // We've seen this one before.
-
- auto __matches = std::count_if(__first2, __last2,
- std::bind(__pred, _1, *__scan));
- if (0 == __matches
- || std::count_if(__scan, __last1,
- std::bind(__pred, _1, *__scan)) != __matches)
- return false;
- }
- return true;
+ return std::__is_permutation(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred));
}
#endif
@@ -4540,6 +3750,7 @@
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_requires_valid_range(__first, __last);
+
for (; __first != __last; ++__first)
__f(*__first);
return _GLIBCXX_MOVE(__f);
@@ -4564,8 +3775,9 @@
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- return std::__find(__first, __last, __val,
- std::__iterator_category(__first));
+
+ return std::__find_if(__first, __last,
+ __gnu_cxx::__ops::__iter_equals_val(__val));
}
/**
@@ -4588,8 +3800,9 @@
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- return std::__find_if(__first, __last, __pred,
- std::__iterator_category(__first));
+
+ return std::__find_if(__first, __last,
+ __gnu_cxx::__ops::__pred_iter(__pred));
}
/**
@@ -4689,16 +3902,9 @@
__glibcxx_function_requires(_EqualityComparableConcept<
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __last;
- _ForwardIterator __next = __first;
- while(++__next != __last)
- {
- if (*__first == *__next)
- return __first;
- __first = __next;
- }
- return __last;
+
+ return std::__adjacent_find(__first, __last,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
}
/**
@@ -4723,16 +3929,9 @@
typename iterator_traits<_ForwardIterator>::value_type,
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __last;
- _ForwardIterator __next = __first;
- while(++__next != __last)
- {
- if (__binary_pred(*__first, *__next))
- return __first;
- __first = __next;
- }
- return __last;
+
+ return std::__adjacent_find(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
}
/**
@@ -4751,13 +3950,11 @@
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_InputIterator>::value_type, _Tp>)
+ typename iterator_traits<_InputIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- typename iterator_traits<_InputIterator>::difference_type __n = 0;
- for (; __first != __last; ++__first)
- if (*__first == __value)
- ++__n;
- return __n;
+
+ return std::__count_if(__first, __last,
+ __gnu_cxx::__ops::__iter_equals_val(__value));
}
/**
@@ -4778,11 +3975,9 @@
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- typename iterator_traits<_InputIterator>::difference_type __n = 0;
- for (; __first != __last; ++__first)
- if (__pred(*__first))
- ++__n;
- return __n;
+
+ return std::__count_if(__first, __last,
+ __gnu_cxx::__ops::__pred_iter(__pred));
}
/**
@@ -4825,40 +4020,8 @@
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- // Test for empty ranges
- if (__first1 == __last1 || __first2 == __last2)
- return __first1;
-
- // Test for a pattern of length 1.
- _ForwardIterator2 __p1(__first2);
- if (++__p1 == __last2)
- return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
-
- // General case.
- _ForwardIterator2 __p;
- _ForwardIterator1 __current = __first1;
-
- for (;;)
- {
- __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
- if (__first1 == __last1)
- return __last1;
-
- __p = __p1;
- __current = __first1;
- if (++__current == __last1)
- return __last1;
-
- while (*__current == *__p)
- {
- if (++__p == __last2)
- return __first1;
- if (++__current == __last1)
- return __last1;
- }
- ++__first1;
- }
- return __first1;
+ return std::__search(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
}
/**
@@ -4898,50 +4061,10 @@
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- // Test for empty ranges
- if (__first1 == __last1 || __first2 == __last2)
- return __first1;
-
- // Test for a pattern of length 1.
- _ForwardIterator2 __p1(__first2);
- if (++__p1 == __last2)
- {
- while (__first1 != __last1
- && !bool(__predicate(*__first1, *__first2)))
- ++__first1;
- return __first1;
- }
-
- // General case.
- _ForwardIterator2 __p;
- _ForwardIterator1 __current = __first1;
-
- for (;;)
- {
- while (__first1 != __last1
- && !bool(__predicate(*__first1, *__first2)))
- ++__first1;
- if (__first1 == __last1)
- return __last1;
-
- __p = __p1;
- __current = __first1;
- if (++__current == __last1)
- return __last1;
-
- while (__predicate(*__current, *__p))
- {
- if (++__p == __last2)
- return __first1;
- if (++__current == __last1)
- return __last1;
- }
- ++__first1;
- }
- return __first1;
+ return std::__search(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate));
}
-
/**
* @brief Search a sequence for a number of consecutive values.
* @ingroup non_mutating_algorithms
@@ -4965,15 +4088,11 @@
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+ typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- if (__count <= 0)
- return __first;
- if (__count == 1)
- return _GLIBCXX_STD_A::find(__first, __last, __val);
- return std::__search_n(__first, __last, __count, __val,
- std::__iterator_category(__first));
+ return std::__search_n(__first, __last, __count,
+ __gnu_cxx::__ops::__iter_equals_val(__val));
}
@@ -5007,16 +4126,8 @@
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- if (__count <= 0)
- return __first;
- if (__count == 1)
- {
- while (__first != __last && !bool(__binary_pred(*__first, __val)))
- ++__first;
- return __first;
- }
- return std::__search_n(__first, __last, __count, __val, __binary_pred,
- std::__iterator_category(__first));
+ return std::__search_n(__first, __last, __count,
+ __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
}
@@ -5216,7 +4327,6 @@
return __first;
}
-
/**
* @brief Copy a sequence, removing consecutive duplicate values.
* @ingroup mutating_algorithms
@@ -5253,7 +4363,9 @@
if (__first == __last)
return __result;
+
return std::__unique_copy(__first, __last, __result,
+ __gnu_cxx::__ops::__iter_equal_to_iter(),
std::__iterator_category(__first),
std::__iterator_category(__result));
}
@@ -5289,12 +4401,17 @@
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
+ __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
+ typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_InputIterator>::value_type>)
if (__first == __last)
return __result;
- return std::__unique_copy(__first, __last, __result, __binary_pred,
- std::__iterator_category(__first),
- std::__iterator_category(__result));
+
+ return std::__unique_copy(__first, __last, __result,
+ __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
+ std::__iterator_category(__first),
+ std::__iterator_category(__result));
}
@@ -5390,7 +4507,6 @@
}
-
/**
* @brief Sort the smallest elements of a sequence.
* @ingroup sorting_algorithms
@@ -5413,18 +4529,16 @@
_RandomAccessIterator __middle,
_RandomAccessIterator __last)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
- std::__heap_select(__first, __middle, __last);
- std::sort_heap(__first, __middle);
+ std::__partial_sort(__first, __middle, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -5453,19 +4567,17 @@
_RandomAccessIterator __last,
_Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType, _ValueType>)
+ typename iterator_traits<_RandomAccessIterator>::value_type,
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
- std::__heap_select(__first, __middle, __last, __comp);
- std::sort_heap(__first, __middle, __comp);
+ std::__partial_sort(__first, __middle, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
/**
@@ -5488,13 +4600,11 @@
nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __nth);
__glibcxx_requires_valid_range(__nth, __last);
@@ -5502,7 +4612,8 @@
return;
std::__introselect(__first, __nth, __last,
- std::__lg(__last - __first) * 2);
+ std::__lg(__last - __first) * 2,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -5527,14 +4638,12 @@
nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType, _ValueType>)
+ typename iterator_traits<_RandomAccessIterator>::value_type,
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __nth);
__glibcxx_requires_valid_range(__nth, __last);
@@ -5542,10 +4651,10 @@
return;
std::__introselect(__first, __nth, __last,
- std::__lg(__last - __first) * 2, __comp);
+ std::__lg(__last - __first) * 2,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
-
/**
* @brief Sort the elements of a sequence.
* @ingroup sorting_algorithms
@@ -5564,21 +4673,14 @@
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first != __last)
- {
- std::__introsort_loop(__first, __last,
- std::__lg(__last - __first) * 2);
- std::__final_insertion_sort(__first, __last);
- }
+ std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -5601,22 +4703,40 @@
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
- _ValueType>)
+ __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
+ typename iterator_traits<_RandomAccessIterator>::value_type,
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first != __last)
+ std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator, typename _Compare>
+ _OutputIterator
+ __merge(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result, _Compare __comp)
+ {
+ while (__first1 != __last1 && __first2 != __last2)
{
- std::__introsort_loop(__first, __last,
- std::__lg(__last - __first) * 2, __comp);
- std::__final_insertion_sort(__first, __last, __comp);
+ if (__comp(__first2, __first1))
+ {
+ *__result = *__first2;
+ ++__first2;
+ }
+ else
+ {
+ *__result = *__first1;
+ ++__first1;
+ }
+ ++__result;
}
+ return std::copy(__first2, __last2,
+ std::copy(__first1, __last1, __result));
}
/**
@@ -5645,38 +4765,22 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set(__first1, __last1, __first2);
__glibcxx_requires_sorted_set(__first2, __last2, __first1);
- while (__first1 != __last1 && __first2 != __last2)
- {
- if (*__first2 < *__first1)
- {
- *__result = *__first2;
- ++__first2;
- }
- else
- {
- *__result = *__first1;
- ++__first1;
- }
- ++__result;
- }
- return std::copy(__first2, __last2, std::copy(__first1, __last1,
- __result));
+ return _GLIBCXX_STD_A::__merge(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -5709,42 +4813,44 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result, _Compare __comp)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType2>)
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
- while (__first1 != __last1 && __first2 != __last2)
- {
- if (__comp(*__first2, *__first1))
- {
- *__result = *__first2;
- ++__first2;
- }
- else
- {
- *__result = *__first1;
- ++__first1;
- }
- ++__result;
- }
- return std::copy(__first2, __last2, std::copy(__first1, __last1,
- __result));
+ return _GLIBCXX_STD_A::__merge(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline void
+ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Compare __comp)
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
+ typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
+ _TmpBuf __buf(__first, __last);
+
+ if (__buf.begin() == 0)
+ std::__inplace_stable_sort(__first, __last, __comp);
+ else
+ std::__stable_sort_adaptive(__first, __last, __buf.begin(),
+ _DistanceType(__buf.size()), __comp);
+ }
+
/**
* @brief Sort the elements of a sequence, preserving the relative order
* of equivalent elements.
@@ -5766,24 +4872,15 @@
inline void
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
- __last);
- if (__buf.begin() == 0)
- std::__inplace_stable_sort(__first, __last);
- else
- std::__stable_sort_adaptive(__first, __last, __buf.begin(),
- _DistanceType(__buf.size()));
+ _GLIBCXX_STD_A::__stable_sort(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -5809,28 +4906,49 @@
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType,
- _ValueType>)
+ typename iterator_traits<_RandomAccessIterator>::value_type,
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
- __last);
- if (__buf.begin() == 0)
- std::__inplace_stable_sort(__first, __last, __comp);
- else
- std::__stable_sort_adaptive(__first, __last, __buf.begin(),
- _DistanceType(__buf.size()), __comp);
+ _GLIBCXX_STD_A::__stable_sort(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare>
+ _OutputIterator
+ __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result, _Compare __comp)
+ {
+ while (__first1 != __last1 && __first2 != __last2)
+ {
+ if (__comp(__first1, __first2))
+ {
+ *__result = *__first1;
+ ++__first1;
+ }
+ else if (__comp(__first2, __first1))
+ {
+ *__result = *__first2;
+ ++__first2;
+ }
+ else
+ {
+ *__result = *__first1;
+ ++__first1;
+ ++__first2;
+ }
+ ++__result;
+ }
+ return std::copy(__first2, __last2,
+ std::copy(__first1, __last1, __result));
+ }
/**
* @brief Return the union of two sorted ranges.
@@ -5857,45 +4975,25 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set(__first1, __last1, __first2);
__glibcxx_requires_sorted_set(__first2, __last2, __first1);
- while (__first1 != __last1 && __first2 != __last2)
- {
- if (*__first1 < *__first2)
- {
- *__result = *__first1;
- ++__first1;
- }
- else if (*__first2 < *__first1)
- {
- *__result = *__first2;
- ++__first2;
- }
- else
- {
- *__result = *__first1;
- ++__first1;
- ++__first2;
- }
- ++__result;
- }
- return std::copy(__first2, __last2, std::copy(__first1, __last1,
- __result));
+ return _GLIBCXX_STD_A::__set_union(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -5924,47 +5022,48 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result, _Compare __comp)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType2>)
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType1, _ValueType2>)
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+ return _GLIBCXX_STD_A::__set_union(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare>
+ _OutputIterator
+ __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result, _Compare __comp)
+ {
while (__first1 != __last1 && __first2 != __last2)
- {
- if (__comp(*__first1, *__first2))
- {
- *__result = *__first1;
- ++__first1;
- }
- else if (__comp(*__first2, *__first1))
- {
- *__result = *__first2;
- ++__first2;
- }
- else
- {
- *__result = *__first1;
- ++__first1;
- ++__first2;
- }
- ++__result;
- }
- return std::copy(__first2, __last2, std::copy(__first1, __last1,
- __result));
+ if (__comp(__first1, __first2))
+ ++__first1;
+ else if (__comp(__first2, __first1))
+ ++__first2;
+ else
+ {
+ *__result = *__first1;
+ ++__first1;
+ ++__first2;
+ ++__result;
+ }
+ return __result;
}
/**
@@ -5991,34 +5090,23 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set(__first1, __last1, __first2);
__glibcxx_requires_sorted_set(__first2, __last2, __first1);
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first1 < *__first2)
- ++__first1;
- else if (*__first2 < *__first1)
- ++__first2;
- else
- {
- *__result = *__first1;
- ++__first1;
- ++__first2;
- ++__result;
- }
- return __result;
+ return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -6048,36 +5136,48 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result, _Compare __comp)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType1, _ValueType2>)
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+ return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare>
+ _OutputIterator
+ __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result, _Compare __comp)
+ {
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
- ++__first1;
- else if (__comp(*__first2, *__first1))
+ if (__comp(__first1, __first2))
+ {
+ *__result = *__first1;
+ ++__first1;
+ ++__result;
+ }
+ else if (__comp(__first2, __first1))
++__first2;
else
{
- *__result = *__first1;
++__first1;
++__first2;
- ++__result;
}
- return __result;
+ return std::copy(__first1, __last1, __result);
}
/**
@@ -6106,36 +5206,23 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set(__first1, __last1, __first2);
__glibcxx_requires_sorted_set(__first2, __last2, __first1);
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first1 < *__first2)
- {
- *__result = *__first1;
- ++__first1;
- ++__result;
- }
- else if (*__first2 < *__first1)
- ++__first2;
- else
- {
- ++__first1;
- ++__first2;
- }
- return std::copy(__first1, __last1, __result);
+ return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -6167,38 +5254,56 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result, _Compare __comp)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType1, _ValueType2>)
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+ return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare>
+ _OutputIterator
+ __set_symmetric_difference(_InputIterator1 __first1,
+ _InputIterator1 __last1,
+ _InputIterator2 __first2,
+ _InputIterator2 __last2,
+ _OutputIterator __result,
+ _Compare __comp)
+ {
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
+ if (__comp(__first1, __first2))
{
*__result = *__first1;
++__first1;
++__result;
}
- else if (__comp(*__first2, *__first1))
- ++__first2;
+ else if (__comp(__first2, __first1))
+ {
+ *__result = *__first2;
+ ++__first2;
+ ++__result;
+ }
else
{
++__first1;
++__first2;
}
- return std::copy(__first1, __last1, __result);
+ return std::copy(__first2, __last2,
+ std::copy(__first1, __last1, __result));
}
/**
@@ -6225,43 +5330,25 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set(__first1, __last1, __first2);
__glibcxx_requires_sorted_set(__first2, __last2, __first1);
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first1 < *__first2)
- {
- *__result = *__first1;
- ++__first1;
- ++__result;
- }
- else if (*__first2 < *__first1)
- {
- *__result = *__first2;
- ++__first2;
- ++__result;
- }
- else
- {
- ++__first1;
- ++__first2;
- }
- return std::copy(__first2, __last2, std::copy(__first1,
- __last1, __result));
+ return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -6292,47 +5379,40 @@
_OutputIterator __result,
_Compare __comp)
{
- typedef typename iterator_traits<_InputIterator1>::value_type
- _ValueType1;
- typedef typename iterator_traits<_InputIterator2>::value_type
- _ValueType2;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType1>)
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- _ValueType2>)
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType1, _ValueType2>)
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- _ValueType2, _ValueType1>)
+ typename iterator_traits<_InputIterator2>::value_type,
+ typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
- while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
- {
- *__result = *__first1;
- ++__first1;
- ++__result;
- }
- else if (__comp(*__first2, *__first1))
- {
- *__result = *__first2;
- ++__first2;
- ++__result;
- }
- else
- {
- ++__first1;
- ++__first2;
- }
- return std::copy(__first2, __last2,
- std::copy(__first1, __last1, __result));
+ return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
+ __first2, __last2, __result,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
+ template<typename _ForwardIterator, typename _Compare>
+ _ForwardIterator
+ __min_element(_ForwardIterator __first, _ForwardIterator __last,
+ _Compare __comp)
+ {
+ if (__first == __last)
+ return __first;
+ _ForwardIterator __result = __first;
+ while (++__first != __last)
+ if (__comp(__first, __result))
+ __result = __first;
+ return __result;
+ }
/**
* @brief Return the minimum element in a range.
@@ -6351,13 +5431,8 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __first;
- _ForwardIterator __result = __first;
- while (++__first != __last)
- if (*__first < *__result)
- __result = __first;
- return __result;
+ return _GLIBCXX_STD_A::__min_element(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -6381,11 +5456,19 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __first;
+ return _GLIBCXX_STD_A::__min_element(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ }
+
+ template<typename _ForwardIterator, typename _Compare>
+ _ForwardIterator
+ __max_element(_ForwardIterator __first, _ForwardIterator __last,
+ _Compare __comp)
+ {
+ if (__first == __last) return __first;
_ForwardIterator __result = __first;
while (++__first != __last)
- if (__comp(*__first, *__result))
+ if (__comp(__result, __first))
__result = __first;
return __result;
}
@@ -6407,13 +5490,8 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __first;
- _ForwardIterator __result = __first;
- while (++__first != __last)
- if (*__result < *__first)
- __result = __first;
- return __result;
+ return _GLIBCXX_STD_A::__max_element(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -6437,12 +5515,8 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last) return __first;
- _ForwardIterator __result = __first;
- while (++__first != __last)
- if (__comp(*__result, *__first))
- __result = __first;
- return __result;
+ return _GLIBCXX_STD_A::__max_element(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
_GLIBCXX_END_NAMESPACE_ALGO
Index: include/bits/predefined_ops.h
===================================================================
--- include/bits/predefined_ops.h (revision 0)
+++ include/bits/predefined_ops.h (revision 0)
@@ -0,0 +1,304 @@
+// Default predicates for internal use -*- C++ -*-
+
+// Copyright (C) 2013 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 3, 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file predefined_ops.h
+ * This is an internal header file, included by other library headers.
+ * You should not attempt to use it directly.
+ */
+
+#ifndef _GLIBCXX_PREDEFINED_OPS_H
+#define _GLIBCXX_PREDEFINED_OPS_H 1
+
+namespace __gnu_cxx
+{
+namespace __ops
+{
+ struct _Iter_less_iter
+ {
+ template<typename _Iterator1, typename _Iterator2>
+ bool
+ operator()(_Iterator1 __it1, _Iterator2 __it2) const
+ { return *__it1 < *__it2; }
+ };
+
+ inline _Iter_less_iter
+ __iter_less_iter()
+ { return _Iter_less_iter(); }
+
+ struct _Iter_less_val
+ {
+ template<typename _Iterator, typename _Value>
+ bool
+ operator()(_Iterator __it, _Value& __val) const
+ { return *__it < __val; }
+ };
+
+ inline _Iter_less_val
+ __iter_less_val()
+ { return _Iter_less_val(); }
+
+ inline _Iter_less_val
+ __iter_comp_val(_Iter_less_iter)
+ { return _Iter_less_val(); }
+
+ struct _Val_less_iter
+ {
+ template<typename _Value, typename _Iterator>
+ bool
+ operator()(_Value& __val, _Iterator __it) const
+ { return __val < *__it; }
+ };
+
+ inline _Val_less_iter
+ __val_less_iter()
+ { return _Val_less_iter(); }
+
+ inline _Val_less_iter
+ __val_comp_iter(_Iter_less_iter)
+ { return _Val_less_iter(); }
+
+ struct _Iter_equal_to_iter
+ {
+ template<typename _Iterator1, typename _Iterator2>
+ bool
+ operator()(_Iterator1 __it1, _Iterator2 __it2) const
+ { return *__it1 == *__it2; }
+ };
+
+ inline _Iter_equal_to_iter
+ __iter_equal_to_iter()
+ { return _Iter_equal_to_iter(); }
+
+ struct _Iter_equal_to_val
+ {
+ template<typename _Iterator, typename _Value>
+ bool
+ operator()(_Iterator __it, _Value& __val) const
+ { return *__it == __val; }
+ };
+
+ inline _Iter_equal_to_val
+ __iter_equal_to_val()
+ { return _Iter_equal_to_val(); }
+
+ inline _Iter_equal_to_val
+ __iter_comp_val(_Iter_equal_to_iter)
+ { return _Iter_equal_to_val(); }
+
+ template<typename _Compare>
+ struct _Iter_comp_iter
+ {
+ _Compare _M_comp;
+
+ _Iter_comp_iter(_Compare __comp)
+ : _M_comp(__comp)
+ { }
+
+ template<typename _Iterator1, typename _Iterator2>
+ bool
+ operator()(_Iterator1 __it1, _Iterator2 __it2)
+ { return bool(_M_comp(*__it1, *__it2)); }
+ };
+
+ template<typename _Compare>
+ inline _Iter_comp_iter<_Compare>
+ __iter_comp_iter(_Compare __comp)
+ { return _Iter_comp_iter<_Compare>(__comp); }
+
+ template<typename _Compare>
+ struct _Iter_comp_val
+ {
+ _Compare _M_comp;
+
+ _Iter_comp_val(_Compare __comp)
+ : _M_comp(__comp)
+ { }
+
+ template<typename _Iterator, typename _Value>
+ bool
+ operator()(_Iterator __it, _Value& __val)
+ { return bool(_M_comp(*__it, __val)); }
+ };
+
+ template<typename _Compare>
+ inline _Iter_comp_val<_Compare>
+ __iter_comp_val(_Compare __comp)
+ { return _Iter_comp_val<_Compare>(__comp); }
+
+ template<typename _Compare>
+ inline _Iter_comp_val<_Compare>
+ __iter_comp_val(_Iter_comp_iter<_Compare> __comp)
+ { return _Iter_comp_val<_Compare>(__comp._M_comp); }
+
+ template<typename _Compare>
+ struct _Val_comp_iter
+ {
+ _Compare _M_comp;
+
+ _Val_comp_iter(_Compare __comp)
+ : _M_comp(__comp)
+ { }
+
+ template<typename _Value, typename _Iterator>
+ bool
+ operator()(_Value& __val, _Iterator __it)
+ { return bool(_M_comp(__val, *__it)); }
+ };
+
+ template<typename _Compare>
+ inline _Val_comp_iter<_Compare>
+ __val_comp_iter(_Compare __comp)
+ { return _Val_comp_iter<_Compare>(__comp); }
+
+ template<typename _Compare>
+ inline _Val_comp_iter<_Compare>
+ __val_comp_iter(_Iter_comp_iter<_Compare> __comp)
+ { return _Val_comp_iter<_Compare>(__comp._M_comp); }
+
+ template<typename _Value>
+ struct _Iter_equals_val
+ {
+ _Value& _M_value;
+
+ _Iter_equals_val(_Value& __value)
+ : _M_value(__value)
+ { }
+
+ template<typename _Iterator>
+ bool
+ operator()(_Iterator __it)
+ { return *__it == _M_value; }
+ };
+
+ template<typename _Value>
+ inline _Iter_equals_val<_Value>
+ __iter_equals_val(_Value& __val)
+ { return _Iter_equals_val<_Value>(__val); }
+
+ template<typename _Iterator1>
+ struct _Iter_equals_iter
+ {
+ typename std::iterator_traits<_Iterator1>::reference _M_ref;
+
+ _Iter_equals_iter(_Iterator1 __it1)
+ : _M_ref(*__it1)
+ { }
+
+ template<typename _Iterator2>
+ bool
+ operator()(_Iterator2 __it2)
+ { return *__it2 == _M_ref; }
+ };
+
+ template<typename _Iterator>
+ inline _Iter_equals_iter<_Iterator>
+ __iter_comp_iter(_Iter_equal_to_iter, _Iterator __it)
+ { return _Iter_equals_iter<_Iterator>(__it); }
+
+ template<typename _Predicate>
+ struct _Iter_pred
+ {
+ _Predicate _M_pred;
+
+ _Iter_pred(_Predicate __pred)
+ : _M_pred(__pred)
+ { }
+
+ template<typename _Iterator>
+ bool
+ operator()(_Iterator __it)
+ { return bool(_M_pred(*__it)); }
+ };
+
+ template<typename _Predicate>
+ inline _Iter_pred<_Predicate>
+ __pred_iter(_Predicate __pred)
+ { return _Iter_pred<_Predicate>(__pred); }
+
+ template<typename _Compare, typename _Value>
+ struct _Iter_comp_to_val
+ {
+ _Compare _M_comp;
+ _Value& _M_value;
+
+ _Iter_comp_to_val(_Compare __comp, _Value& __value)
+ : _M_comp(__comp), _M_value(__value)
+ { }
+
+ template<typename _Iterator>
+ bool
+ operator()(_Iterator __it)
+ { return bool(_M_comp(*__it, _M_value)); }
+ };
+
+ template<typename _Compare, typename _Value>
+ _Iter_comp_to_val<_Compare, _Value>
+ __iter_comp_val(_Compare __comp, _Value &__val)
+ { return _Iter_comp_to_val<_Compare, _Value>(__comp, __val); }
+
+ template<typename _Compare, typename _Iterator1>
+ struct _Iter_comp_to_iter
+ {
+ _Compare _M_comp;
+ typename std::iterator_traits<_Iterator1>::reference _M_ref;
+
+ _Iter_comp_to_iter(_Compare __comp, _Iterator1 __it1)
+ : _M_comp(__comp), _M_ref(*__it1)
+ { }
+
+ template<typename _Iterator2>
+ bool
+ operator()(_Iterator2 __it2)
+ { return bool(_M_comp(*__it2, _M_ref)); }
+ };
+
+ template<typename _Compare, typename _Iterator>
+ inline _Iter_comp_to_iter<_Compare, _Iterator>
+ __iter_comp_iter(_Iter_comp_iter<_Compare> __comp, _Iterator __it)
+ { return _Iter_comp_to_iter<_Compare, _Iterator>(__comp._M_comp, __it); }
+
+ template<typename _Predicate>
+ struct _Iter_negate
+ {
+ _Predicate _M_pred;
+
+ _Iter_negate(_Predicate __pred)
+ : _M_pred(__pred)
+ { }
+
+ template<typename _Iterator>
+ bool
+ operator()(_Iterator __it)
+ { return !bool(_M_pred(*__it)); }
+ };
+
+ template<typename _Predicate>
+ inline _Iter_negate<_Predicate>
+ __negate(_Iter_pred<_Predicate> __pred)
+ { return _Iter_negate<_Predicate>(__pred._M_pred); }
+
+} // namespace __ops
+} // namespace __gnu_cxx
+
+#endif
Property changes on: include/bits/predefined_ops.h
___________________________________________________________________
Added: svn:eol-style
+ native
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h (revision 202818)
+++ include/bits/stl_algobase.h (working copy)
@@ -68,6 +68,7 @@
#include <bits/concept_check.h>
#include <debug/debug.h>
#include <bits/move.h> // For std::swap and _GLIBCXX_MOVE
+#include <bits/predefined_ops.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -862,6 +863,28 @@
{ return true; }
};
+ template<typename _II1, typename _II2, typename _Compare>
+ bool
+ __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2,
+ _Compare __comp)
+ {
+ typedef typename iterator_traits<_II1>::iterator_category _Category1;
+ typedef typename iterator_traits<_II2>::iterator_category _Category2;
+ typedef std::__lc_rai<_Category1, _Category2> __rai_type;
+
+ __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
+ for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
+ ++__first1, ++__first2)
+ {
+ if (__comp(__first1, __first2))
+ return true;
+ if (__comp(__first2, __first1))
+ return false;
+ }
+ return __first1 == __last1 && __first2 != __last2;
+ }
+
template<bool _BoolType>
struct __lexicographical_compare
{
@@ -875,21 +898,9 @@
__lexicographical_compare<_BoolType>::
__lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
{
- typedef typename iterator_traits<_II1>::iterator_category _Category1;
- typedef typename iterator_traits<_II2>::iterator_category _Category2;
- typedef std::__lc_rai<_Category1, _Category2> __rai_type;
-
- __last1 = __rai_type::__newlast1(__first1, __last1,
- __first2, __last2);
- for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
- ++__first1, ++__first2)
- {
- if (*__first1 < *__first2)
- return true;
- if (*__first2 < *__first1)
- return false;
- }
- return __first1 == __last1 && __first2 != __last2;
+ return std::__lexicographical_compare_impl(
+ __first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_less_iter());
}
template<>
@@ -926,34 +937,14 @@
__first2, __last2);
}
- /**
- * @brief Finds the first position in which @a val could be inserted
- * without changing the ordering.
- * @param __first An iterator.
- * @param __last Another iterator.
- * @param __val The search term.
- * @return An iterator pointing to the first element <em>not less
- * than</em> @a val, or end() if every element is less than
- * @a val.
- * @ingroup binary_search_algorithms
- */
- template<typename _ForwardIterator, typename _Tp>
+ template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator
- lower_bound(_ForwardIterator __first, _ForwardIterator __last,
- const _Tp& __val)
+ __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val, _Compare __comp)
{
-#ifdef _GLIBCXX_CONCEPT_CHECKS
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
-#endif
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
- // concept requirements
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
- __glibcxx_requires_partitioned_lower(__first, __last, __val);
-
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
@@ -961,7 +952,7 @@
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
- if (*__middle < __val)
+ if (__comp(__middle, __val))
{
__first = __middle;
++__first;
@@ -973,6 +964,32 @@
return __first;
}
+ /**
+ * @brief Finds the first position in which @a val could be inserted
+ * without changing the ordering.
+ * @param __first An iterator.
+ * @param __last Another iterator.
+ * @param __val The search term.
+ * @return An iterator pointing to the first element <em>not less
+ * than</em> @a val, or end() if every element is less than
+ * @a val.
+ * @ingroup binary_search_algorithms
+ */
+ template<typename _ForwardIterator, typename _Tp>
+ _ForwardIterator
+ lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+ __glibcxx_requires_partitioned_lower(__first, __last, __val);
+
+ return std::__lower_bound(__first, __last, __val,
+ __gnu_cxx::__ops::__iter_less_val());
+ }
+
/// This is a helper function for the sort routines and for random.tcc.
// Precondition: __n > 0.
inline _GLIBCXX_CONSTEXPR int
@@ -1212,28 +1229,31 @@
lexicographical_compare(_II1 __first1, _II1 __last1,
_II2 __first2, _II2 __last2, _Compare __comp)
{
- typedef typename iterator_traits<_II1>::iterator_category _Category1;
- typedef typename iterator_traits<_II2>::iterator_category _Category2;
- typedef std::__lc_rai<_Category1, _Category2> __rai_type;
-
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_II1>)
__glibcxx_function_requires(_InputIteratorConcept<_II2>)
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
- for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
- ++__first1, ++__first2)
- {
- if (__comp(*__first1, *__first2))
- return true;
- if (__comp(*__first2, *__first1))
- return false;
- }
- return __first1 == __last1 && __first2 != __last2;
+ return std::__lexicographical_compare_impl
+ (__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _BinaryPredicate>
+ pair<_InputIterator1, _InputIterator2>
+ __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _BinaryPredicate __binary_pred)
+ {
+ while (__first1 != __last1 && __binary_pred(__first1, __first2))
+ {
+ ++__first1;
+ ++__first2;
+ }
+ return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+ }
+
/**
* @brief Finds the places in ranges which don't match.
* @ingroup non_mutating_algorithms
@@ -1260,12 +1280,8 @@
typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_requires_valid_range(__first1, __last1);
- while (__first1 != __last1 && *__first1 == *__first2)
- {
- ++__first1;
- ++__first2;
- }
- return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+ return std::__mismatch(__first1, __last1, __first2,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
}
/**
@@ -1295,7 +1311,21 @@
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_requires_valid_range(__first1, __last1);
- while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
+ return std::__mismatch(__first1, __last1, __first2,
+ __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
+ }
+
+#if __cplusplus > 201103L
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _BinaryPredicate>
+ pair<_InputIterator1, _InputIterator2>
+ __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _BinaryPredicate __binary_pred)
+ {
+ while (__first1 != __last1 && __first2 != __last2
+ && __binary_pred(__first1, __first2))
{
++__first1;
++__first2;
@@ -1303,7 +1333,6 @@
return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
-#if __cplusplus > 201103L
/**
* @brief Finds the places in ranges which don't match.
* @ingroup non_mutating_algorithms
@@ -1332,13 +1361,8 @@
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- while (__first1 != __last1 && __first2 != __last2
- && *__first1 == *__first2)
- {
- ++__first1;
- ++__first2;
- }
- return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+ return std::__mismatch(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
}
/**
@@ -1371,13 +1395,8 @@
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- while (__first1 != __last1 && __first2 != __last2
- && bool(__binary_pred(*__first1, *__first2)))
- {
- ++__first1;
- ++__first2;
- }
- return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+ return std::__mismatch(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
}
#endif
Index: include/bits/stl_heap.h
===================================================================
--- include/bits/stl_heap.h (revision 202818)
+++ include/bits/stl_heap.h (working copy)
@@ -57,6 +57,7 @@
#include <debug/debug.h>
#include <bits/move.h>
+#include <bits/predefined_ops.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -67,21 +68,6 @@
* @ingroup sorting_algorithms
*/
- template<typename _RandomAccessIterator, typename _Distance>
- _Distance
- __is_heap_until(_RandomAccessIterator __first, _Distance __n)
- {
- _Distance __parent = 0;
- for (_Distance __child = 1; __child < __n; ++__child)
- {
- if (__first[__parent] < __first[__child])
- return __child;
- if ((__child & 1) == 0)
- ++__parent;
- }
- return __n;
- }
-
template<typename _RandomAccessIterator, typename _Distance,
typename _Compare>
_Distance
@@ -91,7 +77,7 @@
_Distance __parent = 0;
for (_Distance __child = 1; __child < __n; ++__child)
{
- if (__comp(__first[__parent], __first[__child]))
+ if (__comp(__first + __parent, __first + __child))
return __child;
if ((__child & 1) == 0)
++__parent;
@@ -104,13 +90,19 @@
template<typename _RandomAccessIterator, typename _Distance>
inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
- { return std::__is_heap_until(__first, __n) == __n; }
+ {
+ return std::__is_heap_until(__first, __n,
+ __gnu_cxx::__ops::__iter_less_iter()) == __n;
+ }
template<typename _RandomAccessIterator, typename _Compare,
typename _Distance>
inline bool
__is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
- { return std::__is_heap_until(__first, __n, __comp) == __n; }
+ {
+ return std::__is_heap_until(__first, __n,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp)) == __n;
+ }
template<typename _RandomAccessIterator>
inline bool
@@ -126,13 +118,15 @@
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
// + is_heap and is_heap_until in C++0x.
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
+ template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
+ typename _Compare>
void
__push_heap(_RandomAccessIterator __first,
- _Distance __holeIndex, _Distance __topIndex, _Tp __value)
+ _Distance __holeIndex, _Distance __topIndex, _Tp __value,
+ _Compare __comp)
{
_Distance __parent = (__holeIndex - 1) / 2;
- while (__holeIndex > __topIndex && *(__first + __parent) < __value)
+ while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
{
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
__holeIndex = __parent;
@@ -169,26 +163,10 @@
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value));
+ _DistanceType(0), _GLIBCXX_MOVE(__value),
+ __gnu_cxx::__ops::__iter_less_val());
}
- 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.
@@ -219,20 +197,23 @@
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
+ _DistanceType(0), _GLIBCXX_MOVE(__value),
+ __gnu_cxx::__ops::__iter_comp_val(__comp));
}
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
+ template<typename _RandomAccessIterator, typename _Distance,
+ typename _Tp, typename _Compare>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __len, _Tp __value)
+ _Distance __len, _Tp __value, _Compare __comp)
{
const _Distance __topIndex = __holeIndex;
_Distance __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
- if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
+ if (__comp(__first + __secondChild,
+ __first + (__secondChild - 1)))
__secondChild--;
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
__holeIndex = __secondChild;
@@ -244,14 +225,15 @@
+ (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
- std::__push_heap(__first, __holeIndex, __topIndex,
- _GLIBCXX_MOVE(__value));
+ std::__push_heap(__first, __holeIndex, __topIndex,
+ _GLIBCXX_MOVE(__value),
+ __gnu_cxx::__ops::__iter_comp_val(__comp));
}
- template<typename _RandomAccessIterator>
+ template<typename _RandomAccessIterator, typename _Compare>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result)
+ _RandomAccessIterator __result, _Compare __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -262,7 +244,7 @@
*__result = _GLIBCXX_MOVE(*__first);
std::__adjust_heap(__first, _DistanceType(0),
_DistanceType(__last - __first),
- _GLIBCXX_MOVE(__value));
+ _GLIBCXX_MOVE(__value), __comp);
}
/**
@@ -294,55 +276,11 @@
if (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last);
+ std::__pop_heap(__first, __last, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
}
- 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.
@@ -369,33 +307,21 @@
if (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last, __comp);
+ std::__pop_heap(__first, __last, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
}
- /**
- * @brief Construct a heap over a range.
- * @param __first Start of heap.
- * @param __last End of heap.
- * @ingroup heap_algorithms
- *
- * This operation makes the elements in [__first,__last) into a heap.
- */
- template<typename _RandomAccessIterator>
+ template<typename _RandomAccessIterator, typename _Compare>
void
- make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+ __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Compare __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;
- // concept requirements
- __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- __glibcxx_requires_valid_range(__first, __last);
-
if (__last - __first < 2)
return;
@@ -404,13 +330,37 @@
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),
+ __comp);
if (__parent == 0)
return;
__parent--;
}
}
+
+ /**
+ * @brief Construct a heap over a range.
+ * @param __first Start of heap.
+ * @param __last End of heap.
+ * @ingroup heap_algorithms
+ *
+ * This operation makes the elements in [__first,__last) into a heap.
+ */
+ template<typename _RandomAccessIterator>
+ void
+ make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
+ _RandomAccessIterator>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
+ __glibcxx_requires_valid_range(__first, __last);
+ std::__make_heap(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
+ }
+
/**
* @brief Construct a heap over a range using comparison functor.
* @param __first Start of heap.
@@ -426,29 +376,24 @@
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
- if (__last - __first < 2)
- return;
+ std::__make_heap(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ }
- const _DistanceType __len = __last - __first;
- _DistanceType __parent = (__len - 2) / 2;
- while (true)
+ template<typename _RandomAccessIterator, typename _Compare>
+ void
+ __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Compare __comp)
+ {
+ while (__last - __first > 1)
{
- _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
- std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
- __comp);
- if (__parent == 0)
- return;
- __parent--;
+ --__last;
+ std::__pop_heap(__first, __last, __last, __comp);
}
}
@@ -472,11 +417,8 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap(__first, __last);
- while (__last - __first > 1)
- {
- --__last;
- std::__pop_heap(__first, __last, __last);
- }
+ std::__sort_heap(__first, __last,
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -500,11 +442,8 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last, __comp);
- while (__last - __first > 1)
- {
- --__last;
- std::__pop_heap(__first, __last, __last, __comp);
- }
+ std::__sort_heap(__first, __last,
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
#if __cplusplus >= 201103L
@@ -529,8 +468,9 @@
typename iterator_traits<_RandomAccessIterator>::value_type>)
__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),
+ __gnu_cxx::__ops::__iter_less_iter());
}
/**
@@ -554,9 +494,9 @@
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
- return __first + std::__is_heap_until(__first, std::distance(__first,
- __last),
- __comp);
+ return __first
+ + std::__is_heap_until(__first, std::distance(__first, __last),
+ __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
/**
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 202818)
+++ include/Makefile.am (working copy)
@@ -121,6 +121,7 @@
${bits_srcdir}/ostream_insert.h \
${bits_srcdir}/parse_numbers.h \
${bits_srcdir}/postypes.h \
+ ${bits_srcdir}/predefined_ops.h \
${bits_srcdir}/ptr_traits.h \
${bits_srcdir}/random.h \
${bits_srcdir}/random.tcc \
Index: testsuite/25_algorithms/find_if/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/find_if/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/find_if/vectorbool.cc (revision 0)
@@ -0,0 +1,39 @@
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.1.2 find
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+void
+test1()
+{
+ std::vector<bool> v;
+ v.push_back(false);
+ v.push_back(false);
+ v.push_back(true);
+ v.push_back(false);
+ VERIFY( std::find(v.begin(), v.end(), true) == v.begin() + 2 );
+}
+
+int
+main()
+{
+ test1();
+}
Index: testsuite/25_algorithms/find/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/find/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/find/vectorbool.cc (revision 0)
@@ -0,0 +1,39 @@
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.1.2 find
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+void
+test1()
+{
+ std::vector<bool> v;
+ v.push_back(false);
+ v.push_back(false);
+ v.push_back(true);
+ v.push_back(false);
+ VERIFY( std::find(v.begin(), v.end(), true) == v.begin() + 2 );
+}
+
+int
+main()
+{
+ test1();
+}
Index: testsuite/25_algorithms/adjacent_find/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/adjacent_find/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/adjacent_find/vectorbool.cc (revision 0)
@@ -0,0 +1,44 @@
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.1.5 [lib.alg.adjacent_find]
+
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::vector<bool> v;
+ v.push_back(true);
+ v.push_back(false);
+ v.push_back(true);
+ v.push_back(false);
+ v.push_back(false);
+
+ VERIFY( std::adjacent_find(v.begin(), v.end()) == v.begin() + 3 );
+ VERIFY( std::adjacent_find(v.begin(), v.end() - 1) == v.end() - 1 );
+}
+
+int
+main()
+{
+ test01();
+}
Index: testsuite/25_algorithms/heap/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/heap/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/heap/vectorbool.cc (revision 0)
@@ -0,0 +1,146 @@
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.3.6 Heap operations [lib.alg.heap.operations]
+
+#include <iterator>
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+const bool A[] = { true, true, false, true, false, false, true, false };
+const int B[] = { false, false, false, false, true, true, true, true };
+const int C[] = { true, true, true, true, false, false, false, false };
+const int N = sizeof(A) / sizeof(bool);
+
+// This functor has the equivalent functionality of std::greater<>,
+// but there is no dependency on <functional> and it also tracks the
+// number of invocations since creation.
+class Gt
+{
+public:
+ static int count() { return _S_count; }
+ static void reset() { _S_count = 0; }
+
+ bool
+ operator()(bool x, bool y) const
+ {
+ ++_S_count;
+ return x > y;
+ }
+
+private:
+ static int _S_count;
+};
+
+int Gt::_S_count = 0;
+
+// Exercise all of the heap functions for operator<. The intermediate
+// results between push_heap and pop_heap and make_heap and sort_heap
+// are not checked (they could be).
+void
+test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ // sort array s1 using push_heap/pop_heap
+ std::vector<bool> s1;
+ std::copy(A, A + N, std::back_inserter(s1));
+ VERIFY( std::equal(s1.begin(), s1.begin() + N, A) );
+
+ for (int i = 2; i <= N; ++i)
+ std::push_heap(s1.begin(), s1.begin() + i);
+
+ for (int i = N; i >= 2; --i)
+ std::pop_heap(s1.begin(), s1.begin() + i);
+
+ VERIFY( std::equal(s1.begin(), s1.begin() + N, B) );
+
+ // sort array s2 using make_heap/sort_heap
+ std::vector<bool> s2;
+ std::copy(A, A + N, std::back_inserter(s2));
+ VERIFY( std::equal(s2.begin(), s2.begin() + N, A) );
+
+ std::make_heap(s2.begin(), s2.begin() + N);
+ std::sort_heap(s2.begin(), s2.begin() + N);
+ VERIFY( std::equal(s2.begin(), s2.begin() + N, B) );
+}
+
+// Perform same tests as above but with the comparison predicate
+// versions, and add complexity constraint checks.
+void
+test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ Gt gt;
+
+#ifndef _GLIBCXX_DEBUG
+ //const int logN = static_cast<int>(std::log(static_cast<double>(N)) + 0.5);
+ const int logN = 3;
+#endif
+
+ std::vector<bool> s1;
+ std::copy(A, A + N, std::back_inserter(s1));
+ VERIFY(std::equal(s1.begin(), s1.begin() + N, A));
+
+ for (int i = 2; i <= N; ++i)
+ {
+ std::push_heap(s1.begin(), s1.begin() + i, gt);
+#ifndef _GLIBCXX_DEBUG
+ VERIFY(gt.count() <= logN);
+#endif
+ gt.reset();
+ }
+
+ for (int i = N; i >= 2; --i)
+ {
+ std::pop_heap(s1.begin(), s1.begin() + i, gt);
+#ifndef _GLIBCXX_DEBUG
+ VERIFY(gt.count() <= 2 * logN);
+#endif
+ gt.reset();
+ }
+
+ VERIFY(std::equal(s1.begin(), s1.begin() + N, C));
+
+ // sort array s2 using make_heap/sort_heap
+ std::vector<bool> s2;
+ std::copy(A, A + N, std::back_inserter(s2));
+ VERIFY(std::equal(s2.begin(), s2.begin() + N, A));
+
+ std::make_heap(s2.begin(), s2.begin() + N, gt);
+#ifndef _GLIBCXX_DEBUG
+ VERIFY(gt.count() <= 3 * N);
+#endif
+ gt.reset();
+
+ std::sort_heap(s2.begin(), s2.begin() + N, gt);
+#ifndef _GLIBCXX_DEBUG
+ VERIFY(gt.count() <= N * logN);
+#endif
+
+ VERIFY(std::equal(s2.begin(), s2.begin() + N, C));
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/25_algorithms/find_if_not/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/find_if_not/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/find_if_not/vectorbool.cc (revision 0)
@@ -0,0 +1,40 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+void
+test1()
+{
+ std::vector<bool> v;
+ v.push_back(false);
+ v.push_back(false);
+ v.push_back(true);
+ v.push_back(false);
+ VERIFY( std::find_if_not(v.begin(), v.end(), [](bool val){ return !val; })
+ == v.begin() + 2 );
+}
+
+int
+main()
+{
+ test1();
+}
Index: testsuite/25_algorithms/is_permutation/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/is_permutation/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/is_permutation/vectorbool.cc (revision 0)
@@ -0,0 +1,50 @@
+// { dg-options "-std=gnu++1y" }
+
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.2.12 [alg.is_permutation] Is permutation
+
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::vector<bool> v1 = { true, false, true, false, true };
+ std::vector<bool> v2 = { false, true, false, true, true };
+ VERIFY( std::is_permutation(v1.begin(), v1.end(), v2.begin()) );
+ VERIFY( !std::is_permutation(v1.begin() + 1, v1.end(), v2.begin() + 1) );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::vector<bool> v1 = { true, false, true, false, true };
+ std::vector<bool> v2 = { false, true, false, true, true };
+ VERIFY( std::is_permutation(v1.begin(), v1.end(), v2.begin(), v2.end()) );
+ VERIFY( !std::is_permutation(v1.begin(), v1.end() - 1, v2.begin(), v2.end()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+}
Index: testsuite/25_algorithms/find_end/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/find_end/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/find_end/vectorbool.cc (revision 0)
@@ -0,0 +1,50 @@
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.1.3 [lib.alg.find.end]
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+void
+test1()
+{
+ std::vector<bool> v1;
+ v1.push_back(false);
+ v1.push_back(false);
+ v1.push_back(false);
+ v1.push_back(true);
+ v1.push_back(true);
+ v1.push_back(false);
+ v1.push_back(true);
+ v1.push_back(true);
+ v1.push_back(false);
+
+ std::vector<bool> v2;
+ v2.push_back(true);
+ v2.push_back(true);
+
+ VERIFY( std::find_end(v1.begin(), v1.end(), v2.begin(), v2.end())
+ == v1.begin() + 6 );
+}
+
+int
+main()
+{
+ test1();
+}
Index: testsuite/25_algorithms/find_first_of/vectorbool.cc
===================================================================
--- testsuite/25_algorithms/find_first_of/vectorbool.cc (revision 0)
+++ testsuite/25_algorithms/find_first_of/vectorbool.cc (revision 0)
@@ -0,0 +1,50 @@
+// Copyright (C) 2013 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.1.4 [lib.alg.find.first.of]
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+void
+test1()
+{
+ std::vector<bool> v1;
+ v1.push_back(false);
+ v1.push_back(false);
+ v1.push_back(true);
+ v1.push_back(false);
+ v1.push_back(true);
+ v1.push_back(true);
+ v1.push_back(false);
+ v1.push_back(true);
+ v1.push_back(true);
+
+ std::vector<bool> v2;
+ v2.push_back(true);
+ v2.push_back(false);
+
+ VERIFY( std::find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end())
+ == v1.begin() );
+}
+
+int
+main()
+{
+ test1();
+}