mstl_deque.hpp

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

    deque( long size, const_reference value )
    : m_map(NULL_POINTER), m_map_size(0), m_start(), m_finish()
    {
        fill_init( static_cast<size_type>( size ), value );
    }

    template< typename InputIterator >
    deque( InputIterator first, InputIterator last, size_type size = 0 )
    : m_map(NULL_POINTER), m_map_size(0), m_start(), m_finish()
    {
    	typedef  typename iterator_traits<InputIterator>::iterator_category
    	         cate;
        range_init( first, last, size, cate() );
    }

    deque( const self& rhs )
    : m_map(NULL_POINTER), m_map_size(0), m_start(), m_finish()
    {
        alloc_map_and_nodes( rhs.size() );
        try
        {
            init_copy( rhs.begin(), rhs.end(), begin() );
        }
        catch(...)
        {
            free_map_and_nodes();
            throw;
        }
    }

    deque& operator=( const self& rhs );

    ~deque();

    iterator begin()              {  return m_start;  }
    iterator end()                {  return m_finish;  }
    const_iterator begin() const  {  return m_start;  }
    const_iterator end() const    {  return m_finish;  }

    reverse_iterator rbegin()              {  return m_finish;  }
    reverse_iterator rend()                {  return m_start;  }
    const_reverse_iterator rbegin() const
        {  return const_reverse_iterator(m_finish);  }
    const_reverse_iterator rend() const
        {  return const_reverse_iterator(m_start);  }

    reference front()              {  return *m_start;  }
    reference back()               {  return *(--end());  }
    const_reference front() const  {  return *m_start;  }
    const_reference back() const   {  return *(--end());  }

    bool empty() const          {  return ( m_start == m_finish );  }
    size_type size() const      {  return ( m_finish - m_start );  }
    size_type max_size() const  {  return size_t_max;  }

    reference operator[]( size_type index )
    {
        iterator result = m_start;
        return *( result += index );
    }
    const_reference operator[]( size_type index ) const
    {
        const_iterator result = m_start;
        return *( result += index );
    }

    reference at( size_type index )
    {
        if( index >= size() )
            throw_out_of_range( "deque::at()" );
        iterator result = m_start;
        return *( result += index );
    }
    const_reference at( size_type index ) const
    {
        if( index >= size() )
            throw_out_of_range( "deque::at()" );
        const_iterator result = m_start;
        return *( result += index );
    }

    void swap( self& rhs )
    {
        if( this != &rhs )
        {
            data_swap( m_map, rhs.m_map );
            data_swap( m_map_size, rhs.m_map_size );
            data_swap( m_start, rhs.m_start );
            data_swap( m_finish, rhs.m_finish );
            data_swap( m_map_alloc, rhs.m_map_alloc );
            data_swap( m_data_alloc, rhs.m_data_alloc );
        }
    }

    void push_back( const_reference value )
    {
        if( m_finish.current != (m_finish.last - 1) )
        {
            construct( m_finish.current, value );
            ++m_finish.current;
        }
        else
            push_back_aux( value );
    }

    void push_front( const_reference value )
    {
        if( m_start.current != m_start.first )
        {
            construct( m_start.current - 1, value );
            --m_start.current;
        }
        else
            push_front_aux( value );
    }

    void pop_back()
    {
        if( m_finish.current != m_finish.first )
        {
            --m_finish.current;
            destroy( m_finish.current );
        }
        else
            pop_back_aux();
    }

    void pop_front()
    {
        if( m_start.current != (m_start.last - 1) )
        {
            destroy( m_start.current );
            ++m_start.current;
        }
        else
            pop_front_aux();
    }

    void resize( size_type new_size, const_reference value = value_type() )
    {
    	const size_type len = size();
    	if( new_size > len )
    	    insert( m_finish, new_size - len, value );
    	else if( new_size < len )
    	    erase( m_start + new_size, m_finish );
    }

    void clear();

    iterator erase( iterator position );
    iterator erase( iterator first, iterator last );


    void assign( size_type new_size, const_reference value = value_type() );
    void assign( int new_size, const_reference value = value_type() )
        {  assign( static_cast<size_type>( new_size ), value );  }
    void assign( long new_size, const_reference value = value_type() )
        {  assign( static_cast<size_type>( new_size ), value );  }

    template< typename InputIterator >
    void assign( InputIterator first, InputIterator last )
    {
    	typedef  typename iterator_traits<InputIterator>::iterator_category  cate;

        if( first == last )
            clear();
        else
            assign_aux( first, last, cate() );
    }


    void insert( iterator position, size_type count, const_reference value )
    {
        if( count > 1 )
            insert_n( position, count, value );
    }
    void insert( iterator position, int count, const_reference value )
        {  insert( position, static_cast<size_type>( count ), value );  }
    void insert( iterator position, long count, const_reference value )
        {  insert( position, static_cast<size_type>( count ), value );  }

    iterator insert( iterator position, const_reference value = value_type() )
    {
        if( position == m_start )
        {
            push_front( value );
            return m_start;
        }
        else if( position == m_finish )
        {
            push_back( value );
            return --end();
        }
        else
            return insert_aux( position, value );
    }

    template< typename InputIterator >
    void insert( iterator position, InputIterator first, InputIterator last,
                 size_type extra_size = 0 )
    {
        if( first != last )
            range_insert( position, first, last,
                          range_length(first, last, extra_size) );
    }

protected:
    //进行初始化的辅助函数
    void fill_init( size_type n, const value_type& value );

    template< typename InputIterator >
    void range_init( InputIterator first, InputIterator last,
                     size_type size, input_iterator_tag )
    {
        alloc_map_and_nodes( size );
        for( ; first != last; ++first )
            push_back( *first );
    }

    template< typename InputIterator >
    void range_init( InputIterator first, InputIterator last,
                     size_type size, random_access_iterator_tag )
    {
        size_type n = last - first;
        alloc_map_and_nodes( max(n, size) );
        try
        {
            init_copy( first, last, m_start );
        }
        catch(...)
        {
            free_map_and_nodes();
            throw;
        }
    }


    //assign、insert、push、pop的辅助函数
    void insert_n( iterator position, size_type extra_size,
                   const_reference value );
    iterator insert_aux( iterator position, const_reference value );

    template< typename InputIterator >
    void range_insert( iterator position, 
                       InputIterator first, InputIterator last,
                       size_type extra_size );

    template< typename InputIterator >
    void assign_aux( InputIterator first, InputIterator last,
                     input_iterator_tag );
    template< typename InputIterator >
    void assign_aux( InputIterator first, InputIterator last,
                     random_access_iterator_tag );

    void reserve_map_at_back( size_type add_nodes = 1 )
    {
        if( add_nodes + 1 > (m_map_size - (m_finish.node - m_map)) )
            reallocate_map( add_nodes, false );
    }

    void reserve_map_at_front( size_type add_nodes = 1 )
    {
        if( add_nodes > (m_start.node - m_map) )
            reallocate_map( add_nodes, true );
    }

    iterator reserve_elements_at_front( size_type n )
    {
        size_type space = m_start.current - m_start.first;
        if( n > space )
            new_elements_at_front( n - space );
        return ( m_start - n );
    }

    iterator reserve_elements_at_back( size_type n )
    {
        size_type space = ( m_finish.last - m_finish.current ) - 1;
        if( n > space )
            new_elements_at_back( n - space );
        return ( m_finish + n );
    }

    void new_elements_at_front( size_type n );
    void new_elements_at_back( size_type n );

    void destroy_nodes_at_front( iterator before_start );
    void destroy_nodes_at_back( iterator after_finish );

    void push_back_aux( const_reference value );
    void push_front_aux( const_reference value );
    void pop_back_aux();
    void pop_front_aux();


    //负责分配和回收map与缓冲区空间的函数
    void alloc_map_and_nodes( size_type n );
    void free_map_and_nodes();
    void reallocate_map( size_type add_nodes, bool add_at_front );

    map_pointer alloc_map( size_type n )
    {
        return m_map_alloc.allocate(n);
    }
    void dealloc_map( map_pointer map_ptr, size_type n )
    {
        if( map_ptr )
            m_map_alloc.deallocate( map_ptr, n );
    }

    pointer alloc_node()
    {
        return m_data_alloc.allocate( buffer_size() );
    }
    void dealloc_node( pointer ptr )
    {
        if( ptr )
            m_data_alloc.deallocate( ptr, buffer_size() );
    }

};  //end class

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

template< typename T, typename Allocator, def_size_t buf_size >
deque<T, Allocator, buf_size>::~deque()
{
    size_type buf = buffer_size();
    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 )  //首尾不在同一个map内
    {
        destroy( m_start.current, m_start.last );
        destroy( m_finish.first, m_finish.current );
        dealloc_node( *(m_start.node) );
        dealloc_node( *(m_finish.node) );
    }
    else  //首尾在同一个map内
    {
        destroy( m_start.current, m_finish.current );