stl_algo.h

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

        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
                __glibcxx_function_requires(_EqualityComparableConcept<
                        typename iterator_traits<_ForwardIterator>::value_type>)
                __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            if (__count <= 0)
                return __first;
            else
            {
                __first = std::find(__first, __last, __val);
                while (__first != __last)
                {
                    typename iterator_traits<_ForwardIterator>::difference_type
                        __n = __count;
                    _ForwardIterator __i = __first;
                    ++__i;
                    while (__i != __last && __n != 1 && *__i == __val)
                    {
                        ++__i;
                        --__n;
                    }
                    if (__n == 1)
                        return __first;
                    else
                        __first = std::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 _ForwardIterator, typename _Integer, typename _Tp,
        typename _BinaryPredicate>
            _ForwardIterator
            search_n(_ForwardIterator __first, _ForwardIterator __last,
                    _Integer __count, const _Tp& __val,
                    _BinaryPredicate __binary_pred)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
                    __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
                            typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
#endif
                    __glibcxx_requires_valid_range(__first, __last);

                if (__count <= 0)
                    return __first;
                else
                {
                    while (__first != __last)
                    {
                        if (__binary_pred(*__first, __val))
                            break;
                        ++__first;
                    }
                    while (__first != __last)
                    {
                        typename iterator_traits<_ForwardIterator>::difference_type
                            __n = __count;
                        _ForwardIterator __i = __first;
                        ++__i;
                        while (__i != __last && __n != 1 && __binary_pred(*__i, __val))
                        {
                            ++__i;
                            --__n;
                        }
                        if (__n == 1)
                            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 _ForwardIterator1, typename _ForwardIterator2>
        _ForwardIterator2
        swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
                _ForwardIterator2 __first2)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                    _ForwardIterator1>)
                __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                        _ForwardIterator2>)
                __glibcxx_function_requires(_ConvertibleConcept<
                        typename iterator_traits<_ForwardIterator1>::value_type,
                        typename iterator_traits<_ForwardIterator2>::value_type>)
                __glibcxx_function_requires(_ConvertibleConcept<
                        typename iterator_traits<_ForwardIterator2>::value_type,
                        typename iterator_traits<_ForwardIterator1>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first1, __last1);

            for ( ; __first1 != __last1; ++__first1, ++__first2)
                std::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 _InputIterator, typename _OutputIterator,
        typename _UnaryOperation>
            _OutputIterator
            transform(_InputIterator __first, _InputIterator __last,
                    _OutputIterator __result, _UnaryOperation __unary_op)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
                    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                            // "the type returned by a _UnaryOperation"
                            __typeof__(__unary_op(*__first))>)
#endif
                    __glibcxx_requires_valid_range(__first, __last);

                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 _InputIterator1, typename _InputIterator2,
        typename _OutputIterator, typename _BinaryOperation>
            _OutputIterator
            transform(_InputIterator1 __first1, _InputIterator1 __last1,
                    _InputIterator2 __first2, _OutputIterator __result,
                    _BinaryOperation __binary_op)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
                    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
                    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                            // "the type returned by a _BinaryOperation"
                            __typeof__(__binary_op(*__first1,*__first2))>)
#endif
                    __glibcxx_requires_valid_range(__first1, __last1);

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

            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 _ForwardIterator, typename _Predicate, typename _Tp>
        void
        replace_if(_ForwardIterator __first, _ForwardIterator __last,
                _Predicate __pred, const _Tp& __new_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(_UnaryPredicateConcept<_Predicate,
                        typename iterator_traits<_ForwardIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            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 _InputIterator, typename _OutputIterator, typename _Tp>
        _OutputIterator
        replace_copy(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result,
                const _Tp& __old_value, 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(_EqualOpConcept<
                        typename iterator_traits<_InputIterator>::value_type, _Tp>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            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).
     *