stl_algobase.h

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

        }

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

    template<typename _Size>
        inline unsigned char*
        fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
        {
            std::fill(__first, __first + __n, __c);
            return __first + __n;
        }

    template<typename _Size>
        inline signed char*
        fill_n(char* __first, _Size __n, const signed char& __c)
        {
            std::fill(__first, __first + __n, __c);
            return __first + __n;
        }

    template<typename _Size>
        inline char*
        fill_n(char* __first, _Size __n, const char& __c)
        {
            std::fill(__first, __first + __n, __c);
            return __first + __n;
        }


    /**
     *  @brief Finds the places in ranges which don't match.
     *  @param  first1  An input iterator.
     *  @param  last1   An input iterator.
     *  @param  first2  An input iterator.
     *  @return   A pair of iterators pointing to the first mismatch.
     *
     *  This compares the elements of two ranges using @c == and returns a pair
     *  of iterators.  The first iterator points into the first range, the
     *  second iterator points into the second range, and the elements pointed
     *  to by the iterators are not equal.
     */
    template<typename _InputIterator1, typename _InputIterator2>
        pair<_InputIterator1, _InputIterator2>
        mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
                _InputIterator2 __first2)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
                __glibcxx_function_requires(_EqualityComparableConcept<
                        typename iterator_traits<_InputIterator1>::value_type>)
                __glibcxx_function_requires(_EqualityComparableConcept<
                        typename iterator_traits<_InputIterator2>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first1, __last1);

            while (__first1 != __last1 && *__first1 == *__first2)
            {
                ++__first1;
                ++__first2;
            }
            return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
        }

    /**
     *  @brief Finds the places in ranges which don't match.
     *  @param  first1  An input iterator.
     *  @param  last1   An input iterator.
     *  @param  first2  An input iterator.
     *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
     *  @return   A pair of iterators pointing to the first mismatch.
     *
     *  This compares the elements of two ranges using the binary_pred
     *  parameter, and returns a pair
     *  of iterators.  The first iterator points into the first range, the
     *  second iterator points into the second range, and the elements pointed
     *  to by the iterators are not equal.
     */
    template<typename _InputIterator1, typename _InputIterator2,
        typename _BinaryPredicate>
            pair<_InputIterator1, _InputIterator2>
            mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
                    _InputIterator2 __first2, _BinaryPredicate __binary_pred)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
                    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
#endif
                    __glibcxx_requires_valid_range(__first1, __last1);

                while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
                {
                    ++__first1;
                    ++__first2;
                }
                return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
            }

    /**
     *  @brief Tests a range for element-wise equality.
     *  @param  first1  An input iterator.
     *  @param  last1   An input iterator.
     *  @param  first2  An input iterator.
     *  @return   A boolean true or false.
     *
     *  This compares the elements of two ranges using @c == and returns true or
     *  false depending on whether all of the corresponding elements of the
     *  ranges are equal.
     */
    template<typename _InputIterator1, typename _InputIterator2>
        inline bool
        equal(_InputIterator1 __first1, _InputIterator1 __last1,
                _InputIterator2 __first2)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
                __glibcxx_function_requires(_EqualOpConcept<
                        typename iterator_traits<_InputIterator1>::value_type,
                        typename iterator_traits<_InputIterator2>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first1, __last1);

            for ( ; __first1 != __last1; ++__first1, ++__first2)
                if (!(*__first1 == *__first2))
                    return false;
            return true;
        }

    /**
     *  @brief Tests a range for element-wise equality.
     *  @param  first1  An input iterator.
     *  @param  last1   An input iterator.
     *  @param  first2  An input iterator.
     *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
     *  @return   A boolean true or false.
     *
     *  This compares the elements of two ranges using the binary_pred
     *  parameter, and returns true or
     *  false depending on whether all of the corresponding elements of the
     *  ranges are equal.
     */
    template<typename _InputIterator1, typename _InputIterator2,
        typename _BinaryPredicate>
            inline bool
            equal(_InputIterator1 __first1, _InputIterator1 __last1,
                    _InputIterator2 __first2,
                    _BinaryPredicate __binary_pred)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
                    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
#endif
                    __glibcxx_requires_valid_range(__first1, __last1);

                for ( ; __first1 != __last1; ++__first1, ++__first2)
                    if (!__binary_pred(*__first1, *__first2))
                        return false;
                return true;
            }

    /**
     *  @brief Performs "dictionary" comparison on ranges.
     *  @param  first1  An input iterator.
     *  @param  last1   An input iterator.
     *  @param  first2  An input iterator.
     *  @param  last2   An input iterator.
     *  @return   A boolean true or false.
     *
     *  "Returns true if the sequence of elements defined by the range
     *  [first1,last1) is lexicographically less than the sequence of elements
     *  defined by the range [first2,last2).  Returns false otherwise."
     *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
     *  then this is an inline call to @c memcmp.
     */
    template<typename _InputIterator1, typename _InputIterator2>
        bool
        lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
                _InputIterator2 __first2, _InputIterator2 __last2)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
                __glibcxx_function_requires(_LessThanComparableConcept<
                        typename iterator_traits<_InputIterator1>::value_type>)
                __glibcxx_function_requires(_LessThanComparableConcept<
                        typename iterator_traits<_InputIterator2>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first1, __last1);
            __glibcxx_requires_valid_range(__first2, __last2);

            for (;__first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
            {
                if (*__first1 < *__first2)
                    return true;
                if (*__first2 < *__first1)
                    return false;
            }
            return __first1 == __last1 && __first2 != __last2;
        }

    /**
     *  @brief Performs "dictionary" comparison on ranges.
     *  @param  first1  An input iterator.
     *  @param  last1   An input iterator.
     *  @param  first2  An input iterator.
     *  @param  last2   An input iterator.
     *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
     *  @return   A boolean true or false.
     *
     *  The same as the four-parameter @c lexigraphical_compare, but uses the
     *  comp parameter instead of @c <.
     */
    template<typename _InputIterator1, typename _InputIterator2,
        typename _Compare>
            bool
            lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
                    _InputIterator2 __first2, _InputIterator2 __last2,
                    _Compare __comp)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
                    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
#endif
                    __glibcxx_requires_valid_range(__first1, __last1);
                __glibcxx_requires_valid_range(__first2, __last2);

                for ( ; __first1 != __last1 && __first2 != __last2
                        ; ++__first1, ++__first2)
                {
                    if (__comp(*__first1, *__first2))
                        return true;
                    if (__comp(*__first2, *__first1))
                        return false;
                }
                return __first1 == __last1 && __first2 != __last2;
            }

    inline bool
        lexicographical_compare(const unsigned char* __first1,
                const unsigned char* __last1,
                const unsigned char* __first2,
                const unsigned char* __last2)
        {
            __glibcxx_requires_valid_range(__first1, __last1);
            __glibcxx_requires_valid_range(__first2, __last2);

            const size_t __len1 = __last1 - __first1;
            const size_t __len2 = __last2 - __first2;
            const int __result = std::memcmp(__first1, __first2,
                    std::min(__len1, __len2));
            return __result != 0 ? __result < 0 : __len1 < __len2;
        }

    inline bool
        lexicographical_compare(const char* __first1, const char* __last1,
                const char* __first2, const char* __last2)
        {
            __glibcxx_requires_valid_range(__first1, __last1);
            __glibcxx_requires_valid_range(__first2, __last2);

#if CHAR_MAX == SCHAR_MAX
            return std::lexicographical_compare((const signed char*) __first1,
                    (const signed char*) __last1,
                    (const signed char*) __first2,
                    (const signed char*) __last2);
#else /* CHAR_MAX == SCHAR_MAX */
            return std::lexicographical_compare((const unsigned char*) __first1,
                    (const unsigned char*) __last1,
                    (const unsigned char*) __first2,
                    (const unsigned char*) __last2);
#endif /* CHAR_MAX == SCHAR_MAX */
        }

} // namespace std

#endif