stl_algo.h

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

  /**
   *  @brief Count the elements of a sequence for which a predicate is true.
   *  @param  first  An input iterator.
   *  @param  last   An input iterator.
   *  @param  pred   A predicate.
   *  @return   The number of iterators @c i in the range @p [first,last)
   *  for which @p pred(*i) is true.
  */
  template<typename _InputIter, typename _Predicate>
    typename iterator_traits<_InputIter>::difference_type
    count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
	    typename iterator_traits<_InputIter>::value_type>)
      typename iterator_traits<_InputIter>::difference_type __n = 0;
      for ( ; __first != __last; ++__first)
	if (__pred(*__first))
	  ++__n;
      return __n;
    }


  /**
   *  @brief Search a sequence for a matching sub-sequence.
   *  @param  first1  A forward iterator.
   *  @param  last1   A forward iterator.
   *  @param  first2  A forward iterator.
   *  @param  last2   A forward iterator.
   *  @return   The first iterator @c i in the range
   *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
   *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
   *  such iterator exists.
   *
   *  Searches the range @p [first1,last1) for a sub-sequence that compares
   *  equal value-by-value with the sequence given by @p [first2,last2) and
   *  returns an iterator to the first element of the sub-sequence, or
   *  @p last1 if the sub-sequence is not found.
   *
   *  Because the sub-sequence must lie completely within the range
   *  @p [first1,last1) it must start at a position less than
   *  @p last1-(last2-first2) where @p last2-first2 is the length of the
   *  sub-sequence.
   *  This means that the returned iterator @c i will be in the range
   *  @p [first1,last1-(last2-first2))
  */
  template<typename _ForwardIter1, typename _ForwardIter2>
    _ForwardIter1
    search(_ForwardIter1 __first1, _ForwardIter1 __last1,
	   _ForwardIter2 __first2, _ForwardIter2 __last2)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
      __glibcpp_function_requires(_EqualOpConcept<
	    typename iterator_traits<_ForwardIter1>::value_type,
	    typename iterator_traits<_ForwardIter2>::value_type>)

      // Test for empty ranges
      if (__first1 == __last1 || __first2 == __last2)
	return __first1;

      // Test for a pattern of length 1.
      _ForwardIter2 __tmp(__first2);
      ++__tmp;
      if (__tmp == __last2)
	return find(__first1, __last1, *__first2);

      // General case.

      _ForwardIter2 __p1, __p;

      __p1 = __first2; ++__p1;

      _ForwardIter1 __current = __first1;

      while (__first1 != __last1) {
	__first1 = 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;
    }

  /**
   *  @brief Search a sequence for a matching sub-sequence using a predicate.
   *  @param  first1     A forward iterator.
   *  @param  last1      A forward iterator.
   *  @param  first2     A forward iterator.
   *  @param  last2      A forward iterator.
   *  @param  predicate  A binary predicate.
   *  @return   The first iterator @c i in the range
   *  @p [first1,last1-(last2-first2)) such that
   *  @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
   *  @p [0,last2-first2), or @p last1 if no such iterator exists.
   *
   *  Searches the range @p [first1,last1) for a sub-sequence that compares
   *  equal value-by-value with the sequence given by @p [first2,last2),
   *  using @p predicate to determine equality, and returns an iterator
   *  to the first element of the sub-sequence, or @p last1 if no such
   *  iterator exists.
   *
   *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
  */
  template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred>
    _ForwardIter1
    search(_ForwardIter1 __first1, _ForwardIter1 __last1,
	   _ForwardIter2 __first2, _ForwardIter2 __last2,
	   _BinaryPred  __predicate)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
      __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
	    typename iterator_traits<_ForwardIter1>::value_type,
	    typename iterator_traits<_ForwardIter2>::value_type>)

      // Test for empty ranges
      if (__first1 == __last1 || __first2 == __last2)
	return __first1;

      // Test for a pattern of length 1.
      _ForwardIter2 __tmp(__first2);
      ++__tmp;
      if (__tmp == __last2) {
	while (__first1 != __last1 && !__predicate(*__first1, *__first2))
	  ++__first1;
	return __first1;
      }

      // General case.

      _ForwardIter2 __p1, __p;

      __p1 = __first2; ++__p1;

      _ForwardIter1 __current = __first1;

      while (__first1 != __last1) {
	while (__first1 != __last1) {
	  if (__predicate(*__first1, *__first2))
	    break;
	  ++__first1;
	}
	while (__first1 != __last1 && !__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;
    }

  /**
   *  @brief Search a sequence for a number of consecutive values.
   *  @param  first  A forward iterator.
   *  @param  last   A forward iterator.
   *  @param  count  The number of consecutive values.
   *  @param  val    The value to find.
   *  @return   The first iterator @c i in the range @p [first,last-count)
   *  such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
   *  or @p last if no such iterator exists.
   *
   *  Searches the range @p [first,last) for @p count consecutive elements
   *  equal to @p val.
  */
  template<typename _ForwardIter, typename _Integer, typename _Tp>
    _ForwardIter
    search_n(_ForwardIter __first, _ForwardIter __last,
	     _Integer __count, const _Tp& __val)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_EqualityComparableConcept<
	    typename iterator_traits<_ForwardIter>::value_type>)
      __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)

      if (__count <= 0)
	return __first;
      else {
	__first = find(__first, __last, __val);
	while (__first != __last) {
	  typename iterator_traits<_ForwardIter>::difference_type __n = __count;
	  --__n;
	  _ForwardIter __i = __first;
	  ++__i;
	  while (__i != __last && __n != 0 && *__i == __val) {
	    ++__i;
	    --__n;
	  }
	  if (__n == 0)
	    return __first;
	  else
	    __first = find(__i, __last, __val);
	}
	return __last;
      }
    }

  /**
   *  @brief Search a sequence for a number of consecutive values using a
   *         predicate.
   *  @param  first        A forward iterator.
   *  @param  last         A forward iterator.
   *  @param  count        The number of consecutive values.
   *  @param  val          The value to find.
   *  @param  binary_pred  A binary predicate.
   *  @return   The first iterator @c i in the range @p [first,last-count)
   *  such that @p binary_pred(*(i+N),val) is true for each @c N in the
   *  range @p [0,count), or @p last if no such iterator exists.
   *
   *  Searches the range @p [first,last) for @p count consecutive elements
   *  for which the predicate returns true.
  */
  template<typename _ForwardIter, typename _Integer, typename _Tp,
           typename _BinaryPred>
    _ForwardIter
    search_n(_ForwardIter __first, _ForwardIter __last,
	     _Integer __count, const _Tp& __val,
	     _BinaryPred __binary_pred)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
	    typename iterator_traits<_ForwardIter>::value_type, _Tp>)

      if (__count <= 0)
	return __first;
      else {
	while (__first != __last) {
	  if (__binary_pred(*__first, __val))
	    break;
	  ++__first;
	}
	while (__first != __last) {
	  typename iterator_traits<_ForwardIter>::difference_type __n = __count;
	  --__n;
	  _ForwardIter __i = __first;
	  ++__i;
	  while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
	    ++__i;
	    --__n;
	  }
	  if (__n == 0)
	    return __first;
	  else {
	    while (__i != __last) {
	      if (__binary_pred(*__i, __val))
		break;
	      ++__i;
	    }
	    __first = __i;
	  }
	}
	return __last;
      }
    }

  /**
   *  @brief Swap the elements of two sequences.
   *  @param  first1  A forward iterator.
   *  @param  last1   A forward iterator.
   *  @param  first2  A forward iterator.
   *  @return   An iterator equal to @p first2+(last1-first1).
   *
   *  Swaps each element in the range @p [first1,last1) with the
   *  corresponding element in the range @p [first2,(last1-first1)).
   *  The ranges must not overlap.
  */
  template<typename _ForwardIter1, typename _ForwardIter2>
    _ForwardIter2
    swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
		_ForwardIter2 __first2)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
      __glibcpp_function_requires(_ConvertibleConcept<
	    typename iterator_traits<_ForwardIter1>::value_type,
	    typename iterator_traits<_ForwardIter2>::value_type>)
      __glibcpp_function_requires(_ConvertibleConcept<
	    typename iterator_traits<_ForwardIter2>::value_type,
	    typename iterator_traits<_ForwardIter1>::value_type>)

      for ( ; __first1 != __last1; ++__first1, ++__first2)
	iter_swap(__first1, __first2);
      return __first2;
    }

  /**
   *  @brief Perform an operation on a sequence.
   *  @param  first     An input iterator.
   *  @param  last      An input iterator.
   *  @param  result    An output iterator.
   *  @param  unary_op  A unary operator.
   *  @return   An output iterator equal to @p result+(last-first).
   *
   *  Applies the operator to each element in the input range and assigns
   *  the results to successive elements of the output sequence.
   *  Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
   *  range @p [0,last-first).
   *
   *  @p unary_op must not alter its argument.
  */
  template<typename _InputIter, typename _OutputIter, typename _UnaryOperation>
    _OutputIter
    transform(_InputIter __first, _InputIter __last,
	      _OutputIter __result, _UnaryOperation __unary_op)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
            // "the type returned by a _UnaryOperation"
            __typeof__(__unary_op(*__first))>)

      for ( ; __first != __last; ++__first, ++__result)
	*__result = __unary_op(*__first);
      return __result;
    }

  /**
   *  @brief Perform an operation on corresponding elements of two sequences.
   *  @param  first1     An input iterator.
   *  @param  last1      An input iterator.
   *  @param  first2     An input iterator.
   *  @param  result     An output iterator.
   *  @param  binary_op  A binary operator.
   *  @return   An output iterator equal to @p result+(last-first).
   *
   *  Applies the operator to the corresponding elements in the two
   *  input ranges and assigns the results to successive elements of the
   *  output sequence.
   *  Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
   *  @c N in the range @p [0,last1-first1).
   *
   *  @p binary_op must not alter either of its arguments.
  */
  template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
	   typename _BinaryOperation>
    _OutputIter
    transform(_InputIter1 __first1, _InputIter1 __last1,
	      _InputIter2 __first2, _OutputIter __result,
	      _BinaryOperation __binary_op)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
            // "the type returned by a _BinaryOperation"
            __typeof__(__binary_op(*__first1,*__first2))>)

      for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
	*__result = __binary_op(*__first1, *__first2);
      return __result;
    }

  /**
   *  @brief Replace each occurrence of one value in a sequence with another
   *         value.
   *  @param  first      A forward iterator.
   *  @param  last       A forward iterator.
   *  @param  old_value  The value to be replaced.
   *  @param  new_value  The replacement value.
   *  @return   replace() returns no value.
   *
   *  For each iterator @c i in the range @p [first,last) if @c *i ==
   *  @p old_value then the assignment @c *i = @p new_value is performed.
  */
  template<typename _ForwardIter, typename _Tp>
    void
    replace(_ForwardIter __first, _ForwardIter __last,
	    const _Tp& __old_value, const _Tp& __new_value)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)