mstl_vector.hpp

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

/*
The young Library
Copyright (c) 2005 by 杨桓

Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_VECTOR_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_VECTOR_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "mstl_allocator.hpp"
#include "mstl_initialization.hpp"
#include "mstl_exception.hpp"
#include "algorithm/mstl_algorithm_base.hpp"
#include "algorithm/mstl_algorithm_copy.hpp"
#include "algorithm/mstl_algorithm_compare.hpp"
#include "algorithm/mstl_algorithm_fill.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename T, typename Allocator = allocator<T> >
class vector
{
public:
    typedef  vector<T, Allocator>  self;
    typedef  Allocator             allocator_type;

    typedef  T                  value_type;
    typedef  value_type&        reference;
    typedef  const value_type&  const_reference;
    typedef  value_type*        pointer;
    typedef  const value_type*  const_pointer;
    typedef  def_size_t         size_type;
    typedef  def_ptrdiff_t      difference_type;

    typedef  value_type*                       iterator;
    typedef  const value_type*                 const_iterator;
    typedef  Reverse_Iterator<iterator>        reverse_iterator;
    typedef  Reverse_Iterator<const_iterator>  const_reverse_iterator;

protected:
    pointer         m_start, m_finish, m_storage;
    allocator_type  m_alloc;

public:
    vector() : m_start(NULL_POINTER),
               m_finish(NULL_POINTER),
               m_storage(NULL_POINTER)  {}

    explicit vector( size_type size )
        {  fill_init( size, value_type() );  }

    vector( size_type size, const_reference value )
        {  fill_init( size, value );  }
    vector( int size, const_reference value )
        {  fill_init( static_cast<size_type>( size ), value );  }
    vector( long size, const_reference value )
        {  fill_init( static_cast<size_type>( size ), value );  }

    template< typename InputIterator >
    vector( InputIterator first, InputIterator last, size_type size = 0 )
    {
        typedef  typename iterator_traits<InputIterator>::iterator_category
                 cate;
        range_init( first, last, size, cate() );
    }

    vector( const self& rhs )
    {
        alloc_data( rhs.size() );
        try
        {
            init_copy( rhs.begin(), rhs.end(), m_start );
        }
        catch(...)
        {
            dealloc_data();
            throw;
        }
        m_finish = m_start + rhs.size();
    }

    self& operator=( const self& rhs )
    {
        if( this != &rhs )
            assign( rhs.begin(), rhs.end(), rhs.size() );
        return *this;
    }

    ~vector()
    {
        destroy( begin(), end() );
        dealloc_data();
    }

    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 end();  }
    reverse_iterator rend()                {  return begin();  }
    const_reverse_iterator rbegin() const  {  return end();  }
    const_reverse_iterator rend() const    {  return begin();  }

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

    bool empty() const          {  return ( m_start == m_finish );  }
    size_type size() const      {  return ( m_finish - m_start );  }
    size_type space() const     {  return ( m_storage - m_finish );  }
    size_type capacity() const  {  return ( m_storage - m_start );  }
    size_type max_size() const  {  return size_t_max / sizeof(value_type);  }

    reference operator[]( size_type index )
        {  return m_start[index];  }
    const_reference operator[]( size_type index ) const
        {  return m_start[index];  }

    reference at( size_type index )
    {
        if( index >= size() )
            throw_out_of_range( "vector::at()" );
        return m_start[index];
    }
    const_reference at( size_type index ) const
    {
        if( index >= size() )
            throw_out_of_range( "vector::at()" );
        return m_start[index];
    }

    void push_back( const_reference value )
    {
        if( m_finish != m_storage )
        {
            construct( m_finish, value );
            ++m_finish;
        }
        else
            insert_aux( end(), value );
    }

    void pop_back()
    {
        --m_finish;
        destroy( m_finish );
    }

    void clear()
    {
        destroy( begin(), end() );
        dealloc_data();
        m_start = NULL_POINTER;
        m_finish = NULL_POINTER;
        m_storage = NULL_POINTER;
    }

    void reserve( size_type new_size )
    {
        if( capacity() < new_size )
        {
            self temp( begin(), end(), new_size );
            swap( temp );
        }
    }

    void swap( self& rhs )
    {
        if( this != &rhs )
        {
            data_swap( m_start, rhs.m_start );
            data_swap( m_finish, rhs.m_finish );
            data_swap( m_storage, rhs.m_storage );
            data_swap( m_alloc, rhs.m_alloc );
        }
    }

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


    void reverse();

    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,
                 size_type new_size = 0 )
    {
        typedef  typename iterator_traits<InputIterator>::iterator_category  cate;

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


    void insert( iterator position, size_type count, const_reference 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() )
    {
        const size_type n = position - m_start;
        if( position == m_finish && m_finish != m_storage )
        {
            construct( m_finish, value );
            ++m_finish;
        }
        else
            insert_aux( position, value );

        return ( m_start + n );
    }

    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:
    //insert辅助函数
    void insert_aux( iterator position, const_reference value );

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


    //assign辅助函数
    template< typename InputIterator >
    void range_assign( InputIterator first, InputIterator last,
                       size_type new_size );

    template< typename InputIterator >
    void assign_aux( InputIterator first, InputIterator last,
                     size_type new_size, input_iterator_tag )
    {
        range_assign( first, last, new_size );
    }
    template< typename InputIterator >
    void assign_aux( InputIterator first, InputIterator last,
                     size_type new_size, random_access_iterator_tag )
    {
        new_size = max( static_cast<size_type>(last - first), new_size );
        range_assign( first, last, new_size );
    }


    //初始化的辅助函数
    template< typename InputIterator >
    void range_init( InputIterator first, InputIterator last,
                     size_type size, input_iterator_tag )
    {
        alloc_data( 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_data( max(n, size) );
        try
        {
            init_copy( first, last, m_start );
        }
        catch(...)
        {
            dealloc_data();
            throw;
        }
        m_finish = m_start + n;
    }

    void fill_init( size_type n, const_reference value )
    {
    	alloc_data( n );
        try
        {
            init_fill_n( m_start, n, value );
        }
        catch(...)
        {
            dealloc_data();
            throw;
        }
        m_finish = m_start + n;
    }


    //负责分配和回收空间的辅助函数
    void alloc_data( size_type n )
    {
    	typedef  typename type_traits<value_type>::is_POD_type  is_pod;

        if( n > 0 )
        {
            m_start = alloc_aux( n, is_pod() );
            m_finish = m_start;
            m_storage = m_start + n;
        }
        else
        {
            m_start = NULL_POINTER;
            m_finish = NULL_POINTER;
            m_storage = NULL_POINTER;
        }
    }