mstl_vector.hpp

来自「一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面」· HPP 代码 · 共 726 行 · 第 1/2 页

    void dealloc_data()
    {
        if( m_start )
            m_alloc.deallocate( m_start, capacity() );
    }

    pointer alloc_aux( size_type& n, true_type );
    pointer alloc_aux( size_type& n, false_type )
    {
        return m_alloc.allocate( n );
    }

};  //end class

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

template< typename T, typename Allocator >
typename vector<T, Allocator>::pointer
vector<T, Allocator>::alloc_aux( size_type& n, true_type )
{
    size_type n_bytes = n * sizeof( value_type );
    size_type i_bytes = alignment_bytes;

    while( i_bytes < n_bytes )
        i_bytes *= 2;

    n = i_bytes / sizeof( value_type );
    return m_alloc.allocate( n );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void vector<T, Allocator>::reverse()
{
    if( size() < 2 )
        return;

    iterator first = begin(), last = end();
    --last;
    for( ; first < last; ++first,--last )
        data_swap( *first, *last );
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void vector<T, Allocator>::assign( size_type new_size, const T& value )
{
    if( capacity() < new_size )
    {
    	self temp( new_size, value );
    	swap( temp );
    }
    else
    {
    	const size_type len = size();
    	if( len > new_size )
    	{
    	    fill_n( begin(), new_size, value );
            destroy( begin() + new_size, end() );
            m_finish = m_start + new_size;
        }
        else if( len < new_size )
        {
            fill( begin(), end(), value );
            init_fill_n( end(), new_size - len, value );
            m_finish = m_start + new_size;
        }
        else
            fill( begin(), end(), value );
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename InputIterator >
void vector<T, Allocator>::range_assign( InputIterator first,
                                         InputIterator last,
                                         size_type new_size )
{
    if( capacity() < new_size )
    {
        self temp( first, last, new_size );
        swap( temp );
    }
    else
    {
        iterator itr = m_start;

        for( ; (itr != m_finish) && (first != last); ++itr,++first )
            *itr = *first;

        if( (itr == m_finish) && (first != last) )
            insert( end(), first, last );
        else if( itr != m_finish )
            erase( itr, end() );
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
typename vector<T, Allocator>::iterator
vector<T, Allocator>::erase( iterator position )
{
    if( position != m_finish )
    {
        if( position + 1 != m_finish )
            copy( position + 1, m_finish, position );

        --m_finish;
        destroy( m_finish );
    }
    return position;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
typename vector<T, Allocator>::iterator
vector<T, Allocator>::erase( iterator first, iterator last )
{
    if( first < last )
    {
        size_type n = m_finish - last;
        iterator itr;
        if( n > 0 )
            itr = copy_n( last, n, first );
        destroy( itr, m_finish );
        m_finish -= ( last - first );
    }
    return first;
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void vector<T, Allocator>::insert_aux( iterator position, const T& value )
{
    if( m_finish != m_storage )  //剩余空间足够
    {
        construct( m_finish, *( m_finish - 1 ) );
        ++m_finish;
        copy_backward( position, m_finish - 2, m_finish - 1 );
        *position = value;
    }
    else  //剩余空间不够
    {
        size_type old_size = size();
        size_type new_capa = max( 2 * old_size, (size_type)1 );

        typedef  typename type_traits<value_type>::is_POD_type  is_pod;

        pointer new_start = alloc_aux( new_capa, is_pod() );
        pointer new_finish = new_start;

        try
        {
            new_finish = init_copy( begin(), position, new_start );
            construct( new_finish, value );
            ++new_finish;
            new_finish = init_copy( position, end(), new_finish );
        }
        catch(...)
        {
            destroy( new_start, new_finish );
            m_alloc.deallocate( new_start, new_capa );
            throw;
        }

        destroy( begin(), end() );
        dealloc_data();
        m_start = new_start;
        m_finish = new_finish;
        m_storage = m_start + new_capa;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
void vector<T, Allocator>::insert( iterator position,
                                   size_type count,
                                   const_reference value )
{
    if( count < 1 || position > m_finish )
        return;

    if( space() >= count )  //剩余空间足够
    {
        size_type elements_after = m_finish - position;
        iterator old_finish = m_finish;

        //position后面的已构造空间可以放进所有的新数据
        if( elements_after >= count )
        {
            m_finish = init_copy( m_finish - count, m_finish, m_finish );
            copy_backward( position, old_finish - count, old_finish );
            fill_n( position, count, value );
        }
        else  //position后面的已构造空间不能放进所有的新数据
        {
            //先将value添满[m_finish, position + count)，
            //再将[position, m_finish)复制进[position + count, enough)
            m_finish = init_fill_copy( m_finish, position + count, value,
                                       position, m_finish );
            fill( position, old_finish, value );
        }
    }
    else  //剩余空间不够
    {
        size_type old_capa = capacity();
        size_type new_capa = max( 2 * old_capa, old_capa + count );

        typedef  typename type_traits<value_type>::is_POD_type  is_pod;

        pointer new_start = alloc_aux( new_capa, is_pod() );
        pointer new_finish = new_start;

        try
        {
            new_finish = init_copy( begin(), position, new_start );
            init_fill_n( new_finish, count, value );
            new_finish += count;
            new_finish = init_copy( position, end(), new_finish );
        }
        catch(...)
        {
            destroy( new_start, new_finish );
            m_alloc.deallocate( new_start, new_capa );
            throw;
        }

        destroy( begin(), end() );
        dealloc_data();
        m_start = new_start;
        m_finish = new_finish;
        m_storage = m_start + new_capa;
    }
}
//-----------------------------------------------------------------------------

template< typename T, typename Allocator >
template< typename InputIterator >
void vector<T, Allocator>::range_insert( iterator position,
                                         InputIterator first,
                                         InputIterator last,
                                         size_type extra_size )
{
    size_type old_capa = capacity();
    size_type new_size = size() + extra_size;

    if( old_capa >= new_size )  //剩余空间足够
    {
        size_type elements_after = m_finish - position;
        iterator old_finish = m_finish;

        //position后面的已构造空间可以放进所有的新数据
        if( elements_after >= extra_size )
        {
            m_finish = init_copy( m_finish - extra_size, m_finish, m_finish );
            copy_backward( position, old_finish - extra_size, old_finish );
            copy( first, last, position );
        }
        else  //position后面的已构造空间不能放进所有的新数据
        {
            InputIterator mid = first;
            advance( mid, elements_after );
            //将[mid, last)和[position, m_finish)依次复制到[m_finish, enough)
            m_finish = init_copy_copy( mid, last, position, m_finish, m_finish );
            copy( first, mid, position );
        }
    }
    else  //剩余空间不够
    {
        size_type new_capa = max( 2 * old_capa, new_size );

        typedef  typename type_traits<value_type>::is_POD_type  is_pod;

        pointer new_start = alloc_aux( new_capa, is_pod() );
        pointer new_finish = new_start;

        try
        {
            new_finish = init_copy( begin(), position, new_start );
            new_finish = init_copy( first, last, new_finish );
            new_finish = init_copy( position, end(), new_finish );
        }
        catch(...)
        {
            destroy( new_start, new_finish );
            m_alloc.deallocate( new_start, new_capa );
            throw;
        }

        destroy( begin(), end() );
        dealloc_data();
        m_start = new_start;
        m_finish = new_finish;
        m_storage = m_start + new_capa;
    }
}

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

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

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

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

template< typename T, typename Allocator >
inline bool operator<( const vector<T, Allocator>& lhs,
                       const vector<T, Allocator>& 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 >
inline bool operator>( const vector<T, Allocator>& lhs,
                       const vector<T, Allocator>& rhs )
{
    return ( rhs < lhs );
}

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

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

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