| Re: [eigen] Re: State of the problem with std::vector |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Re: State of the problem with std::vector
- From: "Benoit Jacob" <jacob.benoit.1@xxxxxxxxx>
- Date: Thu, 8 Jan 2009 23:06:02 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:in-reply-to:mime-version:content-type :content-transfer-encoding:content-disposition:references; bh=cl/EZj+ADzAt/EMRFtmJRJjfvomfShyQ2s/SCuT2ojo=; b=oX/aiOjYjByjJMO7+s/cT6P2beG63dYop/jnyXPHakGp4hThVsB8aMkyxr4+N4w+0y LisHwggOZb81X+gjJZu1bzBECGONqM20HEfkt0C6Pp+w4uEwxIMR3o9wRUwOKYVBQEFO fkn9W/DLUDuhIYxi0/VM/5ytB4zZF3maXrh5M=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:in-reply-to:mime-version :content-type:content-transfer-encoding:content-disposition :references; b=GQEBmZ3b8oENuvmh/vfgVWtEwFzP3/x7zXTp4wAKQOdzWX9fxxkNbxQ41texwiKSfm lS3M86kAwdtaB4A946hui0/Cz43x1XE8Pde2aW/V4K3r5Yar5xu6Ud3uEctFCtZSzCT3 XTN6FDpFJhHmaFd7QT3H5Q+niHIlWND0JoMyw=
interesting: aside from the resize() methods themselves, it seems that
only an internal _Insert_x method calls resize.
Benoit
2009/1/8 FMDSPAM <fmdspam@xxxxxxxxx>:
> Benoit Jacob schrieb:
>>
>> So if you
>> have MSVC and like this possible solution please tell us what other
>> methods of std::vector call resize...
>> Cheers,
>> Benoit
>>
>>
>
> Still without a clear understanding of this threat. Nevertheless:
>
> Microsoft Visual Studio 2008
> Version 9.0.30729.1 SP
>
> In the file "vector" (see attachment) scanning for "resize", i found three
> methods of std::vector<_Ty, _Ax> calling some form of resize().
>
> two public, one protected
>
> hope this help
>
> Frank
>
>
> // vector standard header
> #pragma once
> #ifndef _VECTOR_
> #define _VECTOR_
> #ifndef RC_INVOKED
> #include <memory>
> #include <stdexcept>
>
> #ifdef _MSC_VER
> #pragma pack(push,_CRT_PACKING)
> #pragma warning(push,3)
> #pragma warning(disable: 4244)
> #endif /* _MSC_VER */
>
> _STD_BEGIN
> template<class _Ty,
> class _Ax = allocator<_Ty> >
> class vector;
>
> // TEMPLATE CLASS _Vector_const_iterator
> template<class _Ty,
> class _Alloc>
> class _Vector_const_iterator
> : public _Ranit<_Ty, typename _Alloc::difference_type,
> typename _Alloc::const_pointer, typename
> _Alloc::const_reference>
> { // iterator for nonmutable vector
> public:
> typedef _Vector_const_iterator<_Ty, _Alloc> _Myt;
> typedef vector<_Ty, _Alloc> _Myvec;
> typedef typename _Alloc::pointer _Tptr;
>
> typedef random_access_iterator_tag iterator_category;
> typedef _Ty value_type;
> typedef typename _Alloc::difference_type difference_type;
> typedef typename _Alloc::const_pointer pointer;
> typedef typename _Alloc::const_reference reference;
>
> #if _SECURE_SCL
> typedef _Range_checked_iterator_tag _Checked_iterator_category;
> #endif
>
> #if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING
> typedef pointer _Checked_iterator_base_type;
>
> _Checked_iterator_base_type _Checked_iterator_base() const
> {
> return _Myptr;
> }
>
> void _Checked_iterator_assign_from_base(_Checked_iterator_base_type
> _Base)
> {
> this->_Myptr = const_cast<_Tptr>(_Base);
> }
> #endif
>
> // Setting _Inner_type implies that the internal structure of vector
> is
> // an array of _Ty. This information is used in the copy and move
> algorithm.
> // The helper function _Ptr_cat will return _Scalar_ptr_iterator_tag
> if you
> // pass a vector iterator.
> typedef _Tptr _Inner_type;
>
> _Vector_const_iterator()
> { // construct with null pointer
> _Myptr = 0;
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> _Vector_const_iterator(_Tptr _Ptr, const _Container_base *_Pvector)
> { // construct with pointer _Ptr
> _SCL_SECURE_VALIDATE(_Pvector == NULL || (((_Myvec
> *)_Pvector)->_Myfirst <= _Ptr && _Ptr <= ((_Myvec *)_Pvector)->_Mylast));
> this->_Adopt(_Pvector);
> _Myptr = _Ptr;
> }
>
> #elif _SECURE_SCL
> _Vector_const_iterator(_Tptr _Ptr, const _Container_base *_Pvector)
> { // construct with pointer _Ptr
> _SCL_SECURE_VALIDATE(_Pvector != NULL && ((_Myvec
> *)_Pvector)->_Myfirst <= _Ptr && _Ptr <= ((_Myvec *)_Pvector)->_Mylast);
> this->_Set_container(_Pvector);
> _Myptr = _Ptr;
> }
>
> #else
> explicit _Vector_const_iterator(_Tptr _Ptr)
> { // construct with pointer _Ptr
> _Myptr = _Ptr;
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> reference operator*() const
> { // return designated object
>
> #if _HAS_ITERATOR_DEBUGGING
> if (this->_Mycont == 0
> || _Myptr < ((_Myvec *)this->_Mycont)->_Myfirst
> || ((_Myvec *)this->_Mycont)->_Mylast <= _Myptr)
> {
> _DEBUG_ERROR("vector iterator not dereferencable");
> _SCL_SECURE_OUT_OF_RANGE;
> }
> #else
> _SCL_SECURE_VALIDATE(this->_Has_container());
> _SCL_SECURE_VALIDATE_RANGE(_Myptr < ((_Myvec
> *)(this->_Getmycont()))->_Mylast);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> return (*_Myptr);
> }
>
> pointer operator->() const
> { // return pointer to class object
> return (&**this);
> }
>
> _Myt& operator++()
> { // preincrement
> _SCL_SECURE_VALIDATE(this->_Has_container());
> _SCL_SECURE_VALIDATE_RANGE(_Myptr < ((_Myvec
> *)(this->_Getmycont()))->_Mylast);
>
> #if _HAS_ITERATOR_DEBUGGING
> if (this->_Mycont == 0
> || ((_Myvec *)this->_Mycont)->_Mylast <= _Myptr)
> _DEBUG_ERROR("vector iterator not incrementable");
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> ++_Myptr;
> return (*this);
> }
>
> _Myt operator++(int)
> { // postincrement
> _Myt _Tmp = *this;
> ++*this;
> return (_Tmp);
> }
>
> _Myt& operator--()
> { // predecrement
> _SCL_SECURE_VALIDATE(this->_Has_container());
> _SCL_SECURE_VALIDATE_RANGE(_Myptr > ((_Myvec
> *)(this->_Getmycont()))->_Myfirst);
>
> #if _HAS_ITERATOR_DEBUGGING
> if (this->_Mycont == 0
> || _Myptr == ((_Myvec *)this->_Mycont)->_Myfirst)
> _DEBUG_ERROR("vector iterator not decrementable");
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> --_Myptr;
> return (*this);
> }
>
> _Myt operator--(int)
> { // postdecrement
> _Myt _Tmp = *this;
> --*this;
> return (_Tmp);
> }
>
> _Myt& operator+=(difference_type _Off)
> { // increment by integer
> _SCL_SECURE_VALIDATE(this->_Has_container());
> _SCL_SECURE_VALIDATE_RANGE(
> _Myptr + _Off <= ((_Myvec
> *)(this->_Getmycont()))->_Mylast &&
> _Myptr + _Off >= ((_Myvec
> *)(this->_Getmycont()))->_Myfirst);
> _Myptr += _Off;
> return (*this);
> }
>
> _Myt operator+(difference_type _Off) const
> { // return this + integer
> _Myt _Tmp = *this;
> return (_Tmp += _Off);
> }
>
> _Myt& operator-=(difference_type _Off)
> { // decrement by integer
> return (*this += -_Off);
> }
>
> _Myt operator-(difference_type _Off) const
> { // return this - integer
> _Myt _Tmp = *this;
> return (_Tmp -= _Off);
> }
>
> difference_type operator-(const _Myt& _Right) const
> { // return difference of iterators
>
> #if _HAS_ITERATOR_DEBUGGING
> _Compat(_Right);
> #else
> _SCL_SECURE_VALIDATE(this->_Has_container() &&
> this->_Same_container(_Right));
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> return (_Myptr - _Right._Myptr);
> }
>
> reference operator[](difference_type _Off) const
> { // subscript
> return (*(*this + _Off));
> }
>
> bool operator==(const _Myt& _Right) const
> { // test for iterator equality
>
> #if _HAS_ITERATOR_DEBUGGING
> _Compat(_Right);
> #else
> _SCL_SECURE_VALIDATE(this->_Has_container() &&
> this->_Same_container(_Right));
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> return (_Myptr == _Right._Myptr);
> }
>
> bool operator!=(const _Myt& _Right) const
> { // test for iterator inequality
> return (!(*this == _Right));
> }
>
> bool operator<(const _Myt& _Right) const
> { // test if this < _Right
>
> #if _HAS_ITERATOR_DEBUGGING
> _Compat(_Right);
> #else
> _SCL_SECURE_VALIDATE(this->_Has_container() &&
> this->_Same_container(_Right));
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> return (_Myptr < _Right._Myptr);
> }
>
> bool operator>(const _Myt& _Right) const
> { // test if this > _Right
> return (_Right < *this);
> }
>
> bool operator<=(const _Myt& _Right) const
> { // test if this <= _Right
> return (!(_Right < *this));
> }
>
> bool operator>=(const _Myt& _Right) const
> { // test if this >= _Right
> return (!(*this < _Right));
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> void _Compat(const _Myt& _Right) const
> { // test for compatible iterator pair
> if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
> {
> _DEBUG_ERROR("vector iterators incompatible");
> _SCL_SECURE_INVALID_ARGUMENT;
> }
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> static void _Xlen()
> { // report a length_error
> _THROW(length_error, "vector<T> too long");
> }
>
> static void _Xran()
> { // report an out_of_range error
> _THROW(out_of_range, "invalid vector<T> subscript");
> }
>
> static void _Xinvarg()
> { // report an invalid_argument error
> _THROW(invalid_argument, "invalid vector<T> argument");
> }
>
> _Tptr _Myptr; // offset of element in vector
> };
>
> template<class _Ty,
> class _Alloc> inline
> _Vector_const_iterator<_Ty, _Alloc> operator+(
> typename _Vector_const_iterator<_Ty, _Alloc>::difference_type
> _Off,
> _Vector_const_iterator<_Ty, _Alloc> _Next)
> { // add offset to iterator
> return (_Next += _Off);
> }
>
> // TEMPLATE CLASS _Vector_iterator
> template<class _Ty,
> class _Alloc>
> class _Vector_iterator
> : public _Vector_const_iterator<_Ty, _Alloc>
> { // iterator for mutable vector
> public:
> typedef _Vector_iterator<_Ty, _Alloc> _Myt;
> typedef _Vector_const_iterator<_Ty, _Alloc> _Mybase;
>
> typedef random_access_iterator_tag iterator_category;
> typedef _Ty value_type;
> typedef typename _Alloc::difference_type difference_type;
> typedef typename _Alloc::pointer pointer;
> typedef typename _Alloc::reference reference;
>
> #if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING
> typedef pointer _Checked_iterator_base_type;
>
> _Checked_iterator_base_type _Checked_iterator_base() const
> {
> return (this->_Myptr);
> }
>
> void _Checked_iterator_assign_from_base(_Checked_iterator_base_type
> _Base)
> {
> this->_Myptr = _Base;
> }
> #endif
>
> _Vector_iterator()
> { // construct with null vector pointer
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> _Vector_iterator(pointer _Ptr, const _Container_base *_Pvector)
> : _Mybase(_Ptr, _Pvector)
> { // construct with pointer _Ptr
> }
>
> #elif _SECURE_SCL
> _Vector_iterator(pointer _Ptr, const _Container_base *_Pvector)
> : _Mybase(_Ptr, _Pvector)
> { // construct with pointer _Ptr
> }
>
> #else
> explicit _Vector_iterator(pointer _Ptr)
> : _Mybase(_Ptr)
> { // construct with pointer _Ptr
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> reference operator*() const
> { // return designated object
> return ((reference)**(_Mybase *)this);
> }
>
> pointer operator->() const
> { // return pointer to class object
> return (&**this);
> }
>
> _Myt& operator++()
> { // preincrement
> ++(*(_Mybase *)this);
> return (*this);
> }
>
> _Myt operator++(int)
> { // postincrement
> _Myt _Tmp = *this;
> ++*this;
> return (_Tmp);
> }
>
> _Myt& operator--()
> { // predecrement
> --(*(_Mybase *)this);
> return (*this);
> }
>
> _Myt operator--(int)
> { // postdecrement
> _Myt _Tmp = *this;
> --*this;
> return (_Tmp);
> }
>
> _Myt& operator+=(difference_type _Off)
> { // increment by integer
> (*(_Mybase *)this) += _Off;
> return (*this);
> }
>
> _Myt operator+(difference_type _Off) const
> { // return this + integer
> _Myt _Tmp = *this;
> return (_Tmp += _Off);
> }
>
> _Myt& operator-=(difference_type _Off)
> { // decrement by integer
> return (*this += -_Off);
> }
>
> _Myt operator-(difference_type _Off) const
> { // return this - integer
> _Myt _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 _Ty,
> class _Alloc> inline
> _Vector_iterator<_Ty, _Alloc> operator+(
> typename _Vector_iterator<_Ty, _Alloc>::difference_type _Off,
> _Vector_iterator<_Ty, _Alloc> _Next)
> { // add offset to iterator
> return (_Next += _Off);
> }
>
> // TEMPLATE CLASS _Vector_val
> template<class _Ty,
> class _Alloc>
> class _Vector_val
> : public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
> { // base class for vector to hold allocator _Alval
> protected:
> _Vector_val(_Alloc _Al = _Alloc())
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alval(_Al)
> { // construct allocator from _Al
> }
>
> typedef typename _Alloc::template
> rebind<_Ty>::other _Alty;
>
> _Alty _Alval; // allocator object for values
> };
>
> // TEMPLATE CLASS vector
> template<class _Ty,
> class _Ax>
> class vector
> : public _Vector_val<_Ty, _Ax>
> { // varying size array of values
> public:
> typedef vector<_Ty, _Ax> _Myt;
> typedef _Vector_val<_Ty, _Ax> _Mybase;
> typedef typename _Mybase::_Alty _Alloc;
> typedef _Alloc allocator_type;
> typedef typename _Alloc::size_type size_type;
> typedef typename _Alloc::difference_type _Dift;
> typedef _Dift difference_type;
> typedef typename _Alloc::pointer _Tptr;
> typedef typename _Alloc::const_pointer _Ctptr;
> typedef _Tptr pointer;
> typedef _Ctptr const_pointer;
> typedef typename _Alloc::reference _Reft;
> typedef _Reft reference;
> typedef typename _Alloc::const_reference const_reference;
> typedef typename _Alloc::value_type value_type;
>
> #define _VEC_ITER_BASE(it) (it)._Myptr
>
> typedef _Vector_iterator<_Ty, _Alloc> iterator;
> typedef _Vector_const_iterator<_Ty, _Alloc> const_iterator;
>
> // friend class _Vector_iterator<_Ty, _Alloc>;
> friend class _Vector_const_iterator<_Ty, _Alloc>;
>
> typedef std::reverse_iterator<iterator> reverse_iterator;
> typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
>
> vector()
> : _Mybase()
> { // construct empty vector
> _Buy(0);
> }
>
> explicit vector(const _Alloc& _Al)
> : _Mybase(_Al)
> { // construct empty vector with allocator
> _Buy(0);
> }
>
> explicit vector(size_type _Count)
> : _Mybase()
> { // construct from _Count * _Ty()
> _Construct_n(_Count, _Ty());
> }
>
> vector(size_type _Count, const _Ty& _Val)
> : _Mybase()
> { // construct from _Count * _Val
> _Construct_n(_Count, _Val);
> }
>
> vector(size_type _Count, const _Ty& _Val, const _Alloc& _Al)
> : _Mybase(_Al)
> { // construct from _Count * _Val, with allocator
> _Construct_n(_Count, _Val);
> }
>
> vector(const _Myt& _Right)
> : _Mybase(_Right._Alval)
> { // construct by copying _Right
> if (_Buy(_Right.size()))
> _TRY_BEGIN
> _Mylast = _Ucopy(_Right.begin(), _Right.end(),
> _Myfirst);
> _CATCH_ALL
> _Tidy();
> _RERAISE;
> _CATCH_END
> }
>
> template<class _Iter>
> vector(_Iter _First, _Iter _Last)
> : _Mybase()
> { // construct from [_First, _Last)
> _Construct(_First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> vector(_Iter _First, _Iter _Last, const _Alloc& _Al)
> : _Mybase(_Al)
> { // construct from [_First, _Last), with allocator
> _Construct(_First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> void _Construct(_Iter _Count, _Iter _Val, _Int_iterator_tag)
> { // initialize with _Count * _Val
> size_type _Size = (size_type)_Count;
> _Construct_n(_Size, (_Ty)_Val);
> }
>
> template<class _Iter>
> void _Construct(_Iter _First,
> _Iter _Last, input_iterator_tag)
> { // initialize with [_First, _Last), input iterators
> _Buy(0);
> _TRY_BEGIN
> insert(begin(), _First, _Last);
> _CATCH_ALL
> _Tidy();
> _RERAISE;
> _CATCH_END
> }
>
> void _Construct_n(size_type _Count, const _Ty& _Val)
> { // construct from _Count * _Val
> if (_Buy(_Count))
> { // nonzero, fill it
> _TRY_BEGIN
> _Mylast = _Ufill(_Myfirst, _Count, _Val);
> _CATCH_ALL
> _Tidy();
> _RERAISE;
> _CATCH_END
> }
> }
>
> ~vector()
> { // destroy the object
> _Tidy();
> }
>
> _Myt& operator=(const _Myt& _Right)
> { // assign _Right
> if (this != &_Right)
> { // worth doing
>
> #if _HAS_ITERATOR_DEBUGGING
> this->_Orphan_all();
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> if (_Right.size() == 0)
> clear(); // new sequence empty, erase
> existing sequence
> else if (_Right.size() <= size())
> { // enough elements, copy new and
> destroy old
> pointer _Ptr = _STDEXT
> unchecked_copy(_Right._Myfirst, _Right._Mylast,
> _Myfirst); // copy new
> _Destroy(_Ptr, _Mylast); // destroy
> old
> _Mylast = _Myfirst + _Right.size();
> }
> else if (_Right.size() <= capacity())
> { // enough room, copy and construct
> new
> pointer _Ptr = _Right._Myfirst + size();
> _STDEXT unchecked_copy(_Right._Myfirst, _Ptr,
> _Myfirst);
> _Mylast = _Ucopy(_Ptr, _Right._Mylast,
> _Mylast);
> }
> else
> { // not enough room, allocate new
> array and construct new
> if (_Myfirst != 0)
> { // discard old array
> _Destroy(_Myfirst, _Mylast);
> this->_Alval.deallocate(_Myfirst,
> _Myend - _Myfirst);
> }
> if (_Buy(_Right.size()))
> _Mylast = _Ucopy(_Right._Myfirst,
> _Right._Mylast,
> _Myfirst);
> }
> }
> return (*this);
> }
>
> void reserve(size_type _Count)
> { // determine new minimum length of allocated storage
> if (max_size() < _Count)
> _Xlen(); // result too long
> else if (capacity() < _Count)
> { // not enough room, reallocate
> pointer _Ptr = this->_Alval.allocate(_Count);
>
> _TRY_BEGIN
> _Umove(begin(), end(), _Ptr);
> _CATCH_ALL
> this->_Alval.deallocate(_Ptr, _Count);
> _RERAISE;
> _CATCH_END
>
> size_type _Size = size();
> if (_Myfirst != 0)
> { // destroy and deallocate old array
> _Destroy(_Myfirst, _Mylast);
> this->_Alval.deallocate(_Myfirst, _Myend -
> _Myfirst);
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> this->_Orphan_all();
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _Myend = _Ptr + _Count;
> _Mylast = _Ptr + _Size;
> _Myfirst = _Ptr;
> }
> }
>
> size_type capacity() const
> { // return current length of allocated storage
> return (_Myfirst == 0 ? 0 : _Myend - _Myfirst);
> }
>
> #if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
> iterator begin()
> { // return iterator for beginning of mutable sequence
> return (iterator(_Myfirst, this));
> }
>
> const_iterator begin() const
> { // return iterator for beginning of nonmutable
> sequence
> return (const_iterator(_Myfirst, this));
> }
>
> iterator end()
> { // return iterator for end of mutable sequence
> return (iterator(_Mylast, this));
> }
>
> const_iterator end() const
> { // return iterator for end of nonmutable sequence
> return (const_iterator(_Mylast, this));
> }
>
> iterator _Make_iter(const_iterator _Where) const
> { // make iterator from const_iterator
> return (iterator(_Where._Myptr, this));
> }
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> iterator begin()
> { // return iterator for beginning of mutable sequence
> return (iterator(_Myfirst));
> }
>
> const_iterator begin() const
> { // return iterator for beginning of nonmutable
> sequence
> return (const_iterator(_Myfirst));
> }
>
> iterator end()
> { // return iterator for end of mutable sequence
> return (iterator(_Mylast));
> }
>
> const_iterator end() const
> { // return iterator for end of nonmutable sequence
> return (const_iterator(_Mylast));
> }
>
> iterator _Make_iter(const_iterator _Where) const
> { // make iterator from const_iterator
> return (iterator(_Where._Myptr));
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> reverse_iterator rbegin()
> { // return iterator for beginning of reversed mutable
> sequence
> return (reverse_iterator(end()));
> }
>
> const_reverse_iterator rbegin() const
> { // return iterator for beginning of reversed
> nonmutable sequence
> return (const_reverse_iterator(end()));
> }
>
> reverse_iterator rend()
> { // return iterator for end of reversed mutable
> sequence
> return (reverse_iterator(begin()));
> }
>
> const_reverse_iterator rend() const
> { // return iterator for end of reversed nonmutable
> sequence
> return (const_reverse_iterator(begin()));
> }
>
> void resize(size_type _Newsize)
> { // determine new length, padding with _Ty() elements
> as needed
> resize(_Newsize, _Ty());
> }
>
> void resize(size_type _Newsize, _Ty _Val)
> { // 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
> { // return length of sequence
> return (_Mylast - _Myfirst);
> }
>
> size_type max_size() const
> { // return maximum possible length of sequence
> return (this->_Alval.max_size());
> }
>
> bool empty() const
> { // test if sequence is empty
> return (size() == 0);
> }
>
> _Alloc get_allocator() const
> { // return allocator object for values
> return (this->_Alval);
> }
>
> const_reference at(size_type _Pos) const
> { // subscript nonmutable sequence with checking
> if (size() <= _Pos)
> _Xran();
> return (*(begin() + _Pos));
> }
>
> reference at(size_type _Pos)
> { // subscript mutable sequence with checking
> if (size() <= _Pos)
> _Xran();
> return (*(begin() + _Pos));
> }
>
> const_reference operator[](size_type _Pos) const
> { // subscript nonmutable sequence
>
> #if _HAS_ITERATOR_DEBUGGING
> if (size() <= _Pos)
> {
> _DEBUG_ERROR("vector subscript out of range");
> _SCL_SECURE_OUT_OF_RANGE;
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
> _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
>
> return (*(_Myfirst + _Pos));
> }
>
> reference operator[](size_type _Pos)
> { // subscript mutable sequence
>
> #if _HAS_ITERATOR_DEBUGGING
> if (size() <= _Pos)
> {
> _DEBUG_ERROR("vector subscript out of range");
> _SCL_SECURE_OUT_OF_RANGE;
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
> _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
>
> return (*(_Myfirst + _Pos));
> }
>
> 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 _Ty& _Val)
> { // insert element at end
> if (size() < capacity())
>
> #if _HAS_ITERATOR_DEBUGGING
> { // room at end, construct it there
> _Orphan_range(_Mylast, _Mylast);
> _Mylast = _Ufill(_Mylast, 1, _Val);
> }
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> _Mylast = _Ufill(_Mylast, 1, _Val);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> else
> insert(end(), _Val);
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> void pop_back()
> { // erase element at end
> if (empty())
> _DEBUG_ERROR("vector empty before pop");
> else
> { // erase last element
> _Orphan_range(_Mylast - 1, _Mylast);
> _Destroy(_Mylast - 1, _Mylast);
> --_Mylast;
> }
> }
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> void pop_back()
> { // erase element at end
> if (!empty())
> { // erase last element
> _Destroy(_Mylast - 1, _Mylast);
> --_Mylast;
> }
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> template<class _Iter>
> void assign(_Iter _First, _Iter _Last)
> { // assign [_First, _Last)
> _Assign(_First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag)
> { // assign _Count * _Val
> _Assign_n((size_type)_Count, (_Ty)_Val);
> }
>
> template<class _Iter>
> void _Assign(_Iter _First, _Iter _Last, input_iterator_tag)
> { // assign [_First, _Last), input iterators
> erase(begin(), end());
> insert(begin(), _First, _Last);
> }
>
> void assign(size_type _Count, const _Ty& _Val)
> { // assign _Count * _Val
> _Assign_n(_Count, _Val);
> }
>
> iterator insert(const_iterator _Where, const _Ty& _Val)
> { // insert _Val at _Where
> size_type _Off = size() == 0 ? 0 : _Where - begin();
> _Insert_n(_Where, (size_type)1, _Val);
> return (begin() + _Off);
> }
>
> void insert(const_iterator _Where, size_type _Count, const _Ty& _Val)
> { // insert _Count * _Val at _Where
> _Insert_n(_Where, _Count, _Val);
> }
>
> template<class _Iter>
> void insert(const_iterator _Where, _Iter _First, _Iter _Last)
> { // insert [_First, _Last) at _Where
> _Insert(_Where, _First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> void _Insert(const_iterator _Where, _Iter _First, _Iter
> _Last,
> _Int_iterator_tag)
> { // insert _Count * _Val at _Where
> _Insert_n(_Where, (size_type)_First, (_Ty)_Last);
> }
>
> template<class _Iter>
> void _Insert(const_iterator _Where, _Iter _First, _Iter
> _Last,
> input_iterator_tag)
> { // insert [_First, _Last) at _Where, input iterators
>
> #if _HAS_ITERATOR_DEBUGGING
> if (_Where._Mycont != this
> || _Where._Myptr < _Myfirst || _Mylast <
> _Where._Myptr)
> _DEBUG_ERROR("vector insert iterator outside range");
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> if (_First != _Last)
> { // worth doing, gather at end and rotate into
> place
> size_type _Oldsize = size();
> size_type _Whereoff = _Where._Myptr - _Myfirst;
>
> for (; _First != _Last; ++_First)
> _Insert_n(end(), (size_type)1,
> (value_type)*_First);
>
> _Reverse(_Myfirst + _Whereoff, _Myfirst + _Oldsize);
> _Reverse(_Myfirst + _Oldsize, _Mylast);
> _Reverse(_Myfirst + _Whereoff, _Mylast);
> }
> }
>
> template<class _Iter>
> void _Insert(const_iterator _Where,
> _Iter _First, _Iter _Last, forward_iterator_tag)
> { // insert [_First, _Last) at _Where, forward
> iterators
>
> #if _HAS_ITERATOR_DEBUGGING
> if (_Where._Mycont != this
> || _Where._Myptr < _Myfirst || _Mylast <
> _Where._Myptr)
> _DEBUG_ERROR("vector insert iterator outside range");
> _DEBUG_RANGE(_First, _Last);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> size_type _Count = 0;
> _Distance(_First, _Last, _Count);
> size_type _Capacity = capacity();
>
> if (_Count == 0)
> ;
> else if (max_size() - size() < _Count)
> _Xlen(); // result too long
> else if (_Capacity < size() + _Count)
> { // not enough room, reallocate
> _Capacity = max_size() - _Capacity / 2 < _Capacity
> ? 0 : _Capacity + _Capacity / 2; //
> try to grow by 50%
> if (_Capacity < size() + _Count)
> _Capacity = size() + _Count;
> pointer _Newvec = this->_Alval.allocate(_Capacity);
> pointer _Ptr = _Newvec;
>
> _TRY_BEGIN
> _Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),
> _Newvec); // copy prefix
> _Ptr = _Ucopy(_First, _Last, _Ptr); // add new
> stuff
> _Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr); //
> copy suffix
> _CATCH_ALL
> _Destroy(_Newvec, _Ptr);
> this->_Alval.deallocate(_Newvec, _Capacity);
> _RERAISE;
> _CATCH_END
>
> _Count += size();
> if (_Myfirst != 0)
> { // destroy and deallocate old array
> _Destroy(_Myfirst, _Mylast);
> this->_Alval.deallocate(_Myfirst, _Myend -
> _Myfirst);
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> this->_Orphan_all();
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _Myend = _Newvec + _Capacity;
> _Mylast = _Newvec + _Count;
> _Myfirst = _Newvec;
> }
> else
> { // new stuff fits, append and rotate into
> place
> _Ucopy(_First, _Last, _Mylast);
>
> _Reverse(_Where._Myptr, _Mylast);
> _Reverse(_Mylast, _Mylast + _Count);
> _Reverse(_Where._Myptr, _Mylast + _Count);
>
> _Mylast += _Count;
>
> #if _HAS_ITERATOR_DEBUGGING
> _Orphan_range(_Where._Myptr, _Mylast);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> }
> }
>
> void _Reverse(pointer _First, pointer _Last)
> { // reverse a subrange
> for (; _First != _Last && _First != --_Last; ++_First)
> _STD _Swap_adl(*_First, *_Last);
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> iterator erase(const_iterator _Where)
> { // erase element at where
> if (_Where._Mycont != this
> || _Where._Myptr < _Myfirst || _Mylast <=
> _Where._Myptr)
> _DEBUG_ERROR("vector erase iterator outside range");
> _STDEXT unchecked_copy(_Where._Myptr + 1, _Mylast,
> _Where._Myptr);
> _Destroy(_Mylast - 1, _Mylast);
> _Orphan_range(_Where._Myptr, _Mylast);
> --_Mylast;
> return (iterator(_Where._Myptr, this));
> }
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> iterator erase(const_iterator _Where)
> { // erase element at where
> _STDEXT unchecked_copy(_VEC_ITER_BASE(_Where) + 1, _Mylast,
> _VEC_ITER_BASE(_Where));
> _Destroy(_Mylast - 1, _Mylast);
> --_Mylast;
> return (_Make_iter(_Where));
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> 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);
>
> if (_First != _Last)
> { // worth doing, copy down over hole
>
> #if _HAS_ITERATOR_DEBUGGING
> if (_Last < _First || _First._Mycont != this
> || _First._Myptr < _Myfirst || _Mylast <
> _Last._Myptr)
> _DEBUG_ERROR("vector erase iterator outside
> range");
> pointer _Ptr = _STDEXT
> unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
> _VEC_ITER_BASE(_First));
> _Orphan_range(_First._Myptr, _Mylast);
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> pointer _Ptr = _STDEXT
> unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
> _VEC_ITER_BASE(_First));
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _Destroy(_Ptr, _Mylast);
> _Mylast = _Ptr;
> }
> #if _HAS_ITERATOR_DEBUGGING
> return (iterator(_First._Myptr, this));
> #else
> return (_First);
> #endif
> }
>
> void clear()
> { // erase all
> erase(begin(), end());
> }
>
> void swap(_Myt& _Right)
> { // exchange contents with _Right
> if (this == &_Right)
> ; // same object, do nothing
> else if (this->_Alval == _Right._Alval)
> { // same allocator, swap control information
>
> #if _HAS_ITERATOR_DEBUGGING
> this->_Swap_all(_Right);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> this->_Swap_aux(_Right);
>
> _STD swap(_Myfirst, _Right._Myfirst);
> _STD swap(_Mylast, _Right._Mylast);
> _STD swap(_Myend, _Right._Myend);
> }
> else
> { // different allocator, do multiple assigns
> this->_Swap_aux(_Right);
>
> _Myt _Ts = *this;
>
> *this = _Right;
> _Right = _Ts;
> }
> }
>
>
>
> protected:
> void _Assign_n(size_type _Count, const _Ty& _Val)
> { // assign _Count * _Val
> _Ty _Tmp = _Val; // in case _Val is in sequence
> erase(begin(), end());
> insert(begin(), _Count, _Tmp);
> }
>
> bool _Buy(size_type _Capacity)
> { // allocate array with _Capacity elements
> _Myfirst = 0, _Mylast = 0, _Myend = 0;
> if (_Capacity == 0)
> return (false);
> else if (max_size() < _Capacity)
> _Xlen(); // result too long
> else
> { // nonempty array, allocate storage
> _Myfirst = this->_Alval.allocate(_Capacity);
> _Mylast = _Myfirst;
> _Myend = _Myfirst + _Capacity;
> }
> return (true);
> }
>
> void _Destroy(pointer _First, pointer _Last)
> { // destroy [_First, _Last) using allocator
> _Destroy_range(_First, _Last, this->_Alval);
> }
>
> void _Tidy()
> { // free all storage
> if (_Myfirst != 0)
> { // something to free, destroy and deallocate
> it
>
> #if _HAS_ITERATOR_DEBUGGING
> this->_Orphan_all();
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _Destroy(_Myfirst, _Mylast);
> this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
> }
> _Myfirst = 0, _Mylast = 0, _Myend = 0;
> }
>
> template<class _Iter>
> pointer _Ucopy(_Iter _First, _Iter _Last, pointer _Ptr)
> { // copy initializing [_First, _Last), using allocator
> return (_STDEXT unchecked_uninitialized_copy(_First, _Last,
> _Ptr, this->_Alval));
> }
>
> template<class _Iter>
> pointer _Umove(_Iter _First, _Iter _Last, pointer _Ptr)
> { // move initializing [_First, _Last), using allocator
> return (_STDEXT _Unchecked_uninitialized_move(_First, _Last,
> _Ptr, this->_Alval));
> }
>
> void _Insert_n(const_iterator _Where,
> size_type _Count, const _Ty& _Val)
> { // insert _Count * _Val at _Where
>
> #if _HAS_ITERATOR_DEBUGGING
> if (_Where._Mycont != this
> || _Where._Myptr < _Myfirst || _Mylast <
> _Where._Myptr)
> _DEBUG_ERROR("vector insert iterator outside range");
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> size_type _Capacity = capacity();
>
> if (_Count == 0)
> ;
> else if (max_size() - size() < _Count)
> _Xlen(); // result too long
> else if (_Capacity < size() + _Count)
> { // not enough room, reallocate
> _Capacity = max_size() - _Capacity / 2 < _Capacity
> ? 0 : _Capacity + _Capacity / 2; //
> try to grow by 50%
> if (_Capacity < size() + _Count)
> _Capacity = size() + _Count;
> pointer _Newvec = this->_Alval.allocate(_Capacity);
> size_type _Whereoff = _VEC_ITER_BASE(_Where) -
> _Myfirst;
> int _Ncopied = 0;
>
> _TRY_BEGIN
> _Ufill(_Newvec + _Whereoff, _Count, _Val); //
> add new stuff
> ++_Ncopied;
> _Umove(this->_Myfirst, _VEC_ITER_BASE(_Where),
> _Newvec); // move prefix
> ++_Ncopied;
> _Umove(_VEC_ITER_BASE(_Where), this->_Mylast,
> _Newvec + (_Whereoff + _Count)); //
> move suffix
> _CATCH_ALL
> if (1 < _Ncopied)
> _Destroy(_Newvec, _Newvec + _Whereoff);
> if (0 < _Ncopied)
> _Destroy(_Newvec + _Whereoff, _Newvec +
> _Whereoff + _Count);
> this->_Alval.deallocate(_Newvec, _Capacity);
> _RERAISE;
> _CATCH_END
>
> _Count += size();
> if (_Myfirst != 0)
> { // destroy and deallocate old array
> _Destroy(_Myfirst, _Mylast);
> this->_Alval.deallocate(_Myfirst, _Myend -
> _Myfirst);
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> this->_Orphan_all();
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _Myend = _Newvec + _Capacity;
> _Mylast = _Newvec + _Count;
> _Myfirst = _Newvec;
> }
> else if ((size_type)(_Mylast - _VEC_ITER_BASE(_Where)) <
> _Count)
> { // new stuff spills off end
> _Ty _Tmp = _Val; // in case _Val is in
> sequence
>
> _Umove(_VEC_ITER_BASE(_Where), _Mylast,
> _VEC_ITER_BASE(_Where) + _Count); //
> copy suffix
>
> _TRY_BEGIN
> _Ufill(_Mylast, _Count - (_Mylast -
> _VEC_ITER_BASE(_Where)),
> _Tmp); // insert new stuff off end
> _CATCH_ALL
> _Destroy(_VEC_ITER_BASE(_Where) + _Count, _Mylast +
> _Count);
> _RERAISE;
> _CATCH_END
>
> _Mylast += _Count;
>
> #if _HAS_ITERATOR_DEBUGGING
> _Orphan_range(_Where._Myptr, _Mylast);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> std::fill(_VEC_ITER_BASE(_Where), _Mylast - _Count,
> _Tmp); // insert up to old end
> }
> else
> { // new stuff can all be assigned
> _Ty _Tmp = _Val; // in case _Val is in
> sequence
>
> pointer _Oldend = _Mylast;
> _Mylast = _Umove(_Oldend - _Count, _Oldend,
> _Mylast); // copy suffix
>
> #if _HAS_ITERATOR_DEBUGGING
> _Orphan_range(_Where._Myptr, _Mylast);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _STDEXT
> _Unchecked_move_backward(_VEC_ITER_BASE(_Where), _Oldend - _Count,
> _Oldend); // copy hole
> std::fill(_VEC_ITER_BASE(_Where),
> _VEC_ITER_BASE(_Where) + _Count,
> _Tmp); // insert into hole
> }
> }
>
> pointer _Ufill(pointer _Ptr, size_type _Count, const _Ty &_Val)
> { // copy initializing _Count * _Val, using allocator
> _STDEXT unchecked_uninitialized_fill_n(_Ptr, _Count, _Val,
> this->_Alval);
> return (_Ptr + _Count);
> }
>
> static void _Xlen()
> { // report a length_error
> _THROW(length_error, "vector<T> too long");
> }
>
> static void _Xran()
> { // report an out_of_range error
> _THROW(out_of_range, "invalid vector<T> subscript");
> }
>
> static void _Xinvarg()
> { // report an invalid_argument error
> _THROW(invalid_argument, "invalid vector<T> argument");
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> void _Orphan_range(pointer _First, pointer _Last) const
> { // orphan iterators within specified (inclusive)
> range
> _Lockit _Lock(_LOCK_DEBUG);
> const_iterator **_Pnext = (const_iterator
> **)&this->_Myfirstiter;
> while (*_Pnext != 0)
> if ((*_Pnext)->_Myptr < _First || _Last <
> (*_Pnext)->_Myptr)
> _Pnext = (const_iterator
> **)&(*_Pnext)->_Mynextiter;
> else
> { // orphan the iterator
> (*_Pnext)->_Mycont = 0;
> *_Pnext = (const_iterator
> *)(*_Pnext)->_Mynextiter;
> }
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> pointer _Myfirst; // pointer to beginning of array
> pointer _Mylast; // pointer to current end of sequence
> pointer _Myend; // pointer to end of array
> };
>
> // vector implements a performant swap
> template <class _Ty, class _Ax>
> class _Move_operation_category<vector<_Ty, _Ax> >
> {
> public:
> typedef _Swap_move_tag _Move_cat;
> };
>
> // vector TEMPLATE FUNCTIONS
> 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 _Ty,
> class _Alloc> inline
> void swap(vector<_Ty, _Alloc>& _Left, vector<_Ty, _Alloc>& _Right)
> { // swap _Left and _Right vectors
> _Left.swap(_Right);
> }
>
> //
> // TEMPLATE CLASS vector<bool, Alloc> AND FRIENDS
> //
> typedef unsigned _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 _Sizet,
> class _Difft,
> class _MycontTy>
> class _Vb_iter_base
> : public _Ranit<_Bool, _Difft, bool *, bool>
> { // store information common to reference and iterators
> public:
> #if _SECURE_SCL
> typedef _Range_checked_iterator_tag _Checked_iterator_category;
> #endif
>
> _Vb_iter_base()
> : _Myptr(0), _Myoff(0)
> { // construct with null pointer
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> _Vb_iter_base(_Vbase *_Ptr, _Sizet _Off,
> const _Container_base *_Mypvbool)
> : _Myptr(_Ptr), _Myoff(_Off)
> { // construct with offset and pointer
> _SCL_SECURE_VALIDATE(_Mypvbool != NULL);
> this->_Adopt(_Mypvbool);
> }
>
> #elif _SECURE_SCL
> _Vb_iter_base(_Vbase *_Ptr, _Sizet _Off,
> const _Container_base *_Mypvbool)
> : _Myptr(_Ptr), _Myoff(_Off)
> { // construct with offset and pointer
> _SCL_SECURE_VALIDATE(_Mypvbool != NULL);
> this->_Set_container(_Mypvbool);
> }
> #else
> _Vb_iter_base(_Vbase *_Ptr, _Sizet _Off)
> : _Myptr(_Ptr), _Myoff(_Off)
> { // construct with offset and pointer
> }
> #endif
>
> _Vbase *_Myptr;
> _Sizet _Myoff;
>
> static void _Xlen()
> { // report a length_error
> _THROW(length_error, "vector<bool> too long");
> }
>
> static void _Xran()
> { // report an out_of_range error
> _THROW(out_of_range, "invalid vector<bool> subscript");
> }
>
> static void _Xinvarg()
> { // report an invalid_argument error
> _THROW(invalid_argument, "invalid vector<bool> argument");
> }
>
> #if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
> _Vbase * _My_cont_begin() const
> {
> return (_VEC_ITER_BASE(((_MycontTy *)this->
> _Getmycont())->_Myvec.begin()));
> }
>
> _Sizet _My_actual_offset() const
> {
> _Sizet _Off = this->_Myoff;
> _Off += _VBITS * (this->_Myptr - _My_cont_begin());
> return (_Off);
> }
> #endif
> };
>
> // CLASS _Vb_reference
> template<class _Sizet,
> class _Difft,
> class _MycontTy>
> class _Vb_reference
> : public _Vb_iter_base<_Sizet, _Difft, _MycontTy>
> { // reference to a bit within a base word
> public:
> typedef _Vb_iter_base<_Sizet, _Difft, _MycontTy> _Mybase;
> typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Mytype;
>
> _Vb_reference()
> { // construct with null pointer
> }
>
> #if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
> _Vb_reference(const _Mybase& _Right)
> : _Mybase(_Right._Myptr, _Right._Myoff, _Right._Getmycont())
> { // construct with base
> }
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> _Vb_reference(const _Mybase& _Right)
> : _Mybase(_Right._Myptr, _Right._Myoff)
> { // construct with base
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _Mytype& operator=(const _Mytype& _Right)
> { // assign _Vb_reference _Right to bit
> return (*this = bool(_Right));
> }
>
> _Mytype& operator=(bool _Val)
> { // assign _Val to bit
> if (_Val)
> *_Getptr() |= _Mask();
> else
> *_Getptr() &= ~_Mask();
> return (*this);
> }
>
> void flip()
> { // toggle the bit
> *_Getptr() ^= _Mask();
> }
>
> bool operator~() const
> { // test if bit is reset
> return (!bool(*this));
> }
>
> operator bool() const
> { // test if bit is set
> return ((*_Getptr() & _Mask()) != 0);
> }
>
> _Vbase *_Getptr() const
> { // get pointer to base word
>
> #if _HAS_ITERATOR_DEBUGGING
> if (this->_Mycont == 0 || this->_Myptr == 0)
> {
> _DEBUG_ERROR("vector<bool> iterator not
> dereferencable");
> _SCL_SECURE_OUT_OF_RANGE;
> }
> #else /* _HAS_ITERATOR_DEBUGGING */
> _SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr
> != NULL);
> _SCL_SECURE_VALIDATE_RANGE(this->_My_actual_offset() <
> ((_MycontTy *)this->_Getmycont())->_Mysize);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> return (this->_Myptr);
> }
>
> protected:
> _Vbase _Mask() const
> { // convert offset to mask
> return ((_Vbase)(1 << this->_Myoff));
> }
> };
>
> template<class _Sizet,
> class _Difft,
> class _MycontTy>
> void swap(_Vb_reference<_Sizet, _Difft, _MycontTy> _Left,
> _Vb_reference<_Sizet, _Difft, _MycontTy> _Right)
> { // swap _Left and _Right vector<bool> elements
> bool _Val = _Left;
> _Left = _Right;
> _Right = _Val;
> }
>
> // CLASS _Vb_const_iterator
> template<class _Sizet,
> class _Difft,
> class _MycontTy>
> class _Vb_const_iterator
> : public _Vb_iter_base<_Sizet, _Difft, _MycontTy>
> { // iterator for nonmutable vector<bool>
> public:
> typedef _Vb_iter_base<_Sizet, _Difft, _MycontTy> _Mybase;
> typedef _Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Mytype;
>
> typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Reft;
> typedef bool const_reference;
>
> typedef random_access_iterator_tag iterator_category;
> typedef _Bool value_type;
> typedef _Sizet size_type;
> typedef _Difft difference_type;
> typedef const_reference *pointer;
> typedef const_reference reference;
>
> _Vb_const_iterator()
> { // construct with null reference
> }
>
> #if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
> _Vb_const_iterator(const _Vbase *_Ptr, const _Container_base
> *_Mypvbool)
> : _Mybase((_Vbase *)_Ptr, 0, (_Container_base *)_Mypvbool)
>
> #else
> _Vb_const_iterator(const _Vbase *_Ptr)
> : _Mybase((_Vbase *)_Ptr, 0)
>
> #endif
> { // 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)
> return (*this); // early out
> _SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr
> != NULL);
> if (_Off < 0)
> {
> _SCL_SECURE_VALIDATE_RANGE(this->_My_actual_offset()
>>= ((size_type)-_Off));
> }
> else
> {
> _SCL_SECURE_VALIDATE_RANGE((this->_My_actual_offset()
> + _Off) <= ((_MycontTy *)this->_Getmycont())->_Mysize);
> }
> 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
>
> #if _HAS_ITERATOR_DEBUGGING
> _Compat(_Right);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> 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
>
> #if _HAS_ITERATOR_DEBUGGING
> _Compat(_Right);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> 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
>
> #if _HAS_ITERATOR_DEBUGGING
> _Compat(_Right);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> 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));
> }
>
> protected:
>
> #if _HAS_ITERATOR_DEBUGGING
> void _Compat(const _Mytype& _Right) const
> { // test for compatible iterator pair
> if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
> _DEBUG_ERROR("vector<bool> iterators incompatible");
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> void _Dec()
> { // decrement bit position
> if (this->_Myoff != 0)
> {
> --this->_Myoff;
> }
> else
> {
> _SCL_SECURE_VALIDATE(this->_Has_container() &&
> this->_Myptr != NULL);
> _SCL_SECURE_VALIDATE_RANGE(this->_Myptr >
> this->_My_cont_begin());
> --this->_Myptr;
> this->_Myoff = _VBITS - 1;
> }
> }
>
> void _Inc()
> { // increment bit position
> _SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr
> != NULL);
> _SCL_SECURE_VALIDATE_RANGE((this->_My_actual_offset() + 1) <=
> ((_MycontTy *)this->_Getmycont())->_Mysize);
> if (this->_Myoff < _VBITS - 1)
> ++this->_Myoff;
> else
> this->_Myoff = 0, ++this->_Myptr;
> }
> };
>
> template<class _Sizet,
> class _Difft,
> class _MycontTy>
> _Vb_const_iterator<_Sizet, _Difft, _MycontTy> operator+(_Difft _Off,
> _Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Right)
> { // return _Right + integer
> return (_Right += _Off);
> }
>
> // CLASS _Vb_iterator
> template<class _Sizet,
> class _Difft,
> class _MycontTy>
> class _Vb_iterator
> : public _Vb_const_iterator<_Sizet, _Difft, _MycontTy>
> { // iterator for mutable vector<bool>
> public:
> typedef _Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Mybase;
> typedef _Vb_iterator<_Sizet, _Difft, _MycontTy> _Mytype;
>
> typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Reft;
> typedef bool const_reference;
>
> typedef random_access_iterator_tag iterator_category;
> typedef _Bool value_type;
> typedef _Sizet size_type;
> typedef _Difft difference_type;
> typedef _Reft *pointer;
> typedef _Reft reference;
>
> _Vb_iterator()
> { // construct with null reference
> }
>
> #if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
> _Vb_iterator(_Vbase *_Ptr, _Container_base *_Mypvbool)
> : _Mybase(_Ptr, _Mypvbool)
>
> #else
> _Vb_iterator( _Vbase *_Ptr)
> : _Mybase(_Ptr)
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> { // 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 _Sizet,
> class _Difft,
> class _MycontTy>
> _Vb_iterator<_Sizet, _Difft, _MycontTy> operator+(_Difft _Off,
> _Vb_iterator<_Sizet, _Difft, _MycontTy> _Right)
> { // return _Right + integer
> return (_Right += _Off);
> }
>
> // CLASS vector_bool
> template<class _Alloc>
> class vector<_Bool, _Alloc>
> : public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
> { // varying size array of bits
> public:
> typedef typename _Alloc::size_type size_type;
> typedef typename _Alloc::difference_type _Dift;
> typedef std::vector<_Vbase,
> typename _Alloc::template rebind<_Vbase>::other>
> _Vbtype;
> typedef std::vector<_Bool, _Alloc> _Myt;
>
>
> typedef _Dift difference_type;
> typedef _Bool _Ty;
> typedef _Alloc allocator_type;
>
> typedef _Vb_reference<size_type, _Dift, _Myt> reference;
> typedef bool const_reference;
> typedef bool value_type;
>
> typedef reference _Reft;
> typedef _Vb_const_iterator<size_type, difference_type, _Myt>
> const_iterator;
> typedef _Vb_iterator<size_type, difference_type, _Myt> iterator;
>
> friend class _Vb_iter_base<size_type, difference_type, _Myt>;
> friend class _Vb_reference<size_type, difference_type, _Myt>;
> friend class _Vb_const_iterator<size_type, difference_type, _Myt>;
> friend class _Vb_iterator<size_type, difference_type, _Myt>;
>
> 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;
>
> vector()
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0),
> _Myvec()
> { // construct empty vector
> }
>
> vector(const _Myt& _Right)
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Right.get_allocator()),
> _Mysize(_Right._Mysize), _Myvec(_Right._Myvec)
> { // copy construct vector; an implicitly defined copy
> constructor would not create an aux object.
> }
>
> explicit vector(const _Alloc& _Al)
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0),
> _Myvec(_Al)
> { // construct empty vector, with allocator
> }
>
> explicit vector(size_type _Count, bool _Val = false)
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0),
> _Myvec(_Nw(_Count), (_Vbase)(_Val ? -1 : 0))
> { // construct from _Count * _Val
> _Trim(_Count);
> }
>
> vector(size_type _Count, bool _Val, const _Alloc& _Al)
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0),
> _Myvec(_Nw(_Count), (_Vbase)(_Val ? -1 : 0), _Al)
> { // construct from _Count * _Val, with allocator
> _Trim(_Count);
> }
>
> template<class _Iter>
> vector(_Iter _First, _Iter _Last)
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0),
> _Myvec()
> { // construct from [_First, _Last)
> _BConstruct(_First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> vector(_Iter _First, _Iter _Last, const _Alloc& _Al)
> : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0),
> _Myvec(_Al)
> { // construct from [_First, _Last), with allocator
> _BConstruct(_First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> void _BConstruct(_Iter _Count, _Iter _Val, _Int_iterator_tag)
> { // initialize from _Count * _Val
> size_type _Num = (size_type)_Count;
> _Myvec.assign(_Num, (_Ty)_Val ? -1 : 0);
> _Trim(_Num);
> }
>
> template<class _Iter>
> void _BConstruct(_Iter _First, _Iter _Last,
> input_iterator_tag)
> { // initialize from [_First, _Last), input iterators
> insert(begin(), _First, _Last);
> }
>
> ~vector()
> { // destroy the object
> _Mysize = 0;
> }
>
> void reserve(size_type _Count)
> { // determine new minimum length of allocated storage
> _Myvec.reserve(_Nw(_Count));
> }
>
> size_type capacity() const
> { // return current length of allocated storage
> return (_Myvec.capacity() * _VBITS);
> }
>
> #if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
> iterator begin()
> { // return iterator for beginning of mutable sequence
> return (iterator(_VEC_ITER_BASE(_Myvec.begin()), this));
> }
>
> const_iterator begin() const
> { // return iterator for beginning of nonmutable
> sequence
> return (const_iterator(_VEC_ITER_BASE(_Myvec.begin()),
> this));
> }
>
> #else
> iterator begin()
> { // return iterator for beginning of mutable sequence
> return (iterator(_VEC_ITER_BASE(_Myvec.begin())));
> }
>
> const_iterator begin() const
> { // return iterator for beginning of nonmutable
> sequence
> return (const_iterator(_VEC_ITER_BASE(_Myvec.begin())));
> }
> #endif
>
> iterator end()
> { // return iterator for end of mutable sequence
> iterator _Tmp = begin();
> if (0 < _Mysize)
> _Tmp += _Mysize;
> return (_Tmp);
> }
>
> const_iterator end() const
> { // return iterator for end of nonmutable sequence
> const_iterator _Tmp = begin();
> if (0 < _Mysize)
> _Tmp += _Mysize;
> return (_Tmp);
> }
>
> iterator _Make_iter(const_iterator _Where)
> { // make iterator from const_iterator
> iterator _Tmp = begin();
> if (0 < _Mysize)
> _Tmp += _Where - begin();
> return (_Tmp);
> }
>
> reverse_iterator rbegin()
> { // return iterator for beginning of reversed mutable
> sequence
> return (reverse_iterator(end()));
> }
>
> const_reverse_iterator rbegin() const
> { // return iterator for beginning of reversed
> nonmutable sequence
> return (const_reverse_iterator(end()));
> }
>
> reverse_iterator rend()
> { // return iterator for end of reversed mutable
> sequence
> return (reverse_iterator(begin()));
> }
>
> const_reverse_iterator rend() const
> { // 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
> { // return length of sequence
> return (_Mysize);
> }
>
> size_type max_size() const
> { // return maximum possible length of sequence
> const size_type _Maxsize = _Myvec.max_size();
> return (_Maxsize < (size_type)(-1) / _VBITS
> ? _Maxsize * _VBITS : (size_type)(-1));
> }
>
> bool empty() const
> { // test if sequence is empty
> return (size() == 0);
> }
>
> _Alloc get_allocator() const
> { // return allocator object for values
> // Work around a BE problem.
> _Alloc _Alret = _Myvec.get_allocator();
> return (_Alret);
> }
>
> const_reference at(size_type _Off) const
> { // subscript nonmutable sequence with checking
> if (size() <= _Off)
> _Xran();
> return (*(begin() + _Off));
> }
>
> reference at(size_type _Off)
> { // subscript mutable sequence with checking
> if (size() <= _Off)
> _Xran();
> return (*(begin() + _Off));
> }
>
> const_reference operator[](size_type _Off) const
> { // subscript nonmutable sequence
> return (*(begin() + _Off));
> }
>
> reference operator[](size_type _Off)
> { // subscript mutable sequence
> return (*(begin() + _Off));
> }
>
> 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(bool _Val)
> { // insert element at end
> insert(end(), _Val);
> }
>
> void pop_back()
> { // erase element at end
> if (!empty())
> erase(end() - 1);
> }
>
> template<class _Iter>
> void assign(_Iter _First, _Iter _Last)
> { // assign [_First, _Last)
> _Assign(_First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag)
> { // assign _Count * _Val
> _Assign_n((size_type)_Count, (bool)_Val);
> }
>
> template<class _Iter>
> void _Assign(_Iter _First, _Iter _Last, input_iterator_tag)
> { // assign [_First, _Last), input iterators
> erase(begin(), end());
> insert(begin(), _First, _Last);
> }
>
> void assign(size_type _Count, bool _Val)
> { // assign _Count * _Val
> _Assign_n(_Count, _Val);
> }
>
> iterator insert(const_iterator _Where, bool _Val)
> { // insert _Val at _Where
> size_type _Off = _Where - begin();
> _Insert_n(_Where, (size_type)1, _Val);
> return (begin() + _Off);
> }
>
> void insert(const_iterator _Where, size_type _Count, bool _Val)
> { // insert _Count * _Val at _Where
> _Insert_n(_Where, _Count, _Val);
> }
>
> template<class _Iter>
> void insert(const_iterator _Where, _Iter _First, _Iter _Last)
> { // insert [_First, _Last) at _Where
> _Insert(_Where, _First, _Last, _Iter_cat(_First));
> }
>
> template<class _Iter>
> void _Insert(const_iterator _Where, _Iter _Count, _Iter _Val,
> _Int_iterator_tag)
> { // insert _Count * _Val at _Where
> _Insert_n(_Where, (size_type)_Count, (bool)_Val);
> }
>
> 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
>
> #if _HAS_ITERATOR_DEBUGGING
> _DEBUG_RANGE(_First, _Last);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> 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 _HAS_ITERATOR_DEBUGGING
> if (end() <= _Where)
> _DEBUG_ERROR("vector<bool> erase iterator outside
> range");
> std::copy(_Where + 1, end(), _Where);
> _Orphan_range(_Off, _Mysize);
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> std::copy(_Where + 1, end(), _Where);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> _Trim(_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 _HAS_ITERATOR_DEBUGGING
> 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, _Mysize);
> _Trim(_Newsize);
>
> #else /* _HAS_ITERATOR_DEBUGGING */
> iterator _Next = std::copy(_Last, end(), _First);
> _Trim(_Next - begin());
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> return (begin() + _Off);
> }
>
> void clear()
> { // erase all elements
> erase(begin(), end());
> }
>
> void flip()
> { // toggle all elements
> for (_Vbtype::iterator _Next = _Myvec.begin();
> _Next != _Myvec.end(); ++_Next)
> *_Next = (_Vbase)~*_Next;
> _Trim(_Mysize);
> }
>
> void swap(_Myt& _Right)
> { // exchange contents with right
> if (this != &_Right)
> { // different, worth swapping
>
> #if _HAS_ITERATOR_DEBUGGING
> this->_Swap_all(_Right);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> this->_Swap_aux(_Right);
> _STD swap(_Mysize, _Right._Mysize);
> _Myvec.swap(_Right._Myvec);
> }
> }
>
>
>
> static void swap(reference _Left, reference _Right)
> { // swap _Left and _Right vector<bool> elements
> bool _Val = _Left;
>
> _Left = _Right;
> _Right = _Val;
> }
>
>
> protected:
> void _Assign_n(size_type _Count, bool _Val)
> { // assign _Count * _Val
> erase(begin(), end());
> _Insert_n(begin(), _Count, _Val);
> }
>
> void _Insert_n(const_iterator _Where,
> size_type _Count, bool _Val)
> { // insert _Count * _Val at _Where
> size_type _Off = _Insert_x(_Where, _Count);
> std::fill(begin() + _Off, begin() + (_Off + _Count), _Val);
> }
>
> size_type _Insert_x(const_iterator _Where, size_type _Count)
> { // make room to insert _Count elements at _Where
> size_type _Off = _Where - begin();
>
> #if _HAS_ITERATOR_DEBUGGING
> if (end() < _Where)
> _DEBUG_ERROR("vector<bool> insert iterator outside
> range");
> bool _Realloc = capacity() - size() < _Count;
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> if (_Count == 0)
> ;
> else if (max_size() - size() < _Count)
> _Xlen(); // result too long
> else
> { // worth doing
> _Myvec.resize(_Nw(size() + _Count), 0);
> if (size() == 0)
> _Mysize += _Count;
> else
> { // make room and copy down suffix
> iterator _Oldend = end();
> _Mysize += _Count;
> std::copy_backward(begin() + _Off, _Oldend,
> end());
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> _Orphan_range(_Realloc ? 0 : _Off, _Mysize);
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> }
> return (_Off);
> }
>
> static size_type _Nw(size_type _Count)
> { // return number of base words from number of bits
> return ((_Count + _VBITS - 1) / _VBITS);
> }
>
> #if _HAS_ITERATOR_DEBUGGING
> void _Orphan_range(size_type _Offlo, size_type _Offhi) const
> { // orphan iterators within specified (inclusive)
> range
> typedef _Vb_iter_base<size_type, difference_type, _Myt>
> _Myiterbase;
>
> _Lockit _Lock(_LOCK_DEBUG);
> _Vbase *_Base = (_Vbase *)_VEC_ITER_BASE(_Myvec.begin());
>
> _Myiterbase **_Pnext =
> (_Myiterbase **)&this->_Myfirstiter;
> while (*_Pnext != 0)
> { // test offset from beginning of vector
> size_type _Off = _VBITS * ((*_Pnext)->_Myptr - _Base)
> + (*_Pnext)->_Myoff;
> if (_Off < _Offlo || _Offhi < _Off)
> _Pnext = (_Myiterbase
> **)&(*_Pnext)->_Mynextiter;
> else
> { // orphan the iterator
> (*_Pnext)->_Mycont = 0;
> *_Pnext = (_Myiterbase
> *)(*_Pnext)->_Mynextiter;
> }
> }
> }
> #endif /* _HAS_ITERATOR_DEBUGGING */
>
> void _Trim(size_type _Size)
> { // trim base vector to exact length in bits
> if (max_size() < _Size)
> _Xlen(); // result too long
> size_type _Words = _Nw(_Size);
>
> if (_Words < _Myvec.size())
> _Myvec.erase(_Myvec.begin() + _Words, _Myvec.end());
> _Mysize = _Size;
> _Size %= _VBITS;
> if (0 < _Size)
> _Myvec[_Words - 1] &= (_Vbase)((1 << _Size) - 1);
> }
>
> void _Xlen() const
> { // report a length_error
> _THROW(length_error, "vector<bool> too long");
> }
>
> void _Xran() const
> { // throw an out_of_range error
> _THROW(out_of_range, "invalid vector<bool> subscript");
> }
>
> size_type _Mysize; // current length of sequence
> _Vbtype _Myvec; // base vector of words
> };
>
> typedef vector<bool, allocator<bool> > _Bvector;
>
> #if _HAS_TRADITIONAL_STL
> typedef _Bvector bit_vector;
> #define __vector__ vector
> #endif /* _HAS_TRADITIONAL_STL */
>
> _STD_END
>
> #ifdef _MSC_VER
> #pragma warning(default: 4244)
> #pragma warning(pop)
> #pragma pack(pop)
> #endif /* _MSC_VER */
>
> #endif /* RC_INVOKED */
> #endif /* _VECTOR_ */
>
> /*
> * This file is derived from software bearing the following
> * restrictions:
> *
> * Copyright (c) 1994
> * Hewlett-Packard Company
> *
> * Permission to use, copy, modify, distribute and sell this
> * software and its documentation for any purpose is hereby
> * granted without fee, provided that the above copyright notice
> * appear in all copies and that both that copyright notice and
> * this permission notice appear in supporting documentation.
> * Hewlett-Packard Company makes no representations about the
> * suitability of this software for any purpose. It is provided
> * "as is" without express or implied warranty.
> */
>
> /*
> * Copyright (c) 1992-2008 by P.J. Plauger. ALL RIGHTS RESERVED.
> * Consult your license regarding permissions and restrictions.
> V5.05:0009 */
>
>
---