stl_algo.h

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

    {
      // concept requirements -- iterators already checked
      __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
	    typename iterator_traits<_ForwardIter>::value_type,
	    typename iterator_traits<_InputIter>::value_type>)

      *__result = *__first;
      while (++__first != __last)
	if (!__binary_pred(*__result, *__first)) *++__result = *__first;
      return ++__result;
    }

  /**
   *  @brief Copy a sequence, removing consecutive values using a predicate.
   *  @param  first        An input iterator.
   *  @param  last         An input iterator.
   *  @param  result       An output iterator.
   *  @param  binary_pred  A binary predicate.
   *  @return   An iterator designating the end of the resulting sequence.
   *
   *  Copies each element in the range @p [first,last) to the range
   *  beginning at @p result, except that only the first element is copied
   *  from groups of consecutive elements for which @p binary_pred returns
   *  true.
   *  unique_copy() is stable, so the relative order of elements that are
   *  copied is unchanged.
  */
  template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
    inline _OutputIter
    unique_copy(_InputIter __first, _InputIter __last,
		_OutputIter __result,
		_BinaryPredicate __binary_pred)
    {
      // concept requirements -- predicates checked later
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	    typename iterator_traits<_InputIter>::value_type>)

      typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;

      if (__first == __last) return __result;
      return __unique_copy(__first, __last,
__result, __binary_pred, _IterType());
    }

  /**
   *  @brief Remove consecutive duplicate values from a sequence.
   *  @param  first  A forward iterator.
   *  @param  last   A forward iterator.
   *  @return  An iterator designating the end of the resulting sequence.
   *
   *  Removes all but the first element from each group of consecutive
   *  values that compare equal.
   *  unique() is stable, so the relative order of elements that are
   *  not removed is unchanged.
   *  Elements between the end of the resulting sequence and @p last
   *  are still present, but their value is unspecified.
  */
  template<typename _ForwardIter>
    _ForwardIter
    unique(_ForwardIter __first, _ForwardIter __last)
    {
	  // concept requirements
	  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
	  __glibcpp_function_requires(_EqualityComparableConcept<
		    typename iterator_traits<_ForwardIter>::value_type>)

	  __first = adjacent_find(__first, __last);
	  return unique_copy(__first, __last, __first);
    }

  /**
   *  @brief Remove consecutive values from a sequence using a predicate.
   *  @param  first        A forward iterator.
   *  @param  last         A forward iterator.
   *  @param  binary_pred  A binary predicate.
   *  @return  An iterator designating the end of the resulting sequence.
   *
   *  Removes all but the first element from each group of consecutive
   *  values for which @p binary_pred returns true.
   *  unique() is stable, so the relative order of elements that are
   *  not removed is unchanged.
   *  Elements between the end of the resulting sequence and @p last
   *  are still present, but their value is unspecified.
  */
  template<typename _ForwardIter, typename _BinaryPredicate>
    _ForwardIter
    unique(_ForwardIter __first, _ForwardIter __last,
           _BinaryPredicate __binary_pred)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
		typename iterator_traits<_ForwardIter>::value_type,
		typename iterator_traits<_ForwardIter>::value_type>)

      __first = adjacent_find(__first, __last, __binary_pred);
      return unique_copy(__first, __last, __first, __binary_pred);
    }

  /**
   *  @if maint
   *  This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
   *  overloaded for bidirectional iterators.
   *  @endif
  */
  template<typename _BidirectionalIter>
    void
    __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
			  bidirectional_iterator_tag)
    {
	  while (true)
	    if (__first == __last || __first == --__last)
		  return;
	    else
		  iter_swap(__first++, __last);
    }

  /**
   *  @if maint
   *  This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
   *  overloaded for bidirectional iterators.
   *  @endif
  */
  template<typename _RandomAccessIter>
    void
    __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
			  random_access_iterator_tag)
    {
	  while (__first < __last)
	    iter_swap(__first++, --__last);
    }

  /**
   *  @brief Reverse a sequence.
   *  @param  first  A bidirectional iterator.
   *  @param  last   A bidirectional iterator.
   *  @return   reverse() returns no value.
   *
   *  Reverses the order of the elements in the range @p [first,last),
   *  so that the first element becomes the last etc.
   *  For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
   *  swaps @p *(first+i) and @p *(last-(i+1))
  */
  template<typename _BidirectionalIter>
    inline void
    reverse(_BidirectionalIter __first, _BidirectionalIter __last)
    {
	  // concept requirements
	  __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
		    _BidirectionalIter>)
	  __reverse(__first, __last, __iterator_category(__first));
    }

  /**
   *  @brief Copy a sequence, reversing its elements.
   *  @param  first   A bidirectional iterator.
   *  @param  last    A bidirectional iterator.
   *  @param  result  An output iterator.
   *  @return  An iterator designating the end of the resulting sequence.
   *
   *  Copies the elements in the range @p [first,last) to the range
   *  @p [result,result+(last-first)) such that the order of the
   *  elements is reversed.
   *  For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
   *  performs the assignment @p *(result+(last-first)-i) = *(first+i).
   *  The ranges @p [first,last) and @p [result,result+(last-first))
   *  must not overlap.
  */
  template<typename _BidirectionalIter, typename _OutputIter>
    _OutputIter
    reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last,
			     _OutputIter __result)
    {
      // concept requirements
      __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		typename iterator_traits<_BidirectionalIter>::value_type>)

      while (__first != __last) {
	--__last;
	*__result = *__last;
	++__result;
      }
      return __result;
    }


  /**
   *  @if maint
   *  This is a helper function for the rotate algorithm specialized on RAIs.
   *  It returns the greatest common divisor of two integer values.
   *  @endif
  */
  template<typename _EuclideanRingElement>
    _EuclideanRingElement
    __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
    {
      while (__n != 0) {
	_EuclideanRingElement __t = __m % __n;
	__m = __n;
	__n = __t;
      }
      return __m;
    }

  /**
   *  @if maint
   *  This is a helper function for the rotate algorithm.
   *  @endif
  */
  template<typename _ForwardIter>
    void
    __rotate(_ForwardIter __first,
	     _ForwardIter __middle,
	     _ForwardIter __last,
	      forward_iterator_tag)
    {
      if ((__first == __middle) || (__last  == __middle))
	return;

      _ForwardIter __first2 = __middle;
      do {
	swap(*__first++, *__first2++);
	if (__first == __middle)
	  __middle = __first2;
      } while (__first2 != __last);

      __first2 = __middle;

      while (__first2 != __last) {
	swap(*__first++, *__first2++);
	if (__first == __middle)
	  __middle = __first2;
	else if (__first2 == __last)
	  __first2 = __middle;
      }
    }

  /**
   *  @if maint
   *  This is a helper function for the rotate algorithm.
   *  @endif
  */
  template<typename _BidirectionalIter>
    void
    __rotate(_BidirectionalIter __first,
	     _BidirectionalIter __middle,
	     _BidirectionalIter __last,
	      bidirectional_iterator_tag)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
	    _BidirectionalIter>)

      if ((__first == __middle) || (__last  == __middle))
	return;

      __reverse(__first,  __middle, bidirectional_iterator_tag());
      __reverse(__middle, __last,   bidirectional_iterator_tag());

      while (__first != __middle && __middle != __last)
	swap (*__first++, *--__last);

      if (__first == __middle) {
	__reverse(__middle, __last,   bidirectional_iterator_tag());
      }
      else {
	__reverse(__first,  __middle, bidirectional_iterator_tag());
      }
    }

  /**
   *  @if maint
   *  This is a helper function for the rotate algorithm.
   *  @endif
  */
  template<typename _RandomAccessIter>
    void
    __rotate(_RandomAccessIter __first,
	     _RandomAccessIter __middle,
	     _RandomAccessIter __last,
	     random_access_iterator_tag)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIter>)

      if ((__first == __middle) || (__last  == __middle))
	return;

      typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
      typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;

      _Distance __n = __last   - __first;
      _Distance __k = __middle - __first;
      _Distance __l = __n - __k;

      if (__k == __l) {
	swap_ranges(__first, __middle, __middle);
	return;
      }

      _Distance __d = __gcd(__n, __k);

      for (_Distance __i = 0; __i < __d; __i++) {
	_ValueType __tmp = *__first;
	_RandomAccessIter __p = __first;

	if (__k < __l) {
	  for (_Distance __j = 0; __j < __l/__d; __j++) {
	    if (__p > __first + __l) {
	      *__p = *(__p - __l);
	      __p -= __l;
	    }

	    *__p = *(__p + __k);
	    __p += __k;
	  }
	}

	else {
	  for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
	    if (__p < __last - __k) {
	      *__p = *(__p + __k);
	      __p += __k;
	    }

	    *__p = * (__p - __l);
	    __p -= __l;
	  }
	}

	*__p = __tmp;
	++__first;
      }
    }

  /**
   *  @brief Rotate the elements of a sequence.
   *  @param  first   A forward iterator.
   *  @param  middle  A forward iterator.
   *  @param  last    A forward iterator.
   *  @return  Nothing.
   *
   *  Rotates the elements of the range @p [first,last) by @p (middle-first)
   *  positions so that the element at @p middle is moved to @p first, the
   *  element at @p middle+1 is moved to @first+1 and so on for each element
   *  in the range @p [first,last).
   *
   *  This effectively swaps the ranges @p [first,middle) and
   *  @p [middle,last).
   *
   *  Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
   *  each @p n in the range @p [0,last-first).
  */
  template<typename _ForwardIter>
    inline void
    rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)

      typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
      __rotate(__first, __middle, __last, _IterType());
    }

  /**
   *  @brief Copy a sequence, rotating its elements.
   *  @param  first   A forward iterator.
   *  @param  middle  A forward iterator.
   *  @param  last    A forward iterator.
   *  @param  result  An output iterator.
   *  @return   An iterator designating the end of the resulting sequence.
   *
   *  Copies the elements of the range @p [first,last) to the range
   *  beginning at @result, rotating the copied elements by @p (middle-first)
   *  positions so that the element at @p middle is moved to @p result, the
   *  element at @p middle+1 is moved to @result+1 and so on for each element
   *  in the range @p [first,last).
   *
   *  Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
   *  each @p n in the range @p [0,last-first).
  */
  template<typename _ForwardIter, typename _OutputIter>
    _OutputIter
    rotate_copy(_ForwardIter __first, _ForwardIter __middle,
                _ForwardIter __last, _OutputIter __result)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		typename iterator_traits<_ForwardIter>::value_type>)

      return copy(__first, __middle, copy(__middle, __last, __result));
    }


  /**
   *  @if maint
   *  Return a random number in the range [0, __n).  This function encapsulates
   *  whether we're using rand (part of the standard C library) or lrand48