BANNED
Join Date: May 2015
Location: Wait, where am i again?
|
05-15-2015
, 05:28
Can someone test my c++ code?
|
#1
|
Hello everyone!
I need you to test my code and i want to see your results.
With results i also wish to know:
*used compiler and c++ optimization
*32 or 64bit system?
*If results are alot different than mine then vector source code of yours.
My results:
My c++ optimizations:
Source code:
PHP Code:
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <windows.h>
#include <vector>
#include "common\SparklyVector.h"
LARGE_INTEGER t_start_counter, t_current_counter;
void tstart()
{
QueryPerformanceCounter(&t_start_counter);
}
double tend()
{
QueryPerformanceCounter(&t_current_counter);
double out;
out = (double)(t_current_counter.QuadPart - t_start_counter.QuadPart);
out *= 0.000001;
return out;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a = 0, b = 0;
spvec<int> v;
vector<int> i;
double t1 = 0.0, t2 = 0.0;
v.reservstep_grow = 3.0f;
tstart();
for (a = 0; a < 16777216; a++) v += a + 100;
t1 = tend();
tstart();
for (a = 0; a < 16777216; a++) i.push_back(a + 100);
t2 = tend();
cout << "myvector/defaultvector" << endl;
cout << "reserved:" << v.reservstep << "/" << i.capacity() << endl;
cout << "size:" << v.size << "/" << i.size() << endl;
cout << "times:" << t1 << "/" << t2 << " ration:" << t2 / t1 << endl;
system("pause");
return 0;
}
SparklyVector.h:
PHP Code:
#pragma once
#ifndef SPARKLYVECTOR_H
#define SPARKLYVECTOR_H
template <class T>
class spvec
{
public:
T *data;
int size;
int reserved;
int reservstep;
float reservstep_grow;
spvec()
{
size = 0;
reserved = 0;
reservstep = 1;
data = 0;
reservstep_grow = 1.5f;
}
spvec(int reservstep)
{
size = 0;
reserved = 0;
reservstep = reservstep;
data = 0;
reservstep_grow = 0.0f;
}
spvec(T *indata, int insize)
{
size = insize;
reserved = 0;
reservstep = 1;
data = indata;
reservstep_grow = 1.5f;
}
spvec(T *indata, int insize, int reservstep)
{
size = insize;
reserved = 0;
reservstep = reservstep;
data = indata;
reservstep_grow = 0.0f;
}
~spvec()
{
if( size || reserved ) delete [] data;
}
void destroy()
{
size = 0;
reserved = 0;
delete [] data;
}
void makeroom(int howmuch)
{
if (reservstep_grow > 1.0) reservstep = int((float)size * reservstep_grow);
T *p = new T[size+reserved+howmuch+reservstep];
for( int a = 0; a < size; a++ ) p[a] = data[a];
if(size) delete [] data;
data = p;
reserved += howmuch + reservstep;
}
void takeroom( int howmuch )
{
int needs = reserved - howmuch;
if( needs < 0 ) makeroom(needs / -1);
size += howmuch;
reserved -= howmuch;
}
void trim()
{
T *p = new T[size+reservstep];
for( int a = 0; a < size; a++ ) p[a] = data[a];
if(size) delete [] data;
data = p;
reserved = reservstep;
}
void remove(int pos)
{
reserved++;
for( int a = pos; a < size - 1; a++ ) data[a] = data[a+1];
size--;
}
void remove(int pos, int howmuch)
{
reserved += howmuch;
for( int a = pos; a < size - 1; a++ ) data[a] = data[a+howmuch];
size -= howmuch;
}
void reverse()
{
T temp;
int v = 0;
for( int a = 0; a < size / 2; a++ )
{
v = size - (a + 1);
temp = data[a];
data[a] = data[v];
data[v] = temp;
}
}
void clear()
{
reserved += size;
size = 0;
}
void resize(int newsize)
{
if (newsize == 0)
{
clear();
return;
}
T * t = new T[newsize + reservstep];
int b = size;
if (newsize < size) b = newsize;
if (b) for (int a = 0; a < b; a++) t[a] = data[a];
if (size) delete[] data;
size = b;
data = t;
}
void move( int what, int to )
{
int a; T temp;
if( what > to )
{
temp = data[what];
for( a = what; a > to; a-- ) data[a] = data[a-1];
data[to] = temp;
return;
}
temp = data[what];
for( a = what; a < to; a++ )
{
data[a] = data[a+1];
}
data[to] = temp;
}
void move( int what, int howmuch, int to )
{
howmuch--;
if( what > to )
{
for( int a = 0; a <= howmuch; a++ ) move(what + howmuch, to);
return;
}
for( int a = 0; a <= howmuch; a++ ) move(what, to + howmuch);
}
void push( T in )
{
takeroom( 1 );
data[size - 1] = in;
}
void push( int pos, T in )
{
takeroom(1);
for( int a = size - 2; a >= pos; a-- ) data[a + 1] = data[a];
data[pos] = in;
}
void push(T *in, int insize)
{
int i = size;
takeroom(insize);
for (int a = 0; a < insize; a++) data[i + a] = in[a];
}
void push(int pos, T *in, int insize)
{
int i = size;
takeroom(insize);
int a;
for (a = size - 2; a >= pos; a--) data[a + insize] = data[a];
for (a = pos; a < insize; a++) data[a] = in[a - pos];
}
void swap(int what, int with)
{
T t;
t = data[what];
data[what] = data[with];
data[with] = t;
}
void swap(int start, int end, int to)
{
for (int a = 0; a < end - start; a++) swap(start + a, to + a);
}
const spvec &operator+=(const spvec <T> in)
{
if (!in.size) return (*this);
this->push(in.data, in.size);
return (*this);
}
const spvec &operator-=(const spvec <T> in)
{
if (!in.size) return (*this);
this->push(0, in.data, in.size);
return (*this);
}
const spvec &operator+=(const T in)
{
this->push(in);
return (*this);
}
const spvec &operator%=(int in)
{
this->resize(in);
return (*this);
}
const spvec &operator-=(const int in)
{
this->push(0, in);
return (*this);
}
const spvec &operator=(int in)
{
this->resize(in);
return (*this);
}
T &operator[](int in) const
{
return (*(this->data + in));
}
spvec(spvec <T> &in)
{
cout << "here1" << endl;
if (this == &in)
{
cout << "this == &in" << endl;
return;
}
this->size = in.size;
this->reserved = in.reserved;
this->reservstep = in.reservstep;
if (in.size || in.reserved)
{
this->data = new T[in.size + in.reserved];
for (int a = 0; a < in.size; a++) this->data[a] = in.data[a];
}
}
const spvec <T> &operator=(const spvec <T> &in)
{
cout << "here2" << endl;
if (this == &in)
{
cout << "this == &in" << endl;
return (*this);
}
if (this->size)
{
cout << "clear old" << endl;
delete[] this->data;
}
this->size = in.size;
this->reserved = in.reserved;
this->reservstep = in.reservstep;
if (in.size || in.reserved)
{
this->data = new T[in.size + in.reserved];
for (int a = 0; a < in.size; a++) this->data[a] = in.data[a];
}
return (*this);
}
};
vector ( just in case ):
Code:
// vector standard header
#pragma once
#ifndef _VECTOR_
#define _VECTOR_
#ifndef RC_INVOKED
#include <xmemory>
#include <stdexcept>
#pragma pack(push,_CRT_PACKING)
#pragma warning(push,3)
#pragma push_macro("new")
#undef new
#pragma warning(disable: 4127)
#pragma warning(disable: 4244)
_STD_BEGIN
#define _VECTOR_ORPHAN_RANGE (_ITERATOR_DEBUG_LEVEL == 2)
// TEMPLATE CLASS _Vector_const_iterator
template<class _Myvec>
class _Vector_const_iterator
: public _Iterator012<random_access_iterator_tag,
typename _Myvec::value_type,
typename _Myvec::difference_type,
typename _Myvec::const_pointer,
typename _Myvec::const_reference,
_Iterator_base>
{ // iterator for nonmutable vector
public:
typedef _Vector_const_iterator<_Myvec> _Myiter;
typedef random_access_iterator_tag iterator_category;
typedef typename _Myvec::value_type value_type;
typedef typename _Myvec::difference_type difference_type;
typedef typename _Myvec::const_pointer pointer;
typedef typename _Myvec::const_reference reference;
typedef typename _Myvec::pointer _Tptr;
_Vector_const_iterator()
: _Ptr()
{ // construct with null pointer
}
_Vector_const_iterator(_Tptr _Parg, const _Container_base *_Pvector)
: _Ptr(_Parg)
{ // construct with pointer _Parg
this->_Adopt(_Pvector);
}
typedef pointer _Unchecked_type;
_Myiter& _Rechecked(_Unchecked_type _Right)
{ // reset from unchecked iterator
this->_Ptr = (_Tptr)_Right;
return (*this);
}
_Unchecked_type _Unchecked() const
{ // make an unchecked iterator
return (_Unchecked_type(this->_Ptr));
}
reference operator*() const
{ // return designated object
#if _ITERATOR_DEBUG_LEVEL == 2
if (this->_Getcont() == 0
|| this->_Ptr == 0
|| this->_Ptr < ((_Myvec *)this->_Getcont())->_Myfirst
|| ((_Myvec *)this->_Getcont())->_Mylast <= this->_Ptr)
{ // report error
_DEBUG_ERROR("vector iterator not dereferencable");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(
this->_Ptr != _Tptr()
&& ((_Myvec *)this->_Getcont())->_Myfirst <= this->_Ptr
&& this->_Ptr < ((_Myvec *)this->_Getcont())->_Mylast);
#endif /* _ITERATOR_DEBUG_LEVEL */
_Analysis_assume_(this->_Ptr != _Tptr());
return (*this->_Ptr);
}
pointer operator->() const
{ // return pointer to class object
return (_STD pointer_traits<pointer>::pointer_to(**this));
}
_Myiter& operator++()
{ // preincrement
#if _ITERATOR_DEBUG_LEVEL == 2
if (this->_Getcont() == 0
|| this->_Ptr == 0
|| ((_Myvec *)this->_Getcont())->_Mylast <= this->_Ptr)
{ // report error
_DEBUG_ERROR("vector iterator not incrementable");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(
this->_Ptr != _Tptr()
&& this->_Ptr < ((_Myvec *)this->_Getcont())->_Mylast);
#endif /* _ITERATOR_DEBUG_LEVEL */
++this->_Ptr;
return (*this);
}
_Myiter operator++(int)
{ // postincrement
_Myiter _Tmp = *this;
++*this;
return (_Tmp);
}
_Myiter& operator--()
{ // predecrement
#if _ITERATOR_DEBUG_LEVEL == 2
if (this->_Getcont() == 0
|| this->_Ptr == 0
|| this->_Ptr <= ((_Myvec *)this->_Getcont())->_Myfirst)
{ // report error
_DEBUG_ERROR("vector iterator not decrementable");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(
this->_Ptr != _Tptr()
&& ((_Myvec *)this->_Getcont())->_Myfirst < this->_Ptr);
#endif /* _ITERATOR_DEBUG_LEVEL */
--this->_Ptr;
return (*this);
}
_Myiter operator--(int)
{ // postdecrement
_Myiter _Tmp = *this;
--*this;
return (_Tmp);
}
_Myiter& operator+=(difference_type _Off)
{ // increment by integer
#if _ITERATOR_DEBUG_LEVEL == 2
if (this->_Getcont() == 0
|| this->_Ptr + _Off < ((_Myvec *)this->_Getcont())->_Myfirst
|| ((_Myvec *)this->_Getcont())->_Mylast < this->_Ptr + _Off)
{ // report error
_DEBUG_ERROR("vector iterator + offset out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(
((_Myvec *)this->_Getcont())->_Myfirst <= this->_Ptr + _Off
&& this->_Ptr + _Off <= ((_Myvec *)this->_Getcont())->_Mylast);
#endif /* _ITERATOR_DEBUG_LEVEL */
_Ptr += _Off;
return (*this);
}
_Myiter operator+(difference_type _Off) const
{ // return this + integer
_Myiter _Tmp = *this;
return (_Tmp += _Off);
}
_Myiter& operator-=(difference_type _Off)
{ // decrement by integer
return (*this += -_Off);
}
_Myiter operator-(difference_type _Off) const
{ // return this - integer
_Myiter _Tmp = *this;
return (_Tmp -= _Off);
}
difference_type operator-(const _Myiter& _Right) const
{ // return difference of iterators
_Compat(_Right);
return (this->_Ptr - _Right._Ptr);
}
reference operator[](difference_type _Off) const
{ // subscript
return (*(*this + _Off));
}
bool operator==(const _Myiter& _Right) const
{ // test for iterator equality
_Compat(_Right);
return (this->_Ptr == _Right._Ptr);
}
bool operator!=(const _Myiter& _Right) const
{ // test for iterator inequality
return (!(*this == _Right));
}
bool operator<(const _Myiter& _Right) const
{ // test if this < _Right
_Compat(_Right);
return (this->_Ptr < _Right._Ptr);
}
bool operator>(const _Myiter& _Right) const
{ // test if this > _Right
return (_Right < *this);
}
bool operator<=(const _Myiter& _Right) const
{ // test if this <= _Right
return (!(_Right < *this));
}
bool operator>=(const _Myiter& _Right) const
{ // test if this >= _Right
return (!(*this < _Right));
}
#if _ITERATOR_DEBUG_LEVEL == 2
void _Compat(const _Myiter& _Right) const
{ // test for compatible iterator pair
if (this->_Getcont() == 0
|| this->_Getcont() != _Right._Getcont())
{ // report error
_DEBUG_ERROR("vector iterators incompatible");
_SCL_SECURE_INVALID_ARGUMENT;
}
}
#elif _ITERATOR_DEBUG_LEVEL == 1
void _Compat(const _Myiter& _Right) const
{ // test for compatible iterator pair
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(this->_Getcont() == _Right._Getcont());
}
#else /* _ITERATOR_DEBUG_LEVEL == 0 */
void _Compat(const _Myiter&) const
{ // test for compatible iterator pair
}
#endif /* _ITERATOR_DEBUG_LEVEL */
_Tptr _Ptr; // pointer to element in vector
};
template<class _Myvec> inline
typename _Vector_const_iterator<_Myvec>::_Unchecked_type
_Unchecked(_Vector_const_iterator<_Myvec> _Iter)
{ // convert to unchecked
return (_Iter._Unchecked());
}
template<class _Myvec> inline
_Vector_const_iterator<_Myvec>&
_Rechecked(_Vector_const_iterator<_Myvec>& _Iter,
typename _Vector_const_iterator<_Myvec>
::_Unchecked_type _Right)
{ // convert to checked
return (_Iter._Rechecked(_Right));
}
template<class _Myvec> inline
_Vector_const_iterator<_Myvec> operator+(
typename _Vector_const_iterator<_Myvec>::difference_type _Off,
_Vector_const_iterator<_Myvec> _Next)
{ // add offset to iterator
return (_Next += _Off);
}
// TEMPLATE CLASS _Vector_iterator
template<class _Myvec>
class _Vector_iterator
: public _Vector_const_iterator<_Myvec>
{ // iterator for mutable vector
public:
typedef _Vector_iterator<_Myvec> _Myiter;
typedef _Vector_const_iterator<_Myvec> _Mybase;
typedef random_access_iterator_tag iterator_category;
typedef typename _Myvec::value_type value_type;
typedef typename _Myvec::difference_type difference_type;
typedef typename _Myvec::pointer pointer;
typedef typename _Myvec::reference reference;
_Vector_iterator()
{ // construct with null vector pointer
}
_Vector_iterator(pointer _Parg, const _Container_base *_Pvector)
: _Mybase(_Parg, _Pvector)
{ // construct with pointer _Parg
}
typedef pointer _Unchecked_type;
_Myiter& _Rechecked(_Unchecked_type _Right)
{ // reset from unchecked iterator
this->_Ptr = _Right;
return (*this);
}
_Unchecked_type _Unchecked() const
{ // make an unchecked iterator
return (_Unchecked_type(this->_Ptr));
}
reference operator*() const
{ // return designated object
return ((reference)**(_Mybase *)this);
}
pointer operator->() const
{ // return pointer to class object
return (_STD pointer_traits<pointer>::pointer_to(**this));
}
_Myiter& operator++()
{ // preincrement
++*(_Mybase *)this;
return (*this);
}
_Myiter operator++(int)
{ // postincrement
_Myiter _Tmp = *this;
++*this;
return (_Tmp);
}
_Myiter& operator--()
{ // predecrement
--*(_Mybase *)this;
return (*this);
}
_Myiter operator--(int)
{ // postdecrement
_Myiter _Tmp = *this;
--*this;
return (_Tmp);
}
_Myiter& operator+=(difference_type _Off)
{ // increment by integer
*(_Mybase *)this += _Off;
return (*this);
}
_Myiter operator+(difference_type _Off) const
{ // return this + integer
_Myiter _Tmp = *this;
return (_Tmp += _Off);
}
_Myiter& operator-=(difference_type _Off)
{ // decrement by integer
return (*this += -_Off);
}
_Myiter operator-(difference_type _Off) const
{ // return this - integer
_Myiter _Tmp = *this;
return (_Tmp -= _Off);
}
difference_type operator-(const _Mybase& _Right) const
{ // return difference of iterators
return (*(_Mybase *)this - _Right);
}
reference operator[](difference_type _Off) const
{ // subscript
return (*(*this + _Off));
}
};
template<class _Myvec> inline
typename _Vector_iterator<_Myvec>::_Unchecked_type
_Unchecked(_Vector_iterator<_Myvec> _Iter)
{ // convert to unchecked
return (_Iter._Unchecked());
}
template<class _Myvec> inline
_Vector_iterator<_Myvec>&
_Rechecked(_Vector_iterator<_Myvec>& _Iter,
typename _Vector_iterator<_Myvec>
::_Unchecked_type _Right)
{ // convert to checked
return (_Iter._Rechecked(_Right));
}
template<class _Myvec> inline
_Vector_iterator<_Myvec> operator+(
typename _Vector_iterator<_Myvec>::difference_type _Off,
_Vector_iterator<_Myvec> _Next)
{ // add offset to iterator
return (_Next += _Off);
}
// vector TYPE WRAPPERS
template<class _Value_type,
class _Size_type,
class _Difference_type,
class _Pointer,
class _Const_pointer,
class _Reference,
class _Const_reference>
struct _Vec_iter_types
{ // wraps types needed by iterators
typedef _Value_type value_type;
typedef _Size_type size_type;
typedef _Difference_type difference_type;
typedef _Pointer pointer;
typedef _Const_pointer const_pointer;
typedef _Reference reference;
typedef _Const_reference const_reference;
};
template<class _Ty,
class _Alloc0>
struct _Vec_base_types
{ // types needed for a container base
typedef _Alloc0 _Alloc;
typedef _Vec_base_types<_Ty, _Alloc> _Myt;
typedef _Wrap_alloc<_Alloc> _Alty0;
typedef typename _Alty0::template rebind<_Ty>::other _Alty;
typedef typename _Alty::pointer _Tptr;
typedef typename _Alty::template rebind<_Tptr>::other _Alpty;
typedef typename _If<_Is_simple_alloc<_Alty>::value,
_Simple_types<typename _Alty::value_type>,
_Vec_iter_types<typename _Alty::value_type,
typename _Alty::size_type,
typename _Alty::difference_type,
typename _Alty::pointer,
typename _Alty::const_pointer,
typename _Alty::reference,
typename _Alty::const_reference> >::type
_Val_types;
};
// TEMPLATE CLASS _Vector_val
template<class _Val_types>
class _Vector_val
: public _Container_base
{ // base class for vector to hold data
public:
typedef _Vector_val<_Val_types> _Myt;
typedef typename _Val_types::value_type value_type;
typedef typename _Val_types::size_type size_type;
typedef typename _Val_types::difference_type difference_type;
typedef typename _Val_types::pointer pointer;
typedef typename _Val_types::const_pointer const_pointer;
typedef typename _Val_types::reference reference;
typedef typename _Val_types::const_reference const_reference;
typedef _Vector_iterator<_Myt> iterator;
typedef _Vector_const_iterator<_Myt> const_iterator;
_Vector_val()
{ // initialize values
_Myfirst = pointer();
_Mylast = pointer();
_Myend = pointer();
}
pointer _Myfirst; // pointer to beginning of array
pointer _Mylast; // pointer to current end of sequence
pointer _Myend; // pointer to end of array
};
// TEMPLATE CLASS _Vector_alloc
template<bool _Al_has_storage,
class _Alloc_types>
class _Vector_alloc
: public _Vector_val<typename _Alloc_types::_Val_types>
{ // base class for vector to hold allocator with storage
public:
typename _Alloc_types::_Alty _Alval; // allocator object
typedef _Vector_alloc<_Al_has_storage, _Alloc_types> _Myt;
typedef typename _Alloc_types::_Alloc _Alloc;
typedef typename _Alloc_types::_Alty _Alty;
#if _ITERATOR_DEBUG_LEVEL == 0
_Vector_alloc(const _Alloc& _Al = _Alloc())
: _Alval(_Al)
{ // construct allocator from _Al
}
void _Change_alloc(const _Alty& _Al)
{ // replace old allocator
this->_Alval = _Al;
}
void _Swap_alloc(_Myt& _Right)
{ // swap allocators
_Swap_adl(this->_Alval, _Right._Alval);
}
#else /* _ITERATOR_DEBUG_LEVEL == 0 */
_Vector_alloc(const _Alty& _Al = _Alty())
: _Alval(_Al)
{ // construct allocator from _Al
_Alloc_proxy();
}
~_Vector_alloc() _NOEXCEPT
{ // destroy proxy
_Free_proxy();
}
void _Change_alloc(const _Alty& _Al)
{ // replace old allocator
_Free_proxy();
this->_Alval = _Al;
_Alloc_proxy();
}
void _Swap_alloc(_Myt& _Right)
{ // swap allocators
_Swap_adl(this->_Alval, _Right._Alval);
_Swap_adl(this->_Myproxy, _Right._Myproxy);
}
void _Alloc_proxy()
{ // construct proxy from _Alval
typename _Alty::template rebind<_Container_proxy>::other
_Alproxy(this->_Alval);
this->_Myproxy = _Alproxy.allocate(1);
_Alproxy.construct(this->_Myproxy, _Container_proxy());
this->_Myproxy->_Mycont = this;
}
void _Free_proxy()
{ // destroy proxy
typename _Alty::template rebind<_Container_proxy>::other
_Alproxy(this->_Alval);
this->_Orphan_all();
_Alproxy.destroy(this->_Myproxy);
_Alproxy.deallocate(this->_Myproxy, 1);
this->_Myproxy = 0;
}
#endif /* _ITERATOR_DEBUG_LEVEL == 0 */
_Alty& _Getal()
{ // get reference to allocator
return (this->_Alval);
}
const _Alty& _Getal() const
{ // get reference to allocator
return (this->_Alval);
}
};
template<class _Alloc_types>
class _Vector_alloc<false, _Alloc_types>
: public _Vector_val<typename _Alloc_types::_Val_types>
{ // base class for vector to hold allocator with no storage
public:
typedef _Vector_alloc<false, _Alloc_types> _Myt;
typedef typename _Alloc_types::_Alloc _Alloc;
typedef typename _Alloc_types::_Alty _Alty;
#if _ITERATOR_DEBUG_LEVEL == 0
_Vector_alloc(const _Alloc& = _Alloc())
{ // construct allocator from _Al
}
void _Change_alloc(const _Alty&)
{ // replace old allocator
}
void _Swap_alloc(_Myt&)
{ // swap allocators
}
#else /* _ITERATOR_DEBUG_LEVEL == 0 */
_Vector_alloc(const _Alloc& = _Alloc())
{ // construct allocator from _Al
_Alloc_proxy();
}
~_Vector_alloc() _NOEXCEPT
{ // destroy proxy
_Free_proxy();
}
void _Change_alloc(const _Alty&)
{ // replace old allocator
}
void _Swap_alloc(_Myt& _Right)
{ // swap allocators
_Swap_adl(this->_Myproxy, _Right._Myproxy);
}
void _Alloc_proxy()
{ // construct proxy from _Alval
typename _Alty::template rebind<_Container_proxy>::other
_Alproxy;
this->_Myproxy = _Alproxy.allocate(1);
_Alproxy.construct(this->_Myproxy, _Container_proxy());
this->_Myproxy->_Mycont = this;
}
void _Free_proxy()
{ // destroy proxy
typename _Alty::template rebind<_Container_proxy>::other
_Alproxy;
this->_Orphan_all();
_Alproxy.destroy(this->_Myproxy);
_Alproxy.deallocate(this->_Myproxy, 1);
this->_Myproxy = 0;
}
#endif /* _ITERATOR_DEBUG_LEVEL == 0 */
_Alty _Getal() const
{ // get reference to allocator
return (_Alty());
}
};
// TEMPLATE CLASS vector
template<class _Ty,
class _Alloc = allocator<_Ty> >
class vector
: public _Vector_alloc<!is_empty<_Alloc>::value,
_Vec_base_types<_Ty, _Alloc> >
{ // varying size array of values
public:
typedef vector<_Ty, _Alloc> _Myt;
typedef _Vector_alloc<!is_empty<_Alloc>::value,
_Vec_base_types<_Ty, _Alloc> > _Mybase;
typedef _Alloc allocator_type;
typedef typename _Mybase::_Alty _Alty;
typedef typename _Mybase::value_type value_type;
typedef typename _Mybase::size_type size_type;
typedef typename _Mybase::difference_type difference_type;
typedef typename _Mybase::pointer pointer;
typedef typename _Mybase::const_pointer const_pointer;
typedef typename _Mybase::reference reference;
typedef typename _Mybase::const_reference const_reference;
#define _VICONT(it) it._Getcont()
#define _VIPTR(it) (it)._Ptr
typedef typename _Mybase::iterator iterator;
typedef typename _Mybase::const_iterator const_iterator;
typedef _STD reverse_iterator<iterator> reverse_iterator;
typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;
vector()
: _Mybase()
{ // construct empty vector
}
explicit vector(const _Alloc& _Al)
: _Mybase(_Al)
{ // construct empty vector, allocator
}
explicit vector(size_type _Count)
: _Mybase()
{ // construct from _Count * value_type()
if (_Buy(_Count))
{ // nonzero, fill it
_Alty _Alval(this->_Getal());
_TRY_BEGIN
_Uninitialized_default_fill_n(this->_Myfirst, _Count, _Alval);
this->_Mylast += _Count;
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
}
vector(size_type _Count, const value_type& _Val)
: _Mybase()
{ // construct from _Count * _Val
_Construct_n(_Count, _STD addressof(_Val));
}
vector(size_type _Count, const value_type& _Val, const _Alloc& _Al)
: _Mybase(_Al)
{ // construct from _Count * _Val, allocator
_Construct_n(_Count, _STD addressof(_Val));
}
vector(const _Myt& _Right)
: _Mybase(_Right._Getal().select_on_container_copy_construction())
{ // construct by copying _Right
if (_Buy(_Right.size()))
_TRY_BEGIN
this->_Mylast = _Ucopy(_Right.begin(), _Right.end(),
this->_Myfirst);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
vector(const _Myt& _Right, const _Alloc& _Al)
: _Mybase(_Al)
{ // construct by copying _Right, allocator
if (_Buy(_Right.size()))
_TRY_BEGIN
this->_Mylast = _Ucopy(_Right.begin(), _Right.end(),
this->_Myfirst);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
template<class _Iter,
class = typename enable_if<_Is_iterator<_Iter>::value,
void>:: type>
vector(_Iter _First, _Iter _Last)
: _Mybase()
{ // construct from [_First, _Last)
_Construct(_First, _Last);
}
template<class _Iter,
class = typename enable_if<_Is_iterator<_Iter>::value,
void>:: type>
vector(_Iter _First, _Iter _Last, const _Alloc& _Al)
: _Mybase(_Al)
{ // construct from [_First, _Last) with allocator
_Construct(_First, _Last);
}
template<class _Iter>
void _Construct(_Iter _First, _Iter _Last)
{ // initialize with [_First, _Last)
_Construct(_First, _Last, _Iter_cat(_First));
}
template<class _Iter>
void _Construct(_Iter _First, _Iter _Last, input_iterator_tag)
{ // initialize with [_First, _Last), input iterators
_TRY_BEGIN
for (; _First != _Last; ++_First)
emplace_back(*_First);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
template<class _Iter>
void _Construct(_Iter _First, _Iter _Last, forward_iterator_tag)
{ // initialize with [_First, _Last), forward iterators
if (_Buy(_STD distance(_First, _Last)))
{ // nonzero, fill it
_TRY_BEGIN
this->_Mylast = _Ucopy(_First, _Last, this->_Myfirst);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
}
void _Construct_n(size_type _Count, const value_type *_Pval)
{ // construct from _Count * *_Pval
if (_Buy(_Count))
{ // nonzero, fill it
_TRY_BEGIN
this->_Mylast = _Ufill(this->_Myfirst, _Count, _Pval);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
}
vector(_Myt&& _Right)
: _Mybase(_Right._Getal())
{ // construct by moving _Right
_Assign_rv(_STD forward<_Myt>(_Right), true_type());
}
vector(_Myt&& _Right, const _Alloc& _Al)
: _Mybase(_Al)
{ // construct by moving _Right, allocator
_Assign_rv(_STD forward<_Myt>(_Right));
}
_Myt& operator=(_Myt&& _Right)
{ // assign by moving _Right
if (this != &_Right)
{ // different, assign it
_Tidy();
if (_Alty::propagate_on_container_move_assignment::value
&& this->_Getal() != _Right._Getal())
this->_Change_alloc(_Right._Getal());
_Assign_rv(_STD forward<_Myt>(_Right));
}
return (*this);
}
void _Assign_rv(_Myt&& _Right, true_type)
{ // move from _Right, stealing its contents
this->_Swap_all((_Myt&)_Right);
this->_Myfirst = _Right._Myfirst;
this->_Mylast = _Right._Mylast;
this->_Myend = _Right._Myend;
_Right._Myfirst = pointer();
_Right._Mylast = pointer();
_Right._Myend = pointer();
}
void _Assign_rv(_Myt&& _Right, false_type)
{ // move from _Right, possibly moving its contents
if (get_allocator() == _Right.get_allocator())
_Assign_rv(_STD forward<_Myt>(_Right), true_type());
else
_Construct(_STD make_move_iterator(_Right.begin()),
_STD make_move_iterator(_Right.end()));
}
void _Assign_rv(_Myt&& _Right)
{ // assign by moving _Right
_Assign_rv(_STD forward<_Myt>(_Right),
typename _Alty::propagate_on_container_move_assignment());
}
void push_back(value_type&& _Val)
{ // insert by moving into element at end
if (_Inside(_STD addressof(_Val)))
{ // push back an element
size_type _Idx = _STD addressof(_Val) - this->_Myfirst;
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
this->_Getal().construct(this->_Mylast,
_STD forward<value_type>(this->_Myfirst[_Idx]));
++this->_Mylast;
}
else
{ // push back a non-element
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
this->_Getal().construct(this->_Mylast,
_STD forward<value_type>(_Val));
++this->_Mylast;
}
}
iterator insert(const_iterator _Where, _Ty&& _Val)
{ // insert by moving _Val at _Where
return (emplace(_Where, _STD move(_Val)));
}
template<class... _Valty>
void emplace_back(_Valty&&... _Val)
{ // insert by moving into element at end
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
this->_Getal().construct(this->_Mylast,
_STD forward<_Valty>(_Val)...);
++this->_Mylast;
}
template<class... _Valty>
iterator emplace(const_iterator _Where, _Valty&&... _Val)
{ // insert by moving _Val at _Where
size_type _Off = _VIPTR(_Where) - this->_Myfirst;
#if _ITERATOR_DEBUG_LEVEL == 2
if (size() < _Off)
_DEBUG_ERROR("vector emplace iterator outside range");
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
emplace_back(_STD forward<_Valty>(_Val)...);
_STD rotate(begin() + _Off, end() - 1, end());
return (begin() + _Off);
}
vector(_XSTD initializer_list<value_type> _Ilist,
const _Alloc& _Al = allocator_type())
: _Mybase(_Al)
{ // construct from initializer_list
insert(begin(), _Ilist.begin(), _Ilist.end());
}
_Myt& operator=(_XSTD initializer_list<value_type> _Ilist)
{ // assign initializer_list
assign(_Ilist.begin(), _Ilist.end());
return (*this);
}
void assign(_XSTD initializer_list<value_type> _Ilist)
{ // assign initializer_list
assign(_Ilist.begin(), _Ilist.end());
}
iterator insert(const_iterator _Where,
_XSTD initializer_list<value_type> _Ilist)
{ // insert initializer_list
return (insert(_Where, _Ilist.begin(), _Ilist.end()));
}
~vector() _NOEXCEPT
{ // destroy the object
_Tidy();
}
_Myt& operator=(const _Myt& _Right)
{ // assign _Right
if (this != &_Right)
{ // different, assign it
if (this->_Getal() != _Right._Getal()
&& _Alty::propagate_on_container_copy_assignment::value)
{ // change allocator before copying
_Tidy();
this->_Change_alloc(_Right._Getal());
}
this->_Orphan_all();
if (_Right.empty())
clear(); // new sequence empty, erase existing sequence
else if (_Right.size() <= size())
{ // enough elements, copy new and destroy old
pointer _Ptr = _Copy_impl(_Right._Myfirst,
_Right._Mylast, this->_Myfirst); // copy new
_Destroy(_Ptr, this->_Mylast); // destroy old
this->_Mylast = this->_Myfirst + _Right.size();
}
else if (_Right.size() <= capacity())
{ // enough room, copy and construct new
pointer _Ptr = _Right._Myfirst + size();
_Copy_impl(_Right._Myfirst,
_Ptr, this->_Myfirst);
this->_Mylast = _Ucopy(_Ptr, _Right._Mylast, this->_Mylast);
}
else
{ // not enough room, allocate new array and construct new
if (this->_Myfirst != pointer())
{ // discard old array
_Destroy(this->_Myfirst, this->_Mylast);
this->_Getal().deallocate(this->_Myfirst,
this->_Myend - this->_Myfirst);
}
if (_Buy(_Right.size()))
_TRY_BEGIN
this->_Mylast = _Ucopy(_Right._Myfirst, _Right._Mylast,
this->_Myfirst);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
}
return (*this);
}
void reserve(size_type _Count)
{ // determine new minimum length of allocated storage
if (capacity() < _Count)
{ // something to do, check and reallocate
if (max_size() < _Count)
_Xlen();
_Reallocate(_Count);
}
}
size_type capacity() const _NOEXCEPT
{ // return current length of allocated storage
return (this->_Myend - this->_Myfirst);
}
size_type _Unused_capacity() const _NOEXCEPT
{ // micro-optimization for capacity() - size()
return (this->_Myend - this->_Mylast);
}
size_type _Has_unused_capacity() const _NOEXCEPT
{ // micro-optimization for capacity() != size()
return (this->_Myend != this->_Mylast);
}
iterator begin() _NOEXCEPT
{ // return iterator for beginning of mutable sequence
return (iterator(this->_Myfirst, this));
}
const_iterator begin() const _NOEXCEPT
{ // return iterator for beginning of nonmutable sequence
return (const_iterator(this->_Myfirst, this));
}
iterator end() _NOEXCEPT
{ // return iterator for end of mutable sequence
return (iterator(this->_Mylast, this));
}
const_iterator end() const _NOEXCEPT
{ // return iterator for end of nonmutable sequence
return (const_iterator(this->_Mylast, this));
}
iterator _Make_iter(const_iterator _Where) const
{ // make iterator from const_iterator
return (iterator(_Where._Ptr, this));
}
reverse_iterator rbegin() _NOEXCEPT
{ // return iterator for beginning of reversed mutable sequence
return (reverse_iterator(end()));
}
const_reverse_iterator rbegin() const _NOEXCEPT
{ // return iterator for beginning of reversed nonmutable sequence
return (const_reverse_iterator(end()));
}
reverse_iterator rend() _NOEXCEPT
{ // return iterator for end of reversed mutable sequence
return (reverse_iterator(begin()));
}
const_reverse_iterator rend() const _NOEXCEPT
{ // return iterator for end of reversed nonmutable sequence
return (const_reverse_iterator(begin()));
}
const_iterator cbegin() const _NOEXCEPT
{ // return iterator for beginning of nonmutable sequence
return (((const _Myt *)this)->begin());
}
const_iterator cend() const _NOEXCEPT
{ // return iterator for end of nonmutable sequence
return (((const _Myt *)this)->end());
}
const_reverse_iterator crbegin() const _NOEXCEPT
{ // return iterator for beginning of reversed nonmutable sequence
return (((const _Myt *)this)->rbegin());
}
const_reverse_iterator crend() const _NOEXCEPT
{ // return iterator for end of reversed nonmutable sequence
return (((const _Myt *)this)->rend());
}
void shrink_to_fit()
{ // reduce capacity
if (_Has_unused_capacity())
{ // worth shrinking, do it
if (empty())
_Tidy();
else
_Reallocate(size());
}
}
void resize(size_type _Newsize)
{ // determine new length, padding as needed
if (_Newsize < size())
_Pop_back_n(size() - _Newsize);
else if (size() < _Newsize)
{ // pad as needed
_Alty _Alval(this->_Getal());
_Reserve(_Newsize - size());
_TRY_BEGIN
_Uninitialized_default_fill_n(this->_Mylast, _Newsize - size(),
_Alval);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
this->_Mylast += _Newsize - size();
}
}
void resize(size_type _Newsize, const value_type& _Val)
{ // determine new length, padding with _Val elements as needed
if (_Newsize < size())
_Pop_back_n(size() - _Newsize);
else if (size() < _Newsize)
{ // pad as needed
const value_type *_Ptr = _STD addressof(_Val);
if (_Inside(_Ptr))
{ // padding is inside vector, recompute _Ptr after reserve
const difference_type _Idx = _Ptr
- _STD addressof(*this->_Myfirst);
_Reserve(_Newsize - size());
_Ptr = _STD addressof(*this->_Myfirst) + _Idx;
}
else
_Reserve(_Newsize - size());
_TRY_BEGIN
_Ufill(this->_Mylast, _Newsize - size(), _Ptr);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
this->_Mylast += _Newsize - size();
}
}
size_type size() const _NOEXCEPT
{ // return length of sequence
return (this->_Mylast - this->_Myfirst);
}
size_type max_size() const _NOEXCEPT
{ // return maximum possible length of sequence
return (this->_Getal().max_size());
}
bool empty() const _NOEXCEPT
{ // test if sequence is empty
return (this->_Myfirst == this->_Mylast);
}
_Alloc get_allocator() const _NOEXCEPT
{ // return allocator object for values
return (this->_Getal());
}
const_reference at(size_type _Pos) const
{ // subscript nonmutable sequence with checking
if (size() <= _Pos)
_Xran();
return (*(this->_Myfirst + _Pos));
}
reference at(size_type _Pos)
{ // subscript mutable sequence with checking
if (size() <= _Pos)
_Xran();
return (*(this->_Myfirst + _Pos));
}
const_reference operator[](size_type _Pos) const
{ // subscript nonmutable sequence
#if _ITERATOR_DEBUG_LEVEL == 2
if (size() <= _Pos)
{ // report error
_DEBUG_ERROR("vector subscript out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
#endif /* _ITERATOR_DEBUG_LEVEL */
return (*(this->_Myfirst + _Pos));
}
reference operator[](size_type _Pos)
{ // subscript mutable sequence
#if _ITERATOR_DEBUG_LEVEL == 2
if (size() <= _Pos)
{ // report error
_DEBUG_ERROR("vector subscript out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
#endif /* _ITERATOR_DEBUG_LEVEL */
return (*(this->_Myfirst + _Pos));
}
pointer data() _NOEXCEPT
{ // return address of first element
return (this->_Myfirst);
}
const_pointer data() const _NOEXCEPT
{ // return address of first element
return (this->_Myfirst);
}
reference front()
{ // return first element of mutable sequence
return (*begin());
}
const_reference front() const
{ // return first element of nonmutable sequence
return (*begin());
}
reference back()
{ // return last element of mutable sequence
return (*(end() - 1));
}
const_reference back() const
{ // return last element of nonmutable sequence
return (*(end() - 1));
}
void push_back(const value_type& _Val)
{ // insert element at end
if (_Inside(_STD addressof(_Val)))
{ // push back an element
size_type _Idx = _STD addressof(_Val) - this->_Myfirst;
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
this->_Getal().construct(this->_Mylast,
this->_Myfirst[_Idx]);
++this->_Mylast;
}
else
{ // push back a non-element
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
this->_Getal().construct(this->_Mylast,
_Val);
++this->_Mylast;
}
}
#if _ITERATOR_DEBUG_LEVEL == 2
void pop_back()
{ // erase element at end
if (empty())
_DEBUG_ERROR("vector empty before pop");
else
{ // erase last element
_Orphan_range(this->_Mylast - 1, this->_Mylast);
this->_Getal().destroy(this->_Mylast - 1);
--this->_Mylast;
}
}
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
void pop_back()
{ // erase element at end
this->_Getal().destroy(this->_Mylast - 1);
--this->_Mylast;
}
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
template<class _Iter>
typename enable_if<_Is_iterator<_Iter>::value,
void>::type
assign(_Iter _First, _Iter _Last)
{ // assign [_First, _Last)
clear();
_Assign(_First, _Last, _Iter_cat(_First));
}
template<class _Iter>
void _Assign(_Iter _First, _Iter _Last, input_iterator_tag)
{ // assign [_First, _Last), input iterators
for (; _First != _Last; ++_First)
emplace_back(*_First);
}
template<class _Iter>
void _Assign(_Iter _First, _Iter _Last, forward_iterator_tag)
{ // assign [_First, _Last), forward iterators
if (_First == _Last)
return; // nothing to do
size_type _Newsize = _STD distance(_First, _Last);
if (capacity() < _Newsize)
{ // need more room, try to get it
size_type _Newcapacity = _Grow_to(_Newsize);
_Tidy();
_Buy(_Newcapacity);
}
this->_Mylast = _Ucopy(_First, _Last, this->_Myfirst);
}
void assign(size_type _Count, const value_type& _Val)
{ // assign _Count * _Val
clear();
insert(begin(), _Count, _Val);
}
iterator insert(const_iterator _Where, const _Ty& _Val)
{ // insert _Val at _Where
return (_Insert_n(_Where, (size_type)1, _Val));
}
iterator insert(const_iterator _Where, size_type _Count,
const _Ty& _Val)
{ // insert _Count * _Val at _Where
return (_Insert_n(_Where, _Count, _Val));
}
template<class _Iter>
typename enable_if<_Is_iterator<_Iter>::value,
iterator>::type
insert(const_iterator _Where, _Iter _First, _Iter _Last)
{ // insert [_First, _Last) at _Where
size_type _Off = _VIPTR(_Where) - this->_Myfirst;
_Insert(_Where, _First, _Last, _Iter_cat(_First));
return (begin() + _Off);
}
template<class _Iter>
void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
input_iterator_tag)
{ // insert [_First, _Last) at _Where, input iterators
size_type _Off = _VIPTR(_Where) - this->_Myfirst;
#if _ITERATOR_DEBUG_LEVEL == 2
if (size() < _Off)
_DEBUG_ERROR("vector insert iterator outside range");
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
if (_First != _Last)
{ // worth doing, gather at end and rotate into place
size_type _Oldsize = size();
_TRY_BEGIN
for (; _First != _Last; ++_First)
push_back(*_First); // append
_CATCH_ALL
erase(begin() + _Oldsize, end());
_RERAISE;
_CATCH_END
_STD rotate(begin() + _Off, begin() + _Oldsize, end());
}
}
template<class _Iter>
void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
forward_iterator_tag)
{ // insert [_First, _Last) at _Where, forward iterators
#if _ITERATOR_DEBUG_LEVEL == 2
if (_VICONT(_Where) != this
|| _VIPTR(_Where) < this->_Myfirst
|| this->_Mylast < _VIPTR(_Where))
_DEBUG_ERROR("vector insert iterator outside range");
_DEBUG_RANGE(_First, _Last);
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
size_type _Count = 0;
_Distance(_First, _Last, _Count);
if (_Count == 0)
;
else if (_Unused_capacity() < _Count)
{ // not enough room, reallocate
if (max_size() - size() < _Count)
_Xlen(); // result too long
size_type _Capacity = _Grow_to(size() + _Count);
pointer _Newvec = this->_Getal().allocate(_Capacity);
pointer _Ptr = _Newvec;
_TRY_BEGIN
_Ptr = _Umove(this->_Myfirst, _VIPTR(_Where),
_Newvec); // copy prefix
_Ptr = _Ucopy(_First, _Last, _Ptr); // add new stuff
_Umove(_VIPTR(_Where), this->_Mylast,
_Ptr); // copy suffix
_CATCH_ALL
_Destroy(_Newvec, _Ptr);
this->_Getal().deallocate(_Newvec, _Capacity);
_RERAISE;
_CATCH_END
_Count += size();
if (this->_Myfirst != pointer())
{ // destroy and deallocate old array
_Destroy(this->_Myfirst, this->_Mylast);
this->_Getal().deallocate(this->_Myfirst,
this->_Myend - this->_Myfirst);
}
this->_Orphan_all();
this->_Myend = _Newvec + _Capacity;
this->_Mylast = _Newvec + _Count;
this->_Myfirst = _Newvec;
}
else
{ // new stuff fits, append and rotate into place
_Ucopy(_First, _Last, this->_Mylast);
_STD rotate(_VIPTR(_Where), this->_Mylast,
this->_Mylast + _Count);
this->_Mylast += _Count;
_Orphan_range(_VIPTR(_Where), this->_Mylast);
}
}
#if _ITERATOR_DEBUG_LEVEL == 2
iterator erase(const_iterator _Where)
{ // erase element at where
if (_VICONT(_Where) != this
|| _VIPTR(_Where) < this->_Myfirst
|| this->_Mylast <= _VIPTR(_Where))
_DEBUG_ERROR("vector erase iterator outside range");
_Move(_VIPTR(_Where) + 1, this->_Mylast, _VIPTR(_Where));
_Destroy(this->_Mylast - 1, this->_Mylast);
_Orphan_range(_VIPTR(_Where), this->_Mylast);
--this->_Mylast;
return (_Make_iter(_Where));
}
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
iterator erase(const_iterator _Where)
{ // erase element at where
_Move(_VIPTR(_Where) + 1, this->_Mylast,
_VIPTR(_Where));
_Destroy(this->_Mylast - 1, this->_Mylast);
--this->_Mylast;
return (_Make_iter(_Where));
}
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
iterator erase(const_iterator _First_arg,
const_iterator _Last_arg)
{ // erase [_First, _Last)
if (_First_arg == begin() && _Last_arg == end())
clear();
else if (_First_arg != _Last_arg)
{ // clear partial
iterator _First = _Make_iter(_First_arg);
iterator _Last = _Make_iter(_Last_arg);
if (_First != _Last)
{ // worth doing, copy down over hole
#if _ITERATOR_DEBUG_LEVEL == 2
if (_Last < _First || _VICONT(_First) != this
|| _VIPTR(_First) < this->_Myfirst
|| this->_Mylast < _VIPTR(_Last))
_DEBUG_ERROR("vector erase iterator outside range");
pointer _Ptr = _Move(_VIPTR(_Last), this->_Mylast,
_VIPTR(_First));
_Orphan_range(_VIPTR(_First), this->_Mylast);
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
pointer _Ptr = _Move(_VIPTR(_Last), this->_Mylast,
_VIPTR(_First));
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
_Destroy(_Ptr, this->_Mylast);
this->_Mylast = _Ptr;
}
}
return (_Make_iter(_First_arg));
}
void _Pop_back_n(size_type _Count)
{ // erase _Count elements at end
pointer _Ptr = this->_Mylast - _Count;
#if _ITERATOR_DEBUG_LEVEL == 2
_Orphan_range(_Ptr, this->_Mylast);
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
_Destroy(_Ptr, this->_Mylast);
this->_Mylast = _Ptr;
}
void clear() _NOEXCEPT
{ // erase all
this->_Orphan_all();
_Destroy(this->_Myfirst, this->_Mylast);
this->_Mylast = this->_Myfirst;
}
void swap(_Myt& _Right)
{ // exchange contents with _Right
if (this == &_Right)
; // same object, do nothing
else if (this->_Getal() == _Right._Getal())
{ // same allocator, swap control information
this->_Swap_all(_Right);
_Swap_adl(this->_Myfirst, _Right._Myfirst);
_Swap_adl(this->_Mylast, _Right._Mylast);
_Swap_adl(this->_Myend, _Right._Myend);
}
else if (_Alty::propagate_on_container_swap::value)
{ // swap allocators and control information
this->_Swap_alloc(_Right);
_Swap_adl(this->_Myfirst, _Right._Myfirst);
_Swap_adl(this->_Mylast, _Right._Mylast);
_Swap_adl(this->_Myend, _Right._Myend);
}
else
{ // containers are incompatible
#if _ITERATOR_DEBUG_LEVEL == 2
_DEBUG_ERROR("vector containers incompatible for swap");
#else /* ITERATOR_DEBUG_LEVEL == 2 */
_XSTD terminate();
#endif /* ITERATOR_DEBUG_LEVEL == 2 */
}
}
protected:
bool _Buy(size_type _Capacity)
{ // allocate array with _Capacity elements
this->_Myfirst = pointer();
this->_Mylast = pointer();
this->_Myend = pointer();
if (_Capacity == 0)
return (false);
else if (max_size() < _Capacity)
_Xlen(); // result too long
else
{ // nonempty array, allocate storage
this->_Myfirst = this->_Getal().allocate(_Capacity);
this->_Mylast = this->_Myfirst;
this->_Myend = this->_Myfirst + _Capacity;
}
return (true);
}
void _Destroy(pointer _First, pointer _Last)
{ // destroy [_First, _Last) using allocator
_Alty _Alval(this->_Getal());
_Destroy_range(_First, _Last, _Alval);
}
size_type _Grow_to(size_type _Count) const
{ // grow by 50% or at least to _Count
size_type _Capacity = capacity();
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2; // try to grow by 50%
if (_Capacity < _Count)
_Capacity = _Count;
return (_Capacity);
}
bool _Inside(const value_type *_Ptr) const
{ // test if _Ptr points inside vector
return (_Ptr < this->_Mylast && this->_Myfirst <= _Ptr);
}
void _Reallocate(size_type _Count)
{ // move to array of exactly _Count elements
pointer _Ptr = this->_Getal().allocate(_Count);
_TRY_BEGIN
_Umove(this->_Myfirst, this->_Mylast, _Ptr);
_CATCH_ALL
this->_Getal().deallocate(_Ptr, _Count);
_RERAISE;
_CATCH_END
size_type _Size = size();
if (this->_Myfirst != pointer())
{ // destroy and deallocate old array
_Destroy(this->_Myfirst, this->_Mylast);
this->_Getal().deallocate(this->_Myfirst,
this->_Myend - this->_Myfirst);
}
this->_Orphan_all();
this->_Myend = _Ptr + _Count;
this->_Mylast = _Ptr + _Size;
this->_Myfirst = _Ptr;
}
void _Reserve(size_type _Count)
{ // ensure room for _Count new elements, grow exponentially
if (_Unused_capacity() < _Count)
{ // need more room, try to get it
if (max_size() - size() < _Count)
_Xlen();
_Reallocate(_Grow_to(size() + _Count));
}
}
void _Tidy()
{ // free all storage
if (this->_Myfirst != pointer())
{ // something to free, destroy and deallocate it
this->_Orphan_all();
_Destroy(this->_Myfirst, this->_Mylast);
this->_Getal().deallocate(this->_Myfirst,
this->_Myend - this->_Myfirst);
this->_Myfirst = pointer();
this->_Mylast = pointer();
this->_Myend = pointer();
}
}
template<class _Iter>
pointer _Ucopy(_Iter _First, _Iter _Last, pointer _Ptr)
{ // copy initializing [_First, _Last), using allocator
_Alty _Alval(this->_Getal());
return (_Uninitialized_copy(_First, _Last,
_Ptr, _Alval));
}
template<class _Iter>
pointer _Umove(_Iter _First, _Iter _Last, pointer _Ptr)
{ // move initializing [_First, _Last), using allocator
_Alty _Alval(this->_Getal());
return (_Uninitialized_move(_First, _Last,
_Ptr, _Alval));
}
iterator _Insert_n(const_iterator _Where,
size_type _Count, const value_type& _Val)
{ // insert _Count * _Val at _Where
#if _ITERATOR_DEBUG_LEVEL == 2
if (_VICONT(_Where) != this
|| _VIPTR(_Where) < this->_Myfirst
|| this->_Mylast < _VIPTR(_Where))
_DEBUG_ERROR("vector insert iterator outside range");
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
size_type _Off = _VIPTR(_Where) - this->_Myfirst;
if (_Count == 0)
;
else if (_Unused_capacity() < _Count)
{ // not enough room, reallocate
if (max_size() - size() < _Count)
_Xlen(); // result too long
size_type _Capacity = _Grow_to(size() + _Count);
pointer _Newvec = this->_Getal().allocate(_Capacity);
size_type _Whereoff = _VIPTR(_Where) - this->_Myfirst;
int _Ncopied = 0;
_TRY_BEGIN
_Ufill(_Newvec + _Whereoff, _Count,
_STD addressof(_Val)); // add new stuff
++_Ncopied;
_Umove(this->_Myfirst, _VIPTR(_Where),
_Newvec); // copy prefix
++_Ncopied;
_Umove(_VIPTR(_Where), this->_Mylast,
_Newvec + (_Whereoff + _Count)); // copy suffix
_CATCH_ALL
if (1 < _Ncopied)
_Destroy(_Newvec, _Newvec + _Whereoff);
if (0 < _Ncopied)
_Destroy(_Newvec + _Whereoff, _Newvec + _Whereoff + _Count);
this->_Getal().deallocate(_Newvec, _Capacity);
_RERAISE;
_CATCH_END
_Count += size();
if (this->_Myfirst != pointer())
{ // destroy and deallocate old array
_Destroy(this->_Myfirst, this->_Mylast);
this->_Getal().deallocate(this->_Myfirst,
this->_Myend - this->_Myfirst);
}
this->_Orphan_all();
this->_Myend = _Newvec + _Capacity;
this->_Mylast = _Newvec + _Count;
this->_Myfirst = _Newvec;
}
else if ((size_type)(this->_Mylast - _VIPTR(_Where))
< _Count)
{ // new stuff spills off end
value_type _Tmp = _Val; // in case _Val is in sequence
_Umove(_VIPTR(_Where), this->_Mylast,
_VIPTR(_Where) + _Count); // copy suffix
_TRY_BEGIN
_Ufill(this->_Mylast,
_Count - (this->_Mylast - _VIPTR(_Where)),
_STD addressof(_Tmp)); // insert new stuff off end
_CATCH_ALL
_Destroy(_VIPTR(_Where) + _Count,
this->_Mylast + _Count);
_RERAISE;
_CATCH_END
this->_Mylast += _Count;
_Orphan_range(_VIPTR(_Where), this->_Mylast);
_STD fill(_VIPTR(_Where), this->_Mylast - _Count,
_Tmp); // insert up to old end
}
else
{ // new stuff can all be assigned
value_type _Tmp = _Val; // in case _Val is in sequence
pointer _Oldend = this->_Mylast;
this->_Mylast = _Umove(_Oldend - _Count, _Oldend,
this->_Mylast); // copy suffix
_Orphan_range(_VIPTR(_Where), this->_Mylast);
_Copy_backward(_VIPTR(_Where), _Oldend - _Count,
_Oldend); // copy hole
_STD fill(_VIPTR(_Where),
_VIPTR(_Where) + _Count, _Tmp); // insert into hole
}
return (begin() + _Off);
}
pointer _Ufill(pointer _Ptr, size_type _Count, const value_type *_Pval)
{ // copy initializing _Count * _Val, using allocator
_Alty _Alval(this->_Getal());
_Uninitialized_fill_n(_Ptr, _Count, _Pval, _Alval);
return (_Ptr + _Count);
}
__declspec(noreturn) void _Xlen() const
{ // report a length_error
_Xlength_error("vector<T> too long");
}
__declspec(noreturn) void _Xran() const
{ // report an out_of_range error
_Xout_of_range("invalid vector<T> subscript");
}
#if _VECTOR_ORPHAN_RANGE
void _Orphan_range(pointer _First, pointer _Last) const
{ // orphan iterators within specified (inclusive) range
_Lockit _Lock(_LOCK_DEBUG);
const_iterator **_Pnext = (const_iterator **)this->_Getpfirst();
if (_Pnext != 0)
while (*_Pnext != 0)
if ((*_Pnext)->_Ptr < _First || _Last < (*_Pnext)->_Ptr)
_Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
else
{ // orphan the iterator
(*_Pnext)->_Clrcont();
*_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
}
}
#else /* _VECTOR_ORPHAN_RANGE */
void _Orphan_range(pointer, pointer) const
{ // orphan iterators within specified (inclusive) range
}
#endif /* _VECTOR_ORPHAN_RANGE */
};
// vector TEMPLATE OPERATORS
template<class _Ty,
class _Alloc> inline
void swap(vector<_Ty, _Alloc>& _Left, vector<_Ty, _Alloc>& _Right)
{ // swap _Left and _Right vectors
_Left.swap(_Right);
}
template<class _Ty,
class _Alloc> inline
bool operator==(const vector<_Ty, _Alloc>& _Left,
const vector<_Ty, _Alloc>& _Right)
{ // test for vector equality
return (_Left.size() == _Right.size()
&& equal(_Left.begin(), _Left.end(), _Right.begin()));
}
template<class _Ty,
class _Alloc> inline
bool operator!=(const vector<_Ty, _Alloc>& _Left,
const vector<_Ty, _Alloc>& _Right)
{ // test for vector inequality
return (!(_Left == _Right));
}
template<class _Ty,
class _Alloc> inline
bool operator<(const vector<_Ty, _Alloc>& _Left,
const vector<_Ty, _Alloc>& _Right)
{ // test if _Left < _Right for vectors
return (lexicographical_compare(_Left.begin(), _Left.end(),
_Right.begin(), _Right.end()));
}
template<class _Ty,
class _Alloc> inline
bool operator>(const vector<_Ty, _Alloc>& _Left,
const vector<_Ty, _Alloc>& _Right)
{ // test if _Left > _Right for vectors
return (_Right < _Left);
}
template<class _Ty,
class _Alloc> inline
bool operator<=(const vector<_Ty, _Alloc>& _Left,
const vector<_Ty, _Alloc>& _Right)
{ // test if _Left <= _Right for vectors
return (!(_Right < _Left));
}
template<class _Ty,
class _Alloc> inline
bool operator>=(const vector<_Ty, _Alloc>& _Left,
const vector<_Ty, _Alloc>& _Right)
{ // test if _Left >= _Right for vectors
return (!(_Left < _Right));
}
//
// TEMPLATE CLASS vector<bool, Alloc> AND FRIENDS
//
typedef unsigned int _Vbase; // word type for vector<bool> representation
const int _VBITS = 8 * sizeof (_Vbase); // at least CHAR_BITS bits per word
// CLASS _Vb_iter_base
template<class _Alloc>
class _Vb_iter_base
: public _Iterator012<random_access_iterator_tag,
_Bool,
typename _Alloc::difference_type,
bool *,
bool,
_Iterator_base>
{ // store information common to reference and iterators
public:
typedef typename _Alloc::size_type _Sizet;
typedef vector<_Bool, _Alloc> _Mycont;
_Vb_iter_base()
: _Myptr(0), _Myoff(0)
{ // construct with null pointer
}
_Vb_iter_base(const _Vbase *_Ptr, _Sizet _Off,
const _Container_base *_Mypvbool)
: _Myptr(_Ptr), _Myoff(_Off)
{ // construct with offset and pointer
this->_Adopt(_Mypvbool);
}
void _Advance(_Sizet _Off)
{ // advance iterator by _Off
_Myoff += _Off;
_Myptr += _Myoff / _VBITS;
_Myoff %= _VBITS;
}
int _Valid(_Sizet _Inc) const
{ // test for valid incremented offset
#if _ITERATOR_DEBUG_LEVEL == 2
_Sizet _Mysize = ((_Mycont *)this->_Getcont())->_Mysize;
_Inc += _Myoff;
_Inc += _VBITS * (_Myptr
- (((_Mycont *)this->_Getcont())->_Myvec)._Myfirst);
return (_Inc < _Mysize ? -1 : _Inc == _Mysize ? 0 : +1);
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
return (-1);
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
}
const _Vbase *_Myptr;
_Sizet _Myoff;
};
// CLASS _Vb_reference
template<class _Alloc>
class _Vb_reference
: public _Vb_iter_base<_Alloc>
{ // reference to a bit within a base word
typedef _Vb_iter_base<_Alloc> _Mybase;
typedef _Vb_reference<_Alloc> _Mytype;
_Vb_reference() _NOEXCEPT
{ // construct with null pointer (private)
}
public:
_Vb_reference(const _Mybase& _Right)
: _Mybase(_Right._Myptr, _Right._Myoff, _Right._Getcont())
{ // construct with base
}
_Mytype& operator=(const _Mytype& _Right) _NOEXCEPT
{ // assign _Vb_reference _Right to bit
return (*this = bool(_Right));
}
_Mytype& operator=(bool _Val) _NOEXCEPT
{ // assign _Val to bit
if (_Val)
*(_Vbase *)_Getptr() |= _Mask();
else
*(_Vbase *)_Getptr() &= (~_Mask()); // STET
return (*this);
}
void flip() _NOEXCEPT
{ // toggle the bit
*(_Vbase *)_Getptr() ^= _Mask();
}
operator bool() const _NOEXCEPT
{ // test if bit is set
return ((*_Getptr() & _Mask()) != 0);
}
const _Vbase *_Getptr() const
{ // get pointer to base word
#if _ITERATOR_DEBUG_LEVEL == 2
if (this->_Getcont() == 0
|| this->_Myptr == 0
|| 0 <= this->_Valid(0))
{ // report error
_DEBUG_ERROR("vector<bool> iterator not dereferencable");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Myptr != 0);
_SCL_SECURE_VALIDATE_RANGE(this->_Valid(0) < 0);
#endif /* _ITERATOR_DEBUG_LEVEL */
return (this->_Myptr);
}
protected:
_Vbase _Mask() const
{ // convert offset to mask
return ((_Vbase)(1 << this->_Myoff));
}
};
template<class _Alloc> inline
void swap(_Vb_reference<_Alloc> _Left,
_Vb_reference<_Alloc> _Right)
{ // swap _Left and _Right vector<bool> elements
bool _Val = _Left; // NOT _STD swap
_Left = _Right;
_Right = _Val;
}
// CLASS _Vb_const_iterator
template<class _Alloc>
class _Vb_const_iterator
: public _Vb_iter_base<_Alloc>
{ // iterator for nonmutable vector<bool>
public:
typedef _Vb_iter_base<_Alloc> _Mybase;
typedef _Vb_const_iterator<_Alloc> _Mytype;
typedef _Vb_reference<_Alloc> _Reft;
typedef bool const_reference;
typedef random_access_iterator_tag iterator_category;
typedef _Bool value_type;
typedef typename _Alloc::size_type size_type;
typedef typename _Alloc::difference_type difference_type;
typedef const_reference *pointer;
typedef const_reference reference;
_Vb_const_iterator()
{ // construct with null reference
}
_Vb_const_iterator(const _Vbase *_Ptr, const _Container_base *_Mypvbool)
: _Mybase(_Ptr, 0, _Mypvbool)
{ // construct with offset and pointer
}
const_reference operator*() const
{ // return (reference to) designated object
return (_Reft(*this));
}
_Mytype& operator++()
{ // preincrement
_Inc();
return (*this);
}
_Mytype operator++(int)
{ // postincrement
_Mytype _Tmp = *this;
++*this;
return (_Tmp);
}
_Mytype& operator--()
{ // predecrement
_Dec();
return (*this);
}
_Mytype operator--(int)
{ // postdecrement
_Mytype _Tmp = *this;
--*this;
return (_Tmp);
}
_Mytype& operator+=(difference_type _Off)
{ // increment by integer
if (_Off < 0 && this->_Myoff < 0 - (size_type)_Off)
{ /* add negative increment */
this->_Myoff += _Off;
this->_Myptr -= 1 + ((size_type)(-1) - this->_Myoff) / _VBITS;
this->_Myoff %= _VBITS;
}
else
{ /* add non-negative increment */
this->_Myoff += _Off;
this->_Myptr += this->_Myoff / _VBITS;
this->_Myoff %= _VBITS;
}
return (*this);
}
_Mytype operator+(difference_type _Off) const
{ // return this + integer
_Mytype _Tmp = *this;
return (_Tmp += _Off);
}
_Mytype& operator-=(difference_type _Off)
{ // decrement by integer
return (*this += -_Off);
}
_Mytype operator-(difference_type _Off) const
{ // return this - integer
_Mytype _Tmp = *this;
return (_Tmp -= _Off);
}
difference_type operator-(
const _Mytype& _Right) const
{ // return difference of iterators
_Compat(_Right);
return (_VBITS * (this->_Myptr - _Right._Myptr)
+ (difference_type)this->_Myoff
- (difference_type)_Right._Myoff);
}
const_reference operator[](difference_type _Off) const
{ // subscript
return (*(*this + _Off));
}
bool operator==(const _Mytype& _Right) const
{ // test for iterator equality
_Compat(_Right);
return (this->_Myptr == _Right._Myptr
&& this->_Myoff == _Right._Myoff);
}
bool operator!=(const _Mytype& _Right) const
{ // test for iterator inequality
return (!(*this == _Right));
}
bool operator<(const _Mytype& _Right) const
{ // test if this < _Right
_Compat(_Right);
return (this->_Myptr < _Right._Myptr
|| (this->_Myptr == _Right._Myptr
&& this->_Myoff < _Right._Myoff));
}
bool operator>(const _Mytype& _Right) const
{ // test if this > _Right
return (_Right < *this);
}
bool operator<=(const _Mytype& _Right) const
{ // test if this <= _Right
return (!(_Right < *this));
}
bool operator>=(const _Mytype& _Right) const
{ // test if this >= _Right
return (!(*this < _Right));
}
#if _ITERATOR_DEBUG_LEVEL == 2
void _Compat(const _Mytype& _Right) const
{ // test for compatible iterator pair
if (this->_Getcont() == 0
|| this->_Getcont() != _Right._Getcont())
_DEBUG_ERROR("vector<bool> iterators incompatible");
}
#elif _ITERATOR_DEBUG_LEVEL == 1
void _Compat(const _Mytype& _Right) const
{ // test for compatible iterator pair
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(this->_Getcont() == _Right._Getcont());
}
#else /* _ITERATOR_DEBUG_LEVEL == 0 */
void _Compat(const _Mytype&) const
{ // test for compatible iterator pair
}
#endif /* _ITERATOR_DEBUG_LEVEL */
void _Dec()
{ // decrement bit position
if (this->_Myoff != 0)
--this->_Myoff;
else
{ // move to previous word
#if _ITERATOR_DEBUG_LEVEL == 2
if (this->_Getcont() == 0 || 0 < this->_Valid((size_type)-1))
{ // report error
_DEBUG_ERROR("vector<bool> iterator not decrementable");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(this->_Valid((size_type)-1) <= 0);
#endif /* _ITERATOR_DEBUG_LEVEL */
this->_Myoff = _VBITS - 1;
--this->_Myptr;
}
}
void _Inc()
{ // increment bit position
if (this->_Myoff < _VBITS - 1)
++this->_Myoff;
else
{ // move to next word
#if _ITERATOR_DEBUG_LEVEL == 2
if (this->_Getcont() == 0 || 0 < this->_Valid(1))
{ // report error
_DEBUG_ERROR("vector<bool> iterator not incrementable");
_SCL_SECURE_OUT_OF_RANGE;
}
#elif _ITERATOR_DEBUG_LEVEL == 1
_SCL_SECURE_VALIDATE(this->_Getcont() != 0);
_SCL_SECURE_VALIDATE_RANGE(this->_Valid(1) <= 0);
#endif /* _ITERATOR_DEBUG_LEVEL */
this->_Myoff = 0;
++this->_Myptr;
}
}
};
template<class _Alloc> inline
_Vb_const_iterator<_Alloc> operator+(
typename _Alloc::difference_type _Off,
_Vb_const_iterator<_Alloc> _Right)
{ // return _Right + integer
return (_Right += _Off);
}
template<class _Alloc>
struct _Is_checked_helper<_Vb_const_iterator<_Alloc> >
: public true_type
{ // mark _Vb_const_iterator as checked
};
// CLASS _Vb_iterator
template<class _Alloc>
class _Vb_iterator
: public _Vb_const_iterator<_Alloc>
{ // iterator for mutable vector<bool>
public:
typedef _Vb_const_iterator<_Alloc> _Mybase;
typedef _Vb_iterator<_Alloc> _Mytype;
typedef _Vb_reference<_Alloc> _Reft;
typedef bool const_reference;
typedef random_access_iterator_tag iterator_category;
typedef _Bool value_type;
typedef typename _Alloc::size_type size_type;
typedef typename _Alloc::difference_type difference_type;
typedef _Reft *pointer;
typedef _Reft reference;
_Vb_iterator()
{ // construct with null reference
}
_Vb_iterator(_Vbase *_Ptr, _Container_base *_Mypvbool)
: _Mybase(_Ptr, _Mypvbool)
{ // construct with offset and pointer
}
reference operator*() const
{ // return (reference to) designated object
return (_Reft(*this));
}
_Mytype& operator++()
{ // preincrement
++*(_Mybase *)this;
return (*this);
}
_Mytype operator++(int)
{ // postincrement
_Mytype _Tmp = *this;
++*this;
return (_Tmp);
}
_Mytype& operator--()
{ // predecrement
--*(_Mybase *)this;
return (*this);
}
_Mytype operator--(int)
{ // postdecrement
_Mytype _Tmp = *this;
--*this;
return (_Tmp);
}
_Mytype& operator+=(difference_type _Off)
{ // increment by integer
*(_Mybase *)this += _Off;
return (*this);
}
_Mytype operator+(difference_type _Off) const
{ // return this + integer
_Mytype _Tmp = *this;
return (_Tmp += _Off);
}
_Mytype& operator-=(difference_type _Off)
{ // decrement by integer
return (*this += -_Off);
}
_Mytype operator-(difference_type _Off) const
{ // return this - integer
_Mytype _Tmp = *this;
return (_Tmp -= _Off);
}
difference_type operator-(const _Mybase& _Right) const
{ // return difference of iterators
return (*(_Mybase *)this - _Right);
}
reference operator[](difference_type _Off) const
{ // subscript
return (*(*this + _Off));
}
};
template<class _Alloc> inline
_Vb_iterator<_Alloc> operator+(typename _Alloc::difference_type _Off,
_Vb_iterator<_Alloc> _Right)
{ // return _Right + integer
return (_Right += _Off);
}
template<class _Alloc>
struct _Is_checked_helper<_Vb_iterator<_Alloc> >
: public true_type
{ // mark _Vb_iterator as checked
};
// TEMPLATE CLASS _Vb_val
template<class _Alloc>
class _Vb_val
: public _Container_base
{ // base class for vector<bool> to hold data
public:
typedef _STD vector<_Vbase, _Alloc> _Vectype;
typedef typename _Vectype::_Alty _Alty;
typedef typename _Alty::size_type size_type;
_Vb_val(size_type _Count, const bool& _Val, const _Alloc& _Al = _Alloc())
: _Myvec(_Nw(_Count), (_Vbase)(_Val ? -1 : 0), _Al)
{ // construct _Count * _Val elements with allocator _Al
_Alloc_proxy();
_Mysize = 0;
}
_Vb_val(const _Vb_val& _Right)
: _Myvec(_Right._Myvec),
_Mysize(_Right._Mysize)
{ // copy construct
_Alloc_proxy();
}
_Vb_val(const _Vb_val& _Right, const _Alloc& _Al)
: _Myvec(_Right._Myvec, _Al),
_Mysize(_Right._Mysize)
{ // copy construct, allocator
_Alloc_proxy();
}
_Vb_val(_Vb_val&& _Right)
: _Myvec(_STD forward<_Vectype>(_Right._Myvec)),
_Mysize(_Right._Mysize)
{ // move construct
_Right._Mysize = 0;
_Alloc_proxy();
}
_Vb_val(_Vb_val&& _Right, const _Alloc& _Al)
: _Myvec(_STD forward<_Vectype>(_Right._Myvec), _Al),
_Mysize(_Right._Mysize)
{ // move construct, allocator
_Right._Mysize = 0;
_Alloc_proxy();
}
~_Vb_val() _NOEXCEPT
{ // destroy proxy
_Free_proxy();
}
#if _ITERATOR_DEBUG_LEVEL == 0
void _Swap_alloc(_Vb_val&)
{ // do nothing
}
void _Alloc_proxy()
{ // do nothing
}
void _Free_proxy()
{ // do nothing
}
#else /* _ITERATOR_DEBUG_LEVEL == 0 */
void _Swap_alloc(_Vb_val& _Right)
{ // swap proxies to follow allocators in vector
_Swap_adl(this->_Myproxy, _Right._Myproxy);
}
void _Alloc_proxy()
{ // allocate a proxy
typename _Alty::template rebind<_Container_proxy>::other
_Alproxy(_Myvec.get_allocator());
this->_Myproxy = _Alproxy.allocate(1);
_Alproxy.construct(this->_Myproxy, _Container_proxy());
this->_Myproxy->_Mycont = this;
}
void _Free_proxy()
{ // destroy proxy
typename _Alty::template rebind<_Container_proxy>::other
_Alproxy(_Myvec.get_allocator());
this->_Orphan_all();
_Alproxy.destroy(this->_Myproxy);
_Alproxy.deallocate(this->_Myproxy, 1);
this->_Myproxy = 0;
}
#endif /* _ITERATOR_DEBUG_LEVEL == 0 */
static size_type _Nw(size_type _Count)
{ // return number of base words from number of bits
return ((_Count + _VBITS - 1) / _VBITS);
}
_Vectype _Myvec; // base vector of words
typename _Alty::size_type _Mysize; // current length of sequence
};
// CLASS vector<bool>
template<class _Alloc>
class vector<_Bool, _Alloc>
: public _Vb_val<_Alloc>
{ // varying size array of bits
public:
typedef _STD vector<_Bool, _Alloc> _Myt;
typedef _Vb_val<_Alloc> _Mybase;
typedef typename _Mybase::_Alty _Alty;
typedef typename _Mybase::_Vectype _Vectype;
typedef typename _Alty::size_type size_type;
typedef typename _Alty::difference_type difference_type;
typedef _Bool _Ty;
typedef _Alloc allocator_type;
typedef _Vb_reference<_Alty> reference;
typedef bool const_reference;
typedef bool value_type;
typedef reference _Reft;
typedef _Vb_const_iterator<_Alty> const_iterator;
typedef _Vb_iterator<_Alty> iterator;
typedef iterator pointer;
typedef const_iterator const_pointer;
typedef _STD reverse_iterator<iterator> reverse_iterator;
typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;
static const int _VBITS = _STD _VBITS;
enum {_EEN_VBITS = _VBITS}; // helper for expression evaluator
vector()
: _Mybase(0, false)
{ // construct empty vector
}
explicit vector(const _Alloc& _Al)
: _Mybase(0, false, _Al)
{ // construct empty vector, allocator
}
explicit vector(size_type _Count, const bool& _Val = false)
: _Mybase(_Count, _Val)
{ // construct from _Count * _Val
_Trim(_Count);
}
vector(size_type _Count, const bool& _Val, const _Alloc& _Al)
: _Mybase(_Count, _Val, _Al)
{ // construct from _Count * _Val, allocator
_Trim(_Count);
}
vector(const _Myt& _Right)
: _Mybase(_Right)
{ // construct by copying _Right
}
vector(const _Myt& _Right, const _Alloc& _Al)
: _Mybase(_Right, _Al)
{ // construct by copying _Right, allocator
}
template<class _Iter,
class = typename enable_if<_Is_iterator<_Iter>::value,
void>::type>
vector(_Iter _First, _Iter _Last)
: _Mybase(0, false)
{ // construct from [_First, _Last)
_BConstruct(_First, _Last);
}
template<class _Iter,
class = typename enable_if<_Is_iterator<_Iter>::value,
void>::type>
vector(_Iter _First, _Iter _Last, const _Alloc& _Al)
: _Mybase(0, false, _Al)
{ // construct from [_First, _Last), allocator
_BConstruct(_First, _Last);
}
template<class _Iter>
void _BConstruct(_Iter _First, _Iter _Last)
{ // initialize from [_First, _Last), input iterators
insert(begin(), _First, _Last);
}
vector(_Myt&& _Right)
: _Mybase(_STD forward<_Myt>(_Right))
{ // move construct by moving _Right
}
vector(_Myt&& _Right, const _Alloc& _Al)
: _Mybase(_STD forward<_Myt>(_Right), _Al)
{ // move construct by moving _Right, allocator
}
_Myt& operator=(_Myt&& _Right)
{ // assign by moving _Right
if (this != &_Right)
{ // different, assign it
clear();
if (_Alty::propagate_on_container_move_assignment::value
&& this->get_allocator() != _Right.get_allocator())
{ // assign vector, dumping proxy
this->_Free_proxy();
this->_Myvec = _STD move(_Right._Myvec);
this->_Alloc_proxy();
}
else
this->_Myvec = _STD move(_Right._Myvec);
this->_Mysize = _Right._Mysize;
_Right._Mysize = 0;
}
return (*this);
}
vector(_XSTD initializer_list<bool> _Ilist,
const _Alloc& _Al = allocator_type())
: _Mybase(0, false, _Al)
{ // construct from initializer_list
insert(begin(), _Ilist.begin(), _Ilist.end());
}
_Myt& operator=(_XSTD initializer_list<bool> _Ilist)
{ // assign initializer_list
assign(_Ilist.begin(), _Ilist.end());
return (*this);
}
void assign(_XSTD initializer_list<bool> _Ilist)
{ // assign initializer_list
assign(_Ilist.begin(), _Ilist.end());
}
iterator insert(const_iterator _Where,
_XSTD initializer_list<bool> _Ilist)
{ // insert initializer_list
return (insert(_Where, _Ilist.begin(), _Ilist.end()));
}
~vector() _NOEXCEPT
{ // destroy the object
this->_Mysize = 0;
}
_Myt& operator=(const _Myt& _Right)
{ // assign from _Right
this->_Mysize = _Right._Mysize;
this->_Myvec = _Right._Myvec;
return (*this);
}
void reserve(size_type _Count)
{ // determine new minimum length of allocated storage
this->_Myvec.reserve(this->_Nw(_Count));
}
size_type capacity() const _NOEXCEPT
{ // return current length of allocated storage
return (this->_Myvec.capacity() * _VBITS);
}
iterator begin() _NOEXCEPT
{ // return iterator for beginning of mutable sequence
return (iterator((_Vbase *)this->_Myvec._Myfirst, this));
}
const_iterator begin() const _NOEXCEPT
{ // return iterator for beginning of nonmutable sequence
return (const_iterator((_Vbase *)this->_Myvec._Myfirst, this));
}
iterator end() _NOEXCEPT
{ // return iterator for end of mutable sequence
iterator _Tmp = begin();
if (0 < this->_Mysize)
_Tmp += this->_Mysize;
return (_Tmp);
}
const_iterator end() const _NOEXCEPT
{ // return iterator for end of nonmutable sequence
const_iterator _Tmp = begin();
if (0 < this->_Mysize)
_Tmp += this->_Mysize;
return (_Tmp);
}
const_iterator cbegin() const _NOEXCEPT
{ // return iterator for beginning of nonmutable sequence
return (((const _Myt *)this)->begin());
}
const_iterator cend() const _NOEXCEPT
{ // return iterator for end of nonmutable sequence
return (((const _Myt *)this)->end());
}
const_reverse_iterator crbegin() const _NOEXCEPT
{ // return iterator for beginning of reversed nonmutable sequence
return (((const _Myt *)this)->rbegin());
}
const_reverse_iterator crend() const _NOEXCEPT
{ // return iterator for end of reversed nonmutable sequence
return (((const _Myt *)this)->rend());
}
void shrink_to_fit()
{ // reduce capacity
if (this->_Myvec._Has_unused_capacity())
{ // worth shrinking, do it
_Myt _Tmp(*this);
swap(_Tmp);
}
}
iterator _Make_iter(const_iterator _Where)
{ // make iterator from const_iterator
iterator _Tmp = begin();
if (0 < this->_Mysize)
_Tmp += _Where - begin();
return (_Tmp);
}
reverse_iterator rbegin() _NOEXCEPT
{ // return iterator for beginning of reversed mutable sequence
return (reverse_iterator(end()));
}
const_reverse_iterator rbegin() const _NOEXCEPT
{ // return iterator for beginning of reversed nonmutable sequence
return (const_reverse_iterator(end()));
}
reverse_iterator rend() _NOEXCEPT
{ // return iterator for end of reversed mutable sequence
return (reverse_iterator(begin()));
}
const_reverse_iterator rend() const _NOEXCEPT
{ // return iterator for end of reversed nonmutable sequence
return (const_reverse_iterator(begin()));
}
void resize(size_type _Newsize, bool _Val = false)
{ // determine new length, padding with _Val elements as needed
if (size() < _Newsize)
_Insert_n(end(), _Newsize - size(), _Val);
else if (_Newsize < size())
erase(begin() + _Newsize, end());
}
size_type size() const _NOEXCEPT
{ // return length of sequence
return (this->_Mysize);
}
size_type max_size() const _NOEXCEPT
{ // return maximum possible length of sequence
const size_type _Maxsize = this->_Myvec.max_size();
return (_Maxsize < (size_type)(-1) / _VBITS
? _Maxsize * _VBITS : (size_type)(-1));
}
bool empty() const _NOEXCEPT
{ // test if sequence is empty
return (size() == 0);
}
_Alloc get_allocator() const _NOEXCEPT
{ // return allocator object for values
return (this->_Myvec.get_allocator());
}
const_reference at(size_type _Off) const
{ // subscript nonmutable sequence with checking
if (size() <= _Off)
_Xran();
return ((*this)[_Off]);
}
reference at(size_type _Off)
{ // subscript mutable sequence with checking
if (size() <= _Off)
_Xran();
return ((*this)[_Off]);
}
const_reference operator[](size_type _Off) const
{ // subscript nonmutable sequence
const_iterator _It = begin();
_It._Advance(_Off);
return (*_It);
}
reference operator[](size_type _Off)
{ // subscript mutable sequence
iterator _It = begin();
_It._Advance(_Off);
return (*_It);
}
reference front()
{ // return first element of mutable sequence
return (*begin());
}
const_reference front() const
{ // return first element of nonmutable sequence
return (*begin());
}
reference back()
{ // return last element of mutable sequence
return (*(end() - 1));
}
const_reference back() const
{ // return last element of nonmutable sequence
return (*(end() - 1));
}
void push_back(const bool& _Val)
{ // insert element at end
insert(end(), _Val);
}
void pop_back()
{ // erase element at end
erase(end() - 1);
}
template<class _Iter>
typename enable_if<_Is_iterator<_Iter>::value,
void>::type
assign(_Iter _First, _Iter _Last)
{ // assign [_First, _Last), input iterators
erase(begin(), end());
insert(begin(), _First, _Last);
}
void assign(size_type _Count, const bool& _Val)
{ // assign _Count * _Val
erase(begin(), end());
_Insert_n(begin(), _Count, _Val);
}
iterator insert(const_iterator _Where, const bool& _Val)
{ // insert _Val at _Where
return (_Insert_n(_Where, (size_type)1, _Val));
}
iterator insert(const_iterator _Where, size_type _Count,
const bool& _Val)
{ // insert _Count * _Val at _Where
return (_Insert_n(_Where, _Count, _Val));
}
template<class _Iter>
typename enable_if<_Is_iterator<_Iter>::value,
iterator>::type
insert(const_iterator _Where, _Iter _First, _Iter _Last)
{ // insert [_First, _Last) at _Where
size_type _Off = _Where - begin();
_Insert(_Where, _First, _Last, _Iter_cat(_First));
return (begin() + _Off);
}
template<class _Iter>
void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
input_iterator_tag)
{ // insert [_First, _Last) at _Where, input iterators
size_type _Off = _Where - begin();
for (; _First != _Last; ++_First, ++_Off)
insert(begin() + _Off, *_First);
}
template<class _Iter>
void _Insert(const_iterator _Where,
_Iter _First, _Iter _Last,
forward_iterator_tag)
{ // insert [_First, _Last) at _Where, forward iterators
_DEBUG_RANGE(_First, _Last);
size_type _Count = 0;
_Distance(_First, _Last, _Count);
size_type _Off = _Insert_x(_Where, _Count);
_STD copy(_First, _Last, begin() + _Off);
}
iterator erase(const_iterator _Where_arg)
{ // erase element at _Where
iterator _Where = _Make_iter(_Where_arg);
size_type _Off = _Where - begin();
#if _ITERATOR_DEBUG_LEVEL == 2
if (end() <= _Where)
_DEBUG_ERROR("vector<bool> erase iterator outside range");
_STD copy(_Where + 1, end(), _Where);
_Orphan_range(_Off, this->_Mysize);
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
_STD copy(_Where + 1, end(), _Where);
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
_Trim(this->_Mysize - 1);
return (begin() + _Off);
}
iterator erase(const_iterator _First_arg, const_iterator _Last_arg)
{ // erase [_First, _Last)
iterator _First = _Make_iter(_First_arg);
iterator _Last = _Make_iter(_Last_arg);
size_type _Off = _First - begin();
if (_First != _Last)
{ // worth doing, copy down over hole
#if _ITERATOR_DEBUG_LEVEL == 2
if (_Last < _First || end() < _Last)
_DEBUG_ERROR("vector<bool> erase iterator outside range");
iterator _Next = _STD copy(_Last, end(), _First);
size_type _Newsize = _Next - begin();
_Orphan_range(_Newsize, this->_Mysize);
_Trim(_Newsize);
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
iterator _Next = _STD copy(_Last, end(), _First);
_Trim(_Next - begin());
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
}
return (begin() + _Off);
}
void clear() _NOEXCEPT
{ // erase all elements
erase(begin(), end());
}
void flip() _NOEXCEPT
{ // toggle all elements
for (typename _Vectype::iterator _Next = this->_Myvec.begin();
_Next != this->_Myvec.end(); ++_Next)
*_Next = (_Vbase)~*_Next;
_Trim(this->_Mysize);
}
void swap(_Myt& _Right)
{ // exchange contents with right
if (this == &_Right)
; // same object, do nothing
else if (this->get_allocator() == _Right.get_allocator())
{ // same allocator, swap control information
this->_Swap_all(_Right);
this->_Myvec.swap(_Right._Myvec);
_STD swap(this->_Mysize, _Right._Mysize);
}
else if (_Alty::propagate_on_container_swap::value)
{ // swap allocators and control information
this->_Swap_alloc(_Right);
this->_Myvec.swap(_Right._Myvec);
_STD swap(this->_Mysize, _Right._Mysize);
}
else
{ // containers are incompatible
#if _ITERATOR_DEBUG_LEVEL == 2
_DEBUG_ERROR("vector<bool> containers incompatible for swap");
#else /* ITERATOR_DEBUG_LEVEL == 2 */
_XSTD terminate();
#endif /* ITERATOR_DEBUG_LEVEL == 2 */
}
}
static void swap(reference _Left, reference _Right) _NOEXCEPT
{ // swap _Left and _Right vector<bool> elements
bool _Val = _Left; // NOT _STD swap
_Left = _Right;
_Right = _Val;
}
size_t hash() const
{ // hash bits to size_t value by pseudorandomizing transform
return (_Hash_seq((const unsigned char *)this->_Myvec.data(),
this->_Myvec.size() * sizeof (_Vbase)));
}
iterator _Insert_n(const_iterator _Where,
size_type _Count, const bool& _Val)
{ // insert _Count * _Val at _Where
size_type _Off = _Insert_x(_Where, _Count);
_STD fill(begin() + _Off, begin() + (_Off + _Count), _Val);
return (begin() + _Off);
}
size_type _Insert_x(const_iterator _Where, size_type _Count)
{ // make room to insert _Count elements at _Where
size_type _Off = _Where - begin();
#if _ITERATOR_DEBUG_LEVEL == 2
if (end() < _Where)
_DEBUG_ERROR("vector<bool> insert iterator outside range");
bool _Realloc = capacity() - size() < _Count;
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
if (_Count == 0)
;
else if (max_size() - size() < _Count)
_Xlen(); // result too long
else
{ // worth doing
this->_Myvec.resize(this->_Nw(size() + _Count), 0);
if (empty())
this->_Mysize += _Count;
else
{ // make room and copy down suffix
iterator _Oldend = end();
this->_Mysize += _Count;
_STD copy_backward(begin() + _Off, _Oldend, end());
}
#if _ITERATOR_DEBUG_LEVEL == 2
_Orphan_range(_Realloc ? 0 : _Off, this->_Mysize);
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
}
return (_Off);
}
#if _VECTOR_ORPHAN_RANGE
void _Orphan_range(size_type _Offlo, size_type _Offhi) const
{ // orphan iterators within specified (inclusive) range
typedef _Vb_iter_base<_Alty> _Myiterbase;
_Lockit _Lock(_LOCK_DEBUG);
_Vbase *_Base = (_Vbase *)this->_Myvec._Myfirst;
const_iterator **_Pnext = (const_iterator **)this->_Getpfirst();
if (_Pnext != 0)
while (*_Pnext != 0)
{ // test offset from beginning of vector
size_type _Off = _VBITS * ((*_Pnext)->_Myptr - _Base)
+ (*_Pnext)->_Myoff;
if (_Off < _Offlo || _Offhi < _Off)
_Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
else
{ // orphan the iterator
(*_Pnext)->_Clrcont();
*_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
}
}
}
#else /* _VECTOR_ORPHAN_RANGE */
void _Orphan_range(size_type, size_type) const
{ // orphan iterators within specified (inclusive) range
}
#endif /* _VECTOR_ORPHAN_RANGE */
void _Trim(size_type _Size)
{ // trim base vector to exact length in bits
if (max_size() < _Size)
_Xlen(); // result too long
size_type _Words = this->_Nw(_Size);
if (_Words < this->_Myvec.size())
this->_Myvec.erase(this->_Myvec.begin() + _Words,
this->_Myvec.end());
this->_Mysize = _Size;
_Size %= _VBITS;
if (0 < _Size)
this->_Myvec[_Words - 1] &= (_Vbase)((1 << _Size) - 1);
}
__declspec(noreturn) void _Xlen() const
{ // report a length_error
_Xlength_error("vector<bool> too long");
}
__declspec(noreturn) void _Xran() const
{ // report an out_of_range error
_Xout_of_range("invalid vector<bool> subscript");
}
};
template<class _Alloc> inline
bool operator==(const vector<bool, _Alloc>& _Left,
const vector<bool, _Alloc>& _Right)
{ // test for vector equality
return (_Left.size() == _Right.size()
&& equal(_Left._Myvec.begin(), _Left._Myvec.end(),
_Right._Myvec.begin()));
}
template<class _Alloc> inline
bool operator!=(const vector<bool, _Alloc>& _Left,
const vector<bool, _Alloc>& _Right)
{ // test for vector inequality
return (!(_Left == _Right));
}
// TEMPLATE STRUCT SPECIALIZATION hash
template<class _Alloc>
struct hash<vector<_Bool, _Alloc> >
: public unary_function<vector<_Bool, _Alloc>, size_t>
{ // hash functor
typedef vector<_Bool, _Alloc> _Kty;
size_t operator()(const _Kty& _Keyval) const
{ // hash _Keyval to size_t value by pseudorandomizing transform
return (_Keyval.hash());
}
};
_STD_END
#pragma pop_macro("new")
#pragma warning(pop)
#pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _VECTOR_ */
I'm using Microsoft visual studio 2013
Am also still living in stone age as you can see by looking at my code.
I'm still exploring c++11/14 things. ( just started doing it few days ago. )
My vector class is only slower when it have to move items.
PHP Code:
move();
void push( int pos, T in );
One person reported that he was getting different results.
My vector's push function was slower than default one, was his report.
I would be very grateful if someone can find time to test it out.
Thanks!
|
|