stl_algo.h

来自「symbian上STL模板库的实现」· C头文件 代码 · 共 1,620 行 · 第 1/5 页

     *  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 _InputIterator, typename _OutputIterator,
        typename _Predicate, typename _Tp>
            _OutputIterator
            replace_copy_if(_InputIterator __first, _InputIterator __last,
                    _OutputIterator __result,
                    _Predicate __pred, const _Tp& __new_value)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
                    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                            typename iterator_traits<_InputIterator>::value_type>)
                    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
                            typename iterator_traits<_InputIterator>::value_type>)
#endif
                    __glibcxx_requires_valid_range(__first, __last);

                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 _ForwardIterator, typename _Generator>
        void
        generate(_ForwardIterator __first, _ForwardIterator __last,
                _Generator __gen)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
                __glibcxx_function_requires(_GeneratorConcept<_Generator,
                        typename iterator_traits<_ForwardIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            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 _OutputIterator, typename _Size, typename _Generator>
        _OutputIterator
        generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                    // "the type returned by a _Generator"
                    __typeof__(__gen())>)
#endif

                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 _InputIterator, typename _OutputIterator, typename _Tp>
        _OutputIterator
        remove_copy(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result, const _Tp& __value)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
                __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                        typename iterator_traits<_InputIterator>::value_type>)
                __glibcxx_function_requires(_EqualOpConcept<
                        typename iterator_traits<_InputIterator>::value_type, _Tp>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            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 _InputIterator, typename _OutputIterator,
        typename _Predicate>
            _OutputIterator
            remove_copy_if(_InputIterator __first, _InputIterator __last,
                    _OutputIterator __result, _Predicate __pred)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
                    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                            typename iterator_traits<_InputIterator>::value_type>)
                    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
                            typename iterator_traits<_InputIterator>::value_type>)
#endif
                    __glibcxx_requires_valid_range(__first, __last);

                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 _ForwardIterator, typename _Tp>
        _ForwardIterator
        remove(_ForwardIterator __first, _ForwardIterator __last,
                const _Tp& __value)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                    _ForwardIterator>)
                __glibcxx_function_requires(_ConvertibleConcept<_Tp,
                        typename iterator_traits<_ForwardIterator>::value_type>)
                __glibcxx_function_requires(_EqualOpConcept<
                        typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            __first = std::find(__first, __last, __value);
            _ForwardIterator __i = __first;
            return __first == __last ? __first
                : std::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 _ForwardIterator, typename _Predicate>
        _ForwardIterator
        remove_if(_ForwardIterator __first, _ForwardIterator __last,
                _Predicate __pred)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                    _ForwardIterator>)
                __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
                        typename iterator_traits<_ForwardIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

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

    /**
     *  @if maint
     *  This is an uglified unique_copy(_InputIterator, _InputIterator,
     *                                  _OutputIterator)
     *  overloaded for output iterators.
     *  @endif
     */
    template<typename _InputIterator, typename _OutputIterator>
        _OutputIterator
        __unique_copy(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result,
                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;
        }

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

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

                    typename iterator_traits<_InputIterator>::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(_InputIterator, _InputIterator, _OutputIterator,
     *              _BinaryPredicate)
     *  overloaded for forward iterators.
     *  @endif
     */
    template<typename _InputIterator, typename _ForwardIterator,
        typename _BinaryPredicate>
            _ForwardIterator