mstl_deque.hpp

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

        dealloc_node( *(m_start.node) );
    }

    dealloc_map( m_map, m_map_size );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
deque<T, Allocator, buf_size>&
deque<T, Allocator, buf_size>::operator=( const self& rhs )
{
    if( this != &rhs )
    {
        const size_type len = size();
        if( len >= rhs.size() )
            erase( copy(rhs.begin(), rhs.end(), m_start), m_finish );
        else
        {
       	    const_iterator itr = rhs.begin() + len;
            copy( rhs.begin(), itr, m_start );
            insert( m_finish, itr, rhs.end() );
        }
    }
    return *this;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::alloc_map_and_nodes( size_type data_size )
{
    size_type nodes_count = data_size / buffer_size() + 1;  //可能还有余数，所以要加1
    m_map_size = max( init_map_size, nodes_count + 2 );
    m_map = alloc_map( m_map_size );

    map_pointer node_start = m_map + ( m_map_size - nodes_count ) / 2;
    map_pointer node_finish = node_start + nodes_count - 1;
    map_pointer curr;

    try
    {
        for( curr = node_start; curr <= node_finish; ++curr )
            *curr = alloc_node();
    }
    catch(...)
    {
        for( ; node_start < curr; ++node_start )
            dealloc_node( *node_start );
        dealloc_map( m_map, m_map_size );
        throw;
    }

    m_start.set_node( node_start );
    m_finish.set_node( node_finish );
    m_start.current = m_start.first;
    m_finish.current = m_finish.first + data_size % buffer_size();
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::reallocate_map( size_type add_nodes,
                                                    bool add_at_front )
{
    size_type old_nodes = m_finish.node - m_start.node + 1;
    size_type new_nodes = old_nodes + add_nodes;

    map_pointer new_start;

    if( m_map_size > 2 * new_nodes )  //map空间足够大
    {
        //在起始位置增加节点则需将当前节点数据后移
        new_start = m_map + (m_map_size - new_nodes) / 2
                    + ( add_at_front ? add_nodes : 0 );
        if( new_start < m_start.node )  //在起始处增加节点的操作
            copy( m_start.node, m_finish.node + 1, new_start );
        else  //在末尾增加节点的操作
            copy_backward( m_start.node, m_finish.node + 1, new_start + old_nodes );
    }
    else
    {
        size_type new_map_size = m_map_size + max( m_map_size, add_nodes ) + 2;
        map_pointer new_map = alloc_map( new_map_size );
        new_start = new_map + (new_map_size - new_nodes) / 2
                    + ( add_at_front ? add_nodes : 0 );
        copy( m_start.node, m_finish.node + 1, new_start );
        dealloc_map( m_map, m_map_size );
        m_map = new_map;
        m_map_size = new_map_size;
    }

    m_start.set_node( new_start );
    m_finish.set_node( new_start + old_nodes - 1 );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::free_map_and_nodes()
{
    for( map_pointer curr = m_start.node; curr <= m_finish.node; ++curr )
        dealloc_node( *curr );
    dealloc_map( m_map, m_map_size );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::fill_init( size_type n, const T& value )
{
    alloc_map_and_nodes( n );
    map_pointer curr;
    size_type buf = buffer_size();
    try
    {
        for( curr = m_start.node; curr < m_finish.node; ++curr )
            init_fill_n( *curr, buf, value );
        init_fill_n( m_finish.first, m_finish.current - m_finish.first, value );
    }
    catch(...)
    {
    	for( map_pointer i = m_start.node; i < curr; ++i )
    	    destroy( *i, *i + buf );
        free_map_and_nodes();
        throw;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::clear()
{
    size_type buf = buffer_size();

    //释放start与finish之间的节点所分配的空间
    for( map_pointer curr = m_start.node + 1; curr < m_finish.node; ++curr )
    {
        destroy( *curr, *curr + buf );
        dealloc_node( *curr );
    }

    if( m_start.node != m_finish.node )
    {
        destroy( m_start.current, m_start.last );
        destroy( m_finish.first, m_finish.current );
        dealloc_node( *(m_finish.node) );
    }
    else
        destroy( m_start.current, m_finish.current );

    m_finish = m_start;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::push_back_aux( const_reference value )
{
    reserve_map_at_back();  //检查是否需要为map重新分配内存空间
    *( m_finish.node + 1 ) = alloc_node();
    try
    {
        construct( m_finish.current, value );
    }
    catch(...)
    {
        dealloc_node( *(m_finish.node + 1) );
        throw;
    }
    m_finish.set_node( m_finish.node + 1 );
    m_finish.current = m_finish.first;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::push_front_aux( const_reference value )
{
    reserve_map_at_front();
    *( m_start.node - 1 ) = alloc_node();
    try
    {
        m_start.set_node( m_start.node - 1 );
        m_start.current = m_start.last - 1;
        construct( m_start.current, value );
    }
    catch(...)
    {
        m_start.set_node( m_start.node - 1 );
        m_start.current = m_start.first;
        dealloc_node( *(m_start.node - 1) );
        throw;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::pop_back_aux()
{
    dealloc_node( m_finish.first );
    m_finish.set_node( m_finish.node - 1 );
    m_finish.current = m_finish.last - 1;
    destroy( m_finish.current );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::pop_front_aux()
{
    destroy( m_start.current );
    dealloc_node( m_start.first );
    m_start.set_node( m_start.node + 1 );
    m_start.current = m_start.first;
}
//-----------------------------------------------------------------------------

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

    const size_type len = size();

    if( len < new_size )
    {
        fill_n( m_start, len, value );
        insert( m_finish, new_size - len, value );
    }
    else if( len > new_size )
    {
        fill_n( m_start, new_size, value );
        erase( m_start + new_size, m_finish );
    }
    else
        fill_n( m_start, len, value );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
template< typename InputIterator >
void deque<T, Allocator, buf_size>::assign_aux( InputIterator first,
                                                InputIterator last,
                                                input_iterator_tag )
{
    size_type len = size();
    iterator itr = m_start;

    for( ; (len > 0) && (first != last); --len,++first,++itr )
        *itr = *first;

    if( len > 0 )  //原数据较长
        erase( itr, m_finish );
    else if( (len == 0) && (first != last) )
        insert( m_finish, first, last );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
template< typename InputIterator >
void deque<T, Allocator, buf_size>::assign_aux( InputIterator first,
                                                InputIterator last,
                                                random_access_iterator_tag )
{
    const size_type len = size();
    const size_type itr_len = last - first;

    if( itr_len > len )
    {
        copy_n( first, len, m_start );
        insert( m_finish, first + len, last );
    }
    else if( itr_len < len )
    {
        copy_n( first, itr_len, m_start );
        erase( m_start + itr_len, m_finish );
    }
    else
        copy( first, last, m_start );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
typename deque<T, Allocator, buf_size>::iterator
deque<T, Allocator, buf_size>::insert_aux( iterator position,
                                           const_reference value )
{
    difference_type elements_before = position - m_start;
    if( elements_before < (size() / 2) )  //向前面移动
    {
        push_front( front() );
        position = m_start + elements_before;  //迭代器有可能失效，需重新定位
        iterator front1 = m_start;  ++front1;  //指向原来的第一个数据的位置
        iterator front2 = front1;  ++front2;   //指向原来的第二个数据的位置
        copy( front2, position + 1, front1 );  //从第二个数据开始全部前移一位
    }
    else
    {
        push_back( back() );
        position = m_start + elements_before;
        iterator back1 = m_finish;  --back1;  //原来的end()
        iterator back2 = back1;  --back2;     //原来的back()
        copy_backward( position, back2, back1 );
    }

    *position = value;
    return position;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::insert_n( iterator position,
                                              size_type extra_size,
                                              const_reference value )
{
    if( position == m_start )
    {
        iterator new_start = reserve_elements_at_front( extra_size );
        try
        {
            init_fill_n( new_start, extra_size, value );
        }
        catch(...)
        {
            destroy_nodes_at_front( new_start );
            throw;
        }
        m_start = new_start;
    }
    else if( position == m_finish )
    {
        iterator new_finish = reserve_elements_at_back( extra_size );
        try
        {
            init_fill_n( m_finish, extra_size, value );
        }
        catch(...)
        {
            destroy_nodes_at_back( new_finish );
            throw;
        }
        m_finish = new_finish;
    }
    else  //处理一般情况下的插入操作
    {