vector.mh

来自「开放源码的编译器open watcom 1.6.0版的源代码」· MH 代码 · 共 955 行 · 第 1/2 页

///////////////////////////////////////////////////////////////////////////
// FILE: vector (Definition of std::vector)
//
:keep CPP_HDR
:include crwatcnt.sp
//
// Description: This header is part of the C++ standard library. It
//              defines a vector template that in many cases can be
//              used as a replacement for C-style arrays.
///////////////////////////////////////////////////////////////////////////
#ifndef _VECTOR_INCLUDED
#define _VECTOR_INCLUDED

:include readonly.sp

#ifndef __cplusplus
  #error The header vector requires C++
#endif

#ifndef _ITERATOR_INCLUDED
  #include <iterator>
#endif

#ifndef _LIMITS_INCLUDED
  #include <limits>
#endif

#ifndef _MEMORY_INCLUDED
  #include <memory>
#endif

#ifndef _STDEXCEPT_INCLUDED
  #include <stdexcep>
#endif

#ifndef _TYPE_TRAITS_INCLUDED
  #include <type_tra>
#endif

namespace std {

template<class Type, class Allocator = allocator< Type > >
class vector {
public:
    typedef typename Allocator::reference       reference;
    typedef typename Allocator::const_reference const_reference;
    typedef typename Allocator::size_type       size_type;
    typedef typename Allocator::difference_type difference_type;
    typedef Type                                value_type;
    typedef Allocator                           allocator_type;
    typedef typename Allocator::pointer         pointer;
    typedef typename Allocator::const_pointer   const_pointer;
    typedef pointer                             iterator;
    typedef const_pointer                       const_iterator;
    typedef reverse_iterator< iterator >        reverse_iterator;
    typedef reverse_iterator< const_iterator >  const_reverse_iterator;

    explicit vector( const Allocator & = Allocator( ) );
    explicit vector( size_type n, const Type &value = Type( ), const Allocator & = Allocator( ) );
    vector( const vector &other );
   ~vector( );
    vector &operator=( const vector &other );
    void assign( size_type n, const Type &value );
    allocator_type get_allocator( ) const;

    iterator               begin( );
    const_iterator         begin( ) const;
    iterator               end( );
    const_iterator         end( ) const;
    reverse_iterator       rbegin( );
    const_reverse_iterator rbegin( ) const;
    reverse_iterator       rend( );
    const_reverse_iterator rend( ) const;

    size_type size( ) const;
    size_type max_size( ) const;
    void      resize( size_type n, Type c = Type( ) );
    size_type capacity( ) const;
    bool      empty( ) const;
    void      reserve( size_type n );

    reference       operator[]( size_type n );
    const_reference operator[]( size_type n ) const;
    reference       at( size_type n );
    const_reference at( size_type n ) const;
    reference       front( );
    const_reference front( ) const;
    reference       back( );
    const_reference back( ) const;

    void     push_back( const Type &x );
    void     pop_back( );
    iterator insert( iterator position, const Type &x );
    void     insert( iterator position, size_type n, const Type &x );
    iterator erase( iterator position );
    iterator erase( iterator first, iterator last );
    void     swap( vector &x );
    void     clear( );

    bool     _Sane( ) const;  // Check invariants.

:: Template Members
:: ----------------
:: These must be inline because the compiler does not currently support
:: the syntax of non-inline template member declarations.

    template< class InputIterator >
    void assign( InputIterator first, InputIterator last )
    {
        helper_assign( first, last, tr1::is_integral<InputIterator>::type() );
    }

    template< class Integral >
    void helper_assign( Integral count,
                        Integral value,
                        tr1::true_type )
    {
        vector temp;
        for( Integral i = 0; i < count; ++i )
            temp.push_back( value );
        swap( temp );
    }

    template< class InputIterator >
    void helper_assign( InputIterator first,
                        InputIterator last,
                        tr1::false_type )
    {
        vector temp;
        while( first != last ) {
            temp.push_back( *first );
            ++first;
        }
        swap( temp );
    }
    
    template< class InputIterator >
    void insert(iterator position, InputIterator first, InputIterator last )
    {
        helper_insert( position,
                       first,
                       last,
                       tr1::is_integral<InputIterator>::type( ) );
    }
    
    template< class Integral >
    void helper_insert( iterator position,
                        Integral count,
                        Integral value,
                        tr1::true_type )
    {
        insert( position,
                static_cast<size_type>( count ),
                static_cast<const Type &>( value ) );
    }
    
    template< class InputIterator >
    void helper_insert( iterator position,
                        InputIterator first,
                        InputIterator last,
                        tr1::false_type )
    {
        while( first != last ) {
            insert( position, *first );
            ++position;
            ++first;
        }
    }

private:
    // 1. buffer has size buf_length.
    // 2. buffer never shrinks (except in ...).
    // 3. buf_length >= vec_length.
    // 4. buf_length is a power of two.
    // 5. buffer allocated with mem or a copy of mem.
    //
    Allocator mem;         // Object used to get and release memory.
    pointer   buffer;      // Pointer to start of buffer space.
    size_type buf_length;  // Total number of buffer slots.
    size_type vec_length;  // Number of buffer slots in use by objects.

    // This method encapsulates the memory allocation policy.
    pointer alloc( size_type required, size_type &found );
};

// ==========================
// Member functions of vector
// ==========================

template< class Type, class Allocator >
vector< Type, Allocator >::pointer
    vector< Type, Allocator >::alloc(
        size_type required,
        size_type &found )
{
    pointer   result;
    size_type length = 16;

    // Find a power of two that produces a sufficient size.
    while( length < required ) length <<= 1;
    result = mem.allocate( length );

    // Update outputs only if allocation successful.
    found = length;
    return( result );
}

// vector( const Allocator & )
// ***************************
template< class Type, class Allocator >
vector< Type, Allocator >::vector( const Allocator &a ) : mem( a )
{
    buffer = alloc(1, buf_length );
    vec_length = 0;
}

// vector( size_type, const Type &, const Allocator & )
//*****************************************************
template< class Type, class Allocator >
vector< Type, Allocator >::vector(
    size_type n,
    const Type &value,
    const Allocator &a ) : mem( a )
{
    buffer = alloc( n, buf_length );
    try {
        uninitialized_fill_n( buffer, n, value );
    }
    catch( ... ) {
        mem.deallocate( buffer, buf_length );
        throw;
    }
    vec_length = n;
}

// vector( const vector & )
// ************************
template< class Type, class Allocator >
vector< Type, Allocator >::vector( const vector &other )
    : mem( other.mem )
{
    buffer = alloc( other.vec_length, buf_length );
    try {
        uninitialized_copy( other.buffer,
                            other.buffer + other.vec_length,
                            buffer );
    }
    catch( ... ) {
        mem.deallocate( buffer, buf_length );
        throw;
    }
    vec_length = other.vec_length;
}

// ~vector( )
// **********
template< class Type, class Allocator >
vector< Type, Allocator >::~vector( )
{
    // Delete objects actually in use and deallocate the buffer.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );
}

// operator=( const vector & )
// ***************************
template< class Type, class Allocator >
vector< Type, Allocator > &vector< Type, Allocator >::operator=(
    const vector &other )
{
    if( this == &other ) return( *this );

    // Don't overwrite our allocator just yet.
    Allocator temp_allocator( other.mem );

    // Allocate buffer space for copy and try to make the copy.
    pointer temp_buffer = temp_allocator.allocate( other.buf_length );
    try {
        uninitialized_copy( other.buffer,
                            other.buffer + other.vec_length,
                            temp_buffer );
    }
    catch( ... ) {
        temp_allocator.deallocate( temp_buffer, other.buf_length );
        throw;
    }

    // New allocation successful.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );

    mem        = temp_allocator;
    buffer     = temp_buffer;
    buf_length = other.buf_length;
    vec_length = other.vec_length;

    return( *this );
}

// assign( size_type, const Type & )
// *********************************
template< class Type, class Allocator >
void vector< Type, Allocator >::assign( size_type n, const Type &value )
{
    // Prepare new buffer space.
    size_type temp_length;
    pointer temp_buffer = alloc( n, temp_length );
    try {
        uninitialized_fill_n( temp_buffer, n, value );
    }
    catch( ... ) {
        mem.deallocate( temp_buffer, temp_length );
        throw;
    }

    // New allocation successful.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );

    buffer     = temp_buffer;
    buf_length = temp_length;
    vec_length = n;
}

// get_allocator( ) const
// **********************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::allocator_type
    vector<Type, Allocator>::get_allocator( ) const
{
    return( mem );
}

// begin( )
// ********
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::iterator
    vector<Type, Allocator>::begin( )
{
    return( buffer );
}

// begin( ) const
// **************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_iterator
    vector<Type, Allocator>::begin( ) const
{
    return( buffer );
}

// end( )
// ******
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::iterator
    vector< Type, Allocator >::end( )
{
    return( buffer + vec_length );
}

// end( ) const
// ************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_iterator
    vector< Type, Allocator >::end( ) const
{
    return( buffer + vec_length );
}

// rbegin( )
// *********
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::reverse_iterator
    vector< Type, Allocator >::rbegin( )
{
    return( reverse_iterator( buffer + vec_length ) );
}

// rbegin( ) const
// ***************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_reverse_iterator
    vector< Type, Allocator >::rbegin( ) const
{
    return( const_reverse_iterator( buffer + vec_length ) );
}

// rend( )
// *******
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::reverse_iterator
    vector< Type, Allocator >::rend( )
{
    return( reverse_iterator( buffer ) );
}

// rend( ) const
// *************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_reverse_iterator
    vector< Type, Allocator >::rend( ) const
{
    return( const_reverse_iterator( buffer ) );
}

// size( ) const
// *************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::size_type
    vector< Type, Allocator >::size( ) const
{
    return( vec_length );
}

// max_size( ) const
// *****************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator>::size_type
    vector< Type, Allocator >::max_size( ) const
{
    return( std::numeric_limits< size_type >::max( ) / sizeof( Type ) );
}

// resize( size_type, Type )
// *************************
template< class Type, class Allocator >
void vector< Type, Allocator >::resize( size_type n, Type c )
{
    if( n > vec_length )
        insert( end( ),
                static_cast<size_type>(n - vec_length),
                static_cast<const Type &>( c ) );
    else if ( n < vec_length )
        erase( begin( ) + n, end( ) );
}

// capacity( ) const
// *****************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::size_type
    vector< Type, Allocator >::capacity( ) const
{
    return( buf_length );
}

// empty( ) const
// **************
template< class Type, class Allocator >
inline
bool vector< Type, Allocator >::empty( ) const
{
    return( vec_length == 0 );
}

// reserve( size_type )
// ********************
template< class Type, class Allocator >
void vector< Type, Allocator>::reserve( size_type new_capacity )
{
    if( new_capacity <= buf_length ) return;