stl_algo.h

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

   *  (not standard, but a much better choice whenever it's available).
   *
   *  XXX There is no corresponding encapsulation fn to seed the generator.
   *  @endif
  */
  template<typename _Distance>
    inline _Distance
    __random_number(_Distance __n)
    {
  #ifdef _GLIBCPP_HAVE_DRAND48
      return lrand48() % __n;
  #else
      return rand() % __n;
  #endif
    }


  /**
   *  @brief Randomly shuffle the elements of a sequence.
   *  @param  first   A forward iterator.
   *  @param  last    A forward iterator.
   *  @return  Nothing.
   *
   *  Reorder the elements in the range @p [first,last) using a random
   *  distribution, so that every possible ordering of the sequence is
   *  equally likely.
  */
  template<typename _RandomAccessIter>
    inline void
    random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIter>)

      if (__first == __last) return;
      for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
	iter_swap(__i, __first + __random_number((__i - __first) + 1));
    }

  /**
   *  @brief Shuffle the elements of a sequence using a random number
   *         generator.
   *  @param  first   A forward iterator.
   *  @param  last    A forward iterator.
   *  @param  rand    The RNG functor or function.
   *  @return  Nothing.
   *
   *  Reorders the elements in the range @p [first,last) using @p rand to
   *  provide a random distribution. Calling @p rand(N) for a positive
   *  integer @p N should return a randomly chosen integer from the
   *  range [0,N).
  */
  template<typename _RandomAccessIter, typename _RandomNumberGenerator>
    void
    random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
		   _RandomNumberGenerator& __rand)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIter>)

      if (__first == __last) return;
      for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
	iter_swap(__i, __first + __rand((__i - __first) + 1));
    }


  /**
   *  @if maint
   *  This is a helper function...
   *  @endif
  */
  template<typename _ForwardIter, typename _Predicate>
    _ForwardIter
    __partition(_ForwardIter __first, _ForwardIter __last,
		_Predicate   __pred,
		forward_iterator_tag)
    {
      if (__first == __last) return __first;

      while (__pred(*__first))
	if (++__first == __last) return __first;

      _ForwardIter __next = __first;

      while (++__next != __last)
	if (__pred(*__next)) {
	  swap(*__first, *__next);
	  ++__first;
	}

      return __first;
    }

  /**
   *  @if maint
   *  This is a helper function...
   *  @endif
  */
  template<typename _BidirectionalIter, typename _Predicate>
    _BidirectionalIter
    __partition(_BidirectionalIter __first, _BidirectionalIter __last,
		_Predicate __pred,
		bidirectional_iterator_tag)
    {
      while (true) {
	while (true)
	  if (__first == __last)
	    return __first;
	  else if (__pred(*__first))
	    ++__first;
	  else
	    break;
	--__last;
	while (true)
	  if (__first == __last)
	    return __first;
	  else if (!__pred(*__last))
	    --__last;
	  else
	    break;
	iter_swap(__first, __last);
	++__first;
      }
    }

  /**
   *  @brief Move elements for which a predicate is true to the beginning
   *         of a sequence.
   *  @param  first   A forward iterator.
   *  @param  last    A forward iterator.
   *  @param  pred    A predicate functor.
   *  @return  An iterator @p middle such that @p pred(i) is true for each
   *  iterator @p i in the range @p [first,middle) and false for each @p i
   *  in the range @p [middle,last).
   *  
   *  @p pred must not modify its operand. @p partition() does not preserve
   *  the relative ordering of elements in each group, use
   *  @p stable_partition() if this is needed.
  */
  template<typename _ForwardIter, typename _Predicate>
    inline _ForwardIter
    partition(_ForwardIter __first, _ForwardIter __last,
	      _Predicate   __pred)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
	    typename iterator_traits<_ForwardIter>::value_type>)

      return __partition(__first, __last, __pred, __iterator_category(__first));
    }


  /**
   *  @if maint
   *  This is a helper function...
   *  @endif
  */
  template<typename _ForwardIter, typename _Predicate, typename _Distance>
    _ForwardIter
    __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last,
			       _Predicate __pred, _Distance __len)
    {
      if (__len == 1)
	return __pred(*__first) ? __last : __first;
      _ForwardIter __middle = __first;
      advance(__middle, __len / 2);
      _ForwardIter __begin = __inplace_stable_partition(__first, __middle,
							__pred,
							__len / 2);
      _ForwardIter __end = __inplace_stable_partition(__middle, __last,
						      __pred,
						      __len - __len / 2);
      rotate(__begin, __middle, __end);
      advance(__begin, distance(__middle, __end));
      return __begin;
    }

  /**
   *  @if maint
   *  This is a helper function...
   *  @endif
  */
  template<typename _ForwardIter, typename _Pointer, typename _Predicate,
	   typename _Distance>
    _ForwardIter
    __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last,
				_Predicate __pred, _Distance __len,
				_Pointer __buffer,
				_Distance __buffer_size)
    {
      if (__len <= __buffer_size) {
	_ForwardIter __result1 = __first;
	_Pointer __result2 = __buffer;
	for ( ; __first != __last ; ++__first)
	  if (__pred(*__first)) {
	    *__result1 = *__first;
	    ++__result1;
	  }
	  else {
	    *__result2 = *__first;
	    ++__result2;
	  }
	copy(__buffer, __result2, __result1);
	return __result1;
      }
      else {
	_ForwardIter __middle = __first;
	advance(__middle, __len / 2);
	_ForwardIter __begin = __stable_partition_adaptive(__first, __middle,
							   __pred,
							   __len / 2,
							   __buffer, __buffer_size);
	_ForwardIter __end = __stable_partition_adaptive( __middle, __last,
							  __pred,
							  __len - __len / 2,
							  __buffer, __buffer_size);
	rotate(__begin, __middle, __end);
	advance(__begin, distance(__middle, __end));
	return __begin;
      }
    }

  /**
   *  @brief Move elements for which a predicate is true to the beginning
   *         of a sequence, preserving relative ordering.
   *  @param  first   A forward iterator.
   *  @param  last    A forward iterator.
   *  @param  pred    A predicate functor.
   *  @return  An iterator @p middle such that @p pred(i) is true for each
   *  iterator @p i in the range @p [first,middle) and false for each @p i
   *  in the range @p [middle,last).
   *  
   *  Performs the same function as @p partition() with the additional
   *  guarantee that the relative ordering of elements in each group is
   *  preserved, so any two elements @p x and @p y in the range
   *  @p [first,last) such that @p pred(x)==pred(y) will have the same
   *  relative ordering after calling @p stable_partition().
  */
  template<typename _ForwardIter, typename _Predicate>
    _ForwardIter
    stable_partition(_ForwardIter __first, _ForwardIter __last,
		     _Predicate __pred)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
	    typename iterator_traits<_ForwardIter>::value_type>)

      if (__first == __last)
	return __first;
      else
      {
	typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
	typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;

	_Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last);
	if (__buf.size() > 0)
	  return __stable_partition_adaptive(__first, __last, __pred,
					     _DistanceType(__buf.requested_size()),
					     __buf.begin(), __buf.size());
	else
	  return __inplace_stable_partition(__first, __last, __pred,
					    _DistanceType(__buf.requested_size()));
      }
    }

  /**
   *  @if maint
   *  This is a helper function...
   *  @endif
  */
  template<typename _RandomAccessIter, typename _Tp>
    _RandomAccessIter
    __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
			  _Tp __pivot)
    {
      while (true) {
	while (*__first < __pivot)
	  ++__first;
	--__last;
	while (__pivot < *__last)
	  --__last;
	if (!(__first < __last))
	  return __first;
	iter_swap(__first, __last);
	++__first;
      }
    }

  /**
   *  @if maint
   *  This is a helper function...
   *  @endif
  */
  template<typename _RandomAccessIter, typename _Tp, typename _Compare>
    _RandomAccessIter
    __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
			  _Tp __pivot, _Compare __comp)
    {
      while (true) {
	while (__comp(*__first, __pivot))
	  ++__first;
	--__last;
	while (__comp(__pivot, *__last))
	  --__last;
	if (!(__first < __last))
	  return __first;
	iter_swap(__first, __last);
	++__first;
      }
    }


  /**
   *  @if maint
   *  @doctodo
   *  This controls some aspect of the sort routines.
   *  @endif
  */
  enum { _M_threshold = 16 };

  /**
   *  @if maint
   *  This is a helper function for the sort routine.
   *  @endif
  */
  template<typename _RandomAccessIter, typename _Tp>
    void
    __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
    {
      _RandomAccessIter __next = __last;
      --__next;
      while (__val < *__next) {
	*__last = *__next;
	__last = __next;
	--__next;
      }
      *__last = __val;
    }

  /**
   *  @if maint
   *  This is a helper function for the sort routine.
   *  @endif
  */
  template<typename _RandomAccessIter, typename _Tp, typename _Compare>
    void
    __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp)
    {
      _RandomAccessIter __next = __last;
      --__next;
      while (__comp(__val, *__next)) {
	*__last = *__next;
	__last = __next;
	--__next;
      }
      *__last = __val;
    }

  /**
   *  @if maint
   *  This is a helper function for the sort routine.
   *  @endif
  */
  template<typename _RandomAccessIter>
    void
    __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
    {
      if (__first == __last) return;

      for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
      {
	typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
	if (__val < *__first) {
	  copy_backward(__first, __i, __i + 1);
	  *__first = __val;
	}
	else
	  __unguarded_linear_insert(__i, __val);
      }
    }

  /**
   *  @if maint
   *  This is a helper function for the sort routine.
   *  @endif
  */
  template<typename _RandomAccessIter, typename _Compare>
    void
    __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
		     _Compare __comp)
    {
      if (__first == __last) return;

      for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
      {
	typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
	if (__comp(__