mstl_algorithm.hpp

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

template< typename InputIterator, typename OutputIterator,
          typename UnaryPredicate, typename T >
inline
OutputIterator replace_copy_if( InputIterator first, InputIterator last,
                                OutputIterator result,
                                UnaryPredicate pred, const T& new_value )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return  replace_cp_if_aux( first, last, result, pred, new_value, cate() );
}

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

template< typename InputIterator, typename OutputIterator,
          typename UnaryPredicate, typename T >
OutputIterator replace_cp_if_aux( InputIterator first, InputIterator last,
                                  OutputIterator result,
                                  UnaryPredicate pred, 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( pred(*first) )
            *result = new_value;
        else
            *result = *first;
    }
    return result;
}

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

//*****************************************************************************
//*****************************************************************************
//                               移除元素算法
//
//     remove  remove_if  remove_copy  remove_copy_if  unique  unique_copy
//*****************************************************************************
//*****************************************************************************

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

template< typename InputIterator, typename OutputIterator, typename T >
OutputIterator remove_copy( InputIterator first, InputIterator last,
                            OutputIterator result, const T& value )
{
    for( ; first != last; ++first )
    {
        if( *first != value )
        {
            *result = *first;
            ++result;
        }
    }
    return result;
}

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

template< typename InputIterator, typename OutputIterator, typename Predicate >
OutputIterator remove_copy_if( InputIterator first, InputIterator last,
                               OutputIterator result, Predicate pred )
{
    for( ; first != last; ++first )
    {
        if( !pred(*first) )
        {
            *result = *first;
            ++result;
        }
    }
    return result;
}

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

template< typename ForwardIterator, typename T >
ForwardIterator remove( ForwardIterator first, ForwardIterator last,
                        const T& value )
{
    while( first != last && *first != value )  //找到第一个出现value的位置
        ++first;

    ForwardIterator next = first;
    if( first == last )
        return last;
    else
        return remove_copy( ++next, last, first, value );
}

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

template< typename ForwardIterator, typename Predicate >
ForwardIterator remove_if( ForwardIterator first, ForwardIterator last,
                           Predicate pred )
{
    while( first != last && !pred(*first) )
        ++first;

    ForwardIterator next = first;
    if( first == last )
        return last;
    else
        return remove_copy_if( ++next, last, first, pred );
}

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

template< typename InputIterator, typename OutputIterator >
inline OutputIterator unique_copy( InputIterator first, InputIterator last,
                                   OutputIterator result )
{
    typedef  typename iterator_traits<OutputIterator>::iterator_category  cate;

    if( first == last )
        return result;

    return unique_copy_aux( first, last, result, cate() );
}

template< typename InputIterator, typename OutputIterator >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
                                OutputIterator result, output_iterator_tag )
{
    typedef  typename iterator_traits<OutputIterator>::value_type  value_t;

    value_t value = *first;
    *result = value;
    ++first;

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

    return ++result;
}

template< typename InputIterator, typename OutputIterator >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
                                OutputIterator result, forward_iterator_tag )
{
    *result = *first;
    ++first;

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

    return ++result;
}



template< typename InputIterator, typename OutputIterator,
          typename BinaryPredicate >
inline OutputIterator unique_copy( InputIterator first, InputIterator last,
                                   OutputIterator result,
                                   BinaryPredicate bin_pred )
{
    typedef  typename iterator_traits<OutputIterator>::iterator_category  cate;

    if( first == last )
        return result;

    return unique_copy_aux( first, last, result, bin_pred, cate() );
}

template< typename InputIterator, typename OutputIterator,
          typename BinaryPredicate >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
                                OutputIterator result,
                                BinaryPredicate bin_pred,
                                output_iterator_tag )
{
    typedef  typename iterator_traits<OutputIterator>::value_type  value_t;

    value_t value = *first;
    *result = value;
    ++first;

    for( ; first != last; ++first )
    {
        if( bin_pred(value, *first) )
        {
            value = *first;
            *(++result) = value;
        }
    }

    return ++result;
}

template< typename InputIterator, typename OutputIterator,
          typename BinaryPredicate >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
                                OutputIterator result,
                                BinaryPredicate bin_pred,
                                forward_iterator_tag )
{
    *result = *first;
    ++first;

    for( ; first != last; ++first )
    {
        if( bin_pred(*result, *first) )
            *(++result) = *first;
    }

    return ++result;
}

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

template< typename ForwardIterator >
ForwardIterator unique( ForwardIterator first, ForwardIterator last )
{
    ForwardIterator next = first;
    ++next;
    for( ; next != last; ++next )
    {
        if( *first == *next )
            return first;
        else
            first = next;
    }

    if( first == last )
        return last;
    else
        return unique_copy( first, last, first );
}



template< typename ForwardIterator, typename BinaryPredicate >
ForwardIterator unique( ForwardIterator first, ForwardIterator last,
                        BinaryPredicate bin_pred )
{
    ForwardIterator next = first;
    ++next;
    for( ; next != last; ++next )
    {
        if( bin_pred(*first, *next) )
            return first;
        else
            first = next;
    }

    if( first == last )
        return last;
    else
        return unique_copy( first, last, first, bin_pred );
}

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

//*****************************************************************************
//*****************************************************************************
//                               排列算法
//
//              reverse  reverse_copy  rotate  rotate_copy
//                  prev_permutation  next_permutation
//*****************************************************************************
//*****************************************************************************

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

template< typename BidirectionalIterator >
inline void reverse( BidirectionalIterator first, BidirectionalIterator last )
{
    typedef  typename iterator_traits<BidirectionalIterator>::iterator_category
             cate;

    reverse_aux( first, last, cate() );
}

template< typename BidirectionalIterator >
void reverse_aux( BidirectionalIterator first, BidirectionalIterator last,
                  bidirectional_iterator_tag )
{
    typedef  typename iterator_traits<BidirectionalIterator>::value_type
             value_t;

    value_t temp;
    while( 1 )
    {
        if( first == last || first == --last )
            return;
        temp = *first;
        *first = *last;
        *last = temp;
        ++first;
    }
}

template< typename BidirectionalIterator >
void reverse_aux( BidirectionalIterator first, BidirectionalIterator last,
                  random_access_iterator_tag )
{
    typedef  typename iterator_traits<BidirectionalIterator>::value_type
             value_t;

    value_t temp;
    while( first < last )
    {
        --last;
        temp = *first;
        *first = *last;
        *last = temp;
        ++first;
    }
}

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

template< typename BidirectionalIterator, typename OutputIterator >
inline OutputIterator reverse_copy( BidirectionalIterator first,
                                    BidirectionalIterator last,
                                    OutputIterator result )
{
    typedef  typename iterator_traits<BidirectionalIterator>::iterator_category
             cate;

    if( first == last )
        return result;
    else
        return reverse_copy_aux( first, last, result, cate() );
}

template< typename BidirectionalIterator, typename OutputIterator >
OutputIterator reverse_copy_aux( BidirectionalIterator first,
                                 BidirectionalIterator last,
                                 OutputIterator result,
                                 bidirectional_iterator_tag )
{
    while( first != last )
    {
        --last;
        *result = *last;
        ++result;
    }
    return result;
}

template< typename BidirectionalIterator, typename OutputIterator >
OutputIterator reverse_copy_aux( BidirectionalIterator first,
                                 BidirectionalIterator last,
                                 OutputIterator result,
                                 random_access_iterator_tag )
{
    typedef  typename iterator_traits<BidirectionalIterator>::difference_type
             diff_t;

    for( diff_t n = last - first; n > 0; --n )
    {
        --last;
        *result = *last;
        ++result;
    }
    return result;
}

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

template< typename RandomAccessIterator, typename Integer >
void __rotate_cycle( RandomAccessIterator first, RandomAccessIterator last,
                     RandomAccessIterator initial, Integer shift )
{
    typedef  typename iterator_traits<RandomAccessIterator>::value_type
             value_t;

    value_t value = *initial;
    RandomAccessIterator ptr1 = initial;
    RandomAccessIterator ptr2 = ptr1 + shift;
    while( ptr2 != initial )