stl_algo.h

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

            __unique_copy(_InputIterator __first, _InputIterator __last,
                    _ForwardIterator __result,
                    _BinaryPredicate __binary_pred,
                    forward_iterator_tag)
            {
                // concept requirements -- iterators already checked
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
                        typename iterator_traits<_ForwardIterator>::value_type,
                        typename iterator_traits<_InputIterator>::value_type>)
#endif

                    *__result = *__first;
                while (++__first != __last)
                    if (!__binary_pred(*__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 _InputIterator, typename _OutputIterator>
        inline _OutputIterator
        unique_copy(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result)
        {
            // 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(_EqualityComparableConcept<
                        typename iterator_traits<_InputIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            typedef typename iterator_traits<_OutputIterator>::iterator_category
                _IterType;

            if (__first == __last) return __result;
            return std::__unique_copy(__first, __last, __result, _IterType());
        }

    /**
     *  @brief Copy a sequence, removing consecutive values using a predicate.
     *  @param  first        An input iterator.
     *  @param  last         An input iterator.
     *  @param  result       An output iterator.
     *  @param  binary_pred  A binary predicate.
     *  @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 for which @p binary_pred returns
     *  true.
     *  unique_copy() is stable, so the relative order of elements that are
     *  copied is unchanged.
     */
    template<typename _InputIterator, typename _OutputIterator,
        typename _BinaryPredicate>
            inline _OutputIterator
            unique_copy(_InputIterator __first, _InputIterator __last,
                    _OutputIterator __result,
                    _BinaryPredicate __binary_pred)
            {
                // concept requirements -- predicates checked later
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
                    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                            typename iterator_traits<_InputIterator>::value_type>)
#endif
                    __glibcxx_requires_valid_range(__first, __last);

                typedef typename iterator_traits<_OutputIterator>::iterator_category
                    _IterType;

                if (__first == __last) return __result;
                return std::__unique_copy(__first, __last, __result,
                        __binary_pred, _IterType());
            }

    /**
     *  @brief Remove consecutive duplicate values from a sequence.
     *  @param  first  A forward iterator.
     *  @param  last   A forward iterator.
     *  @return  An iterator designating the end of the resulting sequence.
     *
     *  Removes all but the first element from each group of consecutive
     *  values that compare equal.
     *  unique() 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>
        _ForwardIterator
        unique(_ForwardIterator __first, _ForwardIterator __last)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                    _ForwardIterator>)
                __glibcxx_function_requires(_EqualityComparableConcept<
                        typename iterator_traits<_ForwardIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            // Skip the beginning, if already unique.
            __first = std::adjacent_find(__first, __last);
            if (__first == __last)
                return __last;

            // Do the real copy work.
            _ForwardIterator __dest = __first;
            ++__first;
            while (++__first != __last)
                if (!(*__dest == *__first))
                    *++__dest = *__first;
            return ++__dest;
        }

    /**
     *  @brief Remove consecutive values from a sequence using a predicate.
     *  @param  first        A forward iterator.
     *  @param  last         A forward iterator.
     *  @param  binary_pred  A binary predicate.
     *  @return  An iterator designating the end of the resulting sequence.
     *
     *  Removes all but the first element from each group of consecutive
     *  values for which @p binary_pred returns true.
     *  unique() 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 _BinaryPredicate>
        _ForwardIterator
        unique(_ForwardIterator __first, _ForwardIterator __last,
                _BinaryPredicate __binary_pred)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                    _ForwardIterator>)
                __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
                        typename iterator_traits<_ForwardIterator>::value_type,
                        typename iterator_traits<_ForwardIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            // Skip the beginning, if already unique.
            __first = std::adjacent_find(__first, __last, __binary_pred);
            if (__first == __last)
                return __last;

            // Do the real copy work.
            _ForwardIterator __dest = __first;
            ++__first;
            while (++__first != __last)
                if (!__binary_pred(*__dest, *__first))
                    *++__dest = *__first;
            return ++__dest;
        }

    /**
     *  @if maint
     *  This is an uglified reverse(_BidirectionalIterator,
     *                              _BidirectionalIterator)
     *  overloaded for bidirectional iterators.
     *  @endif
     */
    template<typename _BidirectionalIterator>
        void
        __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
                bidirectional_iterator_tag)
        {
            while (true)
                if (__first == __last || __first == --__last)
                    return;
                else
                    std::iter_swap(__first++, __last);
        }

    /**
     *  @if maint
     *  This is an uglified reverse(_BidirectionalIterator,
     *                              _BidirectionalIterator)
     *  overloaded for bidirectional iterators.
     *  @endif
     */
    template<typename _RandomAccessIterator>
        void
        __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
                random_access_iterator_tag)
        {
            while (__first < __last)
                std::iter_swap(__first++, --__last);
        }

    /**
     *  @brief Reverse a sequence.
     *  @param  first  A bidirectional iterator.
     *  @param  last   A bidirectional iterator.
     *  @return   reverse() returns no value.
     *
     *  Reverses the order of the elements in the range @p [first,last),
     *  so that the first element becomes the last etc.
     *  For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
     *  swaps @p *(first+i) and @p *(last-(i+1))
     */
    template<typename _BidirectionalIterator>
        inline void
        reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
                    _BidirectionalIterator>)
#endif
                __glibcxx_requires_valid_range(__first, __last);
            std::__reverse(__first, __last, std::__iterator_category(__first));
        }

    /**
     *  @brief Copy a sequence, reversing its elements.
     *  @param  first   A bidirectional iterator.
     *  @param  last    A bidirectional iterator.
     *  @param  result  An output iterator.
     *  @return  An iterator designating the end of the resulting sequence.
     *
     *  Copies the elements in the range @p [first,last) to the range
     *  @p [result,result+(last-first)) such that the order of the
     *  elements is reversed.
     *  For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
     *  performs the assignment @p *(result+(last-first)-i) = *(first+i).
     *  The ranges @p [first,last) and @p [result,result+(last-first))
     *  must not overlap.
     */
    template<typename _BidirectionalIterator, typename _OutputIterator>
        _OutputIterator
        reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
                _OutputIterator __result)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_BidirectionalIteratorConcept<
                    _BidirectionalIterator>)
                __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                        typename iterator_traits<_BidirectionalIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            while (__first != __last)
            {
                --__last;
                *__result = *__last;
                ++__result;
            }
            return __result;
        }


    /**
     *  @if maint
     *  This is a helper function for the rotate algorithm specialized on RAIs.
     *  It returns the greatest common divisor of two integer values.
     *  @endif
     */
    template<typename _EuclideanRingElement>
        _EuclideanRingElement
        __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
        {
            while (__n != 0)
            {
                _EuclideanRingElement __t = __m % __n;
                __m = __n;
                __n = __t;
            }
            return __m;
        }

    /**
     *  @if maint
     *  This is a helper function for the rotate algorithm.
     *  @endif
     */
    template<typename _ForwardIterator>
        void
        __rotate(_ForwardIterator __first,
                _ForwardIterator __middle,
                _ForwardIterator __last,
                forward_iterator_tag)
        {
            if ((__first == __middle) || (__last  == __middle))
                return;

            _ForwardIterator __first2 = __middle;
            do
            {
                swap(*__first++, *__first2++);
                if (__first == __middle)
                    __middle = __first2;
            }
            while (__first2 != __last);

            __first2 = __middle;

            while (__first2 != __last)
            {
                swap(*__first++, *__first2++);
                if (__first == __middle)
                    __middle = __first2;
                else if (__first2 == __last)
                    __first2 = __m