This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Remove algo duplications
- 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: Tue, 19 Jun 2012 21:18:43 +0200
- Subject: Re: Remove algo duplications
- References: <4FD7A115.9060203@gmail.com>
Hi
No opinion regarding this patch ? Here is a slightly modified
version without usage of lambda in is_heap_until implementation so that
we use move semantic when possible.
Regards
François
On 06/12/2012 10:05 PM, François Dumont wrote:
Hi
Here is a new version of the patch to remove duplication of algo
implementations.
Compared to the previous version I have rename functors that apply
to iterators (iter_less, iter_equal_to). I have also added move
semantics when iterator dereference operator returns anything except
lvalue reference (rvalue reference or an instance).
2012-06-12 François Dumont <fdumont@gcc.gnu.org>
* include/bits/predefined_ops.h: New. Internal functors use to
avoid algorithm duplications.
* include/bits/stl_algobase.h, stl_algo.h, stl_heap.h: Adapt to
use latter functors, remove many algorithm duplications.
* testsuite/util/testsuite_counter_type.h: New.
* testsuite/25_algorithms/lower_bound/3.cc, 4.cc: New.
I don't think tests are to be added. They are not really tests but
rather use cases to experiment impact of the patch in different
situtations, with/without -fno-elide-constructors, in C++ 11 or C++98.
You can see in those the impact of the patch which is more or less
what Marc Glisse already remarked. You can see an impact mostly when
the iterator::reference type is not a reference, there are additional
copies then. But I still think this patch make sens cause it greatly
simplify library code.
Tested under linux x86_64.
François
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 188314)
+++ 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: include/Makefile.in
===================================================================
--- include/Makefile.in (revision 188314)
+++ 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/predefined_ops.h
===================================================================
--- include/bits/predefined_ops.h (revision 0)
+++ include/bits/predefined_ops.h (revision 0)
@@ -0,0 +1,342 @@
+// Default predicates for internal use -*- C++ -*-
+
+// 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file predefined_ops.h
+ * This is an internal header file, included by other library headers.
+ * You should not attempt to use it directly.
+ */
+
+#ifndef _GLIBCXX_PREDEFINED_OPS_H
+#define _GLIBCXX_PREDEFINED_OPS_H 1
+
+namespace __gnu_cxx
+{
+namespace __ops
+{
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Lhs, typename _Rhs>
+#else
+ template<typename _Lhs, typename _Rhs,
+ bool = std::is_lvalue_reference<_Lhs>::value,
+ bool = std::is_lvalue_reference<_Rhs>::value>
+#endif
+ struct less
+ {
+ bool
+ operator()(_Lhs __lhs, _Rhs __rhs) /* Not const so that we do not force
+ the < operator to be const
+ qualified. */
+ { return __lhs < __rhs; }
+ };
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ /* As soon as the less functor is passing a parameter per value or per rvalue
+ reference type, that is to say not per lvalue reference, we implement the
+ move semantic logic. */
+ template<typename _Lhs, typename _Rhs>
+ struct less<_Lhs, _Rhs, false, true>
+ {
+ bool
+ operator()(_Lhs&& __lhs, _Rhs __rhs)
+ { return std::forward<_Lhs>(__lhs) < __rhs; }
+ };
+
+ template<typename _Lhs, typename _Rhs>
+ struct less<_Lhs, _Rhs, true, false>
+ {
+ bool
+ operator()(_Lhs __lhs, _Rhs&& __rhs)
+ { return __lhs < std::forward<_Rhs>(__rhs); }
+ };
+
+ template<typename _Lhs, typename _Rhs>
+ struct less<_Lhs, _Rhs, false, false>
+ {
+ bool
+ operator()(_Lhs&& __lhs, _Rhs&& __rhs)
+ { return std::forward<_Lhs>(__lhs) < std::forward<_Rhs>(__rhs); }
+ };
+#endif
+
+ template<typename _Iterator1, typename _Iterator2 = _Iterator1>
+ struct iter_less
+ : less<typename std::iterator_traits<_Iterator1>::reference,
+ typename std::iterator_traits<_Iterator2>::reference>
+ { };
+
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Lhs, typename _Rhs>
+#else
+ template<typename _Lhs, typename _Rhs,
+ bool = std::is_lvalue_reference<_Lhs>::value,
+ bool = std::is_lvalue_reference<_Rhs>::value>
+#endif
+ struct equal_to
+ {
+ bool
+ operator()(_Lhs __lhs, _Rhs __rhs) /* Not const so that we do not force
+ the == operator to be const
+ qualified. */
+ { return __lhs == __rhs; }
+ };
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Lhs, typename _Rhs>
+ struct equal_to<_Lhs, _Rhs, false, true>
+ {
+ bool
+ operator()(_Lhs&& __lhs, _Rhs __rhs)
+ { return std::forward<_Lhs>(__lhs) == __rhs; }
+ };
+
+ template<typename _Lhs, typename _Rhs>
+ struct equal_to<_Lhs, _Rhs, true, false>
+ {
+ bool
+ operator()(_Lhs __lhs, _Rhs&& __rhs)
+ { return __lhs == std::forward<_Rhs>(__rhs); }
+ };
+
+ template<typename _Lhs, typename _Rhs>
+ struct equal_to<_Lhs, _Rhs, false, false>
+ {
+ bool
+ operator()(_Lhs&& __lhs, _Rhs&& __rhs)
+ { return std::forward<_Lhs>(__lhs) == std::forward<_Rhs>(__rhs); }
+ };
+#endif
+
+ template<typename _Iterator1, typename _Iterator2 = _Iterator1>
+ struct iter_equal_to
+ : equal_to<typename std::iterator_traits<_Iterator1>::reference,
+ typename std::iterator_traits<_Iterator2>::reference>
+ { };
+
+ template<typename _Iterator, typename _Value>
+ struct iter_equal_to_val
+ : equal_to<typename std::iterator_traits<_Iterator>::reference,
+ const _Value&>
+ { };
+
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Iterator, typename _Pred>
+#else
+ template<typename _Iterator, typename _Pred,
+ bool = std::is_lvalue_reference<typename _Iterator::reference>::value>
+#endif
+ struct __negate
+ {
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ _Pred _M_pred;
+
+ __negate(_Pred __pred) : _M_pred(__pred)
+ { }
+
+ bool
+ operator()(_Ref __x) /* Not const so that we do not force the predicate
+ to be const qualified. */
+ { return !bool(_M_pred(__x)); }
+ };
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Iterator, typename _Pred>
+ struct __negate<_Iterator, _Pred, false>
+ {
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ _Pred _M_pred;
+
+ __negate(_Pred __pred) : _M_pred(__pred)
+ { }
+
+ bool
+ operator()(_Ref&& __x) /* Not const so that we do not force the predicate
+ to be const qualified. */
+ { return !bool(_M_pred(std::forward<_Ref>(__x))); }
+ };
+#endif
+
+ /**
+ * @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
+ */
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Iterator, typename _Pred, typename _Value>
+#else
+ template<typename _Iterator, typename _Pred, typename _Value,
+ bool = std::is_lvalue_reference<typename _Iterator::reference>::value>
+#endif
+ 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) /* Not const so that we do not force the predicate
+ to be const qualified. */
+ { 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::iter_equal_to<_Iterator1, _Iterator2>,
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+ _Value>
+#else
+ _Value, true>
+#endif
+ {
+ const _Value& _M_rhs;
+
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ public:
+ __bind2nd(__gnu_cxx::__ops::iter_equal_to<_Iterator1, _Iterator2>,
+ const _Value& __rhs)
+ : _M_rhs(__rhs) {}
+
+ bool
+ operator()(_Ref __lhs) /* Not const so that we do not force the ==
+ operator to be const qualified. */
+ { return __lhs == _M_rhs; }
+ };
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Iterator, typename _Pred, typename _Value>
+ class __bind2nd<_Iterator, _Pred, _Value, false>
+ {
+ _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) /* Not const so that we do not force the predicate
+ to be const qualified. */
+ { return _M_pred(std::forward<_Ref>(__lhs), _M_rhs); }
+ };
+
+ template<typename _Iterator, typename _Value,
+ typename _Iterator1, typename _Iterator2>
+ class __bind2nd<_Iterator,
+ __gnu_cxx::__ops::iter_equal_to<_Iterator1, _Iterator2>,
+ _Value, false>
+ {
+ const _Value& _M_rhs;
+
+ typedef typename std::iterator_traits<_Iterator>::reference _Ref;
+
+ public:
+ __bind2nd(__gnu_cxx::__ops::iter_equal_to<_Iterator1, _Iterator2>,
+ const _Value& __rhs)
+ : _M_rhs(__rhs) {}
+
+ bool
+ operator()(_Ref&& __lhs) /* Not const so that we do not force the ==
+ operator to be const qualified. */
+ { return std::forward<_Ref>(__lhs) == _M_rhs; }
+ };
+#endif
+
+ 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<_Ref1, _Ref2> >
+ {
+ typedef __gnu_cxx::__ops::less<_Lhs, _Rhs> _Ret;
+
+ static _Ret
+ rebind(__gnu_cxx::__ops::less<_Ref1, _Ref2>)
+ { return _Ret(); }
+ };
+
+ template<typename _Iterator1, typename _Iterator2>
+ struct _NestedHelper<__gnu_cxx::__ops::iter_less<_Iterator1,
+ _Iterator2> >
+ {
+ typedef __gnu_cxx::__ops::less<_Lhs, _Rhs> _Ret;
+
+ static _Ret
+ rebind(__gnu_cxx::__ops::iter_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_algobase.h
===================================================================
--- include/bits/stl_algobase.h (revision 188314)
+++ 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::iter_less<_II1, _II2>(),
+ __gnu_cxx::__ops::iter_less<_II2, _II1>());
}
template<>
@@ -928,34 +941,14 @@
__first2, __last2);
}
- /**
- * @brief Finds the first position in which @a val could be inserted
- * without changing the ordering.
- * @param __first An iterator.
- * @param __last Another iterator.
- * @param __val The search term.
- * @return An iterator pointing to the first element <em>not less
- * than</em> @a val, or end() if every element is less than
- * @a val.
- * @ingroup binary_search_algorithms
- */
- template<typename _ForwardIterator, typename _Tp>
+ template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator
- lower_bound(_ForwardIterator __first, _ForwardIterator __last,
- const _Tp& __val)
+ __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val, _Compare __comp)
{
-#ifdef _GLIBCXX_CONCEPT_CHECKS
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
-#endif
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
- // concept requirements
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
- __glibcxx_requires_partitioned_lower(__first, __last, __val);
-
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
@@ -963,7 +956,7 @@
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
- if (*__middle < __val)
+ if (__comp(*__middle, __val))
{
__first = __middle;
++__first;
@@ -975,6 +968,36 @@
return __first;
}
+ /**
+ * @brief Finds the first position in which @a val could be inserted
+ * without changing the ordering.
+ * @param __first An iterator.
+ * @param __last Another iterator.
+ * @param __val The search term.
+ * @return An iterator pointing to the first element <em>not less
+ * than</em> @a val, or end() if every element is less than
+ * @a val.
+ * @ingroup binary_search_algorithms
+ */
+ template<typename _ForwardIterator, typename _Tp>
+ _ForwardIterator
+ lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val)
+ {
+ typedef iterator_traits<_ForwardIterator> _ItTraits;
+
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+ __glibcxx_function_requires(
+ _LessThanOpConcept<typename _ItTraits::value_type, _Tp>)
+ __glibcxx_requires_partitioned_lower(__first, __last, __val);
+
+ return std::__lower_bound(__first, __last, __val,
+ __gnu_cxx::__ops
+ ::less<typename _ItTraits::reference,
+ const _Tp&>());
+ }
+
/// This is a helper function for the sort routines and for random.tcc.
// Precondition: __n > 0.
inline _GLIBCXX_CONSTEXPR int
@@ -1121,28 +1144,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
@@ -1169,12 +1195,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::iter_equal_to<_InputIterator1,
+ _InputIterator2>());
}
/**
@@ -1204,12 +1227,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 188314)
+++ 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
+ ::iter_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<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::iter_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::iter_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::iter_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,6 +464,8 @@
inline _RandomAccessIterator
is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
+ typedef iterator_traits<_RandomAccessIterator> _ItTraits;
+
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
@@ -524,8 +473,11 @@
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- return __first + std::__is_heap_until(__first, std::distance(__first,
- __last));
+ return __first +
+ std::__is_heap_until(__first,
+ std::distance(__first, __last),
+ __gnu_cxx::__ops
+ ::iter_less<_RandomAccessIterator>());
}
/**
@@ -549,8 +501,8 @@
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
- return __first + std::__is_heap_until(__first, std::distance(__first,
- __last),
+ return __first + std::__is_heap_until(__first,
+ std::distance(__first, __last),
__comp);
}
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 188314)
+++ 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,10 @@
return std::__find_end(__first1, __last1, __first2, __last2,
std::__iterator_category(__first1),
- std::__iterator_category(__first2));
+ std::__iterator_category(__first2),
+ __gnu_cxx::__ops::
+ iter_equal_to<_ForwardIterator1,
+ _ForwardIterator2>());
}
/**
@@ -879,6 +600,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 +642,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
+ ::iter_equal_to<_InputIterator>(),
+ __value));
}
/**
@@ -945,13 +678,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 +822,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 +869,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
+ ::iter_equal_to<_ForwardIterator>(),
+ __value));
}
/**
@@ -1167,18 +905,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 +952,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::iter_equal_to<_ForwardIterator>());
}
/**
@@ -1248,18 +984,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 +1675,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 +1689,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 +1759,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 +1770,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
+ ::iter_less<_InputIterator,
+ _RandomAccessIterator>());
}
/**
@@ -2088,49 +1824,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 +1849,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 +1898,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 +1914,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 +1936,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 +1947,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 +1970,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 +2023,6 @@
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
@@ -2462,6 +2031,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 +2049,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 +2077,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<const _Tp&,
+ typename _ItTraits::reference>());
}
/**
@@ -2558,6 +2123,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 +2143,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 +2186,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<typename _ItTraits::reference,
+ const _Tp&>(),
+ __gnu_cxx::__ops
+ ::less<const _Tp&,
+ typename _ItTraits::reference>());
}
/**
@@ -2677,32 +2244,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 +2264,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<typename _ItTraits::reference,
+ const _Tp&>());
return __i != __last && !(__val < *__i);
}
@@ -2767,7 +2313,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 +2321,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 +2347,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 +2431,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 +2441,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 +2471,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 +2503,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 +2512,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 +2529,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 +2556,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 +2621,9 @@
__glibcxx_requires_sorted(__first, __middle);
__glibcxx_requires_sorted(__middle, __last);
- if (__first == __middle || __middle == __last)
- return;
-
- _DistanceType __len1 = std::distance(__first, __middle);
- _DistanceType __len2 = std::distance(__middle, __last);
-
- _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
- __last);
- if (__buf.begin() == 0)
- std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
- else
- std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
- __buf.begin(), _DistanceType(__buf.size()));
+ std::__inplace_merge(__first, __middle, __last,
+ __gnu_cxx::__ops
+ ::iter_less<_BidirectionalIterator>());
}
/**
@@ -3249,57 +2668,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 +2700,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 +2719,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 +2740,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 +2767,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 +2796,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 +3733,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::
+ iter_equal_to<_InputIterator>(), __val),
+ std::__iterator_category(__first));
}
/**
@@ -4871,6 +4145,8 @@
if (__count == 1)
return _GLIBCXX_STD_A::find(__first, __last, __val);
return std::__search_n(__first, __last, __count, __val,
+ __gnu_cxx::__ops
+ ::iter_equal_to_val<_ForwardIterator, _Tp>(),
std::__iterator_category(__first));
}
@@ -5321,8 +4597,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::iter_less<_RandomAccessIterator>());
+ std::__sort_heap(__first, __middle,
+ __gnu_cxx::__ops::iter_less<_RandomAccessIterator>());
}
/**
@@ -5363,7 +4641,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 +4678,8 @@
return;
std::__introselect(__first, __nth, __last,
- std::__lg(__last - __first) * 2);
+ std::__lg(__last - __first) * 2,
+ __gnu_cxx::__ops::iter_less<_RandomAccessIterator>());
}
/**
@@ -5444,6 +4723,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 +4763,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::iter_less<_RandomAccessIterator>());
}
/**
@@ -5509,12 +4797,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 +4925,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 +4967,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 +4974,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::iter_less<_RandomAccessIterator>());
}
/**
@@ -5709,8 +5003,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 +5012,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 +5091,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::iter_less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::iter_less<_InputIterator2, _InputIterator1>());
}
/**
@@ -5841,28 +5142,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 +5209,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::iter_less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::iter_less<_InputIterator2, _InputIterator1>());
}
/**
@@ -5963,19 +5259,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 +5330,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::iter_less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::iter_less<_InputIterator2, _InputIterator1>());
}
/**
@@ -6082,21 +5382,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 +5458,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::iter_less<_InputIterator1, _InputIterator2>(),
+ __gnu_cxx::__ops::iter_less<_InputIterator2, _InputIterator1>());
}
/**
@@ -6209,28 +5511,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 +5547,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::iter_less<_ForwardIterator>());
}
/**
@@ -6279,15 +5572,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 +5604,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::iter_less<_ForwardIterator>());
}
/**
@@ -6335,12 +5629,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: testsuite/util/testsuite_counter_type.h
===================================================================
--- testsuite/util/testsuite_counter_type.h (revision 0)
+++ testsuite/util/testsuite_counter_type.h (revision 0)
@@ -0,0 +1,332 @@
+// -*- C++ -*-
+//
+// 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/>.
+//
+
+#ifndef _TESTSUITE_COUNTER_TYPE_H
+#define _TESTSUITE_COUNTER_TYPE_H 1
+
+#include <iterator>
+
+namespace __gnu_test
+{
+ // Type counting how many constructors are invoked. Used mainly to check that
+ // in algo implementation we do not copy values too often even when operators
+ // are taking type by value.
+ struct counter_type
+ {
+ // Constructor counters:
+ static int default_count;
+ static int specialize_count;
+ static int copy_count;
+ static int copy_assign_count;
+ static int less_compare_count;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ static int move_count;
+ static int move_assign_count;
+#endif
+
+ int val;
+
+ counter_type() : val(0)
+ {
+ ++default_count;
+ }
+
+ counter_type(int inval) : val(inval)
+ {
+ ++specialize_count;
+ }
+
+ counter_type(const counter_type& in) : val(in.val)
+ {
+ ++copy_count;
+ }
+
+ counter_type&
+ operator=(const counter_type& in)
+ {
+ val = in.val;
+ ++copy_assign_count;
+ return *this;
+ }
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ counter_type(counter_type&& in) noexcept
+ {
+ val = in.val;
+ ++move_count;
+ }
+
+ counter_type&
+ operator=(counter_type&& rhs)
+ {
+ val = rhs.val;
+ ++move_assign_count;
+ return *this;
+ }
+#endif
+
+ static void
+ reset()
+ {
+ default_count = 0;
+ specialize_count = 0;
+ copy_count = 0;
+ copy_assign_count = 0;
+ less_compare_count = 0;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ move_count = 0;
+ move_assign_count = 0;
+#endif
+ }
+
+ bool operator==(counter_type rhs) const
+ { return val == rhs.val; }
+ };
+
+ int counter_type::default_count = 0;
+ int counter_type::specialize_count = 0;
+ int counter_type::copy_count = 0;
+ int counter_type::copy_assign_count = 0;
+ int counter_type::less_compare_count = 0;
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ int counter_type::move_count = 0;
+ int counter_type::move_assign_count = 0;
+#endif
+
+#ifdef LESS_OPERATOR_TAKES_COPY
+ bool operator<(counter_type lhs, counter_type rhs)
+ {
+ ++counter_type::less_compare_count;
+ return lhs.val < rhs.val;
+ }
+#else
+ bool operator<(const counter_type& lhs, const counter_type& rhs)
+ {
+ ++counter_type::less_compare_count;
+ return lhs.val < rhs.val;
+ }
+#endif
+
+ template<typename _Iterator>
+ class copy_iterator
+ {
+ protected:
+ _Iterator _M_current;
+
+ typedef std::iterator_traits<_Iterator> __traits_type;
+
+ public:
+ typedef _Iterator iterator_type;
+ typedef typename __traits_type::iterator_category iterator_category;
+ typedef typename __traits_type::value_type value_type;
+ typedef typename __traits_type::difference_type difference_type;
+ // NB: DR 680.
+ typedef _Iterator pointer;
+ typedef value_type reference;
+
+ copy_iterator()
+ : _M_current() { }
+
+ explicit
+ copy_iterator(iterator_type __i)
+ : _M_current(__i) { }
+
+ template<typename _Iter>
+ copy_iterator(const copy_iterator<_Iter>& __i)
+ : _M_current(__i.base()) { }
+
+ iterator_type
+ base() const
+ { return _M_current; }
+
+ reference
+ operator*() const
+ { return *_M_current; }
+
+ pointer
+ operator->() const
+ { return _M_current; }
+
+ copy_iterator&
+ operator++()
+ {
+ ++_M_current;
+ return *this;
+ }
+
+ copy_iterator
+ operator++(int)
+ {
+ copy_iterator __tmp = *this;
+ ++_M_current;
+ return __tmp;
+ }
+
+ copy_iterator&
+ operator--()
+ {
+ --_M_current;
+ return *this;
+ }
+
+ copy_iterator
+ operator--(int)
+ {
+ copy_iterator __tmp = *this;
+ --_M_current;
+ return __tmp;
+ }
+
+ copy_iterator
+ operator+(difference_type __n) const
+ { return copy_iterator(_M_current + __n); }
+
+ copy_iterator&
+ operator+=(difference_type __n)
+ {
+ _M_current += __n;
+ return *this;
+ }
+
+ copy_iterator
+ operator-(difference_type __n) const
+ { return copy_iterator(_M_current - __n); }
+
+ copy_iterator&
+ operator-=(difference_type __n)
+ {
+ _M_current -= __n;
+ return *this;
+ }
+
+ reference
+ operator[](difference_type __n) const
+ { return _M_current[__n]; }
+ };
+
+ // Note: See __normal_iterator operators note from Gaby to understand
+ // why there are always 2 versions for most of the copy_iterator
+ // operators.
+ template<typename _IteratorL, typename _IteratorR>
+ inline bool
+ operator==(const copy_iterator<_IteratorL>& __x,
+ const copy_iterator<_IteratorR>& __y)
+ { return __x.base() == __y.base(); }
+
+ template<typename _Iterator>
+ inline bool
+ operator==(const copy_iterator<_Iterator>& __x,
+ const copy_iterator<_Iterator>& __y)
+ { return __x.base() == __y.base(); }
+
+ template<typename _IteratorL, typename _IteratorR>
+ inline bool
+ operator!=(const copy_iterator<_IteratorL>& __x,
+ const copy_iterator<_IteratorR>& __y)
+ { return !(__x == __y); }
+
+ template<typename _Iterator>
+ inline bool
+ operator!=(const copy_iterator<_Iterator>& __x,
+ const copy_iterator<_Iterator>& __y)
+ { return !(__x == __y); }
+
+ template<typename _IteratorL, typename _IteratorR>
+ inline bool
+ operator<(const copy_iterator<_IteratorL>& __x,
+ const copy_iterator<_IteratorR>& __y)
+ { return __x.base() < __y.base(); }
+
+ template<typename _Iterator>
+ inline bool
+ operator<(const copy_iterator<_Iterator>& __x,
+ const copy_iterator<_Iterator>& __y)
+ { return __x.base() < __y.base(); }
+
+ template<typename _IteratorL, typename _IteratorR>
+ inline bool
+ operator<=(const copy_iterator<_IteratorL>& __x,
+ const copy_iterator<_IteratorR>& __y)
+ { return !(__y < __x); }
+
+ template<typename _Iterator>
+ inline bool
+ operator<=(const copy_iterator<_Iterator>& __x,
+ const copy_iterator<_Iterator>& __y)
+ { return !(__y < __x); }
+
+ template<typename _IteratorL, typename _IteratorR>
+ inline bool
+ operator>(const copy_iterator<_IteratorL>& __x,
+ const copy_iterator<_IteratorR>& __y)
+ { return __y < __x; }
+
+ template<typename _Iterator>
+ inline bool
+ operator>(const copy_iterator<_Iterator>& __x,
+ const copy_iterator<_Iterator>& __y)
+ { return __y < __x; }
+
+ template<typename _IteratorL, typename _IteratorR>
+ inline bool
+ operator>=(const copy_iterator<_IteratorL>& __x,
+ const copy_iterator<_IteratorR>& __y)
+ { return !(__x < __y); }
+
+ template<typename _Iterator>
+ inline bool
+ operator>=(const copy_iterator<_Iterator>& __x,
+ const copy_iterator<_Iterator>& __y)
+ { return !(__x < __y); }
+
+ // DR 685.
+ template<typename _IteratorL, typename _IteratorR>
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ inline auto
+#else
+ inline typename copy_iterator<_IteratorL>::difference_type
+#endif
+ operator-(const copy_iterator<_IteratorL>& __x,
+ const copy_iterator<_IteratorR>& __y)
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ -> decltype(__x.base() - __y.base())
+#endif
+ { return __x.base() - __y.base(); }
+
+ template<typename _Iterator>
+ inline typename copy_iterator<_Iterator>::difference_type
+ operator-(const copy_iterator<_Iterator>& __x,
+ const copy_iterator<_Iterator>& __y)
+ { return __x.base() - __y.base(); }
+
+ template<typename _Iterator>
+ inline copy_iterator<_Iterator>
+ operator+(typename copy_iterator<_Iterator>::difference_type __n,
+ const copy_iterator<_Iterator>& __x)
+ { return __x + __n; }
+
+ template<typename _Iterator>
+ inline copy_iterator<_Iterator>
+ make_copy_iterator(_Iterator __i)
+ { return copy_iterator<_Iterator>(__i); }
+
+} // namespace __gnu_test
+#endif
Property changes on: testsuite/util/testsuite_counter_type.h
___________________________________________________________________
Added: svn:eol-style
+ native
Index: testsuite/25_algorithms/lower_bound/3.cc
===================================================================
--- testsuite/25_algorithms/lower_bound/3.cc (revision 0)
+++ testsuite/25_algorithms/lower_bound/3.cc (revision 0)
@@ -0,0 +1,216 @@
+// { dg-add-options no_pch }
+// { dg-options "-fno-elide-constructors" }
+// 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.3 [lib.alg.binary.search] Binary search algorithms.
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_counter_type.h>
+
+//#define _ELIDE_CONSTRUCTORS
+//#define _WITHOUT_PATCH
+
+bool test __attribute__((unused)) = true;
+
+// 25.3.3.1 lower_bound, with and without comparison predicate
+
+void
+test01()
+{
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ lower_bound(array, array + size, middle);
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+ VERIFY( counter_type::copy_count == 0 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+#else
+ VERIFY( counter_type::copy_count == 0 );
+ VERIFY( counter_type::move_count == 0 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+void
+test02()
+{
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ lower_bound(make_copy_iterator(array),
+ make_copy_iterator(array + size),
+ middle);
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+# ifdef _WITHOUT_PATCH
+ VERIFY( counter_type::copy_count == 3 );
+# else
+# ifdef _ELIDE_CONSTRUCTORS
+ VERIFY( counter_type::copy_count == 3 );
+# else
+ VERIFY( counter_type::copy_count == 6 );
+# endif
+# endif
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+#else
+ VERIFY( counter_type::copy_count == 3 );
+ VERIFY( counter_type::move_count == 0 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+
+void
+test03()
+{
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ lower_bound(std::make_move_iterator(array),
+ std::make_move_iterator(array + size),
+ middle);
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+ VERIFY( counter_type::copy_count == 0 );
+ VERIFY( counter_type::move_count == 0 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+void
+test04()
+{
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ lower_bound(std::make_move_iterator(make_copy_iterator(array)),
+ std::make_move_iterator(make_copy_iterator(array + size)),
+ middle);
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+ VERIFY( counter_type::copy_count == 3 );
+ VERIFY( counter_type::move_count == 0 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ return 0;
+}
Index: testsuite/25_algorithms/lower_bound/4.cc
===================================================================
--- testsuite/25_algorithms/lower_bound/4.cc (revision 0)
+++ testsuite/25_algorithms/lower_bound/4.cc (revision 0)
@@ -0,0 +1,230 @@
+// { dg-add-options no_pch }
+// { dg-options "-fno-elide-constructors" }
+// 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.3 [lib.alg.binary.search] Binary search algorithms.
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+#define LESS_OPERATOR_TAKES_COPY
+#include <testsuite_counter_type.h>
+
+//#define _ELIDE_CONSTRUCTORS
+//#define _WITHOUT_PATCH
+
+bool test __attribute__((unused)) = true;
+
+// 25.3.3.1 lower_bound, with and without comparison predicate
+
+void
+test01()
+{
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ counter_type* p = lower_bound(array, array + size, middle);
+ VERIFY( p == array + size / 2 );
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+ VERIFY( counter_type::copy_count == 6 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+#else
+ VERIFY( counter_type::copy_count == 6 );
+ VERIFY( counter_type::move_count == 0 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+void
+test02()
+{
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ lower_bound(make_copy_iterator(array),
+ make_copy_iterator(array + size),
+ middle);
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+# ifdef _WITHOUT_PATCH
+# ifdef _ELIDE_CONSTRUCTORS
+ VERIFY( counter_type::copy_count == 6 );
+# else
+ VERIFY( counter_type::copy_count == 9 );
+# endif
+# else
+# ifdef _ELIDE_CONSTRUCTORS
+ VERIFY( counter_type::copy_count == 9 );
+# else
+ VERIFY( counter_type::copy_count == 12 );
+# endif
+# endif
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+#else
+ VERIFY( counter_type::copy_count == 6 );
+# ifdef _WITHOUT_PATCH
+# ifdef _ELIDE_CONSTRUCTORS
+ VERIFY( counter_type::move_count == 0 );
+# else
+ VERIFY( counter_type::move_count == 3 );
+# endif
+# else
+ VERIFY( counter_type::move_count == 3 );
+# endif
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+void
+test03()
+{
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ lower_bound(std::make_move_iterator(array),
+ std::make_move_iterator(array + size),
+ middle);
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+ VERIFY( counter_type::copy_count == 3 );
+ VERIFY( counter_type::move_count == 3 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+void
+test04()
+{
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using std::lower_bound;
+ using __gnu_test::counter_type;
+
+ counter_type array[] =
+ {
+ counter_type(0),
+ counter_type(1),
+ counter_type(2),
+ counter_type(3),
+ counter_type(4),
+ counter_type(5),
+ counter_type(6)
+ };
+
+
+ const std::size_t size = sizeof(array) / sizeof(counter_type);
+
+ const counter_type middle = array[size / 2];
+
+ counter_type::reset();
+
+ lower_bound(std::make_move_iterator(make_copy_iterator(array)),
+ std::make_move_iterator(make_copy_iterator(array + size)),
+ middle);
+
+ VERIFY( counter_type::default_count == 0 );
+ VERIFY( counter_type::specialize_count == 0 );
+ VERIFY( counter_type::copy_count == 6 );
+ VERIFY( counter_type::move_count == 3 );
+ VERIFY( counter_type::copy_assign_count == 0 );
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::less_compare_count == 3 );
+ VERIFY( counter_type::move_less_compare_count == 0 );
+#endif
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ return 0;
+}