mstl_list.hpp

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

        try
        {
            construct( &(ptr->data), x );
        }
        catch(...)
        {
       	    m_alloc.deallocate( ptr, 1 );
       	    throw;
        }
        return ptr;
    }

    void destroy_node( node_ptr ptr )
    {
        destroy( &(ptr->data) );
        m_alloc.deallocate( ptr, 1 );
    }

    void fill_init( size_type n, const_reference value )
    {
        init_header();
        try
        {
            insert( end(), n, value );
        }
        catch(...)
        {
            clear();
            dealloc_header();
            throw;
        }
    }

    void list_reverse( true_type );
    void list_reverse( false_type )
    {
        list_reverse_not_POD( m_header );
    }

    value_type& data( base_ptr x )
    {
        return static_cast<node_ptr>(x)->data;
    }

};  //end class

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

template< typename T, typename Allocator >
typename list<T, Allocator>::reference
list<T, Allocator>::at( size_type index )
{
    if( empty() )
        throw_out_of_range( "list::at()" );

    iterator result = begin();
    iterator finish = end();

    for( ; index > 0; --index,++result )
    {
        if( result == finish )
            throw_out_of_range( "list::at()" );
    }
    return *result;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
typename list<T, Allocator>::const_reference
list<T, Allocator>::at( size_type index ) const
{
    if( empty() )
        throw_out_of_range( "list::at()" );

    const_iterator result = begin();
    const_iterator finish = end();

    for( ; index > 0; --index,++result )
    {
        if( result == finish )
            throw_out_of_range( "list::at()" );
    }
    return *result;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
typename list<T, Allocator>::iterator
list<T, Allocator>::erase( iterator position )
{
    if( position == end() )
        return position;

    base_ptr next_node = list_erase_node( position.node );
    destroy_node( static_cast<node_ptr>(position.node) );
    return next_node;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
typename list<T, Allocator>::iterator
list<T, Allocator>::erase( iterator first, iterator last )
{
    if( first != last && first != end() )
    {
        iterator temp_last = last;
        --temp_last;

        first.node->prev->next = last.node;
        last.node->prev = first.node->prev;

        iterator temp;
        while( temp_last != first )
        {
            temp = temp_last;
            --temp_last;
            destroy_node( static_cast<node_ptr>(temp.node) );
        }
        destroy_node( static_cast<node_ptr>(first.node) );
    }
    return last;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
typename list<T, Allocator>::iterator
list<T, Allocator>::insert( iterator position, const_reference value )
{
    base_ptr new_node = create_node( value );
    return list_insert_link( position.node, new_node );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::insert( iterator position, size_type count,
                                 const_reference value )
{
    for( ; count > 0; --count )
        insert( position, value );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename InputIterator >
void list<T, Allocator>::insert( iterator position,
                                 InputIterator first, InputIterator last )
{
    for( ; first != last; ++first )
        insert( position, *first );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::resize( size_type new_size, const_reference value )
{
    iterator itr1 = begin();
    iterator itr2 = end();

    while( (itr1 != itr2) && (new_size > 0) )
    {
        ++itr1;
        --new_size;
    }

    if( new_size == 0 )
        erase( itr1, itr2 );
    else
        insert( itr2, new_size, value );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::assign( size_type new_size, const_reference value )
{
    if( new_size < 1 )
    {
        clear();
        return;
    }

    iterator itr1 = begin();
    iterator itr2 = end();

    for( ; (itr1 != itr2) && (new_size > 0); ++itr1,--new_size )
        *itr1 = value;

    if( new_size == 0 )
        erase( itr1, itr2 );
    else
        insert( itr1, new_size, value );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename InputIterator >
void list<T, Allocator>::assign( InputIterator first, InputIterator last )
{
    if( first == last )
    {
        clear();
        return;
    }

    iterator itr1 = begin();
    iterator itr2 = end();

    for( ; (itr1 != itr2) && (first != last); ++first,++itr1 )
        *itr1 = *first;

    if( itr1 != itr2 )
        erase( itr1, itr2 );
    else
        insert( itr1, first, last );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::list_reverse( true_type )
{
    if( empty() || m_header->next->next == m_header )
        return;

    iterator first = begin();
    iterator last = --end();
    iterator last_next;

    for( ; (first != last) && (first != last_next); ++first,--last )
    {
        last_next = last;
        data_swap( data(first.node), data(last.node) );
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::remove( const_reference value )
{
    iterator first = begin();
    iterator last = end();
    iterator temp;

    while( first != last )
    {
        temp = first;
        ++first;
        if( *temp == value )
            erase( temp );
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename Predicate >
void list<T, Allocator>::remove_if( Predicate pred )
{
    iterator first = begin();
    iterator last = end();
    iterator temp;

    while( first != last )
    {
        temp = first;
        ++first;
        if( pred(*temp) )
            erase( temp );
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::unique()
{
    if( empty() || m_header->next->next == m_header )
        return;

    iterator first = begin();
    iterator last = end();
    iterator next = first;

    while( (++next) != last )
    {
        if( *next == *first )
            erase( next );
        else
            first = next;
        next = first;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename BinaryPredicate >
void list<T, Allocator>::unique( BinaryPredicate bin_pred )
{
    if( empty() || m_header->next->next == m_header )
        return;

    iterator first = begin();
    iterator last = end();
    iterator next = first;

    while( (++next) != last )
    {
        if( bin_pred(*first, *next) )
            erase( next );
        else
            first = next;
        next = first;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::merge( self& rhs )
{
    if( rhs.empty() )
        return;

    iterator first1 = begin(),     last1 = end();
    iterator first2 = rhs.begin(), last2 = rhs.end();
    iterator temp;

    while( (first1 != last1) && (first2 != last2) )
    {
        if( *first2 < *first1 )
        {
            temp = first2;
            ++first2;
            splice( first1, rhs, temp, first2 );
        }
        else
            ++first1;
    }

    if( first2 != last2 )
        splice( last1, rhs, first2, last2 );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename StrictWeakOrdering >
void list<T, Allocator>::merge( self& rhs, StrictWeakOrdering comp )
{
    if( rhs.empty() )
        return;

    iterator first1 = begin(),     last1 = end();
    iterator first2 = rhs.begin(), last2 = rhs.end();
    iterator temp;

    while( (first1 != last1) && (first2 != last2) )
    {
        if( comp(*first2, *first1) )
        {
            temp = first2;
            ++first2;
            splice( first1, rhs, temp, first2 );
        }
        else
            ++first1;
    }

    if( first2 != last2 )
        splice( last1, rhs, first2, last2 );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void list<T, Allocator>::sort()
{
    if( empty() || m_header->next->next == m_header )
        return;

    self result[ list_sort_array ];
    self carry;
    size_type fill = 0;

    while( !empty() )
    {
        carry.splice( carry.begin(), *this, begin() );
        size_type i = 0;
        while( (i < fill) && (!result[i].empty()) )
        {
            result[i].merge( carry );
            carry.swap( result[i] );
            ++i;
        }
        carry.swap( result[i] );
        if( i == fill )
            ++fill;
    }

    for( size_type j = 1; j < fill; ++j )
        result[j].merge( result[j - 1] );

    swap( result[fill - 1] );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename StrictWeakOrdering >
void list<T, Allocator>::sort( StrictWeakOrdering comp )
{
    if( empty() || m_header->next->next == m_header )
        return;

    self result[ list_sort_array ];
    self carry;
    size_type fill = 0;

    while( !empty() )
    {
        carry.splice( carry.begin(), *this, begin() );
        size_type i = 0;
        while( (i < fill) && (!result[i].empty()) )
        {
            result[i].merge( carry, comp );
            carry.swap( result[i] );
            ++i;
        }
        carry.swap( result[i] );
        if( i == fill )
            ++fill;
    }

    for( size_type j = 1; j < fill; ++j )
        result[j].merge( result[j - 1], comp );

    swap( result[fill - 1] ); 
}

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

template< typename T, typename Allocator >
inline void swap( list<T, Allocator>& lhs, list<T, Allocator>& rhs )
{
    lhs.swap( rhs );
}

template< typename T, typename Allocator >
inline bool operator==( const list<T, Allocator>& lhs,
                        const list<T, Allocator>& rhs )
{
    if( lhs.end() == rhs.end() )
        return true;

    return matching( lhs.begin(), lhs.end(), rhs.begin(), rhs.end() );
}

template< typename T, typename Allocator >
inline bool operator!=( const list<T, Allocator>& lhs,
                        const list<T, Allocator>& rhs )
{
    return !( lhs == rhs );
}

template< typename T, typename Allocator >
inline bool operator<( const list<T, Allocator>& lhs,
                       const list<T, Allocator>& rhs )
{
    if( lhs.end() == rhs.end() )
        return false;

    return lexicographical_compare( lhs.begin(), lhs.end(),
                                    rhs.begin(), rhs.end() );
}

template< typename T, typename Allocator >
inline bool operator>( const list<T, Allocator>& lhs,
                       const list<T, Allocator>& rhs )
{
    return ( rhs < lhs );
}

template< typename T, typename Allocator >
inline bool operator<=( const list<T, Allocator>& lhs,
                        const list<T, Allocator>& rhs )
{
    return !( rhs < lhs );
}

template< typename T, typename Allocator >
inline bool operator>=( const list<T, Allocator>& lhs,
                        const list<T, Allocator>& rhs )
{
    return !( lhs < rhs );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------