mstl_deque.hpp

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

        difference_type elements_before = position - m_start;
        size_type len = size();

        if( elements_before < (len / 2) )  //向前面移动
        {
            iterator new_start = reserve_elements_at_front( extra_size );
            iterator old_start = m_start;
            position = m_start + elements_before;
            try
            {
                //position前面的已构造空间可以放进所有的新数据
                if( elements_before >= difference_type(extra_size) )
                {
                    iterator start_count = m_start + difference_type(extra_size);
                    init_copy( m_start, start_count, new_start );
                    m_start = new_start;
                    copy_n( start_count, position - start_count, old_start );
                    fill( position - extra_size, position, value );
                }
                else  //position前面的已构造空间不能放进所有的新数据
                {
                    //先将[m_start, position)复制进[new_start, m_start)，
                    //然后再将value填满[new_start, m_start)的剩余空间
                    init_copy_fill( m_start, position, new_start, m_start, value );
                    m_start = new_start;
                    fill( old_start, position, value );
                }
            }
            catch(...)
            {
                destroy_nodes_at_front( new_start );
                throw;
            }
        }
    	else  //向后面移动
    	{
            iterator new_finish = reserve_elements_at_back( extra_size );
            iterator old_finish = m_finish;
            difference_type elements_after = difference_type(len) - elements_before;
            position = m_finish - elements_after;
            try
            {
                //position后面的已构造空间可以放进所有的新数据
                if( elements_after >= difference_type(extra_size) )
                {
                    iterator finish_count = m_finish - difference_type(extra_size);
                    init_copy( finish_count, m_finish, m_finish );
                    m_finish = new_finish;
                    copy_backward( position, finish_count, old_finish );
                    fill_n( position, extra_size, value );
                }
                else  //position后面的已构造空间不能放进所有的新数据
                {
                    //先将value添满[m_finish, position + extra_size)，
                    //再将[position, m_finish)复制进[position + extra_size, enough)
                    init_fill_copy( m_finish, position + difference_type(extra_size),
                                    value, position, m_finish );
                    m_finish = new_finish;
                    fill( position, old_finish, value );
                }
            }
            catch(...)
            {
                destroy_nodes_at_back( new_finish );
                throw;
            }
        }  //end else ( elements_before >= (len / 2) )
    }  //end else
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
template< typename InputIterator >
void deque<T, Allocator, buf_size>::range_insert( iterator position,
                                                  InputIterator first,
                                                  InputIterator last,
                                                  size_type extra_size )
{
    difference_type elements_before = position - m_start;
    size_type len = size();

    if( elements_before < (len / 2) )  //向前面移动
    {
        iterator new_start = reserve_elements_at_front( extra_size );
        iterator old_start = m_start;
        position = m_start + elements_before;
        try
        {
            //position前面的已构造空间可以放进所有的新数据
            if( elements_before >= difference_type(extra_size) )
            {
                iterator start_count = m_start + difference_type(extra_size);
                init_copy( m_start, start_count, new_start );
                m_start = new_start;
                copy_n( start_count, position - start_count, old_start );
                copy_n( first, extra_size, position - difference_type(extra_size) );
            }
            else  //position前面的已构造空间不能放进所有的新数据
            {
                InputIterator mid = first;
                difference_type i = difference_type(extra_size) - elements_before;
                advance( mid, i );

                //将[m_start, position)和[first, mid)依次复制到[new_start, enough)
                init_copy_copy( m_start, position, first, mid, new_start );
                m_start = new_start;
                copy_n( mid, extra_size - i, old_start );
            }
        }
        catch(...)
        {
            destroy_nodes_at_front( new_start );
            throw;
        }
    }
    else  //向后面移动
    {
        iterator new_finish = reserve_elements_at_back( extra_size );
        iterator old_finish = m_finish;
    	difference_type elements_after = difference_type(len) - elements_before;
    	position = m_finish - elements_after;
        try
        {
            //position后面的已构造空间可以放进所有的新数据
            if( elements_after >= difference_type(extra_size) )
            {
                iterator finish_count = m_finish - difference_type(extra_size);
                init_copy( finish_count, m_finish, m_finish );
                m_finish = new_finish;
                copy_backward( position, finish_count, old_finish );
                copy_n( first, extra_size, position );
            }
            else  //position后面的已构造空间不能放进所有的新数据
            {
                InputIterator mid = first;
                advance( mid, elements_after );

                //将[mid, last)和[position, m_finish)依次复制进[m_finish, enough)
                init_copy_copy( mid, last, position, m_finish, m_finish );
                m_finish = new_finish;
                copy_n( first, extra_size - elements_after, position );
            }
        }
        catch(...)
        {
            destroy_nodes_at_back( new_finish );
            throw;
        }
    }  //end else
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
typename deque<T, Allocator, buf_size>::iterator
deque<T, Allocator, buf_size>::erase( iterator position )
{
    if( position == m_finish )
        return position;

    iterator next = position;
    ++next;
    difference_type i = position - m_start;

    if( i < (size() / 2) )  //移动前面的数据
    {
        copy_backward( m_start, position, next );
        pop_front();
    }
    else  //移动后面的数据
    {
        copy( next, m_finish, position );
        pop_back();
    }

    return ( m_start + i );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
typename deque<T, Allocator, buf_size>::iterator
deque<T, Allocator, buf_size>::erase( iterator first, iterator last )
{
    if( first == m_start && last == m_finish )
    {
        clear();
        return m_finish;
    }

    difference_type n = last - first;
    difference_type elements_before = first - m_start;

    if( elements_before < ((size() - n) / 2) )  //移动前面的数据
    {
        copy_backward( m_start, first, last );
        iterator new_start = m_start + n;
        destroy( m_start, new_start );
        for( map_pointer curr = m_start.node; curr < new_start.node; ++curr )
            dealloc_node( *curr );
        m_start = new_start;
    }
    else  //移动后面的数据
    {
        copy( last, m_finish, first );
        iterator new_finish = m_finish - n;
        destroy( new_finish, m_finish );
        for( map_pointer curr = m_finish.node; curr > new_finish.node; --curr )
            dealloc_node( *curr );
        m_finish = new_finish;
    }

    return ( m_start + elements_before );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::new_elements_at_front( size_type n )
{
    size_type buf = buffer_size();
    size_type add_nodes = ( n + buf - 1 ) / buf;
    reserve_map_at_front( add_nodes );

    size_type i;
    try
    {
        for( i = 1; i <= add_nodes; ++i )
            *( m_start.node - i ) = alloc_node();
    }
    catch(...)
    {
        for( size_type j = 1; j < i; ++j )
            dealloc_node( *(m_start.node - j) );
        throw;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::new_elements_at_back( size_type n )
{
    size_type buf = buffer_size();
    size_type add_nodes = ( n + buf - 1 ) / buf;
    reserve_map_at_back( add_nodes );

    size_type i;
    try
    {
        for( i = 1; i <= add_nodes; ++i )
            *( m_finish.node + i ) = alloc_node();
    }
    catch(...)
    {
        for( size_type j = 1; j < i; ++j )
            dealloc_node( *(m_finish.node + j) );
        throw;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::
destroy_nodes_at_front( iterator before_start )
{
    for( map_pointer curr = before_start.node; curr < m_start.node; ++curr )
        dealloc_node( *curr );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator, def_size_t buf_size >
void deque<T, Allocator, buf_size>::
destroy_nodes_at_back( iterator after_finish )
{
    for( map_pointer curr = after_finish.node; curr > m_finish.node; --curr )
        dealloc_node( *curr );
}

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

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

template< typename T, typename Allocator, def_size_t buf_size >
inline bool operator==( const deque<T, Allocator, buf_size>& lhs,
                        const deque<T, Allocator, buf_size>& rhs )
{
    return ( lhs.size() == rhs.size()
             && equal( lhs.begin(), lhs.end(), rhs.begin() ) );
}

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

template< typename T, typename Allocator, def_size_t buf_size >
inline bool operator<( const deque<T, Allocator, buf_size>& lhs,
                       const deque<T, Allocator, buf_size>& rhs )
{
    if( lhs.begin() == rhs.begin() || lhs.size() > rhs.size() )
        return false;

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

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

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

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

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