mstl_algorithm.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

    for( ; first != last; ++first )
    {
        if( *first == value )
            ++count;
    }
    return count;
}

template< typename InputIterator, typename T >
typename iterator_traits<InputIterator>::difference_type
count_aux( InputIterator first, InputIterator last, const T& value,
           random_access_iterator_tag )
{
    typename iterator_traits<InputIterator>::difference_type  count = 0;
    typename iterator_traits<InputIterator>::difference_type  n = last - first;

    for( ; n > 0; --n,++first )
    {
        if( *first == value )
            ++count;
    }
    return count;
}

//-----------------------------------------------------------------------------

template< typename InputIterator, typename UnaryPredicate >
inline typename iterator_traits<InputIterator>::difference_type
count_if( InputIterator first, InputIterator last, UnaryPredicate pred )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return count_if_aux( first, last, pred, cate() );
}

template< typename InputIterator, typename UnaryPredicate >
typename iterator_traits<InputIterator>::difference_type
count_if_aux( InputIterator first, InputIterator last, UnaryPredicate pred,
              input_iterator_tag )
{
    typename iterator_traits<InputIterator>::difference_type  count = 0;

    for( ; first != last; ++first )
    {
        if( pred(*first) )
            ++count;
    }
    return count;
}

template< typename InputIterator, typename UnaryPredicate >
typename iterator_traits<InputIterator>::difference_type
count_if_aux( InputIterator first, InputIterator last, UnaryPredicate pred,
              random_access_iterator_tag )
{
    typename iterator_traits<InputIterator>::difference_type  count = 0;
    typename iterator_traits<InputIterator>::difference_type  n = last - first;

    for( ; n > 0; --n,++first )
    {
        if( pred(*first) )
            ++count;
    }
    return count;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//*****************************************************************************
//*****************************************************************************
//                             最大值与最小值算法
//
//                          min_element  max_element
//*****************************************************************************
//*****************************************************************************

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename ForwardIterator >
ForwardIterator min_element( ForwardIterator first, ForwardIterator last )
{
    if( first == last )
        return first;

    ForwardIterator result = first;
    for( ; first != last; ++first )
    {
        if( *first < *result )
            result = first;
    }
    return result;
}



template< typename ForwardIterator, typename StrictWeakOrdering >
ForwardIterator min_element( ForwardIterator first, ForwardIterator last,
                             StrictWeakOrdering comp )
{
    if( first == last )
        return first;

    ForwardIterator result = first;
    for( ; first != last; ++first )
    {
        if( comp(*first, *result) )
            result = first;
    }
    return result;
}

//-----------------------------------------------------------------------------

template< typename ForwardIterator >
ForwardIterator max_element( ForwardIterator first, ForwardIterator last )
{
    if( first == last )
        return first;

    ForwardIterator result = first;
    for( ; first != last; ++first )
    {
        if( *result < *first )
            result = first;
    }
    return result;
}



template< typename ForwardIterator, typename StrictWeakOrdering >
ForwardIterator max_element( ForwardIterator first, ForwardIterator last,
                             StrictWeakOrdering comp )
{
    if( first == last )
        return first;

    ForwardIterator result = first;
    for( ; first != last; ++first )
    {
        if( comp(*result, *first) )
            result = first;
    }
    return result;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//*****************************************************************************
//*****************************************************************************
//                                互换算法
//
//                          iter_swap  swap_ranges
//*****************************************************************************
//*****************************************************************************

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename ForwardIterator1, typename ForwardIterator2 >
inline void iter_swap( ForwardIterator1 lhs, ForwardIterator2 rhs )
{
    typename iterator_traits<ForwardIterator1>::value_type  temp = *lhs;
    *lhs = *rhs;
    *rhs = temp;
}

//-----------------------------------------------------------------------------

template< typename ForwardIterator1, typename ForwardIterator2 >
inline
ForwardIterator2 swap_ranges( ForwardIterator1 first1, ForwardIterator1 last1,
                              ForwardIterator2 first2 )
{
    typedef  typename iterator_traits<ForwardIterator1>::iterator_category  cate;
    return swap_r_aux( first1, last1, first2, cate() );
}

template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator2 swap_r_aux( ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2,
                             forward_iterator_tag )
{
    for( ; first1 != last1; ++first1,++first2 )
        iter_swap( first1, first2 );
    return first2;
}

template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator2 swap_r_aux( ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2,
                             random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator1>::difference_type
             diff_t1;

    for( diff_t1 n = last1 - first1; n > 0; --n,++first1,++first2 )
        iter_swap( first1, first2 );
    return first2;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//*****************************************************************************
//*****************************************************************************
//                       使用Function Object遍历区间的算法
//
//                   for_each  generate  generate_n  transform
//*****************************************************************************
//*****************************************************************************

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename InputIterator, typename Function >
Function for_each( InputIterator first, InputIterator last, Function fun )
{
    for( ; first != last; ++first )
        fun( *first );
    return fun;
}

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename Generator >
void generate( ForwardIterator first, ForwardIterator last, Generator gen )
{
    for( ; first != last; ++first )
        *first = gen();
}

//-----------------------------------------------------------------------------

template< typename OutputIterator, typename Integer, typename Generator >
OutputIterator generate_n( OutputIterator first, Integer n, Generator gen )
{
    typedef  typename primal_type<Integer>::primal_t  primal_int;

    for( primal_int i = 0; i < n; ++i, ++first )
        *first = gen();
    return first;
}

//-----------------------------------------------------------------------------

template< typename InputIterator, typename OutputIterator,
          typename UnaryOperation >
OutputIterator transform( InputIterator first, InputIterator last,
                          OutputIterator result, UnaryOperation op )
{
    for( ; first != last; ++first,++result )
        *result = op( *first );
    return result;
}



template< typename InputIterator1, typename InputIterator2,
          typename OutputIterator, typename BinaryOperation >
OutputIterator transform( InputIterator1 first1, InputIterator1 last1,
                          InputIterator2 first2, OutputIterator result,
                          BinaryOperation bin_op )
{
    for( ; first1 != last1; ++first1,++first2,++result )
        *result = bin_op( *first1, *first2 );
    return result;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//*****************************************************************************
//*****************************************************************************
//                               替换元素算法
//
//             replace  replace_if  replace_copy  replace_copy_if
//*****************************************************************************
//*****************************************************************************

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename T >
inline void replace( ForwardIterator first, ForwardIterator last,
                     const T& old_value, const T& new_value )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;
    replace_aux( first, last, old_value, new_value, cate() );
}

template< typename ForwardIterator, typename T >
void replace_aux( ForwardIterator first, ForwardIterator last,
                  const T& old_value, const T& new_value,
                  forward_iterator_tag )
{
    for( ; first != last; ++first )
    {
        if( *first == old_value )
            *first = new_value;
    }
}

template< typename ForwardIterator, typename T >
void replace_aux( ForwardIterator first, ForwardIterator last,
                  const T& old_value, const T& new_value,
                  random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;

    for( diff_t n = last - first; n > 0; --n,++first )
    {
        if( *first == old_value )
            *first = new_value;
    }
}

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename UnaryPredicate, typename T >
inline void replace_if( ForwardIterator first, ForwardIterator last,
                        UnaryPredicate pred, const T& new_value )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;
    replace_if_aux( first, last, pred, new_value, cate() );
}

template< typename ForwardIterator, typename UnaryPredicate, typename T >
void replace_if_aux( ForwardIterator first, ForwardIterator last,
                     UnaryPredicate pred, const T& new_value,
                     forward_iterator_tag )
{
    for( ; first != last; ++first )
    {
        if( pred(*first) )
            *first = new_value;
    }
}

template< typename ForwardIterator, typename UnaryPredicate, typename T >
void replace_if_aux( ForwardIterator first, ForwardIterator last,
                     UnaryPredicate pred, const T& new_value,
                     random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;

    for( diff_t n = last - first; n > 0; --n,++first )
    {
        if( pred(*first) )
            *first = new_value;
    }
}

//-----------------------------------------------------------------------------

template< typename InputIterator, typename OutputIterator, typename T >
inline OutputIterator replace_copy( InputIterator first, InputIterator last,
                                    OutputIterator result,
                                    const T& old_value, const T& new_value )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return  replace_cp_aux( first, last, result, old_value, new_value, cate() );
}

template< typename InputIterator, typename OutputIterator, typename T >
OutputIterator replace_cp_aux( InputIterator first, InputIterator last,
                               OutputIterator result,
                               const T& old_value, const T& new_value,
                               input_iterator_tag )
{
    for( ; first != last; ++first,++result )
    {
        if( *first == old_value )
            *result = new_value;
        else
            *result = *first;
    }
    return result;
}

template< typename InputIterator, typename OutputIterator, typename T >
OutputIterator replace_cp_aux( InputIterator first, InputIterator last,
                               OutputIterator result,
                               const T& old_value, const T& new_value,
                               random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator>::difference_type  diff_t;

    for( diff_t n = last - first; n > 0; --n,++first,++result )
    {
        if( *first == old_value )
            *result = new_value;
        else
            *result = *first;
    }
    return result;
}

//-----------------------------------------------------------------------------