This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Remove algo code duplication
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Sat, 28 Apr 2012 10:01:19 +0200
- Subject: Remove algo code duplication
Hi
Here is an other attempt to remove duplication of code in
implementation of Standard algos. There are several enhancements on the
last proposal:
1. No usage of C++11 lambdas anymore, code works fine in C++98 and code
has been really deleted this time. About 700 lines removed in stl_algo.h
for instance.
2. Compatible with existing code, code submitted by Christopher last
time will still compile. To do so I used
std::iterator_traits<>::reference type so that if the iterator is not
const then the operator do not have to take const reference or to be
const qualified neither. For the same reason I have also avoided some
const qualifiers on the introduced functors.
3. It is less complex than in libstdcxx_so_7 branch: Introduced functors
always have one operator() so that ambiguity between different overloads
is impossible. To do so I used 2 techniques:
- For equal_range and lexicographical_compare algos, the ones that
really need 2 overloads, I simply pass 2 functors, one to do lhs < rhs
and one for rhs < lhs; when the functor comes from the user code it is
the same that is passed twice.
- In other more complex situation where an algorithm calls other
internal algos resulting in the functor being called with potentially
many slightly different parameter types I use a rebind technique. When
there is a call to an internal algo that need a specific functor
signature I rebind the input functor to match it. In _RebindHelper I
detect when the functor is my newly introduced __gnu_cxx::__ops::less
functor and change it in this case, otherwise it remains unchanged.
In libstdcxx_so_7 branch the algo version using operators was calling
the version taking a functor. The result was that concept checks on the
operator version was performed twice. It is not a big concern when it is
really pure concept checks but in trunk there is also the debug checks
that can be quite expensive, checking that a range is sorted for
instance. So I prefer to introduce an internal implementation that
contains only the algo implementation without any concept checks and
have it call from the Standard algos. Those pure implementations are
also the one used for internal purpose.
Note that doing this job I introduce 2 small unrelated changes:
- __move_merge used to have 2 template iterator types but was called
only with one, I simplify it.
- __unguarded_partition used to have 3 template parameters:
_RandomAccessIterator, _Tp and _Compare. It was taking a const reference
to _Tp which was a useless constraint for the functor. So it now only
have 2 template parameters, const _Tp& has been replaced by
iterator_traits<_RandomAccessIterator>::reference.
2012-04-27 François Dumont <fdumont@gcc.gnu.org>
* include/bits/predefined_ops.h: New.
* include/bits/stl_algobase.h: Use functors from latter file to remove
duplication of algorithm implementation.
* include/bits/stl_algo.h: Likewise.
* include/bits/stl_heap.h: Likewise.
* testsuite/25_algorithms/lexicographical_compare/2.cc: New.
* testsuite/25_algorithms/lexicographical_compare/3.cc: New.
* testsuite/25_algorithms/partial_sort_copy/3.cc: New.
Tested under linux x86_64 normal and debug mode.
François
Index: include/Makefile.in
===================================================================
--- include/Makefile.in (revision 186718)
+++ include/Makefile.in (working copy)
@@ -391,6 +391,7 @@
${bits_srcdir}/shared_ptr_base.h \
${bits_srcdir}/slice_array.h \
${bits_srcdir}/sstream.tcc \
+ ${bits_srcdir}/predefined_ops.h \
${bits_srcdir}/stl_algo.h \
${bits_srcdir}/stl_algobase.h \
${bits_srcdir}/stl_bvector.h \
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h (revision 186718)
+++ include/bits/stl_algobase.h (working copy)
@@ -69,6 +69,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)
{
@@ -864,6 +865,29 @@
{ return true; }
};
+ template<typename _II1, typename _II2,
+ typename _Compare12, typename _Compare21>
+ bool
+ __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2,
+ _Compare12 __comp12, _Compare21 __comp21)
+ {
+ 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 (__comp12(*__first1, *__first2))
+ return true;
+ if (__comp21(*__first2, *__first1))
+ return false;
+ }
+ return __first1 == __last1 && __first2 != __last2;
+ }
+
template<bool _BoolType>
struct __lexicographical_compare
{
@@ -877,21 +901,10 @@
__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::less<_II1, _II2>(),
+ __gnu_cxx::__ops::less<_II2, _II1>());
}
template<>
@@ -928,6 +941,33 @@
__first2, __last2);
}
+ template<typename _ForwardIterator, typename _Tp, typename _Compare>
+ _ForwardIterator
+ __lower_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)
+ {
+ _DistanceType __half = __len >> 1;
+ _ForwardIterator __middle = __first;
+ std::advance(__middle, __half);
+ if (__comp(*__middle, __val))
+ {
+ __first = __middle;
+ ++__first;
+ __len = __len - __half - 1;
+ }
+ else
+ __len = __half;
+ }
+ return __first;
+ }
+
/**
* @brief Finds the first position in which @a val could be inserted
* without changing the ordering.
@@ -944,33 +984,18 @@
lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
+ typedef iterator_traits<_ForwardIterator> _ItTraits;
+ typedef typename _ItTraits::value_type _ValueType;
// 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)
- {
- _DistanceType __half = __len >> 1;
- _ForwardIterator __middle = __first;
- std::advance(__middle, __half);
- if (*__middle < __val)
- {
- __first = __middle;
- ++__first;
- __len = __len - __half - 1;
- }
- else
- __len = __half;
- }
- return __first;
+ return std::__lower_bound(__first, __last, __val,
+ __gnu_cxx::__ops
+ ::less_aux<typename _ItTraits::reference,
+ const _Tp&>());
}
/// This is a helper function for the sort routines and for random.tcc.
@@ -1127,28 +1152,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,
+ __comp, __comp);
}
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _BinaryPredicate>
+ pair<_InputIterator1, _InputIterator2>
+ __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _BinaryPredicate __binary_pred)
+ {
+ while (__first1 != __last1 && bool(__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
@@ -1175,12 +1203,9 @@
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::equal_to<_InputIterator1,
+ _InputIterator2>());
}
/**
@@ -1210,12 +1235,7 @@
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_requires_valid_range(__first1, __last1);
- while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
- {
- ++__first1;
- ++__first2;
- }
- return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+ return std::__mismatch(__first1, __last1, __first2, __binary_pred);
}
_GLIBCXX_END_NAMESPACE_ALGO
Index: include/bits/stl_heap.h
===================================================================
--- include/bits/stl_heap.h (revision 186718)
+++ include/bits/stl_heap.h (working copy)
@@ -58,6 +58,7 @@
#include <debug/debug.h>
#include <bits/move.h>
+#include <bits/predefined_ops.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -68,21 +69,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
@@ -105,7 +91,11 @@
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
+ ::less<_RandomAccessIterator>()) == __n;
+ }
template<typename _RandomAccessIterator, typename _Compare,
typename _Distance>
@@ -127,13 +117,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)
+ __push_heap(_RandomAccessIterator __first, _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;
@@ -156,10 +148,9 @@
inline void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
+ typedef iterator_traits<_RandomAccessIterator> _ItTraits;
+ typedef typename _ItTraits::value_type _ValueType;
+ typedef typename _ItTraits::difference_type _DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
@@ -170,26 +161,12 @@
_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
+ ::less_aux<typename _ItTraits::reference,
+ _ValueType&>());
}
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
- typename _Compare>
- void
- __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __topIndex, _Tp __value, _Compare __comp)
- {
- _Distance __parent = (__holeIndex - 1) / 2;
- while (__holeIndex > __topIndex
- && __comp(*(__first + __parent), __value))
- {
- *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
- __holeIndex = __parent;
- __parent = (__holeIndex - 1) / 2;
- }
- *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
- }
-
/**
* @brief Push an element onto a heap using comparison functor.
* @param __first Start of heap.
@@ -223,17 +200,19 @@
_DistanceType(0), _GLIBCXX_MOVE(__value), __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;
@@ -245,14 +224,19 @@
+ (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
- std::__push_heap(__first, __holeIndex, __topIndex,
- _GLIBCXX_MOVE(__value));
+ typedef iterator_traits<_RandomAccessIterator> _ItTraits;
+ std::__push_heap(__first, __holeIndex, __topIndex,
+ _GLIBCXX_MOVE(__value),
+ __gnu_cxx::__ops
+ ::_RebindHelper<typename _ItTraits::reference,
+ _Tp&>
+ ::rebind(__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;
@@ -263,7 +247,7 @@
*__result = _GLIBCXX_MOVE(*__first);
std::__adjust_heap(__first, _DistanceType(0),
_DistanceType(__last - __first),
- _GLIBCXX_MOVE(__value));
+ _GLIBCXX_MOVE(__value), __comp);
}
/**
@@ -293,54 +277,10 @@
__glibcxx_requires_heap(__first, __last);
--__last;
- std::__pop_heap(__first, __last, __last);
+ std::__pop_heap(__first, __last, __last,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
}
- 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.
@@ -368,6 +308,32 @@
std::__pop_heap(__first, __last, __last, __comp);
}
+ template<typename _RandomAccessIterator, typename _Compare>
+ void
+ __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Compare __comp)
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
+
+ if (__last - __first < 2)
+ return;
+
+ const _DistanceType __len = __last - __first;
+ _DistanceType __parent = (__len - 2) / 2;
+ while (true)
+ {
+ _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
+ 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.
@@ -391,19 +357,8 @@
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
- if (__last - __first < 2)
- return;
-
- const _DistanceType __len = __last - __first;
- _DistanceType __parent = (__len - 2) / 2;
- while (true)
- {
- _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
- std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
- if (__parent == 0)
- return;
- __parent--;
- }
+ std::__make_heap(__first, __last,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
}
/**
@@ -431,19 +386,18 @@
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
- if (__last - __first < 2)
- return;
+ std::__make_heap(__first, __last, __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);
}
}
@@ -467,11 +421,8 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap(__first, __last);
- while (__last - __first > 1)
- {
- --__last;
- std::__pop_heap(__first, __last, __last);
- }
+ __sort_heap(__first, __last,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
}
/**
@@ -495,11 +446,7 @@
__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);
- }
+ __sort_heap(__first, __last, __comp);
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -517,15 +464,21 @@
inline _RandomAccessIterator
is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
+ typedef iterator_traits<_RandomAccessIterator> _ItTraits;
+
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIterator>::value_type>)
+ typename _ItTraits::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),
+ [](typename _ItTraits::reference __lhs,
+ typename _ItTraits::reference __rhs)
+ { return __lhs < __rhs; });
}
/**
@@ -549,8 +502,8 @@
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
- return __first + std::__is_heap_until(__first, std::distance(__first,
- __last),
+ return __first + std::__is_heap_until(__first,
+ std::distance(__first, __last),
__comp);
}
Index: include/bits/predefined_ops.h
===================================================================
--- include/bits/predefined_ops.h (revision 0)
+++ include/bits/predefined_ops.h (revision 0)
@@ -0,0 +1,200 @@
+// Default predicates for internal use -*- C++ -*-
+
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+/** @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
+{
+ template<typename _Lhs, typename _Rhs>
+ struct less_aux
+ {
+ bool
+ operator()(_Lhs __lhs, _Rhs __rhs) const
+ { return __lhs < __rhs; }
+ };
+
+ template<typename _Iterator1, typename _Iterator2 = _Iterator1>
+ struct less
+ : less_aux<typename std::iterator_traits<_Iterator1>::reference,
+ typename std::iterator_traits<_Iterator2>::reference>
+ { };
+
+ template<typename _Iterator1, typename _Iterator2 = _Iterator1>
+ struct equal_to
+ {
+ typedef typename std::iterator_traits<_Iterator1>::reference _Ref1;
+ typedef typename std::iterator_traits<_Iterator2>::reference _Ref2;
+
+ bool
+ operator()(_Ref1 __lhs, _Ref2 __rhs) const
+ { return __lhs == __rhs; }
+ };
+
+ template<typename _Iterator, typename _Value>
+ struct equal_to_val
+ {
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ bool
+ operator()(_Ref __lhs, const _Value& __rhs) const
+ { return __lhs == __rhs; }
+ };
+
+ template<typename _Iterator, typename _Pred>
+ struct __negate
+ {
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ _Pred _M_pred;
+
+ __negate(_Pred __pred) : _M_pred(__pred)
+ { }
+
+ bool
+ operator()(_Ref __x)
+ { return !bool(_M_pred(__x)); }
+ };
+
+ /**
+ * @if maint
+ * A class inspired by bind2nd and company, which wraps a function or
+ * class and a reference, and produces a unary function object. It has less
+ * requirements than the standard version and is designed to be use to wrap
+ * binary predicates given to algorithms in the standard library.
+ * @endif
+ */
+ template<typename _Iterator, typename _Pred, typename _Value>
+ class __bind2nd
+ {
+ _Pred _M_pred;
+ const _Value& _M_rhs;
+
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ public:
+ __bind2nd(_Pred __pred, const _Value& __rhs)
+ : _M_pred(__pred), _M_rhs(__rhs) {}
+
+ bool
+ operator()(_Ref __lhs)
+ { return _M_pred(__lhs, _M_rhs); }
+ };
+
+ /**
+ * @if maint
+ * Specialisation of __bind2nd for equality.
+ * @endif
+ */
+ template<typename _Iterator, typename _Value,
+ typename _Iterator1, typename _Iterator2>
+ class __bind2nd<_Iterator,
+ __gnu_cxx::__ops::equal_to<_Iterator1, _Iterator2>,
+ _Value>
+ {
+ const _Value& _M_rhs;
+
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ public:
+ __bind2nd(__gnu_cxx::__ops::equal_to<_Iterator1, _Iterator2>,
+ const _Value& __rhs)
+ : _M_rhs(__rhs) {}
+
+ bool
+ operator()(_Ref __lhs)
+ { return __lhs == _M_rhs; }
+ };
+
+ template<typename _Iterator>
+ struct _Adapters
+ {
+ template<typename _Pred, typename _Value>
+ static __bind2nd<_Iterator, _Pred, _Value>
+ bind2nd(_Pred __pred, const _Value& __val)
+ { return __bind2nd<_Iterator, _Pred, _Value>(__pred, __val); }
+
+ template<typename _Pred>
+ static __negate<_Iterator, _Pred>
+ negate(_Pred __pred)
+ { return __negate<_Iterator, _Pred>(__pred); }
+ };
+
+ template<typename _Lhs, typename _Rhs>
+ struct _RebindHelper
+ {
+ private:
+ template<typename _Pred>
+ struct _NestedHelper
+ {
+ typedef _Pred _Ret;
+
+ static _Ret
+ rebind(_Pred __pred)
+ { return __pred; }
+ };
+
+ template<typename _Ref1, typename _Ref2>
+ struct _NestedHelper<__gnu_cxx::__ops::less_aux<_Ref1, _Ref2> >
+ {
+ typedef __gnu_cxx::__ops::less_aux<_Lhs, _Rhs> _Ret;
+
+ static _Ret
+ rebind(__gnu_cxx::__ops::less_aux<_Ref1, _Ref2>)
+ { return _Ret(); }
+ };
+
+ template<typename _Iterator1, typename _Iterator2>
+ struct _NestedHelper<__gnu_cxx::__ops::less<_Iterator1, _Iterator2> >
+ {
+ typedef __gnu_cxx::__ops::less_aux<_Lhs, _Rhs> _Ret;
+
+ static _Ret
+ rebind(__gnu_cxx::__ops::less<_Iterator1, _Iterator2>)
+ { return _Ret(); }
+ };
+
+ public:
+ template <typename _Pred>
+ static typename _NestedHelper<_Pred>::_Ret
+ rebind(_Pred __pred)
+ { return _NestedHelper<_Pred>::rebind(__pred); }
+ };
+
+} // namespace __ops
+} // namespace __gnu_cxx
+
+#endif
Property changes on: include/bits/predefined_ops.h
___________________________________________________________________
Added: svn:eol-style
+ native
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 186718)
+++ include/bits/stl_algo.h (working copy)
@@ -62,6 +62,7 @@
#include <bits/algorithmfwd.h>
#include <bits/stl_heap.h>
#include <bits/stl_tempbuf.h> // for _Temporary_buffer
+#include <bits/predefined_ops.h>
#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <random> // for std::uniform_int_distribution
@@ -74,30 +75,6 @@
{
_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
@@ -126,17 +103,6 @@
// 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.
template<typename _InputIterator, typename _Predicate>
inline _InputIterator
@@ -148,54 +114,6 @@
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.
template<typename _RandomAccessIterator, typename _Predicate>
_RandomAccessIterator
@@ -244,73 +162,16 @@
}
}
- /// This is an overload used by find_if_not() for the Input Iterator case.
- template<typename _InputIterator, typename _Predicate>
- inline _InputIterator
- __find_if_not(_InputIterator __first, _InputIterator __last,
- _Predicate __pred, input_iterator_tag)
- {
- while (__first != __last && bool(__pred(*__first)))
- ++__first;
- return __first;
- }
-
- /// This is an overload used by find_if_not() for the RAI case.
- template<typename _RandomAccessIterator, typename _Predicate>
- _RandomAccessIterator
- __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Predicate __pred, random_access_iterator_tag)
- {
- typename iterator_traits<_RandomAccessIterator>::difference_type
- __trip_count = (__last - __first) >> 2;
-
- for (; __trip_count > 0; --__trip_count)
- {
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
-
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
-
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
-
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- }
-
- switch (__last - __first)
- {
- case 3:
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- case 2:
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- case 1:
- if (!bool(__pred(*__first)))
- return __first;
- ++__first;
- case 0:
- default:
- return __last;
- }
- }
-
/// 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
+ ::_Adapters<_InputIterator>::negate(__pred),
+ std::__iterator_category(__first));
}
/// Like find_if_not(), but uses and updates a count of the
@@ -339,88 +200,6 @@
// 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)
- {
- __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;
- }
-
- /**
- * 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;
-
- _DistanceType __tailSize = __last - __first;
- const _DistanceType __pattSize = __count;
-
- if (__tailSize < __pattSize)
- return __last;
-
- const _DistanceType __skipOffset = __pattSize - 1;
- _RandomAccessIter __lookAhead = __first + __skipOffset;
- __tailSize -= __pattSize;
-
- while (1) // the main loop...
- {
- // __lookAhead here is always pointing to the last element of next
- // possible match.
- while (!(*__lookAhead == __val)) // the skip loop...
- {
- if (__tailSize < __pattSize)
- return __last; // Failure
- __lookAhead += __pattSize;
- __tailSize -= __pattSize;
- }
- _DistanceType __remainder = __skipOffset;
- for (_RandomAccessIter __backTrack = __lookAhead - 1;
- *__backTrack == __val; --__backTrack)
- {
- if (--__remainder == 0)
- return (__lookAhead - __skipOffset); // Success
- }
- if (__remainder > __tailSize)
- return __last; // Failure
- __lookAhead += __remainder;
- __tailSize -= __remainder;
- }
- }
-
// search_n
/**
@@ -515,33 +294,6 @@
}
// 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)
- {
- 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;
- }
- }
- }
- }
-
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
_ForwardIterator1
@@ -573,40 +325,6 @@
}
// 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
@@ -684,7 +402,9 @@
return std::__find_end(__first1, __last1, __first2, __last2,
std::__iterator_category(__first1),
- std::__iterator_category(__first2));
+ std::__iterator_category(__first2),
+ __gnu_cxx::__ops::
+ equal_to<_ForwardIterator1, _ForwardIterator2>());
}
/**
@@ -879,6 +599,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 (!bool(__pred(*__first)))
+ {
+ *__result = *__first;
+ ++__result;
+ }
+ return __result;
+ }
/**
* @brief Copy a sequence, removing elements of a given value.
@@ -907,13 +641,11 @@
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::_Adapters<_InputIterator>
+ ::bind2nd(__gnu_cxx::__ops
+ ::equal_to<_InputIterator>(),
+ __value));
}
/**
@@ -945,13 +677,7 @@
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, __pred);
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -1095,6 +821,24 @@
}
#endif
+ template<typename _ForwardIterator, typename _Predicate>
+ _ForwardIterator
+ __remove_if(_ForwardIterator __first, _ForwardIterator __last,
+ _Predicate __pred)
+ {
+ __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
+ if (__first == __last)
+ return __first;
+ _ForwardIterator __result = __first;
+ ++__first;
+ for (; __first != __last; ++__first)
+ if (!bool(__pred(*__first)))
+ {
+ *__result = _GLIBCXX_MOVE(*__first);
+ ++__result;
+ }
+ return __result;
+ }
/**
* @brief Remove elements from a sequence.
* @ingroup mutating_algorithms
@@ -1124,18 +868,11 @@
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::_Adapters<_ForwardIterator>
+ ::bind2nd(__gnu_cxx::__ops
+ ::equal_to<_ForwardIterator>(),
+ __value));
}
/**
@@ -1167,18 +904,26 @@
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, __pred);
+ }
+
+ template<typename _ForwardIterator, typename _BinaryPredicate>
+ _ForwardIterator
+ __unique(_ForwardIterator __first, _ForwardIterator __last,
+ _BinaryPredicate __binary_pred)
+ {
+ // 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;
- for(; __first != __last; ++__first)
- if(!bool(__pred(*__first)))
- {
- *__result = _GLIBCXX_MOVE(*__first);
- ++__result;
- }
- return __result;
+ while (++__first != __last)
+ if (!bool(__binary_pred(*__dest, *__first)))
+ *++__dest = _GLIBCXX_MOVE(*__first);
+ return ++__dest;
}
/**
@@ -1206,18 +951,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 __unique(__first, __last,
+ __gnu_cxx::__ops::equal_to<_ForwardIterator>());
}
/**
@@ -1248,18 +983,7 @@
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 __unique(__first, __last, __binary_pred);
}
/**
@@ -1950,26 +1674,13 @@
}
/// 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))
std::__pop_heap(__first, __middle, __i, __comp);
@@ -1977,6 +1688,48 @@
// 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;
+ }
+
+ typedef __gnu_cxx::__ops
+ ::_RebindHelper<typename _RItTraits::reference,
+ typename _RItTraits::reference> _RbHlp;
+ std::__make_heap(__result_first, __result_real_last,
+ _RbHlp::rebind(__comp));
+ while (__first != __last)
+ {
+ if (__comp(*__first, *__result_first))
+ std::__adjust_heap(__result_first, _DistanceType(0),
+ _DistanceType(__result_real_last
+ - __result_first),
+ _InputValueType(*__first),
+ _RbHlp::rebind(__comp));
+ ++__first;
+ }
+ std::__sort_heap(__result_first, __result_real_last,
+ _RbHlp::rebind(__comp));
+ return __result_real_last;
+ }
+
/**
* @brief Copy the smallest elements of a sequence.
* @ingroup sorting_algorithms
@@ -2005,8 +1758,6 @@
_InputValueType;
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_OutputValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
@@ -2018,27 +1769,11 @@
__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
+ ::less<_InputIterator,
+ _RandomAccessIterator>());
}
/**
@@ -2088,49 +1823,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,
+ __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,
@@ -2150,74 +1848,46 @@
}
/// 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,
_RandomAccessIterator __last, _Compare __comp)
{
+ typedef iterator_traits<_RandomAccessIterator> _ItTraits;
+
if (__first == __last) return;
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
if (__comp(*__i, *__first))
{
- typename iterator_traits<_RandomAccessIterator>::value_type
- __val = _GLIBCXX_MOVE(*__i);
+ typename _ItTraits::value_type __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);
}
else
- std::__unguarded_linear_insert(__i, __comp);
+ std::__unguarded_linear_insert(__i,
+ __gnu_cxx::__ops
+ ::_RebindHelper<typename _ItTraits::value_type&,
+ typename _ItTraits::reference>
+ ::rebind(__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;
+ typedef iterator_traits<_RandomAccessIterator> _ItTraits;
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
- std::__unguarded_linear_insert(__i, __comp);
+ std::__unguarded_linear_insert(__i,
+ __gnu_cxx::__ops
+ ::_RebindHelper<typename _ItTraits::value_type&,
+ typename _ItTraits::reference>
+ ::rebind(__comp));
}
/**
@@ -2227,21 +1897,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,
@@ -2258,31 +1913,12 @@
}
/// 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)
+ typename std::iterator_traits<_RandomAccessIterator>
+ ::reference __pivot, _Compare __comp)
{
while (true)
{
@@ -2299,18 +1935,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,
@@ -2322,28 +1946,6 @@
}
/// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator, typename _Size>
- void
- __introsort_loop(_RandomAccessIterator __first,
- _RandomAccessIterator __last,
- _Size __depth_limit)
- {
- 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;
- }
- }
-
- /// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
@@ -2367,44 +1969,12 @@
// sort
- template<typename _RandomAccessIterator, typename _Size>
- void
- __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
- _RandomAccessIterator __last, _Size __depth_limit)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
- while (__last - __first > 3)
- {
- 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::__insertion_sort(__first, __last);
- }
-
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Size __depth_limit,
_Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
while (__last - __first > 3)
{
if (__depth_limit == 0)
@@ -2452,8 +2022,6 @@
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
@@ -2462,6 +2030,17 @@
__glibcxx_requires_partitioned_lower_pred(__first, __last,
__val, __comp);
+ return std::__lower_bound(__first, __last, __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)
@@ -2469,14 +2048,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;
}
@@ -2497,33 +2076,18 @@
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
+ typedef iterator_traits<_ForwardIterator> _ItTraits;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+ __glibcxx_function_requires(_LessThanOpConcept<_Tp,
+ typename _ItTraits::value_type>)
__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
+ ::less_aux<const _Tp&,
+ typename _ItTraits::reference>());
}
/**
@@ -2558,6 +2122,19 @@
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
+ return std::__upper_bound(__first, __last, __val, __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)
@@ -2565,16 +2142,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);
}
/**
@@ -2599,44 +2185,24 @@
equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
+ typedef iterator_traits<_ForwardIterator> _ItTraits;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
- __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ typename _ItTraits::value_type, _Tp>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ _Tp, typename _ItTraits::value_type>)
__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
+ ::less_aux<typename _ItTraits::reference,
+ const _Tp&>(),
+ __gnu_cxx::__ops
+ ::less_aux<const _Tp&,
+ typename _ItTraits::reference>());
}
/**
@@ -2677,32 +2243,7 @@
__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, __comp, __comp);
}
/**
@@ -2722,16 +2263,20 @@
binary_search(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
+ typedef iterator_traits<_ForwardIterator> _ItTraits;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+ __glibcxx_function_requires(_LessThanOpConcept<
+ _Tp, typename _ItTraits::value_type>)
__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
+ ::less_aux<typename _ItTraits::reference,
+ const _Tp&>());
return __i != __last && !(__val < *__i);
}
@@ -2767,7 +2312,7 @@
__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, __comp);
return __i != __last && !bool(__comp(__val, *__i));
}
@@ -2775,32 +2320,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,
@@ -2827,48 +2346,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,
@@ -2953,62 +2430,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
@@ -3019,17 +2440,25 @@
_Pointer __buffer, _Distance __buffer_size,
_Compare __comp)
{
+ typedef std::iterator_traits<_BidirectionalIterator> _ItTraits;
+ typedef std::iterator_traits<_Pointer> _PtrTraits;
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,
+ __gnu_cxx::__ops::_RebindHelper<typename _ItTraits::reference,
+ typename _PtrTraits::reference>
+ ::rebind(__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,
+ __gnu_cxx::__ops::_RebindHelper<typename _PtrTraits::reference,
+ typename _ItTraits::reference>
+ ::rebind(__comp));
}
else
{
@@ -3041,16 +2470,22 @@
{
__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
+ ::_RebindHelper<typename _ItTraits::reference,
+ typename _ItTraits::value_type const&>
+ ::rebind(__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
+ ::_RebindHelper<typename _ItTraits::value_type const&,
+ typename _ItTraits::reference>
+ ::rebind(__comp));
__len11 = std::distance(__first, __first_cut);
}
_BidirectionalIterator __new_middle =
@@ -3067,49 +2502,6 @@
}
/// 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
@@ -3119,6 +2511,7 @@
_Distance __len1, _Distance __len2,
_Compare __comp)
{
+ typedef std::iterator_traits<_BidirectionalIterator> _ItTraits;
if (__len1 == 0 || __len2 == 0)
return;
if (__len1 + __len2 == 2)
@@ -3135,16 +2528,22 @@
{
__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
+ ::_RebindHelper<typename _ItTraits::reference,
+ typename _ItTraits::value_type const&>
+ ::rebind(__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
+ ::_RebindHelper<typename _ItTraits::value_type const&,
+ typename _ItTraits::reference>
+ ::rebind(__comp));
__len11 = std::distance(__first, __first_cut);
}
std::rotate(__first_cut, __middle, __second_cut);
@@ -3156,6 +2555,35 @@
__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);
+
+ _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);
+ }
+
/**
* @brief Merges two sorted ranges in place.
* @ingroup sorting_algorithms
@@ -3192,19 +2620,8 @@
__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::less<_BidirectionalIterator>());
}
/**
@@ -3249,57 +2666,16 @@
__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, __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)
@@ -3322,29 +2698,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,
@@ -3364,24 +2717,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
@@ -3399,30 +2738,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,
@@ -3450,33 +2765,6 @@
}
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,
@@ -3506,25 +2794,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,
@@ -4462,8 +3731,11 @@
__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::_Adapters<_InputIterator>
+ ::bind2nd(__gnu_cxx::__ops::
+ equal_to<_InputIterator>(), __val),
+ std::__iterator_category(__first));
}
/**
@@ -4871,6 +4143,8 @@
if (__count == 1)
return _GLIBCXX_STD_A::find(__first, __last, __val);
return std::__search_n(__first, __last, __count, __val,
+ __gnu_cxx::__ops
+ ::equal_to_val<_ForwardIterator, _Tp>(),
std::__iterator_category(__first));
}
@@ -5321,8 +4595,10 @@
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
- std::__heap_select(__first, __middle, __last);
- std::sort_heap(__first, __middle);
+ std::__heap_select(__first, __middle, __last,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
+ std::__sort_heap(__first, __middle,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
}
/**
@@ -5363,7 +4639,7 @@
__glibcxx_requires_valid_range(__middle, __last);
std::__heap_select(__first, __middle, __last, __comp);
- std::sort_heap(__first, __middle, __comp);
+ std::__sort_heap(__first, __middle, __comp);
}
/**
@@ -5400,7 +4676,8 @@
return;
std::__introselect(__first, __nth, __last,
- std::__lg(__last - __first) * 2);
+ std::__lg(__last - __first) * 2,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
}
/**
@@ -5444,6 +4721,19 @@
}
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline void
+ __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Compare __comp)
+ {
+ if (__first != __last)
+ {
+ std::__introsort_loop(__first, __last,
+ std::__lg(__last - __first) * 2, __comp);
+ std::__final_insertion_sort(__first, __last, __comp);
+ }
+ }
+
/**
* @brief Sort the elements of a sequence.
* @ingroup sorting_algorithms
@@ -5471,12 +4761,8 @@
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__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);
- }
+ __sort(__first, __last,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
}
/**
@@ -5509,12 +4795,7 @@
_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first != __last)
- {
- std::__introsort_loop(__first, __last,
- std::__lg(__last - __first) * 2, __comp);
- std::__final_insertion_sort(__first, __last, __comp);
- }
+ __sort(__first, __last, __comp);
}
/**
@@ -5642,7 +4923,25 @@
__result));
}
+ 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;
+ _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);
+ }
+
/**
* @brief Sort the elements of a sequence, preserving the relative order
* of equivalent elements.
@@ -5666,8 +4965,6 @@
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
@@ -5675,13 +4972,8 @@
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__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()));
+ std::__stable_sort(__first, __last,
+ __gnu_cxx::__ops::less<_RandomAccessIterator>());
}
/**
@@ -5709,8 +5001,6 @@
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
@@ -5720,16 +5010,43 @@
_ValueType>)
__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);
+ std::__stable_sort(__first, __last, __comp);
}
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare12, typename _Compare21>
+ _OutputIterator
+ __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result,
+ _Compare12 __comp12, _Compare21 __comp21)
+ {
+ while (__first1 != __last1 && __first2 != __last2)
+ {
+ if (__comp12(*__first1, *__first2))
+ {
+ *__result = *__first1;
+ ++__first1;
+ }
+ else if (__comp21(*__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.
* @ingroup set_algorithms
@@ -5772,28 +5089,10 @@
__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 std::__set_union(
+ __first1, __last1, __first2, __last2, __result,
+ __gnu_cxx::__ops::less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::less<_InputIterator2, _InputIterator1>());
}
/**
@@ -5841,28 +5140,32 @@
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+ return std::__set_union(__first1, __last1, __first2, __last2, __result,
+ __comp, __comp);
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare12, typename _Compare21>
+ _OutputIterator
+ __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result,
+ _Compare12 __comp12, _Compare21 __comp21)
+ {
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 (__comp12(*__first1, *__first2))
+ ++__first1;
+ else if (__comp21(*__first2, *__first1))
+ ++__first2;
+ else
+ {
+ *__result = *__first1;
+ ++__first1;
+ ++__first2;
+ ++__result;
+ }
+ return __result;
}
/**
@@ -5904,19 +5207,10 @@
__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 std::__set_intersection(
+ __first1, __last1, __first2, __last2, __result,
+ __gnu_cxx::__ops::less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::less<_InputIterator2, _InputIterator1>());
}
/**
@@ -5963,19 +5257,34 @@
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+ return std::__set_intersection(__first1, __last1, __first2, __last2,
+ __result, __comp, __comp);
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare12, typename _Compare21>
+ _OutputIterator
+ __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result,
+ _Compare12 __comp12, _Compare21 __comp21)
+ {
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
- ++__first1;
- else if (__comp(*__first2, *__first1))
+ if (__comp12(*__first1, *__first2))
+ {
+ *__result = *__first1;
+ ++__first1;
+ ++__result;
+ }
+ else if (__comp21(*__first2, *__first1))
++__first2;
else
{
- *__result = *__first1;
++__first1;
++__first2;
- ++__result;
}
- return __result;
+ return std::copy(__first1, __last1, __result);
}
/**
@@ -6019,21 +5328,10 @@
__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 std::__set_difference(
+ __first1, __last1, __first2, __last2, __result,
+ __gnu_cxx::__ops::less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::less<_InputIterator2, _InputIterator1>());
}
/**
@@ -6082,21 +5380,39 @@
__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+ return std::__set_difference(__first1, __last1, __first2, __last2,
+ __result, __comp, __comp);
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _OutputIterator,
+ typename _Compare12, typename _Compare21>
+ _OutputIterator
+ __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _OutputIterator __result,
+ _Compare12 __comp12, _Compare21 __comp21)
+ {
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
+ if (__comp12(*__first1, *__first2))
{
*__result = *__first1;
++__first1;
++__result;
}
- else if (__comp(*__first2, *__first1))
- ++__first2;
+ else if (__comp21(*__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));
}
/**
@@ -6140,26 +5456,10 @@
__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 std::__set_symmetric_difference(
+ __first1, __last1, __first2, __last2, __result,
+ __gnu_cxx::__ops::less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::less<_InputIterator2, _InputIterator1>());
}
/**
@@ -6209,28 +5509,24 @@
__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 std::__set_symmetric_difference(__first1, __last1,
+ __first2, __last2, __result,
+ __comp, __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.
@@ -6249,13 +5545,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 std::__min_element(__first, __last,
+ __gnu_cxx::__ops::less<_ForwardIterator>());
}
/**
@@ -6279,15 +5570,21 @@
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first == __last)
- return __first;
+ return std::__min_element(__first, __last, __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;
}
-
/**
* @brief Return the maximum element in a range.
* @ingroup sorting_algorithms
@@ -6305,13 +5602,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 std::__max_element(__first, __last,
+ __gnu_cxx::__ops::less<_ForwardIterator>());
}
/**
@@ -6335,12 +5627,7 @@
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 std::__max_element(__first, __last, __comp);
}
_GLIBCXX_END_NAMESPACE_ALGO
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 186718)
+++ include/Makefile.am (working copy)
@@ -138,6 +138,7 @@
${bits_srcdir}/shared_ptr_base.h \
${bits_srcdir}/slice_array.h \
${bits_srcdir}/sstream.tcc \
+ ${bits_srcdir}/predefined_ops.h \
${bits_srcdir}/stl_algo.h \
${bits_srcdir}/stl_algobase.h \
${bits_srcdir}/stl_bvector.h \
Index: testsuite/25_algorithms/lexicographical_compare/2.cc
===================================================================
--- testsuite/25_algorithms/lexicographical_compare/2.cc (revision 0)
+++ testsuite/25_algorithms/lexicographical_compare/2.cc (revision 0)
@@ -0,0 +1,63 @@
+// Copyright (C) 2012 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.8 [lib.alg.lex.comparison]
+
+#include <list>
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test1()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::list<int> l;
+ l.push_back(0);
+ l.push_back(1);
+ l.push_back(2);
+ std::vector<short> v;
+ v.push_back(0);
+ v.push_back(1);
+ v.push_back(3);
+
+ VERIFY( std::lexicographical_compare(l.begin(), l.end(),
+ v.begin(), v.end()) );
+ VERIFY( !std::lexicographical_compare(v.begin(), v.end(),
+ l.begin(), l.end()) );
+
+ const std::list<int>& cl = l;
+
+ VERIFY( std::lexicographical_compare(cl.begin(), cl.end(),
+ v.begin(), v.end()) );
+ VERIFY( !std::lexicographical_compare(v.begin(), v.end(),
+ cl.begin(), cl.end()) );
+
+ const std::vector<short>& cv = v;
+
+ VERIFY( std::lexicographical_compare(cl.begin(), cl.end(),
+ cv.begin(), cv.end()) );
+ VERIFY( !std::lexicographical_compare(cv.begin(), cv.end(),
+ cl.begin(), cl.end()) );
+}
+
+int
+main()
+{
+ test1();
+}
Index: testsuite/25_algorithms/lexicographical_compare/3.cc
===================================================================
--- testsuite/25_algorithms/lexicographical_compare/3.cc (revision 0)
+++ testsuite/25_algorithms/lexicographical_compare/3.cc (revision 0)
@@ -0,0 +1,80 @@
+// Copyright (C) 2012 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.8 [lib.alg.lex.comparison]
+
+#include <vector>
+#include <list>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test1()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::vector<bool> v1;
+ v1.push_back(true);
+ v1.push_back(true);
+ v1.push_back(false);
+ std::vector<bool> v2;
+ v2.push_back(true);
+ v2.push_back(true);
+ v2.push_back(true);
+
+ VERIFY( std::lexicographical_compare(v1.begin(), v1.end(),
+ v2.begin(), v2.end()) );
+ VERIFY( !std::lexicographical_compare(v2.begin(), v2.end(),
+ v1.begin(), v1.end()) );
+
+ const std::vector<bool>& cv1 = v1;
+
+ VERIFY( std::lexicographical_compare(cv1.begin(), cv1.end(),
+ v2.begin(), v2.end()) );
+ VERIFY( !std::lexicographical_compare(v2.begin(), v2.end(),
+ cv1.begin(), cv1.end()) );
+
+ const std::vector<bool>& cv2 = v2;
+
+ VERIFY( std::lexicographical_compare(cv1.begin(), cv1.end(),
+ cv2.begin(), cv2.end()) );
+ VERIFY( !std::lexicographical_compare(cv2.begin(), cv2.end(),
+ cv1.begin(), cv1.end()) );
+
+ std::list<bool> l;
+ l.push_back(true);
+ l.push_back(true);
+ l.push_back(true);
+
+ VERIFY( std::lexicographical_compare(v1.begin(), v1.end(),
+ l.begin(), l.end()) );
+ VERIFY( !std::lexicographical_compare(l.begin(), l.end(),
+ v1.begin(), v1.end()) );
+
+ const std::list<bool>& cl = l;
+
+ VERIFY( std::lexicographical_compare(v1.begin(), v1.end(),
+ cl.begin(), cl.end()) );
+ VERIFY( !std::lexicographical_compare(cl.begin(), cl.end(),
+ v1.begin(), v1.end()) );
+}
+
+int
+main()
+{
+ test1();
+}
Index: testsuite/25_algorithms/partial_sort_copy/3.cc
===================================================================
--- testsuite/25_algorithms/partial_sort_copy/3.cc (revision 0)
+++ testsuite/25_algorithms/partial_sort_copy/3.cc (revision 0)
@@ -0,0 +1,108 @@
+// Copyright (C) 2012 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.1.4 [lib.partial.sort.copy]
+
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using std::partial_sort_copy;
+
+typedef test_container<int, random_access_iterator_wrapper> Rcontainer;
+
+namespace
+{
+ bool
+ compare(int lhs, int rhs)
+ { return lhs > rhs; }
+
+ struct Compare
+ {
+ bool
+ operator()(int lhs, int rhs) const
+ { return lhs > rhs; }
+ };
+}
+
+void
+test1()
+{
+ std::vector<int> v;
+ v.push_back(0);
+ v.push_back(1);
+ v.push_back(2);
+ v.push_back(3);
+ v.push_back(4);
+ {
+ int array2[5];
+ Rcontainer rcon(array2, array2 + 5);
+ partial_sort_copy(v.begin(), v.end(), rcon.begin(), rcon.end(),
+ compare);
+ VERIFY(array2[0] == 4 && array2[1] == 3 && array2[2] == 2 &&
+ array2[3] == 1 && array2[4] == 0);
+ }
+
+ {
+ const std::vector<int>& cv = v;
+ int array2[5];
+ Rcontainer rcon(array2, array2 + 5);
+ partial_sort_copy(cv.begin(), cv.end(), rcon.begin(), rcon.end(),
+ compare);
+ VERIFY(array2[0] == 4 && array2[1] == 3 && array2[2] == 2 &&
+ array2[3] == 1 && array2[4] == 0);
+ }
+}
+
+void
+test2()
+{
+ std::vector<int> v;
+ v.push_back(0);
+ v.push_back(1);
+ v.push_back(2);
+ v.push_back(3);
+ v.push_back(4);
+ {
+ int array2[5];
+ Rcontainer rcon(array2, array2 + 5);
+ partial_sort_copy(v.begin(), v.end(), rcon.begin(), rcon.end(),
+ Compare());
+ VERIFY(array2[0] == 4 && array2[1] == 3 && array2[2] == 2 &&
+ array2[3] == 1 && array2[4] == 0);
+ }
+
+ {
+ const std::vector<int>& cv = v;
+ int array2[5];
+ Rcontainer rcon(array2, array2 + 5);
+ partial_sort_copy(cv.begin(), cv.end(), rcon.begin(), rcon.end(),
+ Compare());
+ VERIFY(array2[0] == 4 && array2[1] == 3 && array2[2] == 2 &&
+ array2[3] == 1 && array2[4] == 0);
+ }
+}
+
+int
+main()
+{
+ test1();
+ test2();
+}