stl_algo.h

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

      __glibcpp_function_requires(_EqualOpConcept<
	    typename iterator_traits<_ForwardIter>::value_type, _Tp>)
      __glibcpp_function_requires(_ConvertibleConcept<_Tp,
	    typename iterator_traits<_ForwardIter>::value_type>)

      for ( ; __first != __last; ++__first)
	if (*__first == __old_value)
	  *__first = __new_value;
    }

  /**
   *  @brief Replace each value in a sequence for which a predicate returns
   *         true with another value.
   *  @param  first      A forward iterator.
   *  @param  last       A forward iterator.
   *  @param  pred       A predicate.
   *  @param  new_value  The replacement value.
   *  @return   replace_if() returns no value.
   *
   *  For each iterator @c i in the range @p [first,last) if @p pred(*i)
   *  is true then the assignment @c *i = @p new_value is performed.
  */
  template<typename _ForwardIter, typename _Predicate, typename _Tp>
    void
    replace_if(_ForwardIter __first, _ForwardIter __last,
	       _Predicate __pred, const _Tp& __new_value)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_ConvertibleConcept<_Tp,
	    typename iterator_traits<_ForwardIter>::value_type>)
      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
	    typename iterator_traits<_ForwardIter>::value_type>)

      for ( ; __first != __last; ++__first)
	if (__pred(*__first))
	  *__first = __new_value;
    }

  /**
   *  @brief Copy a sequence, replacing each element of one value with another
   *         value.
   *  @param  first      An input iterator.
   *  @param  last       An input iterator.
   *  @param  result     An output iterator.
   *  @param  old_value  The value to be replaced.
   *  @param  new_value  The replacement value.
   *  @return   The end of the output sequence, @p result+(last-first).
   *
   *  Copies each element in the input range @p [first,last) to the
   *  output range @p [result,result+(last-first)) replacing elements
   *  equal to @p old_value with @p new_value.
  */
  template<typename _InputIter, typename _OutputIter, typename _Tp>
    _OutputIter
    replace_copy(_InputIter __first, _InputIter __last,
		 _OutputIter __result,
		 const _Tp& __old_value, const _Tp& __new_value)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	    typename iterator_traits<_InputIter>::value_type>)
      __glibcpp_function_requires(_EqualOpConcept<
	    typename iterator_traits<_InputIter>::value_type, _Tp>)

      for ( ; __first != __last; ++__first, ++__result)
	*__result = *__first == __old_value ? __new_value : *__first;
      return __result;
    }

  /**
   *  @brief Copy a sequence, replacing each value for which a predicate
   *         returns true with another value.
   *  @param  first      An input iterator.
   *  @param  last       An input iterator.
   *  @param  result     An output iterator.
   *  @param  pred       A predicate.
   *  @param  new_value  The replacement value.
   *  @return   The end of the output sequence, @p result+(last-first).
   *
   *  Copies each element in the range @p [first,last) to the range
   *  @p [result,result+(last-first)) replacing elements for which
   *  @p pred returns true with @p new_value.
  */
  template<typename _InputIter, typename _OutputIter, typename _Predicate,
           typename _Tp>
    _OutputIter
    replace_copy_if(_InputIter __first, _InputIter __last,
		    _OutputIter __result,
		    _Predicate __pred, const _Tp& __new_value)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	    typename iterator_traits<_InputIter>::value_type>)
      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
	    typename iterator_traits<_InputIter>::value_type>)

      for ( ; __first != __last; ++__first, ++__result)
	*__result = __pred(*__first) ? __new_value : *__first;
      return __result;
    }

  /**
   *  @brief Assign the result of a function object to each value in a
   *         sequence.
   *  @param  first  A forward iterator.
   *  @param  last   A forward iterator.
   *  @param  gen    A function object taking no arguments.
   *  @return   generate() returns no value.
   *
   *  Performs the assignment @c *i = @p gen() for each @c i in the range
   *  @p [first,last).
  */
  template<typename _ForwardIter, typename _Generator>
    void
    generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
    {
      // concept requirements
      __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_GeneratorConcept<_Generator,
	    typename iterator_traits<_ForwardIter>::value_type>)

      for ( ; __first != __last; ++__first)
	*__first = __gen();
    }

  /**
   *  @brief Assign the result of a function object to each value in a
   *         sequence.
   *  @param  first  A forward iterator.
   *  @param  n      The length of the sequence.
   *  @param  gen    A function object taking no arguments.
   *  @return   The end of the sequence, @p first+n
   *
   *  Performs the assignment @c *i = @p gen() for each @c i in the range
   *  @p [first,first+n).
  */
  template<typename _OutputIter, typename _Size, typename _Generator>
    _OutputIter
    generate_n(_OutputIter __first, _Size __n, _Generator __gen)
    {
      // concept requirements
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
            // "the type returned by a _Generator"
            __typeof__(__gen())>)

      for ( ; __n > 0; --__n, ++__first)
	*__first = __gen();
      return __first;
    }

  /**
   *  @brief Copy a sequence, removing elements of a given value.
   *  @param  first   An input iterator.
   *  @param  last    An input iterator.
   *  @param  result  An output iterator.
   *  @param  value   The value to be removed.
   *  @return   An iterator designating the end of the resulting sequence.
   *
   *  Copies each element in the range @p [first,last) not equal to @p value
   *  to the range beginning at @p result.
   *  remove_copy() is stable, so the relative order of elements that are
   *  copied is unchanged.
  */
  template<typename _InputIter, typename _OutputIter, typename _Tp>
    _OutputIter
    remove_copy(_InputIter __first, _InputIter __last,
		_OutputIter __result, const _Tp& __value)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	    typename iterator_traits<_InputIter>::value_type>)
      __glibcpp_function_requires(_EqualOpConcept<
	    typename iterator_traits<_InputIter>::value_type, _Tp>)

      for ( ; __first != __last; ++__first)
	if (!(*__first == __value)) {
	  *__result = *__first;
	  ++__result;
	}
      return __result;
    }

  /**
   *  @brief Copy a sequence, removing elements for which a predicate is true.
   *  @param  first   An input iterator.
   *  @param  last    An input iterator.
   *  @param  result  An output iterator.
   *  @param  pred    A predicate.
   *  @return   An iterator designating the end of the resulting sequence.
   *
   *  Copies each element in the range @p [first,last) for which
   *  @p pred returns true to the range beginning at @p result.
   *
   *  remove_copy_if() is stable, so the relative order of elements that are
   *  copied is unchanged.
  */
  template<typename _InputIter, typename _OutputIter, typename _Predicate>
    _OutputIter
    remove_copy_if(_InputIter __first, _InputIter __last,
		   _OutputIter __result, _Predicate __pred)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	    typename iterator_traits<_InputIter>::value_type>)
      __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
	    typename iterator_traits<_InputIter>::value_type>)

      for ( ; __first != __last; ++__first)
	if (!__pred(*__first)) {
	  *__result = *__first;
	  ++__result;
	}
      return __result;
    }

  /**
   *  @brief Remove elements from a sequence.
   *  @param  first  An input iterator.
   *  @param  last   An input iterator.
   *  @param  value  The value to be removed.
   *  @return   An iterator designating the end of the resulting sequence.
   *
   *  All elements equal to @p value are removed from the range
   *  @p [first,last).
   *
   *  remove() 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 _Tp>
    _ForwardIter
    remove(_ForwardIter __first, _ForwardIter __last,
	   const _Tp& __value)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_ConvertibleConcept<_Tp,
	    typename iterator_traits<_ForwardIter>::value_type>)
      __glibcpp_function_requires(_EqualOpConcept<
	    typename iterator_traits<_ForwardIter>::value_type, _Tp>)

      __first = find(__first, __last, __value);
      _ForwardIter __i = __first;
      return __first == __last ? __first
			       : remove_copy(++__i, __last, __first, __value);
    }

  /**
   *  @brief Remove elements from a sequence using a predicate.
   *  @param  first  A forward iterator.
   *  @param  last   A forward iterator.
   *  @param  pred   A predicate.
   *  @return   An iterator designating the end of the resulting sequence.
   *
   *  All elements for which @p pred returns true are removed from the range
   *  @p [first,last).
   *
   *  remove_if() 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 _Predicate>
    _ForwardIter
    remove_if(_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>)

      __first = find_if(__first, __last, __pred);
      _ForwardIter __i = __first;
      return __first == __last ? __first
			       : remove_copy_if(++__i, __last, __first, __pred);
    }

  /**
   *  @if maint
   *  This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
   *  overloaded for output iterators.
   *  @endif
  */
  template<typename _InputIter, typename _OutputIter>
    _OutputIter
    __unique_copy(_InputIter __first, _InputIter __last,
		  _OutputIter __result,
		  output_iterator_tag)
    {
      // concept requirements -- taken care of in dispatching function
      typename iterator_traits<_InputIter>::value_type __value = *__first;
      *__result = __value;
      while (++__first != __last)
	if (!(__value == *__first)) {
	  __value = *__first;
	  *++__result = __value;
	}
      return ++__result;
    }

  /**
   *  @if maint
   *  This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
   *  overloaded for forward iterators.
   *  @endif
  */
  template<typename _InputIter, typename _ForwardIter>
    _ForwardIter
    __unique_copy(_InputIter __first, _InputIter __last,
		  _ForwardIter __result,
		  forward_iterator_tag)
    {
      // concept requirements -- taken care of in dispatching function
      *__result = *__first;
      while (++__first != __last)
	if (!(*__result == *__first))
	  *++__result = *__first;
      return ++__result;
    }

  /**
   *  @brief Copy a sequence, removing consecutive duplicate values.
   *  @param  first   An input iterator.
   *  @param  last    An input iterator.
   *  @param  result  An output iterator.
   *  @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 that compare equal.
   *  unique_copy() is stable, so the relative order of elements that are
   *  copied is unchanged.
  */
  template<typename _InputIter, typename _OutputIter>
    inline _OutputIter
    unique_copy(_InputIter __first, _InputIter __last,
		_OutputIter __result)
    {
      // concept requirements
      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
	    typename iterator_traits<_InputIter>::value_type>)
      __glibcpp_function_requires(_EqualityComparableConcept<
	    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, _IterType());
    }

  /**
   *  @if maint
   *  This is an uglified
   *  unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
   *  overloaded for output iterators.
   *  @endif
  */
  template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
    _OutputIter
    __unique_copy(_InputIter __first, _InputIter __last,
		  _OutputIter __result,
		  _BinaryPredicate __binary_pred,
		  output_iterator_tag)
    {
      // concept requirements -- iterators already checked
      __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
	  typename iterator_traits<_InputIter>::value_type,
	  typename iterator_traits<_InputIter>::value_type>)

      typename iterator_traits<_InputIter>::value_type __value = *__first;
      *__result = __value;
      while (++__first != __last)
	if (!__binary_pred(__value, *__first)) {
	  __value = *__first;
	  *++__result = __value;
	}
      return ++__result;
    }

  /**
   *  @if maint
   *  This is an uglified
   *  unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
   *  overloaded for forward iterators.
   *  @endif
  */
  template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
    _ForwardIter
    __unique_copy(_InputIter __first, _InputIter __last,
		  _ForwardIter __result,
		  _BinaryPredicate __binary_pred,
		  forward_iterator_tag)