967 lines
26 KiB
Plaintext
967 lines
26 KiB
Plaintext
///////////////////////////////////////////////////////////////////////////
|
|
// FILE: vector (Definition of std::vector)
|
|
//
|
|
// =========================================================================
|
|
//
|
|
// Open Watcom Project
|
|
//
|
|
// Copyright (c) 2004-2010 The Open Watcom Contributors. All Rights Reserved.
|
|
//
|
|
// This file is automatically generated. Do not edit directly.
|
|
//
|
|
// =========================================================================
|
|
//
|
|
// 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
|
|
|
|
#ifndef _ENABLE_AUTODEPEND
|
|
#pragma read_only_file;
|
|
#endif
|
|
|
|
#ifndef __cplusplus
|
|
#error This header file 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 std::reverse_iterator< iterator > reverse_iterator;
|
|
typedef std::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< class InputIterator >
|
|
explicit vector( InputIterator first, InputIterator last, const Allocator &a = Allocator() )
|
|
: mem( a )
|
|
{
|
|
buffer = alloc( 1, buf_length );
|
|
vec_length = 0;
|
|
helper_assign( first, last, tr1::is_integral<InputIterator>::type() );
|
|
}
|
|
|
|
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;
|
|
if( new_capacity > max_size( ) )
|
|
throw length_error( "vector::reserve" );
|
|
|
|
size_type temp_length;
|
|
pointer temp_buffer = alloc( new_capacity, temp_length );
|
|
try {
|
|
uninitialized_copy( buffer, buffer + vec_length, temp_buffer );
|
|
}
|
|
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;
|
|
}
|
|
|
|
// operator[]( size_type )
|
|
// ***********************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
typename vector< Type, Allocator >::reference
|
|
vector< Type, Allocator >::operator[]( size_type n )
|
|
{
|
|
return( buffer[n] );
|
|
}
|
|
|
|
// operator[]( size_type ) const
|
|
// *****************************
|
|
template< class Type, class Allocator >
|
|
inline typename vector< Type, Allocator >::const_reference
|
|
vector< Type, Allocator >::operator[]( size_type n ) const
|
|
{
|
|
return( buffer[n] );
|
|
}
|
|
|
|
// at( size_type )
|
|
// ***************
|
|
template< class Type, class Allocator >
|
|
typename vector< Type, Allocator >::reference
|
|
vector< Type, Allocator >::at( size_type n )
|
|
{
|
|
if( n >= vec_length )
|
|
throw out_of_range( "vector::at" );
|
|
return( buffer[n] );
|
|
}
|
|
|
|
// at( size_type ) const
|
|
// *********************
|
|
template< class Type, class Allocator >
|
|
typename vector< Type, Allocator >::const_reference
|
|
vector< Type, Allocator >::at( size_type n ) const
|
|
{
|
|
if( n >= vec_length )
|
|
throw out_of_range( "vector::at" );
|
|
return( buffer[n] );
|
|
}
|
|
|
|
// front( )
|
|
// ********
|
|
template< class Type, class Allocator >
|
|
inline
|
|
typename vector< Type, Allocator >::reference
|
|
vector< Type, Allocator >::front( )
|
|
{
|
|
return( buffer[0] );
|
|
}
|
|
|
|
// front( ) const
|
|
// **************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
typename vector< Type, Allocator >::const_reference
|
|
vector< Type, Allocator >::front( ) const
|
|
{
|
|
return( buffer[0] );
|
|
}
|
|
|
|
// back( )
|
|
// *******
|
|
template< class Type, class Allocator >
|
|
inline
|
|
typename vector< Type, Allocator >::reference
|
|
vector< Type, Allocator >::back( )
|
|
{
|
|
return( buffer[vec_length - 1] );
|
|
}
|
|
|
|
// back( ) const
|
|
// *************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
typename vector< Type, Allocator >::const_reference
|
|
vector< Type, Allocator >::back( ) const
|
|
{
|
|
return( buffer[vec_length - 1] );
|
|
}
|
|
|
|
// push_back( const Type & )
|
|
// *************************
|
|
template< class Type, class Allocator >
|
|
void vector< Type, Allocator >::push_back( const Type &item )
|
|
{
|
|
if( vec_length + 1 > buf_length ) {
|
|
reserve( buf_length + 1 );
|
|
}
|
|
new ( static_cast<void *>( buffer + vec_length ) ) Type( item );
|
|
++vec_length;
|
|
}
|
|
|
|
// pop_back( )
|
|
// ***********
|
|
template< class Type, class Allocator >
|
|
inline
|
|
void vector< Type, Allocator >::pop_back( )
|
|
{
|
|
mem.destroy( &buffer[vec_length - 1] );
|
|
--vec_length;
|
|
}
|
|
|
|
// insert( iterator, const Type & )
|
|
// ********************************
|
|
template< class Type, class Allocator >
|
|
vector< Type, Allocator >::iterator
|
|
vector< Type, Allocator >::insert( iterator position, const Type &x )
|
|
{
|
|
size_type iposition = static_cast< size_type >( position - buffer );
|
|
size_type tail_count = vec_length - iposition;
|
|
|
|
// Deal with zero length vector as a special case.
|
|
if( vec_length == 0 ) {
|
|
mem.construct( &buffer[0], x );
|
|
vec_length++;
|
|
return( buffer );
|
|
}
|
|
|
|
// Handle case were reallocation isn't necessary.
|
|
if( vec_length + 1 <= buf_length ) {
|
|
mem.construct( &buffer[vec_length], buffer[vec_length - 1] );
|
|
vec_length++;
|
|
for( size_type i = 2; i <= tail_count; ++i ) {
|
|
buffer[vec_length - i] = buffer[vec_length - 1 - i];
|
|
}
|
|
*position = x;
|
|
return( position );
|
|
}
|
|
|
|
// Handle case where reallocation is necessary.
|
|
size_type temp_length;
|
|
pointer temp_buffer = alloc( vec_length + 1, temp_length );
|
|
|
|
size_type copy_count = 0;
|
|
pointer src_iterator = buffer;
|
|
pointer dst_iterator = temp_buffer;
|
|
try {
|
|
while( src_iterator != position ) {
|
|
mem.construct( dst_iterator, *src_iterator );
|
|
++copy_count; ++src_iterator; ++dst_iterator;
|
|
}
|
|
mem.construct( dst_iterator, x );
|
|
++copy_count; ++dst_iterator;
|
|
while( src_iterator != buffer + vec_length ) {
|
|
mem.construct( dst_iterator, *src_iterator );
|
|
++copy_count; ++src_iterator; ++dst_iterator;
|
|
}
|
|
}
|
|
catch( ... ) {
|
|
for( size_type i = 0; i < copy_count; ++i ) {
|
|
mem.destroy( &temp_buffer[i] );
|
|
}
|
|
mem.deallocate( temp_buffer, temp_length );
|
|
throw;
|
|
}
|
|
|
|
// It worked. Commit the new value.
|
|
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++;
|
|
return( buffer + iposition );
|
|
}
|
|
|
|
// insert( iterator, size_type, const Type & )
|
|
// *******************************************
|
|
template< class Type, class Allocator >
|
|
void vector< Type, Allocator >::insert(
|
|
iterator position, size_type n, const Type &x
|
|
)
|
|
{
|
|
size_type iposition = static_cast< size_type >( position - buffer );
|
|
if( n == 0 ) return;
|
|
|
|
// Handle the case where reallocation isn't necessary.
|
|
if( vec_length + n <= buf_length ) {
|
|
|
|
// FIX ME: This code isn't exception safe.
|
|
|
|
// Open a gap of size n.
|
|
size_type copya; // Number of objects needing assignment.
|
|
size_type copyc; // Number of objects needing copy construction.
|
|
|
|
copya = ( iposition + n < vec_length ) ? vec_length - iposition - n : 0;
|
|
copyc = vec_length - iposition - copya;
|
|
|
|
// Copy construct tail of vector into fresh memory.
|
|
uninitialized_copy( position + copya,
|
|
position + copya + copyc,
|
|
position + copya + n );
|
|
|
|
// Assign remaining elements in reverse order.
|
|
iterator src_iterator( position + copya - 1);
|
|
iterator dst_iterator( buffer + vec_length - 1 );
|
|
for( size_type i = 0; i < copya; ++i ) {
|
|
*dst_iterator = *src_iterator;
|
|
--src_iterator; --dst_iterator;
|
|
}
|
|
|
|
// Fill the gap.
|
|
size_type filla; // Number of objects needing assignment.
|
|
size_type fillc; // Number of objects needing copy construction.
|
|
|
|
filla = ( n >= vec_length - iposition ) ? vec_length - iposition : n;
|
|
fillc = n - filla;
|
|
|
|
// Copy construct new objects (if any).
|
|
uninitialized_fill_n( buffer + vec_length, fillc, x );
|
|
|
|
// Assign remaining elements.
|
|
dst_iterator = position;
|
|
for( size_type i = 0; i < filla; ++i ) {
|
|
*dst_iterator = x;
|
|
++dst_iterator;
|
|
}
|
|
|
|
vec_length += copyc + fillc;
|
|
return;
|
|
}
|
|
|
|
// Handle case where reallocation is necessary.
|
|
size_type temp_length;
|
|
pointer temp_buffer = alloc( vec_length + n, temp_length );
|
|
|
|
size_type copy_count = 0;
|
|
pointer src_iterator = buffer;
|
|
pointer dst_iterator = temp_buffer;
|
|
try {
|
|
while( src_iterator != position ) {
|
|
mem.construct( dst_iterator, *src_iterator );
|
|
++copy_count; ++src_iterator; ++dst_iterator;
|
|
}
|
|
for( size_type i = 0; i < n; ++i ) {
|
|
mem.construct( dst_iterator, x );
|
|
++copy_count; ++dst_iterator;
|
|
}
|
|
while( src_iterator != buffer + vec_length ) {
|
|
mem.construct( dst_iterator, *src_iterator );
|
|
++copy_count; ++src_iterator; ++dst_iterator;
|
|
}
|
|
}
|
|
catch( ... ) {
|
|
for( size_type i = 0; i < copy_count; ++i ) {
|
|
mem.destroy( &temp_buffer[i] );
|
|
}
|
|
mem.deallocate( temp_buffer, temp_length );
|
|
throw;
|
|
}
|
|
|
|
// It worked. Commit the new value.
|
|
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 = vec_length + n;
|
|
}
|
|
|
|
// erase( iterator )
|
|
// *****************
|
|
template< class Type, class Allocator >
|
|
typename vector< Type, Allocator >::iterator
|
|
vector< Type, Allocator >::erase( iterator position )
|
|
{
|
|
iterator return_value( position );
|
|
|
|
while( position != buffer + vec_length - 1 ) {
|
|
*position = *( position + 1 );
|
|
++position;
|
|
}
|
|
mem.destroy( position );
|
|
--vec_length;
|
|
return( return_value );
|
|
}
|
|
|
|
// erase( iterator, iterator )
|
|
// ***************************
|
|
template< class Type, class Allocator >
|
|
typename vector< Type, Allocator >::iterator
|
|
vector< Type, Allocator >::erase( iterator first, iterator last )
|
|
{
|
|
iterator return_value( first );
|
|
difference_type removed( last - first );
|
|
|
|
while( last != buffer + vec_length ) {
|
|
*first = *last;
|
|
++first; ++last;
|
|
}
|
|
while( first != buffer + vec_length ) {
|
|
mem.destroy( first );
|
|
++first;
|
|
}
|
|
vec_length -= removed;
|
|
return( return_value );
|
|
}
|
|
|
|
// swap( )
|
|
// *******
|
|
template< class Type, class Allocator >
|
|
void vector< Type, Allocator >::swap( vector &vec )
|
|
{
|
|
typename Allocator::pointer ptemp;
|
|
typename Allocator::size_type stemp;
|
|
Allocator atemp;
|
|
|
|
ptemp = buffer;
|
|
buffer = vec.buffer;
|
|
vec.buffer = ptemp;
|
|
|
|
stemp = buf_length;
|
|
buf_length = vec.buf_length;
|
|
vec.buf_length = stemp;
|
|
|
|
stemp = vec_length;
|
|
vec_length = vec.vec_length;
|
|
vec.vec_length = stemp;
|
|
|
|
atemp = mem;
|
|
mem = vec.mem;
|
|
vec.mem = atemp;
|
|
}
|
|
|
|
// clear( )
|
|
// ********
|
|
template< class Type, class Allocator >
|
|
void vector< Type, Allocator >::clear( )
|
|
{
|
|
// Delete objects actually in use.
|
|
for( size_type i = 0; i < vec_length; ++i ) {
|
|
mem.destroy( &buffer[i] );
|
|
}
|
|
vec_length = 0;
|
|
}
|
|
|
|
// _Sane( ) const
|
|
// **************
|
|
template< class Type, class Allocator >
|
|
bool vector< Type, Allocator >::_Sane( ) const
|
|
{
|
|
if( buf_length == 0 ) return( false );
|
|
if( buf_length < vec_length ) return( false );
|
|
|
|
// Is buf_length a power of 2?
|
|
size_type temp = buf_length;
|
|
while( temp != 1 ) {
|
|
if( temp & 0x1 ) return( false );
|
|
temp >>= 1;
|
|
}
|
|
return( true );
|
|
}
|
|
|
|
// ===============================
|
|
// Ordinary functions using vector
|
|
// ===============================
|
|
|
|
// operator==( const vector &, const vector & )
|
|
// ********************************************
|
|
template< class Type, class Allocator >
|
|
bool operator==(
|
|
const vector< Type, Allocator > &x,
|
|
const vector< Type, Allocator > &y )
|
|
{
|
|
if( x.size( ) != y.size( ) ) return( false );
|
|
|
|
vector< Type, Allocator>::size_type index = 0;
|
|
while( index < x.size( ) ) {
|
|
if( x[index] != y[index] ) return( false );
|
|
++index;
|
|
}
|
|
return( true );
|
|
}
|
|
|
|
// operator!=( const vector &, const vector & )
|
|
// ********************************************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
bool operator!=(
|
|
const vector< Type, Allocator > &x,
|
|
const vector< Type, Allocator > &y )
|
|
{
|
|
return( !(x == y) );
|
|
}
|
|
|
|
// operator<( const vector &, const vector & )
|
|
// *******************************************
|
|
template< class Type, class Allocator >
|
|
bool operator<(
|
|
const vector< Type, Allocator > &x,
|
|
const vector< Type, Allocator > &y )
|
|
{
|
|
vector< Type, Allocator>::size_type index = 0;
|
|
while( index != x.size( ) && index != y.size( ) ) {
|
|
if( x[index] < y[index] ) return( true );
|
|
if( y[index] < x[index] ) return( false );
|
|
++index;
|
|
}
|
|
return( index == x.size( ) && index != y.size( ) );
|
|
}
|
|
|
|
// operator<=( const vector &, const vector & )
|
|
// ********************************************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
bool operator<=(
|
|
const vector< Type, Allocator > &x,
|
|
const vector< Type, Allocator > &y )
|
|
{
|
|
return( !( x > y) );
|
|
}
|
|
|
|
// operator>( const vector &, const vector & )
|
|
// *******************************************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
bool operator>(
|
|
const vector< Type, Allocator > &x,
|
|
const vector< Type, Allocator > &y )
|
|
{
|
|
return( y < x);
|
|
}
|
|
|
|
// operator>=( const vector &, const vector & )
|
|
// ********************************************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
bool operator>=(
|
|
const vector< Type, Allocator > &x,
|
|
const vector< Type, Allocator > &y )
|
|
{
|
|
return( !(x < y) );
|
|
}
|
|
|
|
#ifdef __NEVER
|
|
// swap( vector &, vector & )
|
|
// **************************
|
|
template< class Type, class Allocator >
|
|
inline
|
|
void swap( vector< Type, Allocator > &x, vector< Type, Allocator > &y )
|
|
{
|
|
x.swap( y );
|
|
}
|
|
#endif
|
|
|
|
} // namespace std
|
|
|
|
#endif
|