stl_algobase.h

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

        __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
                __true_type)
        { return std::__copy_trivial(__first, __last, __result); }

    template<typename _InputIterator, typename _OutputIterator>
        inline _OutputIterator
        __copy_ni2(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result, __true_type)
        {
            typedef typename iterator_traits<_InputIterator>::value_type
                _ValueType;
            typedef typename __type_traits<
                _ValueType>::has_trivial_assignment_operator _Trivial;
            return _OutputIterator(std::__copy_aux2(__first, __last, __result.base(),
                        _Trivial()));
        }

    template<typename _InputIterator, typename _OutputIterator>
        inline _OutputIterator
        __copy_ni2(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result, __false_type)
        {
            typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
            typedef typename __type_traits<
                _ValueType>::has_trivial_assignment_operator _Trivial;
            return std::__copy_aux2(__first, __last, __result, _Trivial());
        }

    template<typename _InputIterator, typename _OutputIterator>
        inline _OutputIterator
        __copy_ni1(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result, __true_type)
        {
            typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal;
            return std::__copy_ni2(__first.base(), __last.base(),
                    __result, __Normal());
        }

    template<typename _InputIterator, typename _OutputIterator>
        inline _OutputIterator
        __copy_ni1(_InputIterator __first, _InputIterator __last,
                _OutputIterator __result, __false_type)
        {
            typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal;
            return std::__copy_ni2(__first, __last, __result, __Normal());
        }

    /**
     *  @brief Copies the range [first,last) into result.
     *  @param  first  An input iterator.
     *  @param  last   An input iterator.
     *  @param  result An output iterator.
     *  @return   result + (first - last)
     *
     *  This inline function will boil down to a call to @c memmove whenever
     *  possible.  Failing that, if random access iterators are passed, then the
     *  loop count will be known (and therefore a candidate for compiler
     *  optimizations such as unrolling).  Result may not be contained within
     *  [first,last); the copy_backward function should be used instead.
     *
     *  Note that the end of the output range is permitted to be contained
     *  within [first,last).
     */
    template<typename _InputIterator, typename _OutputIterator>
        inline _OutputIterator
        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>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal;
            return std::__copy_ni1(__first, __last, __result, __Normal());
        }

    template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
        inline _BidirectionalIterator2
        __copy_backward(_BidirectionalIterator1 __first,
                _BidirectionalIterator1 __last,
                _BidirectionalIterator2 __result,
                bidirectional_iterator_tag)
        {
            while (__first != __last)
                *--__result = *--__last;
            return __result;
        }

    template<typename _RandomAccessIterator, typename _BidirectionalIterator>
        inline _BidirectionalIterator
        __copy_backward(_RandomAccessIterator __first, _RandomAccessIterator __last,
                _BidirectionalIterator __result, random_access_iterator_tag)
        {
            typename iterator_traits<_RandomAccessIterator>::difference_type __n;
            for (__n = __last - __first; __n > 0; --__n)
                *--__result = *--__last;
            return __result;
        }


    // This dispatch class is a workaround for compilers that do not
    // have partial ordering of function templates.  All we're doing is
    // creating a specialization so that we can turn a call to copy_backward
    // into a memmove whenever possible.
    template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
        typename _BoolType>
            struct __copy_backward_dispatch
            {
                static _BidirectionalIterator2
                    copy(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
                            _BidirectionalIterator2 __result)
                    { return std::__copy_backward(__first, __last, __result,
                            std::__iterator_category(__first)); }
            };

    template<typename _Tp>
        struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
        {
            static _Tp*
                copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
                {
                    const ptrdiff_t _Num = __last - __first;
                    std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
                    return __result - _Num;
                }
        };

    template<typename _Tp>
        struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
        {
            static _Tp*
                copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
                {
                    return  std::__copy_backward_dispatch<_Tp*, _Tp*, __true_type>
                        ::copy(__first, __last, __result);
                }
        };

    template<typename _BI1, typename _BI2>
        inline _BI2
        __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
        {
            typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
                ::has_trivial_assignment_operator _Trivial;
            return
                std::__copy_backward_dispatch<_BI1, _BI2, _Trivial>::copy(__first,
                        __last,
                        __result);
        }

    template <typename _BI1, typename _BI2>
        inline _BI2
        __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
                _BI2 __result, __true_type)
        { return _BI2(std::__copy_backward_aux(__first, __last, __result.base())); }

    template <typename _BI1, typename _BI2>
        inline _BI2
        __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
                _BI2 __result, __false_type)
        { return std::__copy_backward_aux(__first, __last, __result); }

    template <typename _BI1, typename _BI2>
        inline _BI2
        __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
                _BI2 __result, __true_type)
        {
            typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
            return std::__copy_backward_output_normal_iterator(__first.base(),
                    __last.base(),
                    __result, __Normal());
        }

    template <typename _BI1, typename _BI2>
        inline _BI2
        __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
                _BI2 __result, __false_type)
        {
            typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
            return std::__copy_backward_output_normal_iterator(__first, __last,
                    __result, __Normal());
        }

    /**
     *  @brief Copies the range [first,last) into result.
     *  @param  first  A bidirectional iterator.
     *  @param  last   A bidirectional iterator.
     *  @param  result A bidirectional iterator.
     *  @return   result - (first - last)
     *
     *  The function has the same effect as copy, but starts at the end of the
     *  range and works its way to the start, returning the start of the result.
     *  This inline function will boil down to a call to @c memmove whenever
     *  possible.  Failing that, if random access iterators are passed, then the
     *  loop count will be known (and therefore a candidate for compiler
     *  optimizations such as unrolling).
     *
     *  Result may not be in the range [first,last).  Use copy instead.  Note
     *  that the start of the output range may overlap [first,last).
     */
    template <typename _BI1, typename _BI2>
        inline _BI2
        copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
                __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
                __glibcxx_function_requires(_ConvertibleConcept<
                        typename iterator_traits<_BI1>::value_type,
                        typename iterator_traits<_BI2>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
            return std::__copy_backward_input_normal_iterator(__first, __last,
                    __result, __Normal());
        }


    /**
     *  @brief Fills the range [first,last) with copies of value.
     *  @param  first  A forward iterator.
     *  @param  last   A forward iterator.
     *  @param  value  A reference-to-const of arbitrary type.
     *  @return   Nothing.
     *
     *  This function fills a range with copies of the same value.  For one-byte
     *  types filling contiguous areas of memory, this becomes an inline call to
     *  @c memset.
     */
    template<typename _ForwardIterator, typename _Tp>
        void
        fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                    _ForwardIterator>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

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

    /**
     *  @brief Fills the range [first,first+n) with copies of value.
     *  @param  first  An output iterator.
     *  @param  n      The count of copies to perform.
     *  @param  value  A reference-to-const of arbitrary type.
     *  @return   The iterator at first+n.
     *
     *  This function fills a range with copies of the same value.  For one-byte
     *  types filling contiguous areas of memory, this becomes an inline call to
     *  @c memset.
     */
    template<typename _OutputIterator, typename _Size, typename _Tp>
        _OutputIterator
        fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,_Tp>)
#endif

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

    // Specialization: for one-byte types we can use memset.
    inline void
        fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
        {
            __glibcxx_requires_valid_range(__first, __last);
            const unsigned char __tmp = __c;
            std::memset(__first, __tmp, __last - __first);
        }

    inline void
        fill(signed char* __first, signed char* __last, const signed char& __c)
        {
            __glibcxx_requires_valid_range(__first, __last);
            const signed char __tmp = __c;
            std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);