This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Remove algorithms implementation duplications


Hi

Here is the new patch based on Marc Glisse idea to use functors taking iterators rather than iterators::reference. Compare to the previous proposal there is no more impact on the creation of temporaries instances, no additional copy or move constructor. Of course there are additional iterators or functors copies but those types are supposed to be lightweight types easy to copy.

I have taken this opportunity to also clean the instantiation of types used in concept checks. There have been patches recently to avoid instantiation of the iterator_traits type that became unused if concepts checks are disabled, I have clean this issue in the impacted files.

Note also that this patch in addition to cleaning libstdc++ code will also benefit to our users:
- concept check are no repeated each time an algo call an other algo. Now concept checks are done in Standard algo implementations and those implementations only use internal functions, the "__XXX" functions, that do not redo the checks
- the search algo taking a predicate was not using the find_if algo. When I kept only one implementation of search I use the one with the __find_if call to benefit from its specialization for random access iterators.


I also wonder if I shouldn't move all the implementation details in the std::__detail namespace ? Should I do it now, before eventually applying the patch ?

Tested under linux x86_64 normal, debug and C++11-normal modes.

2012-07-11 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.

François

Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h	(revision 189412)
+++ 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_iter(__first1, __first2),
+		__gnu_cxx::__ops::__iter_less_iter(__first2, __first1));
       }
 
   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,32 @@
       return __first;
     }
 
+  /**
+   *  @brief Finds the first position in which @a val could be inserted
+   *         without changing the ordering.
+   *  @param  __first   An iterator.
+   *  @param  __last    Another iterator.
+   *  @param  __val     The search term.
+   *  @return         An iterator pointing to the first element <em>not less
+   *                  than</em> @a val, or end() if every element is less than 
+   *                  @a val.
+   *  @ingroup binary_search_algorithms
+  */
+  template<typename _ForwardIterator, typename _Tp>
+    _ForwardIterator
+    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+		const _Tp& __val)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+      __glibcxx_requires_partitioned_lower(__first, __last, __val);
+
+      return std::__lower_bound(__first, __last, __val,
+			__gnu_cxx::__ops::__iter_less_cval(__first, __val));
+    }
+
   /// This is a helper function for the sort routines and for random.tcc.
   //  Precondition: __n > 0.
   inline _GLIBCXX_CONSTEXPR int
@@ -1085,15 +1104,14 @@
     lexicographical_compare(_II1 __first1, _II1 __last1,
 			    _II2 __first2, _II2 __last2)
     {
-#ifdef _GLIBCXX_CONCEPT_CHECKS
-      // concept requirements
-      typedef typename iterator_traits<_II1>::value_type _ValueType1;
-      typedef typename iterator_traits<_II2>::value_type _ValueType2;
-#endif
       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_II1>::value_type,
+	    typename iterator_traits<_II2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_II2>::value_type,
+	    typename iterator_traits<_II1>::value_type>)
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
 
@@ -1121,28 +1139,32 @@
     lexicographical_compare(_II1 __first1, _II1 __last1,
 			    _II2 __first2, _II2 __last2, _Compare __comp)
     {
-      typedef typename iterator_traits<_II1>::iterator_category _Category1;
-      typedef typename iterator_traits<_II2>::iterator_category _Category2;
-      typedef std::__lc_rai<_Category1, _Category2> 	__rai_type;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
 
-      __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
-      for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
-	   ++__first1, ++__first2)
-	{
-	  if (__comp(*__first1, *__first2))
-	    return true;
-	  if (__comp(*__first2, *__first1))
-	    return false;
-	}
-      return __first1 == __last1 && __first2 != __last2;
+      return std::__lexicographical_compare_impl(
+	__first1, __last1, __first2, __last2,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first1, __first2),
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first2, __first1));
     }
 
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _BinaryPredicate>
+    pair<_InputIterator1, _InputIterator2>
+    __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
+	       _InputIterator2 __first2, _BinaryPredicate __binary_pred)
+    {
+      while (__first1 != __last1 && __binary_pred(__first1, __first2))
+        {
+	  ++__first1;
+	  ++__first2;
+        }
+      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+    }
+
   /**
    *  @brief Finds the places in ranges which don't match.
    *  @ingroup non_mutating_algorithms
@@ -1169,12 +1191,8 @@
 	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_requires_valid_range(__first1, __last1);
 
-      while (__first1 != __last1 && *__first1 == *__first2)
-        {
-	  ++__first1;
-	  ++__first2;
-        }
-      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+      return std::__mismatch(__first1, __last1, __first2,
+	__gnu_cxx::__ops::__iter_equal_to_iter(__first1, __first2));
     }
 
   /**
@@ -1204,12 +1222,8 @@
       __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,
+	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred, __first1, __first2));
     }
 
 _GLIBCXX_END_NAMESPACE_ALGO
Index: include/bits/stl_heap.h
===================================================================
--- include/bits/stl_heap.h	(revision 189412)
+++ include/bits/stl_heap.h	(working copy)
@@ -1,7 +1,7 @@
 // Heap implementation -*- C++ -*-
 
 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
-// 2011 Free Software Foundation, Inc.
+// 2011, 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
@@ -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
@@ -92,7 +78,7 @@
       _Distance __parent = 0;
       for (_Distance __child = 1; __child < __n; ++__child)
 	{
-	  if (__comp(__first[__parent], __first[__child]))
+	  if (__comp(__first + __parent, __first + __child))
 	    return __child;
 	  if ((__child & 1) == 0)
 	    ++__parent;
@@ -105,13 +91,19 @@
   template<typename _RandomAccessIterator, typename _Distance>
     inline bool
     __is_heap(_RandomAccessIterator __first, _Distance __n)
-    { return std::__is_heap_until(__first, __n) == __n; }
+    {
+      return std::__is_heap_until(__first, __n,
+			__gnu_cxx::__ops::__iter_less_iter(__first)) == __n;
+    }
 
   template<typename _RandomAccessIterator, typename _Compare,
 	   typename _Distance>
     inline bool
     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
-    { return std::__is_heap_until(__first, __n, __comp) == __n; }
+    {
+      return std::__is_heap_until(__first, __n,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first)) == __n;
+    }
 
   template<typename _RandomAccessIterator>
     inline bool
@@ -127,13 +119,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 +150,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 +163,10 @@
 
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
-		       _DistanceType(0), _GLIBCXX_MOVE(__value));
+		       _DistanceType(0), _GLIBCXX_MOVE(__value),
+		       __gnu_cxx::__ops::__iter_less_val(__first, __value));
     }
 
-  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.
@@ -220,20 +197,24 @@
 
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
-		       _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
+		       _DistanceType(0), _GLIBCXX_MOVE(__value),
+		       __gnu_cxx::__ops
+		       ::__iter_comp_val(__comp, __first, __value));
     }
 
-  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 +226,16 @@
 						     + (__secondChild - 1)));
 	  __holeIndex = __secondChild - 1;
 	}
-      std::__push_heap(__first, __holeIndex, __topIndex,
-		       _GLIBCXX_MOVE(__value));
+      std::__push_heap(__first, __holeIndex, __topIndex, 
+		       _GLIBCXX_MOVE(__value),
+		       __gnu_cxx::__ops::__rebind_iter_comp_val(__comp,
+								__value));
     }
 
-  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 +246,7 @@
       *__result = _GLIBCXX_MOVE(*__first);
       std::__adjust_heap(__first, _DistanceType(0),
 			 _DistanceType(__last - __first),
-			 _GLIBCXX_MOVE(__value));
+			 _GLIBCXX_MOVE(__value), __comp);
     }
 
   /**
@@ -281,66 +264,20 @@
     inline void
     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_non_empty_range(__first, __last);
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_heap(__first, __last);
 
       --__last;
-      std::__pop_heap(__first, __last, __last);
+      std::__pop_heap(__first, __last, __last,
+		      __gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
-  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.
@@ -365,32 +302,20 @@
       __glibcxx_requires_heap_pred(__first, __last, __comp);
 
       --__last;
-      std::__pop_heap(__first, __last, __last, __comp);
+      std::__pop_heap(__first, __last, __last,
+		      __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
-  /**
-   *  @brief  Construct a heap over a range.
-   *  @param  __first  Start of heap.
-   *  @param  __last   End of heap.
-   *  @ingroup heap_algorithms
-   *
-   *  This operation makes the elements in [__first,__last) into a heap.
-  */
-  template<typename _RandomAccessIterator>
+  template<typename _RandomAccessIterator, typename _Compare>
     void
-    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+		_Compare __comp)
     {
       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 	  _ValueType;
       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 	  _DistanceType;
 
-      // concept requirements
-      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
-	    _RandomAccessIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
-      __glibcxx_requires_valid_range(__first, __last);
-
       if (__last - __first < 2)
 	return;
 
@@ -399,13 +324,37 @@
       while (true)
 	{
 	  _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
-	  std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
+	  std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
+			     __comp);
 	  if (__parent == 0)
 	    return;
 	  __parent--;
 	}
     }
+  
+  /**
+   *  @brief  Construct a heap over a range.
+   *  @param  __first  Start of heap.
+   *  @param  __last   End of heap.
+   *  @ingroup heap_algorithms
+   *
+   *  This operation makes the elements in [__first,__last) into a heap.
+  */
+  template<typename _RandomAccessIterator>
+    void
+    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
+      std::__make_heap(__first, __last,
+		       __gnu_cxx::__ops::__iter_less_iter(__first));
+    }
+
   /**
    *  @brief  Construct a heap over a range using comparison functor.
    *  @param  __first  Start of heap.
@@ -421,29 +370,24 @@
     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 	      _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	  _ValueType;
-      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
-	  _DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__last - __first < 2)
-	return;
+      std::__make_heap(__first, __last,
+		       __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
+    }
 
-      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 +411,7 @@
       __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_iter(__first));
     }
 
   /**
@@ -495,11 +435,8 @@
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_heap_pred(__first, __last, __comp);
 
-      while (__last - __first > 1)
-	{
-	  --__last;
-	  std::__pop_heap(__first, __last, __last, __comp);
-	}
+      __sort_heap(__first, __last,
+		  __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -524,8 +461,9 @@
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      return __first + std::__is_heap_until(__first, std::distance(__first,
-								   __last));
+      return __first + 
+	std::__is_heap_until(__first, std::distance(__first, __last),
+			     __gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -549,9 +487,9 @@
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      return __first + std::__is_heap_until(__first, std::distance(__first,
-								   __last),
-					    __comp);
+      return __first
+	+ std::__is_heap_until(__first, std::distance(__first, __last),
+			__gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
   /**
Index: include/bits/predefined_ops.h
===================================================================
--- include/bits/predefined_ops.h	(revision 0)
+++ include/bits/predefined_ops.h	(revision 0)
@@ -0,0 +1,489 @@
+// 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
+{
+  template<typename _Iterator1, typename _Iterator2 = _Iterator1>
+    struct _Iter_less_iter
+    {
+      bool
+      operator()(_Iterator1 __it1, _Iterator2 __it2)
+      { return *__it1 < *__it2; }
+    };
+
+  template<typename _Iterator>
+    _Iter_less_iter<_Iterator>
+    __iter_less_iter(_Iterator)
+    { return _Iter_less_iter<_Iterator>(); }
+
+  template<typename _Iterator1, typename _Iterator2>
+    _Iter_less_iter<_Iterator1, _Iterator2>
+    __iter_less_iter(_Iterator1, _Iterator2)
+    { return _Iter_less_iter<_Iterator1, _Iterator2>(); }
+
+  template<typename _Iterator, typename _Value>
+    struct _Iter_less_val
+    {
+      bool
+      operator()(_Iterator __it, _Value& __val)
+      { return *__it < __val; }
+    };
+
+  template<typename _Iterator, typename _Value>
+    _Iter_less_val<_Iterator, _Value>
+    __iter_less_val(_Iterator, const _Value&)
+    { return _Iter_less_val<_Iterator, _Value>(); }
+
+  template<typename _Iterator, typename _Value>
+    _Iter_less_val<_Iterator, _Value const>
+    __iter_less_cval(_Iterator, const _Value&)
+    { return _Iter_less_val<_Iterator, _Value const>(); }
+
+  template<typename _Value, typename _Iterator>
+    struct _Val_less_iter
+    {
+      bool
+      operator()(_Value& __val, _Iterator __it)
+      { return __val < *__it; }
+    };
+
+  template<typename _Value, typename _Iterator>
+    _Val_less_iter<_Value const, _Iterator>
+    __cval_less_iter(const _Value&, _Iterator)
+    { return _Val_less_iter<_Value const, _Iterator>(); }
+
+  template<typename _Iterator1, typename _Iterator2 = _Iterator1>
+    struct _Iter_equal_to_iter
+    {
+      bool
+      operator()(_Iterator1 __it1, _Iterator2 __it2)
+      { return *__it1 == *__it2; }
+    };
+
+  template<typename _Iterator>
+    _Iter_equal_to_iter<_Iterator>
+    __iter_equal_to_iter(_Iterator)
+    { return _Iter_equal_to_iter<_Iterator>(); }
+
+  template<typename _Iterator1, typename _Iterator2>
+    _Iter_equal_to_iter<_Iterator1, _Iterator2>
+    __iter_equal_to_iter(_Iterator1, _Iterator2)
+    { return _Iter_equal_to_iter<_Iterator1, _Iterator2>(); }
+
+  template<typename _Iterator, typename _Value>
+    struct _Iter_equal_to_val
+    {
+      bool
+      operator()(_Iterator __it, _Value& __val)
+      { return *__it == __val; }
+    };
+
+  template<typename _Iterator, typename _Value>
+    _Iter_equal_to_val<_Iterator, _Value const>
+    __iter_equal_to_cval(_Iterator, const _Value&)
+    { return _Iter_equal_to_val<_Iterator, _Value const>(); }
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _Compare>
+    struct _Iter_comp_iter
+    {
+      _Compare _M_comp;
+
+      _Iter_comp_iter(_Compare __comp)
+	: _M_comp(__comp)
+      {}
+
+      bool
+      operator()(_Iterator1 __it1, _Iterator2 __it2)
+      { return bool(_M_comp(*__it1, *__it2)); }
+    };
+
+  template<typename _Iterator, typename _Compare>
+    _Iter_comp_iter<_Iterator, _Iterator, _Compare>
+    __iter_comp_iter(_Compare __comp, _Iterator)
+    { return _Iter_comp_iter<_Iterator, _Iterator, _Compare>(__comp); }
+
+  template<typename _Iterator1, typename _Iterator2, typename _Compare>
+    _Iter_comp_iter<_Iterator1, _Iterator2, _Compare>
+    __iter_comp_iter(_Compare __comp, _Iterator1, _Iterator2)
+    { return _Iter_comp_iter<_Iterator1, _Iterator2, _Compare>(__comp); }
+
+  template<typename _Iterator, typename _Value,
+	   typename _Compare>
+    struct _Iter_comp_val
+    {
+      _Compare _M_comp;
+
+      _Iter_comp_val(_Compare __comp)
+	: _M_comp(__comp)
+      {}
+
+      bool
+      operator()(_Iterator __it, _Value& __val)
+      { return bool(_M_comp(*__it, __val)); }
+    };
+
+  template<typename _Iterator, typename _Value, typename _Compare>
+   _Iter_comp_val<_Iterator, _Value, _Compare>
+    __iter_comp_val(_Compare __comp, _Iterator, _Value&)
+    { return _Iter_comp_val<_Iterator, _Value, _Compare>(__comp); }
+
+  template<typename _Iterator, typename _Value, typename _Compare>
+   _Iter_comp_val<_Iterator, const _Value, _Compare>
+    __iter_comp_cval(_Compare __comp, _Iterator, const _Value&)
+    { return _Iter_comp_val<_Iterator, const _Value, _Compare>(__comp); }
+
+  template<typename _Value, typename _Iterator,
+	   typename _Compare>
+    struct _Val_comp_iter
+    {
+      _Compare _M_comp;
+
+      _Val_comp_iter(_Compare __comp)
+	: _M_comp(__comp)
+      {}
+
+      bool
+      operator()(_Value& __val, _Iterator __it)
+      { return bool(_M_comp(__val, *__it)); }
+    };
+
+  template<typename _Value, typename _Iterator, typename _Compare>
+    _Val_comp_iter<const _Value, _Iterator, _Compare>
+    __cval_comp_iter(_Compare __comp, const _Value&, _Iterator)
+    { return _Val_comp_iter<const _Value, _Iterator, _Compare>(__comp); }
+
+  template<typename _Iterator, typename _Value>
+    struct _Iter_equals_val
+    {
+      _Value& _M_value;
+
+      _Iter_equals_val(_Value& __value)
+	: _M_value(__value)
+      {}
+
+      bool
+      operator()(_Iterator __it)
+      { return *__it == _M_value; }
+    };
+
+  template<typename _Iterator1, typename _Iterator2,
+	   bool = false>
+    struct _Iter_equals_iter
+    {
+      typename std::iterator_traits<_Iterator2>::reference _M_value;
+
+      _Iter_equals_iter(_Iterator2 __it2)
+	: _M_value(*__it2)
+      {}
+
+      bool
+      operator()(_Iterator1 __it1)
+      { return *__it1 == _M_value; }
+    };
+
+  template<typename _Iterator1, typename _Iterator2>
+    struct _Iter_equals_iter<_Iterator1, _Iterator2, true>
+    {
+      typename std::iterator_traits<_Iterator1>::reference _M_value;
+
+      _Iter_equals_iter(_Iterator1 __it1)
+	: _M_value(*__it1)
+      {}
+
+      bool
+      operator()(_Iterator2 __it2)
+      { return _M_value == *__it2; }
+    };
+
+  template<typename _Iterator, typename _Predicate>
+    struct _Iter_pred
+    {
+      _Predicate _M_pred;
+
+      _Iter_pred(_Predicate __pred)
+	: _M_pred(__pred)
+      {}
+
+      bool
+      operator()(_Iterator __it)
+      { return bool(_M_pred(*__it)); }
+    };
+
+  template<typename _Predicate, typename _Iterator>
+    _Iter_pred<_Iterator, _Predicate>
+    __pred_iter(_Predicate __pred, _Iterator)
+    { return _Iter_pred<_Iterator, _Predicate>(__pred); }
+
+  template<typename _Iterator, typename _Value,
+	   typename _Compare>
+    struct _Iter_bind2nd_val
+    {
+      _Compare _M_comp;
+      _Value& _M_value;
+
+      _Iter_bind2nd_val(_Compare __comp, _Value& __value)
+	: _M_comp(__comp), _M_value(__value)
+      {}
+
+      bool
+      operator()(_Iterator __it)
+      { return bool(_M_comp(*__it, _M_value)); }
+    };
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _Compare>
+    struct _Iter_bind2nd_iter
+    {
+      _Compare _M_comp;
+      typename std::iterator_traits<_Iterator2>::reference _M_value;
+
+      _Iter_bind2nd_iter(_Compare __comp, _Iterator2 __it2)
+	: _M_comp(__comp), _M_value(*__it2)
+      {}
+
+      bool
+      operator()(_Iterator1 __it1)
+      { return bool(_M_comp(*__it1, _M_value)); }
+    };
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _Iterator>
+    _Iter_equals_iter<_Iterator1, _Iterator>
+    __bind2nd(_Iter_equal_to_iter<_Iterator1, _Iterator2>,
+	      _Iterator __it)
+    { return _Iter_equals_iter<_Iterator1, _Iterator>(__it); }
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _Iterator, typename _Compare>
+    _Iter_bind2nd_iter<_Iterator1, _Iterator, _Compare>
+    __bind2nd(_Iter_comp_iter<_Iterator1, _Iterator2, _Compare> __comp,
+	      _Iterator __it)
+    {
+      return _Iter_bind2nd_iter<_Iterator1, _Iterator,
+				_Compare>(__comp._M_comp, __it);
+    }
+
+  template<typename _Iterator, typename _Value>
+    _Iter_equals_val<_Iterator, _Value>
+    __bind2nd(_Iter_equal_to_val<_Iterator, _Value>, _Value& __value)
+    { return _Iter_equals_val<_Iterator, _Value>(__value); }
+
+  template<typename _Iterator, typename _Value, typename _Compare>
+    _Iter_bind2nd_val<_Iterator, _Value, _Compare>
+    __bind2nd(_Iter_comp_val<_Iterator, _Value, _Compare> __comp,
+	      _Value& __value)
+    {
+      return _Iter_bind2nd_val<_Iterator, _Value, _Compare>(__comp._M_comp,
+							    __value);
+    }
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _Compare>
+    struct _Iter_bind1st_iter
+    {
+      _Compare _M_comp;
+      typename std::iterator_traits<_Iterator1>::reference _M_value;
+
+      _Iter_bind1st_iter(_Compare __comp, _Iterator1 __it1)
+	: _M_comp(__comp), _M_value(*__it1)
+      {}
+
+      bool
+      operator()(_Iterator2 __it2)
+      { return bool(_M_comp(_M_value, *__it2)); }
+    };
+
+  template<typename _Iterator1, typename _Iterator2>
+    _Iter_equals_iter<_Iterator1, _Iterator2, true>
+    __bind1st(_Iter_equal_to_iter<_Iterator1, _Iterator2>,
+	      _Iterator1 __it1)
+    { return _Iter_equals_iter<_Iterator1, _Iterator2, true>(__it1); }
+
+  template<typename _Iterator1, typename _Iterator2, typename _Compare>
+    _Iter_bind1st_iter<_Iterator1, _Iterator2, _Compare>
+    __bind1st(_Iter_comp_iter<_Iterator1, _Iterator2, _Compare> __comp,
+	      _Iterator1 __it1)
+    {
+      return _Iter_bind1st_iter<_Iterator1, _Iterator2,
+				_Compare>(__comp._M_comp, __it1);
+    }
+
+  template<typename _Iterator, typename _Predicate>
+    struct _Iter_negate
+    {
+      _Predicate _M_pred;
+
+      _Iter_negate(_Predicate __pred)
+	: _M_pred(__pred)
+      {}
+
+      bool
+      operator()(_Iterator __it)
+      { return !bool(_M_pred(*__it)); }
+    };
+
+  template<typename _Iterator, typename _Predicate>
+    _Iter_negate<_Iterator, _Predicate>
+    __negate(_Iter_pred<_Iterator, _Predicate> __pred)
+    { return _Iter_negate<_Iterator, _Predicate>(__pred._M_pred); }
+
+  template<typename _Iterator,
+	   typename _OtherIt1, typename _OtherIt2>
+    _Iter_less_iter<_Iterator>
+    __rebind(_Iter_less_iter<_OtherIt1, _OtherIt2>, _Iterator)
+    { return _Iter_less_iter<_Iterator>(); }
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _OtherIt1, typename _OtherIt2>
+    _Iter_less_iter<_Iterator1, _Iterator2>
+    __rebind(_Iter_less_iter<_OtherIt1, _OtherIt2>, _Iterator1, _Iterator2)
+    { return _Iter_less_iter<_Iterator1, _Iterator2>(); }
+
+  template<typename _Iterator,
+	   typename _OtherIt1, typename _OtherIt2>
+    _Iter_equal_to_iter<_Iterator>
+    __rebind(_Iter_equal_to_iter<_OtherIt1, _OtherIt2>, _Iterator)
+    { return _Iter_equal_to_iter<_Iterator>(); }
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _OtherIt1, typename _OtherIt2>
+    _Iter_equal_to_iter<_Iterator1, _Iterator2>
+    __rebind(_Iter_equal_to_iter<_OtherIt1, _OtherIt2>, _Iterator1, _Iterator2)
+    { return _Iter_equal_to_iter<_Iterator1, _Iterator2>(); }
+
+  template<typename _Iterator,
+	   typename _OtherIt1, typename _OtherIt2, typename _Compare>
+    _Iter_comp_iter<_Iterator, _Iterator, _Compare>
+    __rebind(_Iter_comp_iter<_OtherIt1, _OtherIt2, _Compare> __comp,
+	     _Iterator)
+    { return _Iter_comp_iter<_Iterator, _Iterator, _Compare>(__comp._M_comp); }
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _OtherIt1, typename _OtherIt2, typename _Compare>
+    _Iter_comp_iter<_Iterator1, _Iterator2, _Compare>
+    __rebind(_Iter_comp_iter<_OtherIt1, _OtherIt2, _Compare> __comp,
+	     _Iterator1, _Iterator2)
+    {
+      return _Iter_comp_iter<_Iterator1, _Iterator2, _Compare>(__comp._M_comp);
+    }
+
+  template<typename _Iterator1, typename _Iterator2,
+	   typename _Value, typename _Compare>
+    _Iter_comp_val<_Iterator1, _Value, _Compare>
+    __rebind_iter_comp_val(_Iter_comp_iter<_Iterator1, _Iterator2,
+					   _Compare> __comp,
+			   const _Value&)
+    { return _Iter_comp_val<_Iterator1, _Value, _Compare>(__comp._M_comp); }
+
+  template<typename _Iterator1, typename _Iterator2, typename _Value>
+    _Iter_less_val<_Iterator1, _Value>
+    __rebind_iter_comp_val(_Iter_less_iter<_Iterator1, _Iterator2>,
+			   const _Value&)
+    { return _Iter_less_val<_Iterator1, _Value>(); }
+
+  template<typename _Iterator1, typename _Iterator2, typename _Value>
+    _Iter_equal_to_val<_Iterator1, _Value>
+    __rebind_iter_comp_val(_Iter_equal_to_iter<_Iterator1, _Iterator2>,
+			   const _Value&)
+    { return _Iter_equal_to_val<_Iterator1, _Value>(); }
+
+  template<typename _Iterator1, typename _Iterator2, typename _Compare>
+    _Iter_comp_val<_Iterator1,
+		   typename std::iterator_traits<_Iterator1>::value_type const,
+		   _Compare>
+    __rebind_iter_cval(_Iter_comp_iter<_Iterator1, _Iterator2, _Compare> __comp,
+		       _Iterator1)
+    {
+      typedef typename std::iterator_traits<_Iterator1>::value_type _ValType;
+      return _Iter_comp_val<_Iterator1, _ValType const,
+			    _Compare>(__comp._M_comp);
+    }
+
+  template<typename _Iterator1, typename _Iterator2>
+    _Iter_less_val<_Iterator1,
+		   typename std::iterator_traits<_Iterator1>::value_type const>
+    __rebind_iter_cval(_Iter_less_iter<_Iterator1, _Iterator2>, _Iterator1)
+    {
+      typedef typename std::iterator_traits<_Iterator1>::value_type _ValType;
+      return _Iter_less_val<_Iterator1, _ValType const>();
+    }
+
+  template<typename _Iterator1, typename _Iterator2, typename _Compare>
+    _Val_comp_iter<typename std::iterator_traits<_Iterator1>::value_type,
+		   _Iterator1, _Compare>
+    __rebind_val_comp_iter(_Iter_comp_iter<_Iterator1, _Iterator2,
+					   _Compare> __comp,
+			   _Iterator1)
+    {
+      typedef typename std::iterator_traits<_Iterator1>::value_type _ValType;
+      return _Val_comp_iter<_ValType, _Iterator1, _Compare>(__comp._M_comp);
+    }
+
+  template<typename _Iterator1, typename _Iterator2>
+    _Val_less_iter<typename std::iterator_traits<_Iterator1>::value_type,
+		   _Iterator1>
+    __rebind_val_comp_iter(_Iter_less_iter<_Iterator1, _Iterator2>,
+			   _Iterator1)
+    {
+      typedef typename std::iterator_traits<_Iterator1>::value_type _ValType;
+      return _Val_less_iter<_ValType, _Iterator1>();
+    }
+
+  template<typename _Iterator1, typename _Iterator2, typename _Compare>
+    _Val_comp_iter<typename std::iterator_traits<_Iterator1>::value_type const,
+		   _Iterator1, _Compare>
+    __rebind_cval_comp_iter(_Iter_comp_iter<_Iterator1, _Iterator2,
+					    _Compare> __comp,
+			    _Iterator1)
+    {
+      typedef typename std::iterator_traits<_Iterator1>::value_type _ValType;
+      return _Val_comp_iter<const _ValType, _Iterator1,
+			    _Compare>(__comp._M_comp);
+    }
+
+  template<typename _Iterator1, typename _Iterator2>
+    _Val_less_iter<typename std::iterator_traits<_Iterator1>::value_type const,
+		   _Iterator1>
+    __rebind_cval_comp_iter(_Iter_less_iter<_Iterator1, _Iterator2>,
+			    _Iterator1)
+    {
+      typedef typename std::iterator_traits<_Iterator1>::value_type _ValType;
+      return _Val_less_iter<const _ValType, _Iterator1>();
+    }
+
+} // namespace __ops
+} // namespace __gnu_cxx
+
+#endif

Property changes on: include/bits/predefined_ops.h
___________________________________________________________________
Added: svn:eol-style
   + native

Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h	(revision 189412)
+++ include/bits/stl_algo.h	(working copy)
@@ -1,7 +1,7 @@
 // Algorithm implementation -*- C++ -*-
 
 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
-// 2010, 2011
+// 2010, 2011, 2012
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -62,10 +62,10 @@
 #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
-#include <functional> // for std::bind
 #endif
 
 // See concept_check.h for the __glibcxx_*_requires macros.
@@ -74,51 +74,22 @@
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
-  /// Swaps the median value of *__a, *__b and *__c to *__a
-  template<typename _Iterator>
-    void
-    __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
-    {
-      // concept requirements
-      __glibcxx_function_requires(_LessThanComparableConcept<
-	    typename iterator_traits<_Iterator>::value_type>)
-
-      if (*__a < *__b)
-	{
-	  if (*__b < *__c)
-	    std::iter_swap(__a, __b);
-	  else if (*__a < *__c)
-	    std::iter_swap(__a, __c);
-	}
-      else if (*__a < *__c)
-	return;
-      else if (*__b < *__c)
-	std::iter_swap(__a, __c);
-      else
-	std::iter_swap(__a, __b);
-    }
-
   /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
   template<typename _Iterator, typename _Compare>
     void
     __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
 			_Compare __comp)
     {
-      // concept requirements
-      __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
-	    typename iterator_traits<_Iterator>::value_type,
-	    typename iterator_traits<_Iterator>::value_type>)
-
-      if (__comp(*__a, *__b))
+      if (__comp(__a, __b))
 	{
-	  if (__comp(*__b, *__c))
+	  if (__comp(__b, __c))
 	    std::iter_swap(__a, __b);
-	  else if (__comp(*__a, *__c))
+	  else if (__comp(__a, __c))
 	    std::iter_swap(__a, __c);
 	}
-      else if (__comp(*__a, *__c))
+      else if (__comp(__a, __c))
 	return;
-      else if (__comp(*__b, *__c))
+      else if (__comp(__b, __c))
 	std::iter_swap(__a, __c);
       else
 	std::iter_swap(__a, __b);
@@ -126,76 +97,17 @@
 
   // 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
     __find_if(_InputIterator __first, _InputIterator __last,
 	      _Predicate __pred, input_iterator_tag)
     {
-      while (__first != __last && !bool(__pred(*__first)))
+      while (__first != __last && !__pred(__first))
 	++__first;
       return __first;
     }
 
-  /// This is an overload used by find() for the RAI case.
-  template<typename _RandomAccessIterator, typename _Tp>
-    _RandomAccessIterator
-    __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
-	   const _Tp& __val, random_access_iterator_tag)
-    {
-      typename iterator_traits<_RandomAccessIterator>::difference_type
-	__trip_count = (__last - __first) >> 2;
-
-      for (; __trip_count > 0; --__trip_count)
-	{
-	  if (*__first == __val)
-	    return __first;
-	  ++__first;
-
-	  if (*__first == __val)
-	    return __first;
-	  ++__first;
-
-	  if (*__first == __val)
-	    return __first;
-	  ++__first;
-
-	  if (*__first == __val)
-	    return __first;
-	  ++__first;
-	}
-
-      switch (__last - __first)
-	{
-	case 3:
-	  if (*__first == __val)
-	    return __first;
-	  ++__first;
-	case 2:
-	  if (*__first == __val)
-	    return __first;
-	  ++__first;
-	case 1:
-	  if (*__first == __val)
-	    return __first;
-	  ++__first;
-	case 0:
-	default:
-	  return __last;
-	}
-    }
-
   /// This is an overload used by find_if() for the RAI case.
   template<typename _RandomAccessIterator, typename _Predicate>
     _RandomAccessIterator
@@ -207,19 +119,19 @@
 
       for (; __trip_count > 0; --__trip_count)
 	{
-	  if (__pred(*__first))
+	  if (__pred(__first))
 	    return __first;
 	  ++__first;
 
-	  if (__pred(*__first))
+	  if (__pred(__first))
 	    return __first;
 	  ++__first;
 
-	  if (__pred(*__first))
+	  if (__pred(__first))
 	    return __first;
 	  ++__first;
 
-	  if (__pred(*__first))
+	  if (__pred(__first))
 	    return __first;
 	  ++__first;
 	}
@@ -227,15 +139,15 @@
       switch (__last - __first)
 	{
 	case 3:
-	  if (__pred(*__first))
+	  if (__pred(__first))
 	    return __first;
 	  ++__first;
 	case 2:
-	  if (__pred(*__first))
+	  if (__pred(__first))
 	    return __first;
 	  ++__first;
 	case 1:
-	  if (__pred(*__first))
+	  if (__pred(__first))
 	    return __first;
 	  ++__first;
 	case 0:
@@ -244,73 +156,15 @@
 	}
     }
 
-  /// 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::__negate(__pred),
+			    std::__iterator_category(__first));
     }
 
   /// Like find_if_not(), but uses and updates a count of the
@@ -321,7 +175,7 @@
     __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
     {
       for (; __len; --__len, ++__first)
-	if (!bool(__pred(*__first)))
+	if (!__pred(__first))
 	  break;
       return __first;
     }
@@ -339,86 +193,53 @@
   // count_if
   // search
 
-  /**
-   *  This is an uglified
-   *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
-   *  overloaded for forward iterators.
-  */
-  template<typename _ForwardIterator, typename _Integer, typename _Tp>
-    _ForwardIterator
-    __search_n(_ForwardIterator __first, _ForwardIterator __last,
-	       _Integer __count, const _Tp& __val,
-	       std::forward_iterator_tag)
+  template<typename _ForwardIterator1, typename _ForwardIterator2,
+	   typename _BinaryPredicate>
+    _ForwardIterator1
+    __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+	     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+	     _BinaryPredicate  __predicate)
     {
-      __first = _GLIBCXX_STD_A::find(__first, __last, __val);
-      while (__first != __last)
-	{
-	  typename iterator_traits<_ForwardIterator>::difference_type
-	    __n = __count;
-	  _ForwardIterator __i = __first;
-	  ++__i;
-	  while (__i != __last && __n != 1 && *__i == __val)
-	    {
-	      ++__i;
-	      --__n;
-	    }
-	  if (__n == 1)
-	    return __first;
-	  if (__i == __last)
-	    return __last;
-	  __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
-	}
-      return __last;
-    }
+      // Test for empty ranges
+      if (__first1 == __last1 || __first2 == __last2)
+	return __first1;
 
-  /**
-   *  This is an uglified
-   *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
-   *  overloaded for random access iterators.
-  */
-  template<typename _RandomAccessIter, typename _Integer, typename _Tp>
-    _RandomAccessIter
-    __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
-	       _Integer __count, const _Tp& __val, 
-	       std::random_access_iterator_tag)
-    {
-      
-      typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
-	_DistanceType;
+      // Test for a pattern of length 1.
+      _ForwardIterator2 __p1(__first2);
+      if (++__p1 == __last2)
+	return std::__find_if(__first1, __last1,
+			      __gnu_cxx::__ops::__bind2nd(__predicate, __first2),
+			      std::__iterator_category(__first1));
 
-      _DistanceType __tailSize = __last - __first;
-      const _DistanceType __pattSize = __count;
+      // General case.
+      _ForwardIterator2 __p;
+      _ForwardIterator1 __current = __first1;
 
-      if (__tailSize < __pattSize)
-        return __last;
+      for (;;)
+	{
+	  __first1 =
+	    std::__find_if(__first1, __last1,
+			   __gnu_cxx::__ops::__bind2nd(__predicate, __first2),
+			   std::__iterator_category(__first1));
 
-      const _DistanceType __skipOffset = __pattSize - 1;
-      _RandomAccessIter __lookAhead = __first + __skipOffset;
-      __tailSize -= __pattSize;
+	  if (__first1 == __last1)
+	    return __last1;
 
-      while (1) // the main loop...
-	{
-	  // __lookAhead here is always pointing to the last element of next 
-	  // possible match.
-	  while (!(*__lookAhead == __val)) // the skip loop...
+	  __p = __p1;
+	  __current = __first1;
+	  if (++__current == __last1)
+	    return __last1;
+
+	  while (__predicate(__current, __p))
 	    {
-	      if (__tailSize < __pattSize)
-		return __last;  // Failure
-	      __lookAhead += __pattSize;
-	      __tailSize -= __pattSize;
+	      if (++__p == __last2)
+		return __first1;
+	      if (++__current == __last1)
+		return __last1;
 	    }
-	  _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;
+	  ++__first1;
 	}
+      return __first1;
     }
 
   // search_n
@@ -432,20 +253,20 @@
   template<typename _ForwardIterator, typename _Integer, typename _Tp,
            typename _BinaryPredicate>
     _ForwardIterator
-    __search_n(_ForwardIterator __first, _ForwardIterator __last,
-	       _Integer __count, const _Tp& __val,
-	       _BinaryPredicate __binary_pred, std::forward_iterator_tag)
+    __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
+		   _Integer __count, const _Tp& __val,
+		   _BinaryPredicate __binary_pred, std::forward_iterator_tag)
     {
-      while (__first != __last && !bool(__binary_pred(*__first, __val)))
-        ++__first;
-
+      __first = std::__find_if(__first, __last,
+			       __gnu_cxx::__ops::__bind2nd(__binary_pred, __val),
+			       std::__iterator_category(__first));
       while (__first != __last)
 	{
 	  typename iterator_traits<_ForwardIterator>::difference_type
 	    __n = __count;
 	  _ForwardIterator __i = __first;
 	  ++__i;
-	  while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
+	  while (__i != __last && __n != 1 && __binary_pred(__i, __val))
 	    {
 	      ++__i;
 	      --__n;
@@ -454,10 +275,10 @@
 	    return __first;
 	  if (__i == __last)
 	    return __last;
-	  __first = ++__i;
-	  while (__first != __last
-		 && !bool(__binary_pred(*__first, __val)))
-	    ++__first;
+	  __first
+	    = std::__find_if(++__i, __last,
+			     __gnu_cxx::__ops::__bind2nd(__binary_pred, __val),
+			     std::__iterator_category(__first));
 	}
       return __last;
     }
@@ -471,12 +292,12 @@
   template<typename _RandomAccessIter, typename _Integer, typename _Tp,
 	   typename _BinaryPredicate>
     _RandomAccessIter
-    __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
-	       _Integer __count, const _Tp& __val,
-	       _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
+    __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
+		   _Integer __count, const _Tp& __val,
+		   _BinaryPredicate __binary_pred,
+		   std::random_access_iterator_tag)
     {
-      
-      typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
+      typedef typename iterator_traits<_RandomAccessIter>::difference_type
 	_DistanceType;
 
       _DistanceType __tailSize = __last - __first;
@@ -493,7 +314,7 @@
 	{
 	  // __lookAhead here is always pointing to the last element of next 
 	  // possible match.
-	  while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
+	  while (!__binary_pred(__lookAhead, __val)) // the skip loop...
 	    {
 	      if (__tailSize < __pattSize)
 		return __last;  // Failure
@@ -502,7 +323,7 @@
 	    }
 	  _DistanceType __remainder = __skipOffset;
 	  for (_RandomAccessIter __backTrack = __lookAhead - 1; 
-	       __binary_pred(*__backTrack, __val); --__backTrack)
+	       __binary_pred(__backTrack, __val); --__backTrack)
 	    {
 	      if (--__remainder == 0)
 		return (__lookAhead - __skipOffset); // Success
@@ -514,34 +335,27 @@
 	}
     }
 
-  // find_end for forward iterators.
-  template<typename _ForwardIterator1, typename _ForwardIterator2>
-    _ForwardIterator1
-    __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-	       _ForwardIterator2 __first2, _ForwardIterator2 __last2,
-	       forward_iterator_tag, forward_iterator_tag)
+  template<typename _ForwardIterator, typename _Integer, typename _Tp,
+           typename _BinaryPredicate>
+    _ForwardIterator
+    __search_n(_ForwardIterator __first, _ForwardIterator __last,
+	       _Integer __count, const _Tp& __val,
+	       _BinaryPredicate __binary_pred)
     {
-      if (__first2 == __last2)
-	return __last1;
-      else
-	{
-	  _ForwardIterator1 __result = __last1;
-	  while (1)
-	    {
-	      _ForwardIterator1 __new_result
-		= _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
-	      if (__new_result == __last1)
-		return __result;
-	      else
-		{
-		  __result = __new_result;
-		  __first1 = __new_result;
-		  ++__first1;
-		}
-	    }
-	}
+      if (__count <= 0)
+	return __first;
+
+      if (__count == 1)
+	return std::__find_if(__first, __last,
+		__gnu_cxx::__ops::__bind2nd(__binary_pred, __val),
+		std::__iterator_category(__first));
+
+      return std::__search_n_aux(__first, __last, __count, __val,
+				 __binary_pred,
+				 std::__iterator_category(__first));
     }
 
+  // find_end for forward iterators.
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
     _ForwardIterator1
@@ -558,8 +372,7 @@
 	  while (1)
 	    {
 	      _ForwardIterator1 __new_result
-		= _GLIBCXX_STD_A::search(__first1, __last1, __first2,
-					 __last2, __comp);
+		= std::__search(__first1, __last1, __first2, __last2, __comp);
 	      if (__new_result == __last1)
 		return __result;
 	      else
@@ -573,40 +386,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
@@ -628,9 +407,10 @@
 
       _RevIterator1 __rlast1(__first1);
       _RevIterator2 __rlast2(__first2);
-      _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
-					    _RevIterator2(__last2), __rlast2,
-					    __comp);
+      _RevIterator1 __rresult =
+	std::__search(
+	  _RevIterator1(__last1), __rlast1, _RevIterator2(__last2), __rlast2,
+	  __gnu_cxx::__ops::__rebind(__comp, __rlast1, __rlast2));
 
       if (__rresult == __rlast1)
 	return __last1;
@@ -683,8 +463,9 @@
       __glibcxx_requires_valid_range(__first2, __last2);
 
       return std::__find_end(__first1, __last1, __first2, __last2,
-			     std::__iterator_category(__first1),
-			     std::__iterator_category(__first2));
+		std::__iterator_category(__first1),
+		std::__iterator_category(__first2),
+		__gnu_cxx::__ops::__iter_equal_to_iter(__first1, __first2));
     }
 
   /**
@@ -732,9 +513,8 @@
       __glibcxx_requires_valid_range(__first2, __last2);
 
       return std::__find_end(__first1, __last1, __first2, __last2,
-			     std::__iterator_category(__first1),
-			     std::__iterator_category(__first2),
-			     __comp);
+	std::__iterator_category(__first1), std::__iterator_category(__first2),
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first1, __first2));
     }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -810,7 +590,9 @@
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 	      typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
-      return std::__find_if_not(__first, __last, __pred);
+
+      return std::__find_if_not(__first, __last,
+				__gnu_cxx::__ops::__pred_iter(__pred, __first));
     }
 
   /**
@@ -879,6 +661,20 @@
     }
 #endif
 
+  template<typename _InputIterator, typename _OutputIterator,
+	   typename _Predicate>
+    _OutputIterator
+    __remove_copy_if(_InputIterator __first, _InputIterator __last,
+		     _OutputIterator __result, _Predicate __pred)
+    {
+      for (; __first != __last; ++__first)
+	if (!__pred(__first))
+	  {
+	    *__result = *__first;
+	    ++__result;
+	  }
+      return __result;
+    }
 
   /**
    *  @brief Copy a sequence, removing elements of a given value.
@@ -907,13 +703,10 @@
 	    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::__bind2nd(__gnu_cxx::__ops
+				    ::__iter_equal_to_cval(__first, __value),
+				    __value));
     }
 
   /**
@@ -945,13 +738,8 @@
 	    typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      for (; __first != __last; ++__first)
-	if (!bool(__pred(*__first)))
-	  {
-	    *__result = *__first;
-	    ++__result;
-	  }
-      return __result;
+      return std::__remove_copy_if(__first, __last, __result,
+				__gnu_cxx::__ops::__pred_iter(__pred, __first));
     }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -993,7 +781,6 @@
       return __result;
     }
 
-
   template<typename _InputIterator, typename _Size, typename _OutputIterator>
     _OutputIterator
     __copy_n(_InputIterator __first, _Size __n,
@@ -1095,6 +882,26 @@
     }
 #endif
 
+  template<typename _ForwardIterator, typename _Predicate>
+    _ForwardIterator
+    __remove_if(_ForwardIterator __first, _ForwardIterator __last,
+		_Predicate __pred)
+    {
+      __first = std::__find_if(__first, __last, __pred,
+			       std::__iterator_category(__first));
+      if (__first == __last)
+        return __first;
+      _ForwardIterator __result = __first;
+      ++__first;
+      for (; __first != __last; ++__first)
+        if (!__pred(__first))
+          {
+            *__result = _GLIBCXX_MOVE(*__first);
+            ++__result;
+          }
+      return __result;
+    }
+
   /**
    *  @brief Remove elements from a sequence.
    *  @ingroup mutating_algorithms
@@ -1124,18 +931,10 @@
 	    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::__bind2nd(__gnu_cxx::__ops
+				    ::__iter_equal_to_cval(__first, __value),
+				    __value));
     }
 
   /**
@@ -1167,18 +966,44 @@
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
-      if(__first == __last)
-        return __first;
-      _ForwardIterator __result = __first;
+      return std::__remove_if(__first, __last,
+			      __gnu_cxx::__ops::__pred_iter(__pred, __first));
+    }
+
+  template<typename _ForwardIterator, typename _BinaryPredicate>
+    _ForwardIterator
+    __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
+		    _BinaryPredicate __binary_pred)
+    {
+      if (__first == __last)
+	return __last;
+      _ForwardIterator __next = __first;
+      while (++__next != __last)
+	{
+	  if (__binary_pred(__first, __next))
+	    return __first;
+	  __first = __next;
+	}
+      return __last;
+    }
+
+  template<typename _ForwardIterator, typename _BinaryPredicate>
+    _ForwardIterator
+    __unique(_ForwardIterator __first, _ForwardIterator __last,
+	     _BinaryPredicate __binary_pred)
+    {
+      // Skip the beginning, if already unique.
+      __first = std::__adjacent_find(__first, __last, __binary_pred);
+      if (__first == __last)
+	return __last;
+
+      // Do the real copy work.
+      _ForwardIterator __dest = __first;
       ++__first;
-      for(; __first != __last; ++__first)
-        if(!bool(__pred(*__first)))
-          {
-            *__result = _GLIBCXX_MOVE(*__first);
-            ++__result;
-          }
-      return __result;
+      while (++__first != __last)
+	if (!__binary_pred(__dest, __first))
+	  *++__dest = _GLIBCXX_MOVE(*__first);
+      return ++__dest;
     }
 
   /**
@@ -1206,18 +1031,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_iter(__first));
     }
 
   /**
@@ -1248,86 +1063,11 @@
 		typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      // Skip the beginning, if already unique.
-      __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
-      if (__first == __last)
-	return __last;
-
-      // Do the real copy work.
-      _ForwardIterator __dest = __first;
-      ++__first;
-      while (++__first != __last)
-	if (!bool(__binary_pred(*__dest, *__first)))
-	  *++__dest = _GLIBCXX_MOVE(*__first);
-      return ++__dest;
+      return __unique(__first, __last,
+		__gnu_cxx::__ops::__iter_comp_iter(__binary_pred, __first));
     }
 
   /**
-   *  This is an uglified unique_copy(_InputIterator, _InputIterator,
-   *                                  _OutputIterator)
-   *  overloaded for forward iterators and output iterator as result.
-  */
-  template<typename _ForwardIterator, typename _OutputIterator>
-    _OutputIterator
-    __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
-		  _OutputIterator __result,
-		  forward_iterator_tag, output_iterator_tag)
-    {
-      // concept requirements -- taken care of in dispatching function
-      _ForwardIterator __next = __first;
-      *__result = *__first;
-      while (++__next != __last)
-	if (!(*__first == *__next))
-	  {
-	    __first = __next;
-	    *++__result = *__first;
-	  }
-      return ++__result;
-    }
-
-  /**
-   *  This is an uglified unique_copy(_InputIterator, _InputIterator,
-   *                                  _OutputIterator)
-   *  overloaded for input iterators and output iterator as result.
-  */
-  template<typename _InputIterator, typename _OutputIterator>
-    _OutputIterator
-    __unique_copy(_InputIterator __first, _InputIterator __last,
-		  _OutputIterator __result,
-		  input_iterator_tag, output_iterator_tag)
-    {
-      // concept requirements -- taken care of in dispatching function
-      typename iterator_traits<_InputIterator>::value_type __value = *__first;
-      *__result = __value;
-      while (++__first != __last)
-	if (!(__value == *__first))
-	  {
-	    __value = *__first;
-	    *++__result = __value;
-	  }
-      return ++__result;
-    }
-
-  /**
-   *  This is an uglified unique_copy(_InputIterator, _InputIterator,
-   *                                  _OutputIterator)
-   *  overloaded for input iterators and forward iterator as result.
-  */
-  template<typename _InputIterator, typename _ForwardIterator>
-    _ForwardIterator
-    __unique_copy(_InputIterator __first, _InputIterator __last,
-		  _ForwardIterator __result,
-		  input_iterator_tag, forward_iterator_tag)
-    {
-      // concept requirements -- taken care of in dispatching function
-      *__result = *__first;
-      while (++__first != __last)
-	if (!(*__result == *__first))
-	  *++__result = *__first;
-      return ++__result;
-    }
-
-  /**
    *  This is an uglified
    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
    *              _BinaryPredicate)
@@ -1340,15 +1080,11 @@
 		  _OutputIterator __result, _BinaryPredicate __binary_pred,
 		  forward_iterator_tag, output_iterator_tag)
     {
-      // concept requirements -- iterators already checked
-      __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
-	  typename iterator_traits<_ForwardIterator>::value_type,
-	  typename iterator_traits<_ForwardIterator>::value_type>)
-
+      // concept requirements -- taken care of in dispatching function
       _ForwardIterator __next = __first;
       *__result = *__first;
       while (++__next != __last)
-	if (!bool(__binary_pred(*__first, *__next)))
+	if (!__binary_pred(__first, __next))
 	  {
 	    __first = __next;
 	    *++__result = *__first;
@@ -1369,15 +1105,15 @@
 		  _OutputIterator __result, _BinaryPredicate __binary_pred,
 		  input_iterator_tag, output_iterator_tag)
     {
-      // concept requirements -- iterators already checked
-      __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
-	  typename iterator_traits<_InputIterator>::value_type,
-	  typename iterator_traits<_InputIterator>::value_type>)
-
+      // concept requirements -- taken care of in dispatching function
       typename iterator_traits<_InputIterator>::value_type __value = *__first;
+      __decltype(__gnu_cxx::__ops::__rebind_iter_comp_val(__binary_pred,
+							  __value))
+	__rebound_pred
+	= __gnu_cxx::__ops::__rebind_iter_comp_val(__binary_pred, __value);
       *__result = __value;
       while (++__first != __last)
-	if (!bool(__binary_pred(__value, *__first)))
+	if (!__rebound_pred(__first, __value))
 	  {
 	    __value = *__first;
 	    *++__result = __value;
@@ -1398,14 +1134,13 @@
 		  _ForwardIterator __result, _BinaryPredicate __binary_pred,
 		  input_iterator_tag, forward_iterator_tag)
     {
-      // concept requirements -- iterators already checked
-      __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
-	  typename iterator_traits<_ForwardIterator>::value_type,
-	  typename iterator_traits<_InputIterator>::value_type>)
-
+      // concept requirements -- taken care of in dispatching function
+      __decltype(__gnu_cxx::__ops::__rebind(__binary_pred, __result, __first))
+	__rebound_pred
+	= __gnu_cxx::__ops::__rebind(__binary_pred, __result, __first);
       *__result = *__first;
       while (++__first != __last)
-	if (!bool(__binary_pred(*__result, *__first)))
+	if (!__rebound_pred(__result, __first))
 	  *++__result = *__first;
       return ++__result;
     }
@@ -1707,9 +1442,8 @@
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
 
-      typedef typename iterator_traits<_ForwardIterator>::iterator_category
-	_IterType;
-      std::__rotate(__first, __middle, __last, _IterType());
+      std::__rotate(__first, __middle, __last,
+		    std::__iterator_category(__first));
     }
 
   /**
@@ -1850,14 +1584,14 @@
 	{
 	  _ForwardIterator __result1 = __first;
 	  _Pointer __result2 = __buffer;
-	  // The precondition guarantees that !__pred(*__first), so
+	  // The precondition guarantees that !__pred(__first), so
 	  // move that element to the buffer before starting the loop.
 	  // This ensures that we only call __pred once per element.
 	  *__result2 = _GLIBCXX_MOVE(*__first);
 	  ++__result2;
 	  ++__first;
 	  for (; __first != __last; ++__first)
-	    if (__pred(*__first))
+	    if (__pred(__first))
 	      {
 		*__result1 = _GLIBCXX_MOVE(*__first);
 		++__result1;
@@ -1894,6 +1628,37 @@
 	}
     }
 
+  template<typename _ForwardIterator, typename _Predicate>
+    _ForwardIterator
+    __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
+		       _Predicate __pred)
+    {
+      __first = std::__find_if_not(__first, __last, __pred);
+
+      if (__first == __last)
+	return __first;
+      else
+	{
+	  typedef typename iterator_traits<_ForwardIterator>::value_type
+	    _ValueType;
+	  typedef typename iterator_traits<_ForwardIterator>::difference_type
+	    _DistanceType;
+
+	  _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
+								__last);
+	  if (__buf.size() > 0)
+	    return
+	      std::__stable_partition_adaptive(__first, __last, __pred,
+					  _DistanceType(__buf.requested_size()),
+					  __buf.begin(),
+					  _DistanceType(__buf.size()));
+	  else
+	    return
+	      std::__inplace_stable_partition(__first, __pred,
+					 _DistanceType(__buf.requested_size()));
+	}
+    }
+
   /**
    *  @brief Move elements for which a predicate is true to the beginning
    *         of a sequence, preserving relative ordering.
@@ -1923,60 +1688,66 @@
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      __first = std::__find_if_not(__first, __last, __pred);
-
-      if (__first == __last)
-	return __first;
-      else
-	{
-	  typedef typename iterator_traits<_ForwardIterator>::value_type
-	    _ValueType;
-	  typedef typename iterator_traits<_ForwardIterator>::difference_type
-	    _DistanceType;
-
-	  _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
-								__last);
-	if (__buf.size() > 0)
-	  return
-	    std::__stable_partition_adaptive(__first, __last, __pred,
-					  _DistanceType(__buf.requested_size()),
-					  __buf.begin(),
-					  _DistanceType(__buf.size()));
-	else
-	  return
-	    std::__inplace_stable_partition(__first, __pred,
-					 _DistanceType(__buf.requested_size()));
-	}
+      return std::__stable_partition(__first, __last,
+				__gnu_cxx::__ops::__pred_iter(__pred, __first));
     }
 
   /// This is a helper function for the sort routines.
-  template<typename _RandomAccessIterator>
-    void
-    __heap_select(_RandomAccessIterator __first,
-		  _RandomAccessIterator __middle,
-		  _RandomAccessIterator __last)
-    {
-      std::make_heap(__first, __middle);
-      for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
-	if (*__i < *__first)
-	  std::__pop_heap(__first, __middle, __i);
-    }
-
-  /// This is a helper function for the sort routines.
   template<typename _RandomAccessIterator, typename _Compare>
     void
     __heap_select(_RandomAccessIterator __first,
 		  _RandomAccessIterator __middle,
 		  _RandomAccessIterator __last, _Compare __comp)
     {
-      std::make_heap(__first, __middle, __comp);
+      std::__make_heap(__first, __middle, __comp);
       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
-	if (__comp(*__i, *__first))
+	if (__comp(__i, __first))
 	  std::__pop_heap(__first, __middle, __i, __comp);
     }
 
   // partial_sort
 
+  template<typename _InputIterator, typename _RandomAccessIterator,
+	   typename _Compare>
+    _RandomAccessIterator
+    __partial_sort_copy(_InputIterator __first, _InputIterator __last,
+			_RandomAccessIterator __result_first,
+			_RandomAccessIterator __result_last,
+			_Compare __comp)
+    {
+      typedef typename iterator_traits<_InputIterator>::value_type
+	_InputValueType;
+      typedef iterator_traits<_RandomAccessIterator> _RItTraits;
+      typedef typename _RItTraits::difference_type _DistanceType;
+
+      if (__result_first == __result_last)
+	return __result_last;
+      _RandomAccessIterator __result_real_last = __result_first;
+      while (__first != __last && __result_real_last != __result_last)
+	{
+	  *__result_real_last = *__first;
+	  ++__result_real_last;
+	  ++__first;
+	}
+      
+      std::__make_heap(__result_first, __result_real_last,
+		       __gnu_cxx::__ops::__rebind(__comp, __result_first));
+      while (__first != __last)
+	{
+	  if (__comp(__first, __result_first))
+	    std::__adjust_heap(__result_first, _DistanceType(0),
+			       _DistanceType(__result_real_last
+					     - __result_first),
+			       _InputValueType(*__first),
+			       __gnu_cxx::__ops::__rebind(__comp,
+							  __result_first));
+	  ++__first;
+	}
+      std::__sort_heap(__result_first, __result_real_last,
+		       __gnu_cxx::__ops::__rebind(__comp, __result_first));
+      return __result_real_last;
+    }
+
   /**
    *  @brief Copy the smallest elements of a sequence.
    *  @ingroup sorting_algorithms
@@ -2001,44 +1772,22 @@
 		      _RandomAccessIterator __result_first,
 		      _RandomAccessIterator __result_last)
     {
-      typedef typename iterator_traits<_InputIterator>::value_type
-	_InputValueType;
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_OutputValueType;
-      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
-	_DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
-      __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
-				  _OutputValueType>)
-      __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
-				                     _OutputValueType>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
+      __glibcxx_function_requires(_ConvertibleConcept<
+	    typename iterator_traits<_InputIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_valid_range(__result_first, __result_last);
 
-      if (__result_first == __result_last)
-	return __result_last;
-      _RandomAccessIterator __result_real_last = __result_first;
-      while(__first != __last && __result_real_last != __result_last)
-	{
-	  *__result_real_last = *__first;
-	  ++__result_real_last;
-	  ++__first;
-	}
-      std::make_heap(__result_first, __result_real_last);
-      while (__first != __last)
-	{
-	  if (*__first < *__result_first)
-	    std::__adjust_heap(__result_first, _DistanceType(0),
-			       _DistanceType(__result_real_last
-					     - __result_first),
-			       _InputValueType(*__first));
-	  ++__first;
-	}
-      std::sort_heap(__result_first, __result_real_last);
-      return __result_real_last;
+      return std::__partial_sort_copy(__first, __last,
+	__result_first, __result_last,
+	__gnu_cxx::__ops::__iter_less_iter(__first, __result_first));
     }
 
   /**
@@ -2061,76 +1810,36 @@
    *  @p __comp(*j,*i) is false.
    *  The value returned is @p __result_first+N.
   */
-  template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
+  template<typename _InputIterator, typename _RandomAccessIterator,
+	   typename _Compare>
     _RandomAccessIterator
     partial_sort_copy(_InputIterator __first, _InputIterator __last,
 		      _RandomAccessIterator __result_first,
 		      _RandomAccessIterator __result_last,
 		      _Compare __comp)
     {
-      typedef typename iterator_traits<_InputIterator>::value_type
-	_InputValueType;
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_OutputValueType;
-      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
-	_DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 				  _RandomAccessIterator>)
-      __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
-				  _OutputValueType>)
+      __glibcxx_function_requires(_ConvertibleConcept<
+	    typename iterator_traits<_InputIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _InputValueType, _OutputValueType>)
+	    typename iterator_traits<_InputIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _OutputValueType, _OutputValueType>)
+	    typename iterator_traits<_RandomAccessIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_valid_range(__result_first, __result_last);
 
-      if (__result_first == __result_last)
-	return __result_last;
-      _RandomAccessIterator __result_real_last = __result_first;
-      while(__first != __last && __result_real_last != __result_last)
-	{
-	  *__result_real_last = *__first;
-	  ++__result_real_last;
-	  ++__first;
-	}
-      std::make_heap(__result_first, __result_real_last, __comp);
-      while (__first != __last)
-	{
-	  if (__comp(*__first, *__result_first))
-	    std::__adjust_heap(__result_first, _DistanceType(0),
-			       _DistanceType(__result_real_last
-					     - __result_first),
-			       _InputValueType(*__first),
-			       __comp);
-	  ++__first;
-	}
-      std::sort_heap(__result_first, __result_real_last, __comp);
-      return __result_real_last;
+      return std::__partial_sort_copy(__first, __last,
+				      __result_first, __result_last,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first, __result_first));
     }
 
   /// 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,
@@ -2140,7 +1849,7 @@
 	__val = _GLIBCXX_MOVE(*__last);
       _RandomAccessIterator __next = __last;
       --__next;
-      while (__comp(__val, *__next))
+      while (__comp(__val, __next))
 	{
 	  *__last = _GLIBCXX_MOVE(*__next);
 	  __last = __next;
@@ -2150,74 +1859,38 @@
     }
 
   /// 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))
+	  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::__rebind_val_comp_iter(__comp, __first));
 	}
     }
 
   /// This is a helper function for the sort routine.
-  template<typename _RandomAccessIterator>
-    inline void
-    __unguarded_insertion_sort(_RandomAccessIterator __first,
-			       _RandomAccessIterator __last)
-    {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
-      for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
-	std::__unguarded_linear_insert(__i);
-    }
-
-  /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Compare>
     inline void
     __unguarded_insertion_sort(_RandomAccessIterator __first,
 			       _RandomAccessIterator __last, _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
-	std::__unguarded_linear_insert(__i, __comp);
+	std::__unguarded_linear_insert(__i,
+	  __gnu_cxx::__ops::__rebind_val_comp_iter(__comp, __first));
     }
 
   /**
@@ -2227,21 +1900,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,38 +1916,18 @@
     }
 
   /// This is a helper function...
-  template<typename _RandomAccessIterator, typename _Tp>
+  template<typename _RandomAccessIterator, typename _Compare>
     _RandomAccessIterator
     __unguarded_partition(_RandomAccessIterator __first,
-			  _RandomAccessIterator __last, const _Tp& __pivot)
-    {
-      while (true)
-	{
-	  while (*__first < __pivot)
-	    ++__first;
-	  --__last;
-	  while (__pivot < *__last)
-	    --__last;
-	  if (!(__first < __last))
-	    return __first;
-	  std::iter_swap(__first, __last);
-	  ++__first;
-	}
-    }
-
-  /// This is a helper function...
-  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
-    _RandomAccessIterator
-    __unguarded_partition(_RandomAccessIterator __first,
 			  _RandomAccessIterator __last,
-			  const _Tp& __pivot, _Compare __comp)
+			  _RandomAccessIterator __pivot, _Compare __comp)
     {
       while (true)
 	{
-	  while (__comp(*__first, __pivot))
+	  while (__comp(__first, __pivot))
 	    ++__first;
 	  --__last;
-	  while (__comp(__pivot, *__last))
+	  while (__comp(__pivot, __last))
 	    --__last;
 	  if (!(__first < __last))
 	    return __first;
@@ -2299,18 +1937,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,
@@ -2318,29 +1944,18 @@
     {
       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
       std::__move_median_first(__first, __mid, (__last - 1), __comp);
-      return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
+      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
     }
 
-  /// This is a helper function for the sort routine.
-  template<typename _RandomAccessIterator, typename _Size>
-    void
-    __introsort_loop(_RandomAccessIterator __first,
-		     _RandomAccessIterator __last,
-		     _Size __depth_limit)
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline void
+    __partial_sort(_RandomAccessIterator __first,
+		   _RandomAccessIterator __middle,
+		   _RandomAccessIterator __last,
+		   _Compare __comp)
     {
-      while (__last - __first > int(_S_threshold))
-	{
-	  if (__depth_limit == 0)
-	    {
-	      _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
-	      return;
-	    }
-	  --__depth_limit;
-	  _RandomAccessIterator __cut =
-	    std::__unguarded_partition_pivot(__first, __last);
-	  std::__introsort_loop(__cut, __last, __depth_limit);
-	  __last = __cut;
-	}
+      std::__heap_select(__first, __middle, __last, __comp);
+      std::__sort_heap(__first, __middle, __comp);
     }
 
   /// This is a helper function for the sort routine.
@@ -2354,7 +1969,7 @@
 	{
 	  if (__depth_limit == 0)
 	    {
-	      _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
+	      __partial_sort(__first, __last, __last, __comp);
 	      return;
 	    }
 	  --__depth_limit;
@@ -2367,44 +1982,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)
@@ -2450,18 +2033,25 @@
     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
     {
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-      typedef typename iterator_traits<_ForwardIterator>::difference_type
-	_DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType, _Tp>)
+	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_requires_partitioned_lower_pred(__first, __last,
 						__val, __comp);
 
+      return std::__lower_bound(__first, __last, __val,
+	__gnu_cxx::__ops::__iter_comp_cval(__comp, __first, __val));
+    }
+
+  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 +2059,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 +2087,14 @@
     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;
-
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-      __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+      __glibcxx_function_requires(_LessThanOpConcept<_Tp,
+	    typename iterator_traits<_ForwardIterator>::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::__cval_less_iter(__val, __first));
     }
 
   /**
@@ -2546,18 +2117,27 @@
     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
     {
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-      typedef typename iterator_traits<_ForwardIterator>::difference_type
-	_DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _Tp, _ValueType>)
+      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
+	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
 
+      return std::__upper_bound(__first, __last, __val,
+	__gnu_cxx::__ops::__cval_comp_iter(__comp, __val, __first));
+    }
+
+  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 +2145,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 +2188,18 @@
     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;
-
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
-      __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)	
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    _Tp, typename iterator_traits<_ForwardIterator>::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::__iter_less_cval(__first, __val),
+			__gnu_cxx::__ops::__cval_less_iter(__val, __first));
     }
 
   /**
@@ -2661,48 +2224,20 @@
     equal_range(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
     {
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-      typedef typename iterator_traits<_ForwardIterator>::difference_type
-	_DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType, _Tp>)
+	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _Tp, _ValueType>)
+	    _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_partitioned_lower_pred(__first, __last,
 						__val, __comp);
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
 
-      _DistanceType __len = std::distance(__first, __last);
-
-      while (__len > 0)
-	{
-	  _DistanceType __half = __len >> 1;
-	  _ForwardIterator __middle = __first;
-	  std::advance(__middle, __half);
-	  if (__comp(*__middle, __val))
-	    {
-	      __first = __middle;
-	      ++__first;
-	      __len = __len - __half - 1;
-	    }
-	  else if (__comp(__val, *__middle))
-	    __len = __half;
-	  else
-	    {
-	      _ForwardIterator __left = std::lower_bound(__first, __middle,
-							 __val, __comp);
-	      std::advance(__first, __len);
-	      _ForwardIterator __right = std::upper_bound(++__middle, __first,
-							  __val, __comp);
-	      return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
-	    }
-	}
-      return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
+      return std::__equal_range(__first, __last, __val,
+	__gnu_cxx::__ops::__iter_comp_cval(__comp, __first, __val),
+	__gnu_cxx::__ops::__cval_comp_iter(__comp, __val, __first));
     }
 
   /**
@@ -2722,16 +2257,16 @@
     binary_search(_ForwardIterator __first, _ForwardIterator __last,
                   const _Tp& __val)
     {
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-      __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    _Tp, typename iterator_traits<_ForwardIterator>::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::__iter_less_cval(__first, __val));
       return __i != __last && !(__val < *__i);
     }
 
@@ -2755,19 +2290,17 @@
     binary_search(_ForwardIterator __first, _ForwardIterator __last,
                   const _Tp& __val, _Compare __comp)
     {
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _Tp, _ValueType>)
+	    _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_partitioned_lower_pred(__first, __last,
 						__val, __comp);
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
 
-      _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
+      _ForwardIterator __i = std::__lower_bound(__first, __last, __val,
+	__gnu_cxx::__ops::__iter_comp_cval(__comp, __first, __val));
       return __i != __last && !bool(__comp(__val, *__i));
     }
 
@@ -2775,32 +2308,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,
@@ -2809,7 +2316,7 @@
     {
       while (__first1 != __last1 && __first2 != __last2)
 	{
-	  if (__comp(*__first2, *__first1))
+	  if (__comp(__first2, __first1))
 	    {
 	      *__result = _GLIBCXX_MOVE(*__first2);
 	      ++__first2;
@@ -2827,48 +2334,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,
@@ -2890,7 +2355,7 @@
       --__last2;
       while (true)
 	{
-	  if (__comp(*__last2, *__last1))
+	  if (__comp(__last2, __last1))
 	    {
 	      *--__result = _GLIBCXX_MOVE(*__last1);
 	      if (__first1 == __last1)
@@ -2953,62 +2418,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
@@ -3022,14 +2431,16 @@
       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::__rebind(__comp, __first, __buffer));
 	}
       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::__rebind(__comp, __buffer, __first));
 	}
       else
 	{
@@ -3041,16 +2452,16 @@
 	    {
 	      __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::__rebind_iter_cval(__comp, __first));
 	      __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::__rebind_cval_comp_iter(__comp, __first));
 	      __len11 = std::distance(__first, __first_cut);
 	    }
 	  _BidirectionalIterator __new_middle =
@@ -3067,49 +2478,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
@@ -3123,7 +2491,7 @@
 	return;
       if (__len1 + __len2 == 2)
 	{
-	  if (__comp(*__middle, *__first))
+	  if (__comp(__middle, __first))
 	    std::iter_swap(__first, __middle);
 	  return;
 	}
@@ -3135,16 +2503,16 @@
 	{
 	  __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::__rebind_iter_cval(__comp, __first));
 	  __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::__rebind_cval_comp_iter(__comp, __first));
 	  __len11 = std::distance(__first, __first_cut);
 	}
       std::rotate(__first_cut, __middle, __second_cut);
@@ -3156,6 +2524,37 @@
 				  __len1 - __len11, __len2 - __len22, __comp);
     }
 
+  template<typename _BidirectionalIterator, typename _Compare>
+    void
+    __inplace_merge(_BidirectionalIterator __first,
+		    _BidirectionalIterator __middle,
+		    _BidirectionalIterator __last,
+		    _Compare __comp)
+    {
+      typedef typename iterator_traits<_BidirectionalIterator>::value_type
+          _ValueType;
+      typedef typename iterator_traits<_BidirectionalIterator>::difference_type
+          _DistanceType;
+
+      if (__first == __middle || __middle == __last)
+	return;
+
+      const _DistanceType __len1 = std::distance(__first, __middle);
+      const _DistanceType __len2 = std::distance(__middle, __last);
+
+      typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
+      _TmpBuf __buf(__first, __last);
+
+      if (__buf.begin() == 0)
+	std::__merge_without_buffer(__first, __middle, __last, __len1,
+				    __len2, __comp);
+      else
+	std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
+			      __buf.begin(), _DistanceType(__buf.size()),
+			      __gnu_cxx::__ops::__rebind(__comp, __first,
+							 __buf.begin()));
+    }
+
   /**
    *  @brief Merges two sorted ranges in place.
    *  @ingroup sorting_algorithms
@@ -3180,31 +2579,16 @@
 		  _BidirectionalIterator __middle,
 		  _BidirectionalIterator __last)
     {
-      typedef typename iterator_traits<_BidirectionalIterator>::value_type
-          _ValueType;
-      typedef typename iterator_traits<_BidirectionalIterator>::difference_type
-          _DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
 	    _BidirectionalIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_sorted(__first, __middle);
       __glibcxx_requires_sorted(__middle, __last);
 
-      if (__first == __middle || __middle == __last)
-	return;
-
-      _DistanceType __len1 = std::distance(__first, __middle);
-      _DistanceType __len2 = std::distance(__middle, __last);
-
-      _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
-								  __last);
-      if (__buf.begin() == 0)
-	std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
-      else
-	std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
-			      __buf.begin(), _DistanceType(__buf.size()));
+      std::__inplace_merge(__first, __middle, __last,
+			   __gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -3236,75 +2620,31 @@
 		  _BidirectionalIterator __last,
 		  _Compare __comp)
     {
-      typedef typename iterator_traits<_BidirectionalIterator>::value_type
-          _ValueType;
-      typedef typename iterator_traits<_BidirectionalIterator>::difference_type
-          _DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
 	    _BidirectionalIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-	    _ValueType, _ValueType>)
+	    typename iterator_traits<_BidirectionalIterator>::value_type,
+	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
 
-      if (__first == __middle || __middle == __last)
-	return;
-
-      const _DistanceType __len1 = std::distance(__first, __middle);
-      const _DistanceType __len2 = std::distance(__middle, __last);
-
-      _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
-								  __last);
-      if (__buf.begin() == 0)
-	std::__merge_without_buffer(__first, __middle, __last, __len1,
-				    __len2, __comp);
-      else
-	std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
-			      __buf.begin(), _DistanceType(__buf.size()),
-			      __comp);
+      std::__inplace_merge(__first, __middle, __last,
+			   __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
 
   /// This is a helper function for the __merge_sort_loop routines.
-  template<typename _InputIterator1, typename _InputIterator2,
-	   typename _OutputIterator>
+  template<typename _InputIterator, typename _OutputIterator,
+	   typename _Compare>
     _OutputIterator
-    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
-		 _InputIterator2 __first2, _InputIterator2 __last2,
-		 _OutputIterator __result)
-    {
-      while (__first1 != __last1 && __first2 != __last2)
-	{
-	  if (*__first2 < *__first1)
-	    {
-	      *__result = _GLIBCXX_MOVE(*__first2);
-	      ++__first2;
-	    }
-	  else
-	    {
-	      *__result = _GLIBCXX_MOVE(*__first1);
-	      ++__first1;
-	    }
-	  ++__result;
-	}
-      return _GLIBCXX_MOVE3(__first2, __last2,
-			    _GLIBCXX_MOVE3(__first1, __last1,
-					   __result));
-    }
-
-  /// This is a helper function for the __merge_sort_loop routines.
-  template<typename _InputIterator1, typename _InputIterator2,
-	   typename _OutputIterator, typename _Compare>
-    _OutputIterator
-    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
-		 _InputIterator2 __first2, _InputIterator2 __last2,
+    __move_merge(_InputIterator __first1, _InputIterator __last1,
+		 _InputIterator __first2, _InputIterator __last2,
 		 _OutputIterator __result, _Compare __comp)
     {
       while (__first1 != __last1 && __first2 != __last2)
 	{
-	  if (__comp(*__first2, *__first1))
+	  if (__comp(__first2, __first1))
 	    {
 	      *__result = _GLIBCXX_MOVE(*__first2);
 	      ++__first2;
@@ -3322,29 +2662,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 +2681,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 +2702,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,
@@ -3443,40 +2722,13 @@
 	  std::__merge_sort_loop(__first, __last, __buffer,
 				 __step_size, __comp);
 	  __step_size *= 2;
-	  std::__merge_sort_loop(__buffer, __buffer_last, __first,
-				 __step_size, __comp);
+	  std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size,
+				 __gnu_cxx::__ops::__rebind(__comp, __buffer));
 	  __step_size *= 2;
 	}
     }
 
   template<typename _RandomAccessIterator, typename _Pointer,
-	   typename _Distance>
-    void
-    __stable_sort_adaptive(_RandomAccessIterator __first,
-			   _RandomAccessIterator __last,
-                           _Pointer __buffer, _Distance __buffer_size)
-    {
-      const _Distance __len = (__last - __first + 1) / 2;
-      const _RandomAccessIterator __middle = __first + __len;
-      if (__len > __buffer_size)
-	{
-	  std::__stable_sort_adaptive(__first, __middle,
-				      __buffer, __buffer_size);
-	  std::__stable_sort_adaptive(__middle, __last,
-				      __buffer, __buffer_size);
-	}
-      else
-	{
-	  std::__merge_sort_with_buffer(__first, __middle, __buffer);
-	  std::__merge_sort_with_buffer(__middle, __last, __buffer);
-	}
-      std::__merge_adaptive(__first, __middle, __last,
-			    _Distance(__middle - __first),
-			    _Distance(__last - __middle),
-			    __buffer, __buffer_size);
-    }
-
-  template<typename _RandomAccessIterator, typename _Pointer,
 	   typename _Distance, typename _Compare>
     void
     __stable_sort_adaptive(_RandomAccessIterator __first,
@@ -3506,25 +2758,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,
@@ -3551,6 +2784,24 @@
   // that their input ranges are sorted and the postcondition that their output
   // ranges are sorted.
 
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _Compare12, typename _Compare21>
+    bool
+    __includes(_InputIterator1 __first1, _InputIterator1 __last1,
+	       _InputIterator2 __first2, _InputIterator2 __last2,
+	       _Compare12 __comp12, _Compare21 __comp21)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	if (__comp21(__first2, __first1))
+	  return false;
+	else if(__comp12(__first1, __first2))
+	  ++__first1;
+	else
+	  ++__first1, ++__first2;
+
+      return __first2 == __last2;
+    }
+
   /**
    *  @brief Determines whether all elements of a sequence exists in a range.
    *  @param  __first1  Start of search range.
@@ -3574,28 +2825,21 @@
     includes(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	if (*__first2 < *__first1)
-	  return false;
-	else if(*__first1 < *__first2)
-	  ++__first1;
-	else
-	  ++__first1, ++__first2;
-
-      return __first2 == __last2;
+      return std::__includes(__first1, __last1, __first2, __last2,
+		__gnu_cxx::__ops::__iter_less_iter(__first1, __first2),
+		__gnu_cxx::__ops::__iter_less_iter(__first2, __first1));
     }
 
   /**
@@ -3626,30 +2870,21 @@
 	     _InputIterator2 __first2, _InputIterator2 __last2,
 	     _Compare __comp)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType1, _ValueType2>)
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(*__first2, *__first1))
-	  return false;
-	else if(__comp(*__first1, *__first2))
-	  ++__first1;
-	else
-	  ++__first1, ++__first2;
-
-      return __first2 == __last2;
+      return std::__includes(__first1, __last1, __first2, __last2,
+		__gnu_cxx::__ops::__iter_comp_iter(__comp, __first1, __first2),
+		__gnu_cxx::__ops::__iter_comp_iter(__comp, __first2, __first1));
     }
 
   // nth_element
@@ -3662,30 +2897,11 @@
   // min_element
   // max_element
 
-  /**
-   *  @brief  Permute range into the next @e dictionary ordering.
-   *  @ingroup sorting_algorithms
-   *  @param  __first  Start of range.
-   *  @param  __last   End of range.
-   *  @return  False if wrapped to first permutation, true otherwise.
-   *
-   *  Treats all permutations of the range as a set of @e dictionary sorted
-   *  sequences.  Permutes the current sequence into the next one of this set.
-   *  Returns true if there are more sequences to generate.  If the sequence
-   *  is the largest of the set, the smallest is generated and false returned.
-  */
-  template<typename _BidirectionalIterator>
+  template<typename _BidirectionalIterator, typename _Compare>
     bool
-    next_permutation(_BidirectionalIterator __first,
-		     _BidirectionalIterator __last)
+    __next_permutation(_BidirectionalIterator __first,
+		       _BidirectionalIterator __last, _Compare __comp)
     {
-      // concept requirements
-      __glibcxx_function_requires(_BidirectionalIteratorConcept<
-				  _BidirectionalIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<
-	    typename iterator_traits<_BidirectionalIterator>::value_type>)
-      __glibcxx_requires_valid_range(__first, __last);
-
       if (__first == __last)
 	return false;
       _BidirectionalIterator __i = __first;
@@ -3699,10 +2915,10 @@
 	{
 	  _BidirectionalIterator __ii = __i;
 	  --__i;
-	  if (*__i < *__ii)
+	  if (__comp(__i, __ii))
 	    {
 	      _BidirectionalIterator __j = __last;
-	      while (!(*__i < *--__j))
+	      while (!__comp(__i, --__j))
 		{}
 	      std::iter_swap(__i, __j);
 	      std::reverse(__ii, __last);
@@ -3717,6 +2933,34 @@
     }
 
   /**
+   *  @brief  Permute range into the next @e dictionary ordering.
+   *  @ingroup sorting_algorithms
+   *  @param  __first  Start of range.
+   *  @param  __last   End of range.
+   *  @return  False if wrapped to first permutation, true otherwise.
+   *
+   *  Treats all permutations of the range as a set of @e dictionary sorted
+   *  sequences.  Permutes the current sequence into the next one of this set.
+   *  Returns true if there are more sequences to generate.  If the sequence
+   *  is the largest of the set, the smallest is generated and false returned.
+  */
+  template<typename _BidirectionalIterator>
+    bool
+    next_permutation(_BidirectionalIterator __first,
+		     _BidirectionalIterator __last)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_BidirectionalIteratorConcept<
+				  _BidirectionalIterator>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_BidirectionalIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
+
+      return std::__next_permutation(__first, __last,
+			__gnu_cxx::__ops::__iter_less_iter(__first));
+    }
+
+  /**
    *  @brief  Permute range into the next @e dictionary ordering using
    *          comparison functor.
    *  @ingroup sorting_algorithms
@@ -3744,6 +2988,15 @@
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
+      return std::__next_permutation(__first, __last,
+		__gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
+    }
+
+  template<typename _BidirectionalIterator, typename _Compare>
+    bool
+    __prev_permutation(_BidirectionalIterator __first,
+		       _BidirectionalIterator __last, _Compare __comp)
+    {
       if (__first == __last)
 	return false;
       _BidirectionalIterator __i = __first;
@@ -3757,10 +3010,10 @@
 	{
 	  _BidirectionalIterator __ii = __i;
 	  --__i;
-	  if (__comp(*__i, *__ii))
+	  if (__comp(__ii, __i))
 	    {
 	      _BidirectionalIterator __j = __last;
-	      while (!bool(__comp(*__i, *--__j)))
+	      while (!__comp(--__j, __i))
 		{}
 	      std::iter_swap(__i, __j);
 	      std::reverse(__ii, __last);
@@ -3799,34 +3052,8 @@
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first == __last)
-	return false;
-      _BidirectionalIterator __i = __first;
-      ++__i;
-      if (__i == __last)
-	return false;
-      __i = __last;
-      --__i;
-
-      for(;;)
-	{
-	  _BidirectionalIterator __ii = __i;
-	  --__i;
-	  if (*__ii < *__i)
-	    {
-	      _BidirectionalIterator __j = __last;
-	      while (!(*--__j < *__i))
-		{}
-	      std::iter_swap(__i, __j);
-	      std::reverse(__ii, __last);
-	      return true;
-	    }
-	  if (__i == __first)
-	    {
-	      std::reverse(__first, __last);
-	      return false;
-	    }
-	}
+      return std::__prev_permutation(__first, __last,
+			__gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -3857,39 +3084,28 @@
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first == __last)
-	return false;
-      _BidirectionalIterator __i = __first;
-      ++__i;
-      if (__i == __last)
-	return false;
-      __i = __last;
-      --__i;
-
-      for(;;)
-	{
-	  _BidirectionalIterator __ii = __i;
-	  --__i;
-	  if (__comp(*__ii, *__i))
-	    {
-	      _BidirectionalIterator __j = __last;
-	      while (!bool(__comp(*--__j, *__i)))
-		{}
-	      std::iter_swap(__i, __j);
-	      std::reverse(__ii, __last);
-	      return true;
-	    }
-	  if (__i == __first)
-	    {
-	      std::reverse(__first, __last);
-	      return false;
-	    }
-	}
+      return std::__prev_permutation(__first, __last,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
   // replace
   // replace_if
 
+  template<typename _InputIterator, typename _OutputIterator,
+	   typename _Predicate, typename _Tp>
+    _OutputIterator
+    __replace_copy_if(_InputIterator __first, _InputIterator __last,
+		      _OutputIterator __result,
+		      _Predicate __pred, const _Tp& __new_value)
+    {
+      for (; __first != __last; ++__first, ++__result)
+	if (__pred(__first))
+	  *__result = __new_value;
+	else
+	  *__result = *__first;
+      return __result;
+    }
+
   /**
    *  @brief Copy a sequence, replacing each element of one value with another
    *         value.
@@ -3918,12 +3134,12 @@
 	    typename iterator_traits<_InputIterator>::value_type, _Tp>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      for (; __first != __last; ++__first, ++__result)
-	if (*__first == __old_value)
-	  *__result = __new_value;
-	else
-	  *__result = *__first;
-      return __result;
+      return std::__replace_copy_if(__first, __last, __result,
+	__gnu_cxx::__ops::__bind2nd(__gnu_cxx::__ops
+				    ::__iter_equal_to_cval(__first,
+							   __old_value),
+				    __old_value),
+				    __new_value);
     }
 
   /**
@@ -3956,14 +3172,23 @@
 	    typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      for (; __first != __last; ++__first, ++__result)
-	if (__pred(*__first))
-	  *__result = __new_value;
-	else
-	  *__result = *__first;
-      return __result;
+      return std::__replace_copy_if(__first, __last, __result,
+				    __gnu_cxx::__ops::__pred_iter(__pred,
+								  __first),
+				    __new_value);
     }
 
+  template<typename _InputIterator, typename _Predicate>
+    typename iterator_traits<_InputIterator>::difference_type
+    __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
+    {
+      typename iterator_traits<_InputIterator>::difference_type __n = 0;
+      for (; __first != __last; ++__first)
+	if (__pred(__first))
+	  ++__n;
+      return __n;
+    }
+
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
   /**
    *  @brief  Determines whether the elements of a sequence are sorted.
@@ -3992,6 +3217,21 @@
 	      _Compare __comp)
     { return std::is_sorted_until(__first, __last, __comp) == __last; }
 
+  template<typename _ForwardIterator, typename _Compare>
+    _ForwardIterator
+    __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
+		      _Compare __comp)
+    {
+      if (__first == __last)
+	return __last;
+
+      _ForwardIterator __next = __first;
+      for (++__next; __next != __last; __first = __next, ++__next)
+	if (__comp(__next, __first))
+	  return __next;
+      return __next;
+    }
+
   /**
    *  @brief  Determines the end of a sorted sequence.
    *  @ingroup sorting_algorithms
@@ -4010,14 +3250,8 @@
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first == __last)
-	return __last;
-
-      _ForwardIterator __next = __first;
-      for (++__next; __next != __last; __first = __next, ++__next)
-	if (*__next < *__first)
-	  return __next;
-      return __next;
+      return std::__is_sorted_until(__first, __last,
+			__gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -4041,14 +3275,8 @@
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first == __last)
-	return __last;
-
-      _ForwardIterator __next = __first;
-      for (++__next; __next != __last; __first = __next, ++__next)
-	if (__comp(*__next, *__first))
-	  return __next;
-      return __next;
+      return std::__is_sorted_until(__first, __last,
+			__gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
   /**
@@ -4087,34 +3315,18 @@
 	                      : pair<const _Tp&, const _Tp&>(__a, __b);
     }
 
-  /**
-   *  @brief  Return a pair of iterators pointing to the minimum and maximum
-   *          elements in a range.
-   *  @ingroup sorting_algorithms
-   *  @param  __first  Start of range.
-   *  @param  __last   End of range.
-   *  @return  make_pair(m, M), where m is the first iterator i in 
-   *           [__first, __last) such that no other element in the range is
-   *           smaller, and where M is the last iterator i in [__first, __last)
-   *           such that no other element in the range is larger.
-  */
-  template<typename _ForwardIterator>
+  template<typename _ForwardIterator, typename _Compare>
     pair<_ForwardIterator, _ForwardIterator>
-    minmax_element(_ForwardIterator __first, _ForwardIterator __last)
+    __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
+		     _Compare __comp)
     {
-      // concept requirements
-      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<
-	    typename iterator_traits<_ForwardIterator>::value_type>)
-      __glibcxx_requires_valid_range(__first, __last);
-
       _ForwardIterator __next = __first;
       if (__first == __last
 	  || ++__next == __last)
 	return std::make_pair(__first, __first);
 
       _ForwardIterator __min, __max;
-      if (*__next < *__first)
+      if (__comp(__next, __first))
 	{
 	  __min = __next;
 	  __max = __first;
@@ -4133,25 +3345,25 @@
 	  __next = __first;
 	  if (++__next == __last)
 	    {
-	      if (*__first < *__min)
+	      if (__comp(__first, __min))
 		__min = __first;
-	      else if (!(*__first < *__max))
+	      else if (!__comp(__first, __max))
 		__max = __first;
 	      break;
 	    }
 
-	  if (*__next < *__first)
+	  if (__comp(__next, __first))
 	    {
-	      if (*__next < *__min)
+	      if (__comp(__next, __min))
 		__min = __next;
-	      if (!(*__first < *__max))
+	      if (!__comp(__first, __max))
 		__max = __first;
 	    }
 	  else
 	    {
-	      if (*__first < *__min)
+	      if (__comp(__first, __min))
 		__min = __first;
-	      if (!(*__next < *__max))
+	      if (!__comp(__next, __max))
 		__max = __next;
 	    }
 
@@ -4168,6 +3380,31 @@
    *  @ingroup sorting_algorithms
    *  @param  __first  Start of range.
    *  @param  __last   End of range.
+   *  @return  make_pair(m, M), where m is the first iterator i in 
+   *           [__first, __last) such that no other element in the range is
+   *           smaller, and where M is the last iterator i in [__first, __last)
+   *           such that no other element in the range is larger.
+  */
+  template<typename _ForwardIterator>
+    pair<_ForwardIterator, _ForwardIterator>
+    minmax_element(_ForwardIterator __first, _ForwardIterator __last)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
+
+      return std::__minmax_element(__first, __last,
+				   __gnu_cxx::__ops::__iter_less_iter(__first));
+    }
+
+  /**
+   *  @brief  Return a pair of iterators pointing to the minimum and maximum
+   *          elements in a range.
+   *  @ingroup sorting_algorithms
+   *  @param  __first  Start of range.
+   *  @param  __last   End of range.
    *  @param  __comp   Comparison functor.
    *  @return  make_pair(m, M), where m is the first iterator i in 
    *           [__first, __last) such that no other element in the range is
@@ -4186,58 +3423,8 @@
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      _ForwardIterator __next = __first;
-      if (__first == __last
-	  || ++__next == __last)
-	return std::make_pair(__first, __first);
-
-      _ForwardIterator __min, __max;
-      if (__comp(*__next, *__first))
-	{
-	  __min = __next;
-	  __max = __first;
-	}
-      else
-	{
-	  __min = __first;
-	  __max = __next;
-	}
-
-      __first = __next;
-      ++__first;
-
-      while (__first != __last)
-	{
-	  __next = __first;
-	  if (++__next == __last)
-	    {
-	      if (__comp(*__first, *__min))
-		__min = __first;
-	      else if (!__comp(*__first, *__max))
-		__max = __first;
-	      break;
-	    }
-
-	  if (__comp(*__next, *__first))
-	    {
-	      if (__comp(*__next, *__min))
-		__min = __next;
-	      if (!__comp(*__first, *__max))
-		__max = __first;
-	    }
-	  else
-	    {
-	      if (__comp(*__first, *__min))
-		__min = __first;
-	      if (!__comp(*__next, *__max))
-		__max = __next;
-	    }
-
-	  __first = __next;
-	  ++__first;
-	}
-
-      return std::make_pair(__min, __max);
+      return std::__minmax_element(__first, __last,
+			__gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
   // N2722 + DR 915.
@@ -4279,27 +3466,16 @@
       return std::make_pair(*__p.first, *__p.second);
     }
 
-  /**
-   *  @brief  Checks whether a permutaion of the second sequence is equal
-   *          to the first sequence.
-   *  @ingroup non_mutating_algorithms
-   *  @param  __first1  Start of first range.
-   *  @param  __last1   End of first range.
-   *  @param  __first2  Start of second range.
-   *  @return true if there exists a permutation of the elements in the range
-   *          [__first2, __first2 + (__last1 - __first1)), beginning with 
-   *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
-   *          returns true; otherwise, returns false.
-  */
-  template<typename _ForwardIterator1, typename _ForwardIterator2>
+  template<typename _ForwardIterator1, typename _ForwardIterator2,
+	   typename _BinaryPredicate>
     bool
-    is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-		   _ForwardIterator2 __first2)
+    __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+		     _ForwardIterator2 __first2, _BinaryPredicate __pred)
     {
       // Efficiently compare identical prefixes:  O(N) if sequences
       // have the same elements in the same order.
       for (; __first1 != __last1; ++__first1, ++__first2)
-	if (!(*__first1 == *__first2))
+	if (!__pred(__first1, __first2))
 	  break;
 
       if (__first1 == __last1)
@@ -4311,18 +3487,53 @@
       std::advance(__last2, std::distance(__first1, __last1));
       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
 	{
-	  if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
+	  if (__scan != std::__find_if(__first1, __scan,
+				__gnu_cxx::__ops::__bind2nd(__pred, __scan),
+				std::__iterator_category(__first1)))
 	    continue; // We've seen this one before.
-
-	  auto __matches = std::count(__first2, __last2, *__scan);
+	  
+	  auto __matches
+	    = std::__count_if(__first2, __last2,
+			      __gnu_cxx::__ops::__bind1st(__pred, __scan));
 	  if (0 == __matches
-	      || std::count(__scan, __last1, *__scan) != __matches)
+	      || std::__count_if(__scan, __last1,
+				 __gnu_cxx::__ops
+				 ::__bind2nd(__pred, __scan)) != __matches)
 	    return false;
 	}
       return true;
     }
 
   /**
+   *  @brief  Checks whether a permutaion of the second sequence is equal
+   *          to the first sequence.
+   *  @ingroup non_mutating_algorithms
+   *  @param  __first1  Start of first range.
+   *  @param  __last1   End of first range.
+   *  @param  __first2  Start of second range.
+   *  @return true if there exists a permutation of the elements in the range
+   *          [__first2, __first2 + (__last1 - __first1)), beginning with 
+   *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
+   *          returns true; otherwise, returns false.
+  */
+  template<typename _ForwardIterator1, typename _ForwardIterator2>
+    bool
+    is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+		   _ForwardIterator2 __first2)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
+      __glibcxx_function_requires(_EqualOpConcept<
+		typename iterator_traits<_ForwardIterator1>::value_type,
+		typename iterator_traits<_ForwardIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+
+      return std::__is_permutation(__first1, __last1, __first2,
+	__gnu_cxx::__ops::__iter_equal_to_iter(__first1, __first2));
+    }
+
+  /**
    *  @brief  Checks whether a permutation of the second sequence is equal
    *          to the first sequence.
    *  @ingroup non_mutating_algorithms
@@ -4342,35 +3553,16 @@
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2, _BinaryPredicate __pred)
     {
-      // Efficiently compare identical prefixes:  O(N) if sequences
-      // have the same elements in the same order.
-      for (; __first1 != __last1; ++__first1, ++__first2)
-	if (!bool(__pred(*__first1, *__first2)))
-	  break;
+      // concept requirements
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
+      __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
+	    typename iterator_traits<_ForwardIterator1>::value_type,
+	    typename iterator_traits<_ForwardIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
-      if (__first1 == __last1)
-	return true;
-
-      // Establish __last2 assuming equal ranges by iterating over the
-      // rest of the list.
-      _ForwardIterator2 __last2 = __first2;
-      std::advance(__last2, std::distance(__first1, __last1));
-      for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
-	{
-	  using std::placeholders::_1;
-
-	  if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
-						std::bind(__pred, _1, *__scan)))
-	    continue; // We've seen this one before.
-	  
-	  auto __matches = std::count_if(__first2, __last2,
-					 std::bind(__pred, _1, *__scan));
-	  if (0 == __matches
-	      || std::count_if(__scan, __last1,
-			       std::bind(__pred, _1, *__scan)) != __matches)
-	    return false;
-	}
-      return true;
+      return std::__is_permutation(__first1, __last1, __first2,
+	__gnu_cxx::__ops::__iter_comp_iter(__pred, __first1, __first2));
     }
 
 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
@@ -4462,8 +3654,12 @@
       __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::__bind2nd(__gnu_cxx::__ops::
+				    __iter_equal_to_cval(__first, __val),
+				    __val),
+			    std::__iterator_category(__first));
     }
 
   /**
@@ -4486,7 +3682,8 @@
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 	      typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
-      return std::__find_if(__first, __last, __pred,
+      return std::__find_if(__first, __last,
+			    __gnu_cxx::__ops::__pred_iter(__pred, __first),
 			    std::__iterator_category(__first));
     }
 
@@ -4587,16 +3784,9 @@
       __glibcxx_function_requires(_EqualityComparableConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
-      if (__first == __last)
-	return __last;
-      _ForwardIterator __next = __first;
-      while(++__next != __last)
-	{
-	  if (*__first == *__next)
-	    return __first;
-	  __first = __next;
-	}
-      return __last;
+
+      return std::__adjacent_find(__first, __last,
+			__gnu_cxx::__ops::__iter_equal_to_iter(__first));
     }
 
   /**
@@ -4621,16 +3811,9 @@
 	    typename iterator_traits<_ForwardIterator>::value_type,
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
-      if (__first == __last)
-	return __last;
-      _ForwardIterator __next = __first;
-      while(++__next != __last)
-	{
-	  if (__binary_pred(*__first, *__next))
-	    return __first;
-	  __first = __next;
-	}
-      return __last;
+
+      return std::__adjacent_find(__first, __last,
+		__gnu_cxx::__ops::__iter_comp_iter(__binary_pred, __first));
     }
 
   /**
@@ -4649,13 +3832,13 @@
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_EqualOpConcept<
-	typename iterator_traits<_InputIterator>::value_type, _Tp>)
+	    typename iterator_traits<_InputIterator>::value_type, _Tp>)
       __glibcxx_requires_valid_range(__first, __last);
-      typename iterator_traits<_InputIterator>::difference_type __n = 0;
-      for (; __first != __last; ++__first)
-	if (*__first == __value)
-	  ++__n;
-      return __n;
+
+      return std::__count_if(__first, __last,
+	__gnu_cxx::__ops::__bind2nd(__gnu_cxx::__ops
+				    ::__iter_equal_to_cval(__first, __value),
+				    __value));
     }
 
   /**
@@ -4676,11 +3859,9 @@
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 	    typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
-      typename iterator_traits<_InputIterator>::difference_type __n = 0;
-      for (; __first != __last; ++__first)
-	if (__pred(*__first))
-	  ++__n;
-      return __n;
+
+      return std::__count_if(__first, __last,
+			     __gnu_cxx::__ops::__pred_iter(__pred, __first));
     }
 
   /**
@@ -4723,40 +3904,8 @@
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
 
-      // Test for empty ranges
-      if (__first1 == __last1 || __first2 == __last2)
-	return __first1;
-
-      // Test for a pattern of length 1.
-      _ForwardIterator2 __p1(__first2);
-      if (++__p1 == __last2)
-	return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
-
-      // General case.
-      _ForwardIterator2 __p;
-      _ForwardIterator1 __current = __first1;
-
-      for (;;)
-	{
-	  __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
-	  if (__first1 == __last1)
-	    return __last1;
-
-	  __p = __p1;
-	  __current = __first1;
-	  if (++__current == __last1)
-	    return __last1;
-
-	  while (*__current == *__p)
-	    {
-	      if (++__p == __last2)
-		return __first1;
-	      if (++__current == __last1)
-		return __last1;
-	    }
-	  ++__first1;
-	}
-      return __first1;
+      return std::__search(__first1, __last1, __first2, __last2,
+	__gnu_cxx::__ops::__iter_equal_to_iter(__first1, __first2));
     }
 
   /**
@@ -4796,50 +3945,10 @@
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
 
-      // Test for empty ranges
-      if (__first1 == __last1 || __first2 == __last2)
-	return __first1;
-
-      // Test for a pattern of length 1.
-      _ForwardIterator2 __p1(__first2);
-      if (++__p1 == __last2)
-	{
-	  while (__first1 != __last1
-		 && !bool(__predicate(*__first1, *__first2)))
-	    ++__first1;
-	  return __first1;
-	}
-
-      // General case.
-      _ForwardIterator2 __p;
-      _ForwardIterator1 __current = __first1;
-
-      for (;;)
-	{
-	  while (__first1 != __last1
-		 && !bool(__predicate(*__first1, *__first2)))
-	    ++__first1;
-	  if (__first1 == __last1)
-	    return __last1;
-
-	  __p = __p1;
-	  __current = __first1;
-	  if (++__current == __last1)
-	    return __last1;
-
-	  while (__predicate(*__current, *__p))
-	    {
-	      if (++__p == __last2)
-		return __first1;
-	      if (++__current == __last1)
-		return __last1;
-	    }
-	  ++__first1;
-	}
-      return __first1;
+      return std::__search(__first1, __last1, __first2, __last2,
+	__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first1, __first2));
     }
 
-
   /**
    *  @brief Search a sequence for a number of consecutive values.
    *  @ingroup non_mutating_algorithms
@@ -4863,15 +3972,12 @@
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_EqualOpConcept<
-	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__count <= 0)
-	return __first;
-      if (__count == 1)
-	return _GLIBCXX_STD_A::find(__first, __last, __val);
       return std::__search_n(__first, __last, __count, __val,
-			     std::__iterator_category(__first));
+			     __gnu_cxx::__ops
+			     ::__iter_equal_to_cval(__first, __val));
     }
 
 
@@ -4905,16 +4011,8 @@
 	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__count <= 0)
-	return __first;
-      if (__count == 1)
-	{
-	  while (__first != __last && !bool(__binary_pred(*__first, __val)))
-	    ++__first;
-	  return __first;
-	}
-      return std::__search_n(__first, __last, __count, __val, __binary_pred,
-			     std::__iterator_category(__first));
+      return std::__search_n(__first, __last, __count, __val,
+	__gnu_cxx::__ops::__iter_comp_cval(__binary_pred, __first, __val));
     }
 
 
@@ -5152,6 +4250,7 @@
       if (__first == __last)
 	return __result;
       return std::__unique_copy(__first, __last, __result,
+				__gnu_cxx::__ops::__iter_equal_to_iter(__first),
 				std::__iterator_category(__first),
 				std::__iterator_category(__result));
     }
@@ -5187,10 +4286,14 @@
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 	    typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
+	    typename iterator_traits<_InputIterator>::value_type,
+	    typename iterator_traits<_InputIterator>::value_type>)
 
       if (__first == __last)
 	return __result;
-      return std::__unique_copy(__first, __last, __result, __binary_pred,
+      return std::__unique_copy(__first, __last, __result,
+		__gnu_cxx::__ops::__iter_comp_iter(__binary_pred, __first),
 				std::__iterator_category(__first),
 				std::__iterator_category(__result));
     }
@@ -5288,7 +4391,6 @@
     }
 
 
-
   /**
    *  @brief Sort the smallest elements of a sequence.
    *  @ingroup sorting_algorithms
@@ -5311,18 +4413,16 @@
 		 _RandomAccessIterator __middle,
 		 _RandomAccessIterator __last)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
 
-      std::__heap_select(__first, __middle, __last);
-      std::sort_heap(__first, __middle);
+      std::__partial_sort(__first, __middle, __last,
+			  __gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -5351,19 +4451,17 @@
 		 _RandomAccessIterator __last,
 		 _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType, _ValueType>)
+	    typename iterator_traits<_RandomAccessIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
 
-      std::__heap_select(__first, __middle, __last, __comp);
-      std::sort_heap(__first, __middle, __comp);
+      std::__partial_sort(__first, __middle, __last,
+			  __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
   /**
@@ -5386,13 +4484,11 @@
     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
 		_RandomAccessIterator __last)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 				  _RandomAccessIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __nth);
       __glibcxx_requires_valid_range(__nth, __last);
 
@@ -5400,7 +4496,8 @@
 	return;
 
       std::__introselect(__first, __nth, __last,
-			 std::__lg(__last - __first) * 2);
+			 std::__lg(__last - __first) * 2,
+			 __gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -5425,14 +4522,12 @@
     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
 		_RandomAccessIterator __last, _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 				  _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType, _ValueType>)
+	    typename iterator_traits<_RandomAccessIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __nth);
       __glibcxx_requires_valid_range(__nth, __last);
 
@@ -5440,10 +4535,24 @@
 	return;
 
       std::__introselect(__first, __nth, __last,
-			 std::__lg(__last - __first) * 2, __comp);
+			 std::__lg(__last - __first) * 2,
+			 __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
 
+  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
@@ -5462,21 +4571,14 @@
     inline void
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first != __last)
-	{
-	  std::__introsort_loop(__first, __last,
-				std::__lg(__last - __first) * 2);
-	  std::__final_insertion_sort(__first, __last);
-	}
+      __sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -5499,22 +4601,41 @@
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
 	 _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
-      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
-				  _ValueType>)
+      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
+	    typename iterator_traits<_RandomAccessIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first != __last)
+      __sort(__first, __last,
+	     __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
+    }
+
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator, typename _Compare>
+    _OutputIterator
+    __merge(_InputIterator1 __first1, _InputIterator1 __last1,
+	    _InputIterator2 __first2, _InputIterator2 __last2,
+	    _OutputIterator __result, _Compare __comp)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
 	{
-	  std::__introsort_loop(__first, __last,
-				std::__lg(__last - __first) * 2, __comp);
-	  std::__final_insertion_sort(__first, __last, __comp);
+	  if (__comp(__first2, __first1))
+	    {
+	      *__result = *__first2;
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = *__first1;
+	      ++__first1;
+	    }
+	  ++__result;
 	}
+      return std::copy(__first2, __last2, std::copy(__first1, __last1,
+						    __result));
     }
 
   /**
@@ -5543,38 +4664,21 @@
 	  _InputIterator2 __first2, _InputIterator2 __last2,
 	  _OutputIterator __result)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)	
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)	
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	{
-	  if (*__first2 < *__first1)
-	    {
-	      *__result = *__first2;
-	      ++__first2;
-	    }
-	  else
-	    {
-	      *__result = *__first1;
-	      ++__first1;
-	    }
-	  ++__result;
-	}
-      return std::copy(__first2, __last2, std::copy(__first1, __last1,
-						    __result));
+      return std::__merge(__first1, __last1, __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_less_iter(__first1, __first2));
     }
 
   /**
@@ -5607,42 +4711,43 @@
 	  _InputIterator2 __first2, _InputIterator2 __last2,
 	  _OutputIterator __result, _Compare __comp)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType2>)
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	{
-	  if (__comp(*__first2, *__first1))
-	    {
-	      *__result = *__first2;
-	      ++__first2;
-	    }
-	  else
-	    {
-	      *__result = *__first1;
-	      ++__first1;
-	    }
-	  ++__result;
-	}
-      return std::copy(__first2, __last2, std::copy(__first1, __last1,
-						    __result));
+      return std::__merge(__first1, __last1, __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first2, __first1));
     }
 
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline void
+    __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
+		  _Compare __comp)
+    {
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type
+	_ValueType;
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+	_DistanceType;
 
+      typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
+      _TmpBuf __buf(__first, __last);
+
+      if (__buf.begin() == 0)
+	std::__inplace_stable_sort(__first, __last, __comp);
+      else
+	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
+				    _DistanceType(__buf.size()), __comp);
+    }
+
   /**
    *  @brief Sort the elements of a sequence, preserving the relative order
    *         of equivalent elements.
@@ -5664,24 +4769,15 @@
     inline void
     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
-	_DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
-      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
-								 __last);
-      if (__buf.begin() == 0)
-	std::__inplace_stable_sort(__first, __last);
-      else
-	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
-				    _DistanceType(__buf.size()));
+      std::__stable_sort(__first, __last,
+			 __gnu_cxx::__ops::__iter_less_iter(__first));
     }
 
   /**
@@ -5707,29 +4803,52 @@
     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
 		_Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
-	_DistanceType;
-
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType,
-				  _ValueType>)
+	    typename iterator_traits<_RandomAccessIterator>::value_type,
+	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
-								 __last);
-      if (__buf.begin() == 0)
-	std::__inplace_stable_sort(__first, __last, __comp);
-      else
-	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
-				    _DistanceType(__buf.size()), __comp);
+      std::__stable_sort(__first, __last,
+			 __gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
+  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
@@ -5755,45 +4874,26 @@
 	      _InputIterator2 __first2, _InputIterator2 __last2,
 	      _OutputIterator __result)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	{
-	  if (*__first1 < *__first2)
-	    {
-	      *__result = *__first1;
-	      ++__first1;
-	    }
-	  else if (*__first2 < *__first1)
-	    {
-	      *__result = *__first2;
-	      ++__first2;
-	    }
-	  else
-	    {
-	      *__result = *__first1;
-	      ++__first1;
-	      ++__first2;
-	    }
-	  ++__result;
-	}
-      return std::copy(__first2, __last2, std::copy(__first1, __last1,
-						    __result));
+      return std::__set_union(
+	__first1, __last1, __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_less_iter(__first1, __first2),
+	__gnu_cxx::__ops::__iter_less_iter(__first2, __first1));
     }
 
   /**
@@ -5822,47 +4922,49 @@
 	      _InputIterator2 __first2, _InputIterator2 __last2,
 	      _OutputIterator __result, _Compare __comp)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType2>)
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType1, _ValueType2>)
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
+      return std::__set_union(__first1, __last1, __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first1, __first2),
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first2, __first1));
+    }
+
+  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;
     }
 
   /**
@@ -5889,34 +4991,24 @@
 		     _InputIterator2 __first2, _InputIterator2 __last2,
 		     _OutputIterator __result)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	if (*__first1 < *__first2)
-	  ++__first1;
-	else if (*__first2 < *__first1)
-	  ++__first2;
-	else
-	  {
-	    *__result = *__first1;
-	    ++__first1;
-	    ++__first2;
-	    ++__result;
-	  }
-      return __result;
+      return std::__set_intersection(
+	__first1, __last1, __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_less_iter(__first1, __first2),
+	__gnu_cxx::__ops::__iter_less_iter(__first2, __first1));
     }
 
   /**
@@ -5946,36 +5038,50 @@
 		     _InputIterator2 __first2, _InputIterator2 __last2,
 		     _OutputIterator __result, _Compare __comp)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType1, _ValueType2>)
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
+      return std::__set_intersection(__first1, __last1, __first2, __last2,
+				     __result,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first1, __first2),
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first2, __first1));
+    }
+
+  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);
     }
 
   /**
@@ -6004,36 +5110,24 @@
 		   _InputIterator2 __first2, _InputIterator2 __last2,
 		   _OutputIterator __result)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)	
+	    typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)	
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	if (*__first1 < *__first2)
-	  {
-	    *__result = *__first1;
-	    ++__first1;
-	    ++__result;
-	  }
-	else if (*__first2 < *__first1)
-	  ++__first2;
-	else
-	  {
-	    ++__first1;
-	    ++__first2;
-	  }
-      return std::copy(__first1, __last1, __result);
+      return std::__set_difference(
+	__first1, __last1, __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_less_iter(__first1, __first2),
+	__gnu_cxx::__ops::__iter_less_iter(__first2, __first1));
     }
 
   /**
@@ -6065,38 +5159,57 @@
 		   _InputIterator2 __first2, _InputIterator2 __last2,
 		   _OutputIterator __result, _Compare __comp)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType1, _ValueType2>)
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
+      return std::__set_difference(__first1, __last1, __first2, __last2,
+				   __result,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first1, __first2),
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first2, __first1));
+    }
+
+  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));
     }
 
   /**
@@ -6123,43 +5236,26 @@
 			     _InputIterator2 __first2, _InputIterator2 __last2,
 			     _OutputIterator __result)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
-      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)	
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_function_requires(_LessThanOpConcept<
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)	
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	if (*__first1 < *__first2)
-	  {
-	    *__result = *__first1;
-	    ++__first1;
-	    ++__result;
-	  }
-	else if (*__first2 < *__first1)
-	  {
-	    *__result = *__first2;
-	    ++__first2;
-	    ++__result;
-	  }
-	else
-	  {
-	    ++__first1;
-	    ++__first2;
-	  }
-      return std::copy(__first2, __last2, std::copy(__first1,
-						    __last1, __result));
+      return std::__set_symmetric_difference(
+	__first1, __last1, __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_less_iter(__first1, __first2),
+	__gnu_cxx::__ops::__iter_less_iter(__first2, __first1));
     }
 
   /**
@@ -6190,47 +5286,41 @@
 			     _OutputIterator __result,
 			     _Compare __comp)
     {
-      typedef typename iterator_traits<_InputIterator1>::value_type
-	_ValueType1;
-      typedef typename iterator_traits<_InputIterator2>::value_type
-	_ValueType2;
-
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType1>)
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
-				  _ValueType2>)
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType1, _ValueType2>)
+	    typename iterator_traits<_InputIterator1>::value_type,
+	    typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType2, _ValueType1>)
+	    typename iterator_traits<_InputIterator2>::value_type,
+	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
-      while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(*__first1, *__first2))
-	  {
-	    *__result = *__first1;
-	    ++__first1;
-	    ++__result;
-	  }
-	else if (__comp(*__first2, *__first1))
-	  {
-	    *__result = *__first2;
-	    ++__first2;
-	    ++__result;
-	  }
-	else
-	  {
-	    ++__first1;
-	    ++__first2;
-	  }
-      return std::copy(__first2, __last2, 
-		       std::copy(__first1, __last1, __result));
+      return std::__set_symmetric_difference(__first1, __last1,
+					     __first2, __last2, __result,
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first1, __first2),
+	__gnu_cxx::__ops::__iter_comp_iter(__comp, __first2, __first1));
     }
 
+  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 +5339,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_iter(__first));
     }
 
   /**
@@ -6279,11 +5364,19 @@
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first == __last)
-	return __first;
+      return std::__min_element(__first, __last,
+			__gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
+    }
+
+  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;
     }
@@ -6305,13 +5398,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_iter(__first));
     }
 
   /**
@@ -6335,12 +5423,8 @@
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first == __last) return __first;
-      _ForwardIterator __result = __first;
-      while (++__first != __last)
-	if (__comp(*__result, *__first))
-	  __result = __first;
-      return __result;
+      return std::__max_element(__first, __last,
+			__gnu_cxx::__ops::__iter_comp_iter(__comp, __first));
     }
 
 _GLIBCXX_END_NAMESPACE_ALGO
Index: include/Makefile.am
===================================================================
--- include/Makefile.am	(revision 189412)
+++ 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 189412)
+++ 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 Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]