mstl_algorithm.hpp

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

    {
        *ptr1 = *ptr2;
        ptr1 = ptr2;
        if( last - ptr2 > shift )
            ptr2 += shift;
        else
            ptr2 = first + ( shift - (last - ptr2) );
    }
    *ptr1 = value;
}

template< typename ForwardIterator >
inline void rotate( ForwardIterator first, ForwardIterator middle,
                    ForwardIterator last )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;

    if( first == middle || middle == last )
        return;
    rotate_aux( first, middle, last, cate() );
}

template< typename ForwardIterator >
void rotate_aux( ForwardIterator first, ForwardIterator middle,
                 ForwardIterator last, forward_iterator_tag )
{
    ForwardIterator iter = middle;
    while( 1 )
    {
        iter_swap( first, iter );
        ++first;
        ++iter;
        if( first == middle )  //前半区间遍历完毕
        {
            if( iter == last )  //区间遍历完成
                return;
            middle = iter;
        }
        else if( iter == last )  //后半区间遍历完毕
            iter = middle;
    }
}

template< typename ForwardIterator >
void rotate_aux( ForwardIterator first, ForwardIterator middle,
                 ForwardIterator last, bidirectional_iterator_tag )
{
    reverse( first, middle );
    reverse( middle, last );
    reverse( first, last );
}

template< typename ForwardIterator >
void rotate_aux( ForwardIterator first, ForwardIterator middle,
                 ForwardIterator last, random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;
    typedef  typename iterator_traits<ForwardIterator>::value_type  value_t;

    diff_t n = gcd( last - first, middle - first );

    while( n-- )
        __rotate_cycle( first, last, first + n, middle - first );
}

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

template< typename ForwardIterator, typename OutputIterator >
inline
OutputIterator rotate_copy( ForwardIterator first, ForwardIterator middle,
                            ForwardIterator last, OutputIterator result )
{
    result = copy( middle, last, result );
    return copy( first, middle, result );
}

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

template< typename BidirectionalIterator >
bool prev_permutation( BidirectionalIterator first,
                       BidirectionalIterator last )
{
    if( first == last )
        return false;
    BidirectionalIterator iter_before = first;
    ++iter_before;
    if( iter_before == last )
        return false;
    iter_before = last;
    --iter_before;  //指向倒数第一个元素

    while( 1 )
    {
        BidirectionalIterator iter_after = iter_before;
        --iter_before;  //指向前一个元素
        if( *iter_after < *iter_before )  //后一个元素小于前一个元素
        {
            BidirectionalIterator temp = last;
            while( !(*--temp < *iter_before) ) ;  //寻找比*iter_before小的值位置
            iter_swap( iter_before, temp );
            reverse( iter_after, last );
            return true;
        }
        if( iter_before == first )
        {
            reverse( first, last );
            return false;
        }
    }
}



template< typename BidirectionalIterator, typename StrictWeakOrdering >
bool prev_permutation( BidirectionalIterator first,
                       BidirectionalIterator last,
                       StrictWeakOrdering comp )
{
    if( first == last )
        return false;
    BidirectionalIterator iter_before = first;
    ++iter_before;
    if( iter_before == last )
        return false;
    iter_before = last;
    --iter_before;

    while( 1 )
    {
        BidirectionalIterator iter_after = iter_before;
        --iter_before;
        if( comp(*iter_after, *iter_before) )
        {
            BidirectionalIterator temp = last;
            while( !comp(*--temp, *iter_before) ) ;
            iter_swap( iter_before, temp );
            reverse( iter_after, last );
            return true;
        }
        if( iter_before == first )
        {
            reverse( first, last );
            return false;
        }
    }
}

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

template< typename BidirectionalIterator >
bool next_permutation( BidirectionalIterator first,
                       BidirectionalIterator last )
{
    if( first == last )
        return false;
    BidirectionalIterator iter_before = first;
    ++iter_before;
    if( iter_before == last )
        return false;
    iter_before = last;
    --iter_before;  //指向倒数第一个元素

    while( 1 )
    {
        BidirectionalIterator iter_after = iter_before;
        --iter_before;  //指向前一个元素
        if( *iter_before < *iter_after )  //后一个元素大于前一个元素
        {
            BidirectionalIterator temp = last;
            while( !(*iter_before < *--temp) ) ;  //寻找比*iter_before大的值位置
            iter_swap( iter_before, temp );
            reverse( iter_after, last );
            return true;
        }
        if( iter_before == first )
        {
            reverse( first, last );
            return false;
        }
    }
}



template< typename BidirectionalIterator, typename StrictWeakOrdering >
bool next_permutation( BidirectionalIterator first,
                       BidirectionalIterator last,
                       StrictWeakOrdering comp )
{
    if( first == last )
        return false;
    BidirectionalIterator iter_before = first;
    ++iter_before;
    if( iter_before == last )
        return false;
    iter_before = last;
    --iter_before;

    while( 1 )
    {
        BidirectionalIterator iter_after = iter_before;
        --iter_before;
        if( comp(*iter_before, *iter_after) )
        {
            BidirectionalIterator temp = last;
            while( !comp(*iter_before, *--temp) ) ;
            iter_swap( iter_before, temp );
            reverse( iter_after, last );
            return true;
        }
        if( iter_before == first )
        {
            reverse( first, last );
            return false;
        }
    }
}

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

//*****************************************************************************
//*****************************************************************************
//                                  分割算法
//
//                          partition  stable_partition
//*****************************************************************************
//*****************************************************************************

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

template< typename BidirectionalIterator, typename Predicate >
BidirectionalIterator partition( BidirectionalIterator first,
                                 BidirectionalIterator last,
                                 Predicate pred )
{
    while( 1 )
    {
        while( 1 )  //从前面查找不符合条件的数据
        {
            if( first == last )
                return first;
            else if( pred(*first) )
                ++first;
            else
                break;
        }

        --last;

        while( 1 )  //从后面查找符合条件的数据
        {
            if( first == last )
                return first;
            else if( !pred(*last) )
                --last;
            else
                break;
        }

        iter_swap( first, last );  //前后数据交换
        ++first;
    }
}

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

template< typename ForwardIterator, typename Predicate >
inline ForwardIterator stable_partition( ForwardIterator first,
                                         ForwardIterator last,
                                         Predicate pred )
{
    typedef  typename iterator_traits<ForwardIterator>::value_type  value_t;

    if( first == last )
        return first;

    temporary_buffer<ForwardIterator, value_t> buf( first, last );
    if( buf.size() > 0 )  //临时缓冲区申请成功
        return stable_partition_adaptive( first, last, pred,
                                          buf.requested_size(), buf.begin(),
                                          buf.size() );
    else
        return inplace_stable_partition( first, last, pred,
                                         buf.requested_size() );
}

template< typename ForwardIterator, typename Predicate, typename Integer >
ForwardIterator inplace_stable_partition( ForwardIterator first,
                                          ForwardIterator last,
                                          Predicate pred,
                                          Integer len )
{
    if( len == 1 )
        return ( pred(*first) ? last : first );

    ForwardIterator middle = first;
    advance( middle, len / 2 );

    ForwardIterator first_cut = inplace_stable_partition( first, middle,
                                                          pred, len / 2 );
    ForwardIterator second_cut = inplace_stable_partition( middle, last,
                                                           pred, len / 2 );

    rotate( first_cut, middle, second_cut );
    len = distance( middle, second_cut );
    advance( first_cut, len );
    return first_cut;
}

template< typename ForwardIterator, typename Predicate, typename Integer,
          typename Pointer >
ForwardIterator stable_partition_adaptive( ForwardIterator first,
                                           ForwardIterator last,
                                           Predicate pred,
                                           Integer len,
                                           Pointer buffer,
                                           Integer buffer_size )
{
    if( len <= buffer_size )  //缓存空间可以容纳所有的数据
    {
        ForwardIterator result = first;
        Pointer temp = buffer;
        for( ; first != last; ++first )
        {
            if( pred(*first) )  //符合条件的数据
            {
                *result = *first;
                ++result;
            }
            else  //不符合条件的数据放进缓存内
            {
                *temp = *first;
                ++temp;
            }
        }
        copy( buffer, temp, result );
        return result;
    }
    else  //缓存空间无法容纳所有的数据
    {
        ForwardIterator middle = first;
        advance( middle, len / 2 );
        ForwardIterator first_cut =
                        stable_partition_adaptive( first, middle, pred, len / 2,
                                                   buffer, buffer_size );
        ForwardIterator second_cut =
                        stable_partition_adaptive( middle, last, pred, len / 2,
                                                   buffer, buffer_size );

        //将后半部分满足条件的数据和前半部分不满足条件的数据调换
        rotate( first_cut, middle, second_cut );
        len = distance( middle, second_cut );
        advance( first_cut, len );
        return first_cut;
    }
}

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

//*****************************************************************************
//*****************************************************************************
//                              随机重排与抽样算法
//
//                   random_shuffle  random_sample  random_sample_n
//*****************************************************************************
//*****************************************************************************

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

template< typename RandomAccessIterator >
void random_shuffle( RandomAccessIterator first,
                     RandomAccessIterator last )
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type
             diff_t;

    if( first != last )
    {
        diff_t len = last - first;
        for( diff_t i = 1; i < len; ++i )
            iter_swap( first + i, first + (std::rand() % (i + 1)) );
    }
}



template< typename RandomAccessIterator, typename RandomNumberGenerator >
void random_shuffle( RandomAccessIterator first,
                     RandomAccessIterator last,
                     RandomNumberGenerator& rand )
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type
             diff_t;

    if( first != last )
    {