algorithm

symbian上STL模板库的实现

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

            _Distance __remaining = std::distance(__first, __last);
            _Distance __m = min(__n, __remaining);

            while (__m > 0) {
                if ((std::rand() % __remaining) < __m) {
                    *__out = *__first;
                    ++__out;
                    --__m;
                }

                --__remaining;
                ++__first;
            }
            return __out;
        }

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template<typename _ForwardIterator, typename _OutputIterator, typename _Distance,
        typename _RandomNumberGenerator>
            _OutputIterator
            random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
                    _OutputIterator __out, const _Distance __n,
                    _RandomNumberGenerator& __rand)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
                    __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                            typename iterator_traits<_ForwardIterator>::value_type>)
                    __glibcxx_function_requires(_UnaryFunctionConcept<
                            _RandomNumberGenerator, _Distance, _Distance>)
#endif
                    __glibcxx_requires_valid_range(__first, __last);

                _Distance __remaining = std::distance(__first, __last);
                _Distance __m = min(__n, __remaining);

                while (__m > 0) {
                    if (__rand(__remaining) < __m) {
                        *__out = *__first;
                        ++__out;
                        --__m;
                    }

                    --__remaining;
                    ++__first;
                }
                return __out;
            }

    template<typename _InputIterator, typename _RandomAccessIterator, typename _Distance>
        _RandomAccessIterator
        __random_sample(_InputIterator __first, _InputIterator __last,
                _RandomAccessIterator __out,
                const _Distance __n)
        {
            _Distance __m = 0;
            _Distance __t = __n;
            for ( ; __first != __last && __m < __n; ++__m, ++__first)
                __out[__m] = *__first;

            while (__first != __last) {
                ++__t;
                _Distance __M = std::rand() % (__t);
                if (__M < __n)
                    __out[__M] = *__first;
                ++__first;
            }

            return __out + __m;
        }

    template<typename _InputIterator, typename _RandomAccessIterator,
        typename _RandomNumberGenerator, typename _Distance>
            _RandomAccessIterator
            __random_sample(_InputIterator __first, _InputIterator __last,
                    _RandomAccessIterator __out,
                    _RandomNumberGenerator& __rand,
                    const _Distance __n)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_UnaryFunctionConcept<
                        _RandomNumberGenerator, _Distance, _Distance>)
#endif

                    _Distance __m = 0;
                _Distance __t = __n;
                for ( ; __first != __last && __m < __n; ++__m, ++__first)
                    __out[__m] = *__first;

                while (__first != __last) {
                    ++__t;
                    _Distance __M = __rand(__t);
                    if (__M < __n)
                        __out[__M] = *__first;
                    ++__first;
                }

                return __out + __m;
            }

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template<typename _InputIterator, typename _RandomAccessIterator>
        inline _RandomAccessIterator
        random_sample(_InputIterator __first, _InputIterator __last,
                _RandomAccessIterator __out_first, _RandomAccessIterator __out_last)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
                __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                        _RandomAccessIterator>)
#endif
                __glibcxx_requires_valid_range(__first, __last);
            __glibcxx_requires_valid_range(__out_first, __out_last);

            return __random_sample(__first, __last,
                    __out_first, __out_last - __out_first);
        }

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template<typename _InputIterator, typename _RandomAccessIterator,
        typename _RandomNumberGenerator>
            inline _RandomAccessIterator
            random_sample(_InputIterator __first, _InputIterator __last,
                    _RandomAccessIterator __out_first, _RandomAccessIterator __out_last,
                    _RandomNumberGenerator& __rand)
            {
                // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
                __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
                    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                            _RandomAccessIterator>)
#endif
                    __glibcxx_requires_valid_range(__first, __last);
                __glibcxx_requires_valid_range(__out_first, __out_last);

                return __random_sample(__first, __last,
                        __out_first, __rand,
                        __out_last - __out_first);
            }

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template<typename _RandomAccessIterator>
        inline bool
        is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
                __glibcxx_function_requires(_LessThanComparableConcept<
                        typename iterator_traits<_RandomAccessIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            return std::__is_heap(__first, __last - __first);
        }

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
        inline bool
        is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
                _StrictWeakOrdering __comp)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
                __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
                        typename iterator_traits<_RandomAccessIterator>::value_type,
                        typename iterator_traits<_RandomAccessIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            return std::__is_heap(__first, __comp, __last - __first);
        }

    // is_sorted, a predicated testing whether a range is sorted in
    // nondescending order.  This is an extension, not part of the C++
    // standard.

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template<typename _ForwardIterator>
        bool
        is_sorted(_ForwardIterator __first, _ForwardIterator __last)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
                __glibcxx_function_requires(_LessThanComparableConcept<
                        typename iterator_traits<_ForwardIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            if (__first == __last)
                return true;

            _ForwardIterator __next = __first;
            for (++__next; __next != __last; __first = __next, ++__next) {
                if (*__next < *__first)
                    return false;
            }

            return true;
        }

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template<typename _ForwardIterator, typename _StrictWeakOrdering>
        bool
        is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
                __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
                        typename iterator_traits<_ForwardIterator>::value_type,
                        typename iterator_traits<_ForwardIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            if (__first == __last)
                return true;

            _ForwardIterator __next = __first;
            for (++__next; __next != __last; __first = __next, ++__next) {
                if (__comp(*__next, *__first))
                    return false;
            }

            return true;
        }
} // namespace __gnu_cxx

#endif /* _EXT_ALGORITHM */