mstl_slist.hpp

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

    void init_header()  {  m_header.next = NULL_POINTER;  }

    iterator header()  {  return &m_header;  }

    node_ptr create_node( const T& x )
    {
        node_ptr ptr = m_alloc.allocate( 1 );
        try
        {
            construct( &(ptr->data), x );
        }
        catch(...)
        {
       	    m_alloc.deallocate( ptr, 1 );
       	    throw;
        }
        ptr->next = NULL_POINTER;
        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_after( header(), n, value );
        }
        catch(...)
        {
            clear();
            throw;
        }
    }

};  //end class

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

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

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

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

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

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

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

template< typename T, typename Allocator >
void slist<T, Allocator>::insert_after( iterator position,
                                        size_type count,
                                        const_reference value )
{
    base_ptr pos = position.node;
    for( ; count > 0; --count )
        pos = slist_make_link( pos, create_node(value) );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename InputIterator >
void slist<T, Allocator>::insert_after( iterator position,
                                        InputIterator first,
                                        InputIterator last )
{
    base_ptr pos = position.node;
    while( first != last )
    {
        pos = slist_make_link( pos, create_node(*first) );
        ++first;
    }
}
//-----------------------------------------------------------------------------

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

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

template< typename T, typename Allocator >
typename slist<T, Allocator>::iterator
slist<T, Allocator>::erase_after( iterator before_first, iterator last )
{
    base_ptr curr = before_first.node->next;
    base_ptr temp;

    while( curr != last.node )
    {
        temp = curr;
        curr = curr->next;
        destroy_node( static_cast<node_ptr>(temp) );
    }

    before_first.node->next = last.node;
    return last;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void slist<T, Allocator>::resize( size_type new_size, const_reference value )
{
    base_ptr curr = &m_header;

    while( curr->next && new_size > 0 )
    {
        --new_size;
        curr = curr->next;
    }

    if( new_size == 0 )
        erase_after( curr, end() );
    else
        insert_after( curr, new_size, value );
}
//-----------------------------------------------------------------------------

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

    base_ptr curr = &m_header;

    while( curr->next && new_size > 0 )
    {
        curr = curr->next;
        static_cast<node_ptr>(curr)->data = value;
        --new_size;
    }

    if( curr->next )
        erase_after( iterator(curr), end() );
    else
        insert_after( iterator(curr), new_size, value );
}
//-----------------------------------------------------------------------------

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

    base_ptr curr = &m_header;

    while( curr->next && first != last )
    {
        curr = curr->next;
        static_cast<node_ptr>(curr)->data = *first;
        ++first;
    }

    if( curr->next )
        erase_after( iterator(curr), end() );
    else
        insert_after( iterator(curr), first, last );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void slist<T, Allocator>::remove( const_reference value )
{
    iterator first = header();
    iterator temp;

    while( first.node->next )
    {
        temp = first;
        ++temp;
        if( *temp == value )
            erase_after( first );
        else
            ++first;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename Predicate >
void slist<T, Allocator>::remove_if( Predicate pred )
{
    iterator first = header();
    iterator temp;

    while( first.node->next )
    {
        temp = first;
        ++temp;
        if( pred(*temp) )
            erase_after( first );
        else
            ++first;
    }
}
//-----------------------------------------------------------------------------

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

    iterator first = begin();
    iterator temp;

    while( first.node->next )
    {
        temp = first;
        ++temp;
        if( *temp == *first )
            erase_after( first );
        else
            ++first;
    }
}
//-----------------------------------------------------------------------------

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

    iterator first = begin();
    iterator temp;

    while( first.node->next )
    {
        temp = first;
        ++temp;
        if( bin_pred(*temp, *first) )
            erase_after( first );
        else
            ++first;
    }
}
//-----------------------------------------------------------------------------

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

    iterator curr = header();
    iterator next;

    while( curr.node->next && rhs.m_header.next )
    {
        next = curr;
        ++next;
        if( *(rhs.begin()) < *next )
            splice_after( curr, rhs.header(), rhs.begin() );
        ++curr;
    }

    if( rhs.m_header.next )
    {
        curr.node->next = rhs.m_header.next;
        rhs.m_header.next = NULL_POINTER;
    }
}
//-----------------------------------------------------------------------------

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

    iterator curr = header();
    iterator next;

    while( curr.node->next && rhs.m_header.next )
    {
        next = curr;
        ++next;
        if( comp( *(rhs.begin()), *next ) )
            splice_after( curr, rhs.header(), rhs.begin() );
        ++curr;
    }

    if( rhs.m_header.next )
    {
        curr.node->next = rhs.m_header.next;
        rhs.m_header.next = NULL_POINTER;
    }
}
//-----------------------------------------------------------------------------

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

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

    while( !empty() )
    {
        carry.splice_after( carry.header(), header(), 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 slist<T, Allocator>::sort( StrictWeakOrdering comp )
{
    if( empty() || m_header.next->next == NULL_POINTER )
        return;

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

    while( !empty() )
    {
        carry.splice_after( carry.header(), header(), 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( slist<T,Allocator>& lhs, slist<T,Allocator>& rhs )
{
    lhs.swap( rhs );
}

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

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

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

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

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

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

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

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

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