mstl_algorithm.hpp

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

    	    {
    	        *itr1 = first;
    	        ++itr1;
    	    }
    	    else
    	        result.push_back( first );
    	}
    }
}

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

template< typename InputIterator, typename OutputIterator,
          typename UnaryPredicate >
OutputIterator find_all_if( InputIterator first,
                            InputIterator last,
                            OutputIterator result_first,
                            OutputIterator result_last,
                            UnaryPredicate pred )
{
    for( ; first != last && result_first != result_last; ++first )
    {
    	if( pred(*first) )
    	{
    	    *result_first = first;
    	    ++result_first;
    	}
    }

    return result_first;
}



template< typename InputIterator, typename Container, typename UnaryPredicate >
void find_all_if( InputIterator first, InputIterator last, Container& result,
                  UnaryPredicate pred )
{
    typename Container::iterator itr1 = result.begin();
    typename Container::iterator itr2 = result.end();

    for( ; first != last; ++first )
    {
    	if( pred(*first) )
    	{
    	    if( itr1 != itr2 )
    	    {
    	        *itr1 = first;
    	        ++itr1;
    	    }
    	    else
    	        result.push_back( first );
    	}
    }
}

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

//*****************************************************************************
//*****************************************************************************
//                             子序列匹配算法
//
//                        search  find_end  search_n
//*****************************************************************************
//*****************************************************************************

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

//[first2, last2)是否包含于[first1, last1)
template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2 )
{
    typedef  typename iterator_traits<ForwardIterator1>::difference_type
             diff_t1;
    typedef  typename iterator_traits<ForwardIterator2>::difference_type
             diff_t2;

    diff_t1 len1 = distance( first1, last1 );
    diff_t2 len2 = distance( first2, last2 );

    if( len1 < len2 )
        return last1;

    ForwardIterator1 current1 = first1;
    ForwardIterator2 current2 = first2;

    while( current2 != last2 )
    {
        if( *current1 == *current2 )
        {
            ++current1;
            ++current2;
        }
        else  //遇到不相等时的处理
        {
            if( len1 == len2 )  //此时first1再前进则len1<len2，匹配失败
                return last1;
            else
            {
                current1 = ++first1;  //first1前进一个位置，重新开始匹配
                current2 = first2;
                --len1;
            }
        }
    }

    return first1;
}



template< typename ForwardIterator1, typename ForwardIterator2,
          typename BinaryPredicate >
ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2,
                         BinaryPredicate bin_pred )
{
    typedef  typename iterator_traits<ForwardIterator1>::difference_type
             diff_t1;
    typedef  typename iterator_traits<ForwardIterator2>::difference_type
             diff_t2;

    diff_t1 len1 = distance( first1, last1 );
    diff_t2 len2 = distance( first2, last2 );

    if( len1 < len2 )
        return last1;

    ForwardIterator1 current1 = first1;
    ForwardIterator2 current2 = first2;

    while( current2 != last2 )
    {
        if( bin_pred(*current1, *current2) )
        {
            ++current1;
            ++current2;
        }
        else
        {
            if( len1 == len2 )
                return last1;
            else
            {
                current1 = ++first1;
                current2 = first2;
                --len1;
            }
        }
    }

    return first1;
}

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

//在 [first1, last1) 中查找 [first2, last2)
template< typename ForwardIterator1, typename ForwardIterator2 >
inline ForwardIterator1
find_end( ForwardIterator1 first1, ForwardIterator1 last1,
          ForwardIterator2 first2, ForwardIterator2 last2 )
{
    typedef  typename iterator_traits<ForwardIterator1>::iterator_category
             cate1;
    typedef  typename iterator_traits<ForwardIterator2>::iterator_category
             cate2;

    if( first1 == last1 || first2 == last2 )
        return last1;
    else
        return find_end_aux( first1, last1, first2, last2, cate1(), cate2() );
}

template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2,
              forward_iterator_tag, forward_iterator_tag )
{
    ForwardIterator1 result = last1;

    while( 1 )
    {
        ForwardIterator1 new_result = search( first1, last1, first2, last2 );
        if( new_result == last1 )
            return result;
        else
        {
            result = new_result;
            first1 = new_result;
            ++first1;
        }
    }  //end while
}

template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2,
              bidirectional_iterator_tag, bidirectional_iterator_tag )
{
    typedef  Reverse_Iterator<ForwardIterator1>  r_iter1;
    typedef  Reverse_Iterator<ForwardIterator2>  r_iter2;

    r_iter1 rlast1( first1 );
    r_iter2 rlast2( first2 );

    //反向匹配的第一个即为正向的最后一个
    r_iter1 rresult = search( r_iter1(last1), rlast1, r_iter2(last2), rlast2 );

    if( rresult = rlast1 )
        return last1;
    else
    {
        ForwardIterator1 result = rresult.base();
        advance( result, -distance(first2, last2) );  //前进到匹配子序列的开头
        return result;
    }
}



template< typename ForwardIterator1, typename ForwardIterator2,
          typename BinaryPredicate >
inline ForwardIterator1
find_end( ForwardIterator1 first1, ForwardIterator1 last1,
          ForwardIterator2 first2, ForwardIterator2 last2,
          BinaryPredicate bin_pred )
{
    typedef  typename iterator_traits<ForwardIterator1>::iterator_category
             cate1;
    typedef  typename iterator_traits<ForwardIterator2>::iterator_category
             cate2;

    if( first1 == last1 || first2 == last2 )
        return last1;
    else
        return find_end_aux( first1, last1, first2, last2, bin_pred,
                             cate1(), cate2() );
}

template< typename ForwardIterator1, typename ForwardIterator2,
          typename BinaryPredicate >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2,
              BinaryPredicate bin_pred,
              forward_iterator_tag, forward_iterator_tag )
{
    ForwardIterator1 result = last1;

    while( 1 )
    {
        ForwardIterator1 new_result = search( first1, last1, first2, last2,
                                              bin_pred );
        if( new_result == last1 )
            return result;
        else
        {
            result = new_result;
            first1 = new_result;
            ++first1;
        }
    }
}

template< typename ForwardIterator1, typename ForwardIterator2,
          typename BinaryPredicate >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2,
              BinaryPredicate bin_pred,
              bidirectional_iterator_tag, bidirectional_iterator_tag )
{
    typedef  Reverse_Iterator<ForwardIterator1>  r_iter1;
    typedef  Reverse_Iterator<ForwardIterator2>  r_iter2;

    r_iter1 rlast1( first1 );
    r_iter2 rlast2( first2 );

    r_iter1 rresult = search( r_iter1(last1), rlast1, r_iter2(last2), rlast2,
                              bin_pred );

    if( rresult = rlast1 )
        return last1;
    else
    {
        ForwardIterator1 result = rresult.base();
        advance( result, -distance(first2, last2) );
        return result;
    }
}

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

template< typename ForwardIterator, typename Integer, typename T >
ForwardIterator search_n( ForwardIterator first, ForwardIterator last,
                          Integer count, const T& value )
{
    if( count < 1 )
        return first;

    first = find( first, last, value );  //找到第一个要查找的值

    while( first != last )
    {
        Integer n = count - 1;
        ForwardIterator itr = first;
        ++itr;

        while( itr != last && n != 0 && *itr == value )  //向后进行迭代并比较
        {
            ++itr;
            --n;
        }

        if( n == 0 )
            return first;
        else
            first = find( itr, last, value );
    }

    return last;
}



template< typename ForwardIterator, typename Integer, typename T,
          typename BinaryPredicate >
ForwardIterator search_n( ForwardIterator first, ForwardIterator last,
                          Integer count, const T& value,
                          BinaryPredicate bin_pred )
{
    if( count < 1 )
        return first;

    while( first != last )
    {
        if( binary_pred(*first, value) )
            break;
        ++first;
    }

    while( first != last )
    {
        Integer n = count - 1;
        ForwardIterator itr = first;
        ++itr;

        while( itr != last && n != 0 && bin_pred(*itr, value) )
        {
            ++itr;
            --n;
        }

        if( n == 0 )
            return first;
        else
        {
            while( itr != last )
            {
                if( binary_pred(*itr, value) )
                    break;
                ++itr;
            }
            first = itr;
        }
    }

    return last;
}

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

//*****************************************************************************
//*****************************************************************************
//                             计算元素个数算法
//
//                             count  count_if
//*****************************************************************************
//*****************************************************************************

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

template< typename InputIterator, typename T >
inline typename iterator_traits<InputIterator>::difference_type
count( InputIterator first, InputIterator last, const T& value )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return count_aux( first, last, value, cate() );
}

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