1		// vector standard header
2		#pragma once
3		#ifndef _VECTOR_
4		#define _VECTOR_
5		#ifndef RC_INVOKED
6		#include <memory>
7		#include <stdexcept>
8
9		#ifdef _MSC_VER
10		#pragma pack(push,_CRT_PACKING)
11		#pragma warning(push,3)
12		#pragma warning(disable: 4244)
13		#endif  /* _MSC_VER */
14
15		_STD_BEGIN
16		template<class _Ty,
17		class _Ax = allocator<_Ty> >
18		class vector;
19
20		// TEMPLATE CLASS _Vector_const_iterator
21		template<class _Ty,
22		class _Alloc>
23		class _Vector_const_iterator
24		: public _Ranit<_Ty, typename _Alloc::difference_type,
25		typename _Alloc::const_pointer, typename _Alloc::const_reference>
26		{    // iterator for nonmutable vector
27		public:
28		typedef _Vector_const_iterator<_Ty, _Alloc> _Myt;
29		typedef vector<_Ty, _Alloc> _Myvec;
30		typedef typename _Alloc::pointer _Tptr;
31
32		typedef random_access_iterator_tag iterator_category;
33		typedef _Ty value_type;
34		typedef typename _Alloc::difference_type difference_type;
35		typedef typename _Alloc::const_pointer pointer;
36		typedef typename _Alloc::const_reference reference;
37
38		#if _SECURE_SCL
39		typedef _Range_checked_iterator_tag _Checked_iterator_category;
40		#endif
41
42		#if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING
43		typedef pointer _Checked_iterator_base_type;
44
45		_Checked_iterator_base_type _Checked_iterator_base() const
46		{
47		return _Myptr;
48		}
49
50		void _Checked_iterator_assign_from_base(_Checked_iterator_base_type _Base)
51		{
52		this->_Myptr = const_cast<_Tptr>(_Base);
53		}
54		#endif
55
56		// Setting _Inner_type implies that the internal structure of vector is
57		// an array of _Ty. This information is used in the copy and move algorithm.
58		// The helper function _Ptr_cat will return _Scalar_ptr_iterator_tag if you
59		// pass a vector iterator.
60		typedef _Tptr _Inner_type;
61
62		_Vector_const_iterator()
63		{    // construct with null pointer
64		_Myptr = 0;
65		}
66
67		#if _HAS_ITERATOR_DEBUGGING
68		_Vector_const_iterator(_Tptr _Ptr, const _Container_base *_Pvector)
69		{    // construct with pointer _Ptr
70		_SCL_SECURE_VALIDATE(_Pvector == NULL || (((_Myvec *)_Pvector)->_Myfirst <= _Ptr && _Ptr <= ((_Myvec *)_Pvector)->_Mylast));
71		this->_Adopt(_Pvector);
72		_Myptr = _Ptr;
73		}
74
75		#elif _SECURE_SCL
76		_Vector_const_iterator(_Tptr _Ptr, const _Container_base *_Pvector)
77		{    // construct with pointer _Ptr
78		_SCL_SECURE_VALIDATE(_Pvector != NULL && ((_Myvec *)_Pvector)->_Myfirst <= _Ptr && _Ptr <= ((_Myvec *)_Pvector)->_Mylast);
79		this->_Set_container(_Pvector);
80		_Myptr = _Ptr;
81		}
82
83		#else
84		explicit _Vector_const_iterator(_Tptr _Ptr)
85		{    // construct with pointer _Ptr
86		_Myptr = _Ptr;
87		}
88		#endif /* _HAS_ITERATOR_DEBUGGING */
89
90		reference operator*() const
91		{    // return designated object
92
93		#if _HAS_ITERATOR_DEBUGGING
94		if (this->_Mycont == 0
95		|| _Myptr < ((_Myvec *)this->_Mycont)->_Myfirst
96		|| ((_Myvec *)this->_Mycont)->_Mylast <= _Myptr)
97		{
98		_DEBUG_ERROR("vector iterator not dereferencable");
99		_SCL_SECURE_OUT_OF_RANGE;
100		}
101		#else
102		_SCL_SECURE_VALIDATE(this->_Has_container());
103		_SCL_SECURE_VALIDATE_RANGE(_Myptr < ((_Myvec *)(this->_Getmycont()))->_Mylast);
104		#endif /* _HAS_ITERATOR_DEBUGGING */
105
106		return (*_Myptr);
107		}
108
109		pointer operator->() const
110		{    // return pointer to class object
111		return (&**this);
112		}
113
114		_Myt& operator++()
115		{    // preincrement
116		_SCL_SECURE_VALIDATE(this->_Has_container());
117		_SCL_SECURE_VALIDATE_RANGE(_Myptr < ((_Myvec *)(this->_Getmycont()))->_Mylast);
118
119		#if _HAS_ITERATOR_DEBUGGING
120		if (this->_Mycont == 0
121		|| ((_Myvec *)this->_Mycont)->_Mylast <= _Myptr)
122		_DEBUG_ERROR("vector iterator not incrementable");
123		#endif /* _HAS_ITERATOR_DEBUGGING */
124
125		++_Myptr;
126		return (*this);
127		}
128
129		_Myt operator++(int)
130		{    // postincrement
131		_Myt _Tmp = *this;
132		++*this;
133		return (_Tmp);
134		}
135
136		_Myt& operator--()
137		{    // predecrement
138		_SCL_SECURE_VALIDATE(this->_Has_container());
139		_SCL_SECURE_VALIDATE_RANGE(_Myptr > ((_Myvec *)(this->_Getmycont()))->_Myfirst);
140
141		#if _HAS_ITERATOR_DEBUGGING
142		if (this->_Mycont == 0
143		|| _Myptr == ((_Myvec *)this->_Mycont)->_Myfirst)
144		_DEBUG_ERROR("vector iterator not decrementable");
145		#endif /* _HAS_ITERATOR_DEBUGGING */
146
147		--_Myptr;
148		return (*this);
149		}
150
151		_Myt operator--(int)
152		{    // postdecrement
153		_Myt _Tmp = *this;
154		--*this;
155		return (_Tmp);
156		}
157
158		_Myt& operator+=(difference_type _Off)
159		{    // increment by integer
160		_SCL_SECURE_VALIDATE(this->_Has_container());
161		_SCL_SECURE_VALIDATE_RANGE(
162		_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast &&
163		_Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst);
164		_Myptr += _Off;
165		return (*this);
166		}
167
168		_Myt operator+(difference_type _Off) const
169		{    // return this + integer
170		_Myt _Tmp = *this;
171		return (_Tmp += _Off);
172		}
173
174		_Myt& operator-=(difference_type _Off)
175		{    // decrement by integer
176		return (*this += -_Off);
177		}
178
179		_Myt operator-(difference_type _Off) const
180		{    // return this - integer
181		_Myt _Tmp = *this;
182		return (_Tmp -= _Off);
183		}
184
185		difference_type operator-(const _Myt& _Right) const
186		{    // return difference of iterators
187
188		#if _HAS_ITERATOR_DEBUGGING
189		_Compat(_Right);
190		#else
191		_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
192		#endif /* _HAS_ITERATOR_DEBUGGING */
193
194		return (_Myptr - _Right._Myptr);
195		}
196
197		reference operator[](difference_type _Off) const
198		{    // subscript
199		return (*(*this + _Off));
200		}
201
202		bool operator==(const _Myt& _Right) const
203		{    // test for iterator equality
204
205		#if _HAS_ITERATOR_DEBUGGING
206		_Compat(_Right);
207		#else
208		_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
209		#endif /* _HAS_ITERATOR_DEBUGGING */
210
211		return (_Myptr == _Right._Myptr);
212		}
213
214		bool operator!=(const _Myt& _Right) const
215		{    // test for iterator inequality
216		return (!(*this == _Right));
217		}
218
219		bool operator<(const _Myt& _Right) const
220		{    // test if this < _Right
221
222		#if _HAS_ITERATOR_DEBUGGING
223		_Compat(_Right);
224		#else
225		_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
226		#endif /* _HAS_ITERATOR_DEBUGGING */
227
228		return (_Myptr < _Right._Myptr);
229		}
230
231		bool operator>(const _Myt& _Right) const
232		{    // test if this > _Right
233		return (_Right < *this);
234		}
235
236		bool operator<=(const _Myt& _Right) const
237		{    // test if this <= _Right
238		return (!(_Right < *this));
239		}
240
241		bool operator>=(const _Myt& _Right) const
242		{    // test if this >= _Right
243		return (!(*this < _Right));
244		}
245
246		#if _HAS_ITERATOR_DEBUGGING
247		void _Compat(const _Myt& _Right) const
248		{    // test for compatible iterator pair
249		if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
250		{
251		_DEBUG_ERROR("vector iterators incompatible");
252		_SCL_SECURE_INVALID_ARGUMENT;
253		}
254		}
255		#endif /* _HAS_ITERATOR_DEBUGGING */
256
257		static void _Xlen()
258		{    // report a length_error
259		_THROW(length_error, "vector<T> too long");
260		}
261
262		static void _Xran()
263		{    // report an out_of_range error
264		_THROW(out_of_range, "invalid vector<T> subscript");
265		}
266
267		static void _Xinvarg()
268		{    // report an invalid_argument error
269		_THROW(invalid_argument, "invalid vector<T> argument");
270		}
271
272		_Tptr _Myptr;    // offset of element in vector
273		};
274
275		template<class _Ty,
276		class _Alloc> inline
277		_Vector_const_iterator<_Ty, _Alloc> operator+(
278		typename _Vector_const_iterator<_Ty, _Alloc>::difference_type _Off,
279		_Vector_const_iterator<_Ty, _Alloc> _Next)
280		{    // add offset to iterator
281		return (_Next += _Off);
282		}
283
284		// TEMPLATE CLASS _Vector_iterator
285		template<class _Ty,
286		class _Alloc>
287		class _Vector_iterator
288		: public _Vector_const_iterator<_Ty, _Alloc>
289		{    // iterator for mutable vector
290		public:
291		typedef _Vector_iterator<_Ty, _Alloc> _Myt;
292		typedef _Vector_const_iterator<_Ty, _Alloc> _Mybase;
293
294		typedef random_access_iterator_tag iterator_category;
295		typedef _Ty value_type;
296		typedef typename _Alloc::difference_type difference_type;
297		typedef typename _Alloc::pointer pointer;
298		typedef typename _Alloc::reference reference;
299
300		#if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING
301		typedef pointer _Checked_iterator_base_type;
302
303		_Checked_iterator_base_type _Checked_iterator_base() const
304		{
305		return (this->_Myptr);
306		}
307
308		void _Checked_iterator_assign_from_base(_Checked_iterator_base_type _Base)
309		{
310		this->_Myptr = _Base;
311		}
312		#endif
313
314		_Vector_iterator()
315		{    // construct with null vector pointer
316		}
317
318		#if _HAS_ITERATOR_DEBUGGING
319		_Vector_iterator(pointer _Ptr, const _Container_base *_Pvector)
320		: _Mybase(_Ptr, _Pvector)
321		{    // construct with pointer _Ptr
322		}
323
324		#elif _SECURE_SCL
325		_Vector_iterator(pointer _Ptr, const _Container_base *_Pvector)
326		: _Mybase(_Ptr, _Pvector)
327		{    // construct with pointer _Ptr
328		}
329
330		#else
331		explicit _Vector_iterator(pointer _Ptr)
332		: _Mybase(_Ptr)
333		{    // construct with pointer _Ptr
334		}
335		#endif /* _HAS_ITERATOR_DEBUGGING */
336
337		reference operator*() const
338		{    // return designated object
339		return ((reference)**(_Mybase *)this);
340		}
341
342		pointer operator->() const
343		{    // return pointer to class object
344		return (&**this);
345		}
346
347		_Myt& operator++()
348		{    // preincrement
349		++(*(_Mybase *)this);
350		return (*this);
351		}
352
353		_Myt operator++(int)
354		{    // postincrement
355		_Myt _Tmp = *this;
356		++*this;
357		return (_Tmp);
358		}
359
360		_Myt& operator--()
361		{    // predecrement
362		--(*(_Mybase *)this);
363		return (*this);
364		}
365
366		_Myt operator--(int)
367		{    // postdecrement
368		_Myt _Tmp = *this;
369		--*this;
370		return (_Tmp);
371		}
372
373		_Myt& operator+=(difference_type _Off)
374		{    // increment by integer
375		(*(_Mybase *)this) += _Off;
376		return (*this);
377		}
378
379		_Myt operator+(difference_type _Off) const
380		{    // return this + integer
381		_Myt _Tmp = *this;
382		return (_Tmp += _Off);
383		}
384
385		_Myt& operator-=(difference_type _Off)
386		{    // decrement by integer
387		return (*this += -_Off);
388		}
389
390		_Myt operator-(difference_type _Off) const
391		{    // return this - integer
392		_Myt _Tmp = *this;
393		return (_Tmp -= _Off);
394		}
395
396		difference_type operator-(const _Mybase& _Right) const
397		{    // return difference of iterators
398		return (*(_Mybase *)this - _Right);
399		}
400
401		reference operator[](difference_type _Off) const
402		{    // subscript
403		return (*(*this + _Off));
404		}
405		};
406
407		template<class _Ty,
408		class _Alloc> inline
409		_Vector_iterator<_Ty, _Alloc> operator+(
410		typename _Vector_iterator<_Ty, _Alloc>::difference_type _Off,
411		_Vector_iterator<_Ty, _Alloc> _Next)
412		{    // add offset to iterator
413		return (_Next += _Off);
414		}
415
416		// TEMPLATE CLASS _Vector_val
417		template<class _Ty,
418		class _Alloc>
419		class _Vector_val
420		: public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
421		{    // base class for vector to hold allocator _Alval
422		protected:
423		_Vector_val(_Alloc _Al = _Alloc())
424		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alval(_Al)
425		{    // construct allocator from _Al
426		}
427
428		typedef typename _Alloc::template
429		rebind<_Ty>::other _Alty;
430
431		_Alty _Alval;    // allocator object for values
432		};
433
434		// TEMPLATE CLASS vector
435		template<class _Ty,
436		class _Ax>
437		class vector
438		: public _Vector_val<_Ty, _Ax>
439		{    // varying size array of values
440		public:

Lines 441 ... 450 are skipped.

451		typedef _Ctptr const_pointer;
452		typedef typename _Alloc::reference _Reft;
453		typedef _Reft reference;
454		typedef typename _Alloc::const_reference const_reference;
455		typedef typename _Alloc::value_type value_type;
456
457		#define _VEC_ITER_BASE(it)    (it)._Myptr
458
459		typedef _Vector_iterator<_Ty, _Alloc> iterator;
460		typedef _Vector_const_iterator<_Ty, _Alloc> const_iterator;
461
462		//    friend class _Vector_iterator<_Ty, _Alloc>;
463		friend class _Vector_const_iterator<_Ty, _Alloc>;
464
465		typedef std::reverse_iterator<iterator> reverse_iterator;
466		typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
467
468		vector()
469		: _Mybase()
470		{    // construct empty vector
471		_Buy(0);
472		}
473
474		explicit vector(const _Alloc& _Al)
475		: _Mybase(_Al)
476		{    // construct empty vector with allocator
477		_Buy(0);
478		}
479
480		explicit vector(size_type _Count)
481		: _Mybase()
482		{    // construct from _Count * _Ty()
483		_Construct_n(_Count, _Ty());
484		}
485
486		vector(size_type _Count, const _Ty& _Val)
487		: _Mybase()
488		{    // construct from _Count * _Val
489		_Construct_n(_Count, _Val);
490		}
491
492		vector(size_type _Count, const _Ty& _Val, const _Alloc& _Al)
493		: _Mybase(_Al)
494		{    // construct from _Count * _Val, with allocator
495		_Construct_n(_Count, _Val);
496		}
497
498		vector(const _Myt& _Right)
499		: _Mybase(_Right._Alval)
500		{    // construct by copying _Right
501		if (_Buy(_Right.size()))
502		_TRY_BEGIN
503		_Mylast = _Ucopy(_Right.begin(), _Right.end(), _Myfirst);
504		_CATCH_ALL
505		_Tidy();
506		_RERAISE;
507		_CATCH_END
508		}
509
510		template<class _Iter>
511		vector(_Iter _First, _Iter _Last)
512		: _Mybase()
513		{    // construct from [_First, _Last)
514		_Construct(_First, _Last, _Iter_cat(_First));
515		}
516
517		template<class _Iter>
518		vector(_Iter _First, _Iter _Last, const _Alloc& _Al)
519		: _Mybase(_Al)
520		{    // construct from [_First, _Last), with allocator
521		_Construct(_First, _Last, _Iter_cat(_First));
522		}
523
524		template<class _Iter>
525		void _Construct(_Iter _Count, _Iter _Val, _Int_iterator_tag)
526		{    // initialize with _Count * _Val
527		size_type _Size = (size_type)_Count;
528		_Construct_n(_Size, (_Ty)_Val);
529		}
530
531		template<class _Iter>
532		void _Construct(_Iter _First,
533		_Iter _Last, input_iterator_tag)
534		{    // initialize with [_First, _Last), input iterators
535		_Buy(0);
536		_TRY_BEGIN
537		insert(begin(), _First, _Last);
538		_CATCH_ALL
539		_Tidy();
540		_RERAISE;
541		_CATCH_END
542		}
543
544		void _Construct_n(size_type _Count, const _Ty& _Val)
545		{    // construct from _Count * _Val
546		if (_Buy(_Count))
547		{    // nonzero, fill it
548		_TRY_BEGIN
549		_Mylast = _Ufill(_Myfirst, _Count, _Val);
550		_CATCH_ALL
551		_Tidy();
552		_RERAISE;
553		_CATCH_END
554		}
555		}
556
557		~vector()
558		{    // destroy the object
559		_Tidy();
560		}
561
562		_Myt& operator=(const _Myt& _Right)
563		{    // assign _Right
564		if (this != &_Right)
565		{    // worth doing
566
567		#if _HAS_ITERATOR_DEBUGGING
568		this->_Orphan_all();
569		#endif /* _HAS_ITERATOR_DEBUGGING */
570
571		if (_Right.size() == 0)
572		clear();    // new sequence empty, erase existing sequence
573		else if (_Right.size() <= size())
574		{    // enough elements, copy new and destroy old
575		pointer _Ptr = _STDEXT unchecked_copy(_Right._Myfirst, _Right._Mylast,
576		_Myfirst);    // copy new
577		_Destroy(_Ptr, _Mylast);    // destroy old
578		_Mylast = _Myfirst + _Right.size();
579		}
580		else if (_Right.size() <= capacity())
581		{    // enough room, copy and construct new
582		pointer _Ptr = _Right._Myfirst + size();
583		_STDEXT unchecked_copy(_Right._Myfirst, _Ptr, _Myfirst);
584		_Mylast = _Ucopy(_Ptr, _Right._Mylast, _Mylast);
585		}
586		else
587		{    // not enough room, allocate new array and construct new
588		if (_Myfirst != 0)
589		{    // discard old array
590		_Destroy(_Myfirst, _Mylast);
591		this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
592		}
593		if (_Buy(_Right.size()))
594		_Mylast = _Ucopy(_Right._Myfirst, _Right._Mylast,
595		_Myfirst);
596		}
597		}
598		return (*this);
599		}
600
601		void reserve(size_type _Count)
602		{    // determine new minimum length of allocated storage
603		if (max_size() < _Count)
604		_Xlen();    // result too long
605		else if (capacity() < _Count)
606		{    // not enough room, reallocate
607		pointer _Ptr = this->_Alval.allocate(_Count);
608
609		_TRY_BEGIN
610		_Umove(begin(), end(), _Ptr);
611		_CATCH_ALL
612		this->_Alval.deallocate(_Ptr, _Count);
613		_RERAISE;
614		_CATCH_END
615
616		size_type _Size = size();
617		if (_Myfirst != 0)
618		{    // destroy and deallocate old array
619		_Destroy(_Myfirst, _Mylast);
620		this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
621		}
622
623		#if _HAS_ITERATOR_DEBUGGING
624		this->_Orphan_all();
625		#endif /* _HAS_ITERATOR_DEBUGGING */
626
627		_Myend = _Ptr + _Count;
628		_Mylast = _Ptr + _Size;
629		_Myfirst = _Ptr;
630		}
631		}
632
633		size_type capacity() const
634		{    // return current length of allocated storage
635		return (_Myfirst == 0 ? 0 : _Myend - _Myfirst);
636		}
637
638		#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
639		iterator begin()
640		{    // return iterator for beginning of mutable sequence
641		return (iterator(_Myfirst, this));
642		}
643
644		const_iterator begin() const
645		{    // return iterator for beginning of nonmutable sequence
646		return (const_iterator(_Myfirst, this));
647		}
648
649		iterator end()
650		{    // return iterator for end of mutable sequence
651		return (iterator(_Mylast, this));
652		}
653
654		const_iterator end() const
655		{    // return iterator for end of nonmutable sequence
656		return (const_iterator(_Mylast, this));
657		}
658
659		iterator _Make_iter(const_iterator _Where) const
660		{    // make iterator from const_iterator
661		return (iterator(_Where._Myptr, this));
662		}
663
664		#else /* _HAS_ITERATOR_DEBUGGING */
665		iterator begin()
666		{    // return iterator for beginning of mutable sequence
667		return (iterator(_Myfirst));
668		}
669
670		const_iterator begin() const
671		{    // return iterator for beginning of nonmutable sequence
672		return (const_iterator(_Myfirst));
673		}
674
675		iterator end()
676		{    // return iterator for end of mutable sequence
677		return (iterator(_Mylast));
678		}
679
680		const_iterator end() const
681		{    // return iterator for end of nonmutable sequence
682		return (const_iterator(_Mylast));
683		}
684
685		iterator _Make_iter(const_iterator _Where) const
686		{    // make iterator from const_iterator
687		return (iterator(_Where._Myptr));
688		}
689		#endif /* _HAS_ITERATOR_DEBUGGING */
690
691		reverse_iterator rbegin()
692		{    // return iterator for beginning of reversed mutable sequence
693		return (reverse_iterator(end()));
694		}
695
696		const_reverse_iterator rbegin() const
697		{    // return iterator for beginning of reversed nonmutable sequence
698		return (const_reverse_iterator(end()));
699		}
700
701		reverse_iterator rend()
702		{    // return iterator for end of reversed mutable sequence
703		return (reverse_iterator(begin()));
704		}
705
706		const_reverse_iterator rend() const
707		{    // return iterator for end of reversed nonmutable sequence
708		return (const_reverse_iterator(begin()));
709		}
710
711		void resize(size_type _Newsize)
712		{    // determine new length, padding with _Ty() elements as needed
713		resize(_Newsize, _Ty());
714		}
715
716		void resize(size_type _Newsize, _Ty _Val)
717		{    // determine new length, padding with _Val elements as needed
718		if (size() < _Newsize)
719		_Insert_n(end(), _Newsize - size(), _Val);
720		else if (_Newsize < size())
721		erase(begin() + _Newsize, end());
722		}
723
724		size_type size() const
725		{    // return length of sequence
726		return (_Mylast - _Myfirst);
727		}
728
729		size_type max_size() const
730		{    // return maximum possible length of sequence
731		return (this->_Alval.max_size());
732		}
733
734		bool empty() const
735		{    // test if sequence is empty
736		return (size() == 0);
737		}
738
739		_Alloc get_allocator() const
740		{    // return allocator object for values
741		return (this->_Alval);
742		}
743
744		const_reference at(size_type _Pos) const
745		{    // subscript nonmutable sequence with checking
746		if (size() <= _Pos)
747		_Xran();
748		return (*(begin() + _Pos));
749		}
750
751		reference at(size_type _Pos)
752		{    // subscript mutable sequence with checking
753		if (size() <= _Pos)
754		_Xran();
755		return (*(begin() + _Pos));
756		}
757
758		const_reference operator[](size_type _Pos) const
759		{    // subscript nonmutable sequence
760
761		#if _HAS_ITERATOR_DEBUGGING
762		if (size() <= _Pos)
763		{
764		_DEBUG_ERROR("vector subscript out of range");
765		_SCL_SECURE_OUT_OF_RANGE;
766		}
767		#endif /* _HAS_ITERATOR_DEBUGGING */
768		_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
769
770		return (*(_Myfirst + _Pos));
771		}
772
773		reference operator[](size_type _Pos)
774		{    // subscript mutable sequence
775
776		#if _HAS_ITERATOR_DEBUGGING
777		if (size() <= _Pos)
778		{
779		_DEBUG_ERROR("vector subscript out of range");
780		_SCL_SECURE_OUT_OF_RANGE;
781		}
782		#endif /* _HAS_ITERATOR_DEBUGGING */
783		_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
784
785		return (*(_Myfirst + _Pos));
786		}
787
788		reference front()
789		{    // return first element of mutable sequence
790		return (*begin());
791		}
792
793		const_reference front() const
794		{    // return first element of nonmutable sequence
795		return (*begin());
796		}
797
798		reference back()
799		{    // return last element of mutable sequence
800		return (*(end() - 1));
801		}
802
803		const_reference back() const
804		{    // return last element of nonmutable sequence
805		return (*(end() - 1));
806		}
807
808		void push_back(const _Ty& _Val)
809		{    // insert element at end
810		if (size() < capacity())
811
812		#if _HAS_ITERATOR_DEBUGGING
813		{ // room at end, construct it there
814		_Orphan_range(_Mylast, _Mylast);
815		_Mylast = _Ufill(_Mylast, 1, _Val);
816		}
817
818		#else /* _HAS_ITERATOR_DEBUGGING */
819		_Mylast = _Ufill(_Mylast, 1, _Val);
820		#endif /* _HAS_ITERATOR_DEBUGGING */
821
822		else
823		insert(end(), _Val);
824		}
825
826		#if _HAS_ITERATOR_DEBUGGING
827		void pop_back()
828		{    // erase element at end
829		if (empty())
830		_DEBUG_ERROR("vector empty before pop");
831		else
832		{    // erase last element
833		_Orphan_range(_Mylast - 1, _Mylast);
834		_Destroy(_Mylast - 1, _Mylast);
835		--_Mylast;
836		}
837		}
838
839		#else /* _HAS_ITERATOR_DEBUGGING */
840		void pop_back()
841		{    // erase element at end
842		if (!empty())
843		{    // erase last element
844		_Destroy(_Mylast - 1, _Mylast);
845		--_Mylast;
846		}
847		}
848		#endif /* _HAS_ITERATOR_DEBUGGING */
849
850		template<class _Iter>
851		void assign(_Iter _First, _Iter _Last)
852		{    // assign [_First, _Last)
853		_Assign(_First, _Last, _Iter_cat(_First));
854		}
855
856		template<class _Iter>
857		void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag)
858		{    // assign _Count * _Val
859		_Assign_n((size_type)_Count, (_Ty)_Val);
860		}
861
862		template<class _Iter>
863		void _Assign(_Iter _First, _Iter _Last, input_iterator_tag)
864		{    // assign [_First, _Last), input iterators
865		erase(begin(), end());
866		insert(begin(), _First, _Last);
867		}
868
869		void assign(size_type _Count, const _Ty& _Val)
870		{    // assign _Count * _Val
871		_Assign_n(_Count, _Val);
872		}
873
874		iterator insert(const_iterator _Where, const _Ty& _Val)
875		{    // insert _Val at _Where
876		size_type _Off = size() == 0 ? 0 : _Where - begin();
877		_Insert_n(_Where, (size_type)1, _Val);
878		return (begin() + _Off);
879		}
880
881		void insert(const_iterator _Where, size_type _Count, const _Ty& _Val)
882		{    // insert _Count * _Val at _Where
883		_Insert_n(_Where, _Count, _Val);
884		}
885
886		template<class _Iter>
887		void insert(const_iterator _Where, _Iter _First, _Iter _Last)
888		{    // insert [_First, _Last) at _Where
889		_Insert(_Where, _First, _Last, _Iter_cat(_First));
890		}
891
892		template<class _Iter>
893		void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
894		_Int_iterator_tag)
895		{    // insert _Count * _Val at _Where
896		_Insert_n(_Where, (size_type)_First, (_Ty)_Last);
897		}
898
899		template<class _Iter>
900		void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
901		input_iterator_tag)
902		{    // insert [_First, _Last) at _Where, input iterators
903
904		#if _HAS_ITERATOR_DEBUGGING
905		if (_Where._Mycont != this
906		|| _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr)
907		_DEBUG_ERROR("vector insert iterator outside range");
908		#endif /* _HAS_ITERATOR_DEBUGGING */
909
910		if (_First != _Last)
911		{    // worth doing, gather at end and rotate into place
912		size_type _Oldsize = size();
913		size_type _Whereoff = _Where._Myptr - _Myfirst;
914
915		for (; _First != _Last; ++_First)
916		_Insert_n(end(), (size_type)1, (value_type)*_First);
917
918		_Reverse(_Myfirst + _Whereoff, _Myfirst + _Oldsize);
919		_Reverse(_Myfirst + _Oldsize, _Mylast);
920		_Reverse(_Myfirst + _Whereoff, _Mylast);
921		}
922		}
923
924		template<class _Iter>
925		void _Insert(const_iterator _Where,
926		_Iter _First, _Iter _Last, forward_iterator_tag)
927		{    // insert [_First, _Last) at _Where, forward iterators
928
929		#if _HAS_ITERATOR_DEBUGGING
930		if (_Where._Mycont != this
931		|| _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr)
932		_DEBUG_ERROR("vector insert iterator outside range");
933		_DEBUG_RANGE(_First, _Last);
934		#endif /* _HAS_ITERATOR_DEBUGGING */
935
936		size_type _Count = 0;
937		_Distance(_First, _Last, _Count);
938		size_type _Capacity = capacity();
939
940		if (_Count == 0)
941		;
942		else if (max_size() - size() < _Count)
943		_Xlen();    // result too long
944		else if (_Capacity < size() + _Count)
945		{    // not enough room, reallocate
946		_Capacity = max_size() - _Capacity / 2 < _Capacity
947		? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%
948		if (_Capacity < size() + _Count)
949		_Capacity = size() + _Count;
950		pointer _Newvec = this->_Alval.allocate(_Capacity);
951		pointer _Ptr = _Newvec;
952
953		_TRY_BEGIN
954		_Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),
955		_Newvec);    // copy prefix
956		_Ptr = _Ucopy(_First, _Last, _Ptr);    // add new stuff
957		_Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr);    // copy suffix
958		_CATCH_ALL
959		_Destroy(_Newvec, _Ptr);
960		this->_Alval.deallocate(_Newvec, _Capacity);
961		_RERAISE;
962		_CATCH_END
963
964		_Count += size();
965		if (_Myfirst != 0)
966		{    // destroy and deallocate old array
967		_Destroy(_Myfirst, _Mylast);
968		this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
969		}
970
971		#if _HAS_ITERATOR_DEBUGGING
972		this->_Orphan_all();
973		#endif /* _HAS_ITERATOR_DEBUGGING */
974
975		_Myend = _Newvec + _Capacity;
976		_Mylast = _Newvec + _Count;
977		_Myfirst = _Newvec;
978		}
979		else
980		{    // new stuff fits, append and rotate into place
981		_Ucopy(_First, _Last, _Mylast);
982
983		_Reverse(_Where._Myptr, _Mylast);
984		_Reverse(_Mylast, _Mylast + _Count);
985		_Reverse(_Where._Myptr, _Mylast + _Count);
986
987		_Mylast += _Count;
988
989		#if _HAS_ITERATOR_DEBUGGING
990		_Orphan_range(_Where._Myptr, _Mylast);
991		#endif /* _HAS_ITERATOR_DEBUGGING */
992
993		}
994		}
995
996		void _Reverse(pointer _First, pointer _Last)
997		{    // reverse a subrange
998		for (; _First != _Last && _First != --_Last; ++_First)
999		_STD _Swap_adl(*_First, *_Last);
1000		}
1001
1002		#if _HAS_ITERATOR_DEBUGGING
1003		iterator erase(const_iterator _Where)
1004		{    // erase element at where
1005		if (_Where._Mycont != this
1006		|| _Where._Myptr < _Myfirst || _Mylast <= _Where._Myptr)
1007		_DEBUG_ERROR("vector erase iterator outside range");
1008		_STDEXT unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);
1009		_Destroy(_Mylast - 1, _Mylast);
1010		_Orphan_range(_Where._Myptr, _Mylast);
1011		--_Mylast;
1012		return (iterator(_Where._Myptr, this));
1013		}
1014
1015		#else /* _HAS_ITERATOR_DEBUGGING */
1016		iterator erase(const_iterator _Where)
1017		{    // erase element at where
1018		_STDEXT unchecked_copy(_VEC_ITER_BASE(_Where) + 1, _Mylast,
1019		_VEC_ITER_BASE(_Where));
1020		_Destroy(_Mylast - 1, _Mylast);
1021		--_Mylast;
1022		return (_Make_iter(_Where));
1023		}
1024		#endif /* _HAS_ITERATOR_DEBUGGING */
1025
1026		iterator erase(const_iterator _First_arg,
1027		const_iterator _Last_arg)
1028		{    // erase [_First, _Last)
1029		iterator _First = _Make_iter(_First_arg);
1030		iterator _Last = _Make_iter(_Last_arg);
1031
1032		if (_First != _Last)
1033		{    // worth doing, copy down over hole
1034
1035		#if _HAS_ITERATOR_DEBUGGING
1036		if (_Last < _First || _First._Mycont != this
1037		|| _First._Myptr < _Myfirst || _Mylast < _Last._Myptr)
1038		_DEBUG_ERROR("vector erase iterator outside range");
1039		pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
1040		_VEC_ITER_BASE(_First));
1041		_Orphan_range(_First._Myptr, _Mylast);
1042
1043		#else /* _HAS_ITERATOR_DEBUGGING */
1044		pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
1045		_VEC_ITER_BASE(_First));
1046		#endif /* _HAS_ITERATOR_DEBUGGING */
1047
1048		_Destroy(_Ptr, _Mylast);
1049		_Mylast = _Ptr;
1050		}
1051		#if _HAS_ITERATOR_DEBUGGING
1052		return (iterator(_First._Myptr, this));
1053		#else
1054		return (_First);
1055		#endif
1056		}
1057
1058		void clear()
1059		{    // erase all
1060		erase(begin(), end());
1061		}
1062
1063		void swap(_Myt& _Right)
1064		{    // exchange contents with _Right
1065		if (this == &_Right)
1066		;    // same object, do nothing
1067		else if (this->_Alval == _Right._Alval)
1068		{    // same allocator, swap control information
1069
1070		#if _HAS_ITERATOR_DEBUGGING
1071		this->_Swap_all(_Right);
1072		#endif /* _HAS_ITERATOR_DEBUGGING */
1073
1074		this->_Swap_aux(_Right);
1075
1076		_STD swap(_Myfirst, _Right._Myfirst);
1077		_STD swap(_Mylast, _Right._Mylast);
1078		_STD swap(_Myend, _Right._Myend);
1079		}
1080		else
1081		{    // different allocator, do multiple assigns
1082		this->_Swap_aux(_Right);
1083
1084		_Myt _Ts = *this;
1085
1086		*this = _Right;
1087		_Right = _Ts;
1088		}
1089		}
1090
1091
1092
1093		protected:
1094		void _Assign_n(size_type _Count, const _Ty& _Val)
1095		{    // assign _Count * _Val
1096		_Ty _Tmp = _Val;    // in case _Val is in sequence
1097		erase(begin(), end());
1098		insert(begin(), _Count, _Tmp);
1099		}
1100
1101		bool _Buy(size_type _Capacity)
1102		{    // allocate array with _Capacity elements
1103		_Myfirst = 0, _Mylast = 0, _Myend = 0;
1104		if (_Capacity == 0)
1105		return (false);
1106		else if (max_size() < _Capacity)
1107		_Xlen();    // result too long
1108		else
1109		{    // nonempty array, allocate storage
1110		_Myfirst = this->_Alval.allocate(_Capacity);
1111		_Mylast = _Myfirst;
1112		_Myend = _Myfirst + _Capacity;
1113		}
1114		return (true);
1115		}
1116
1117		void _Destroy(pointer _First, pointer _Last)
1118		{    // destroy [_First, _Last) using allocator
1119		_Destroy_range(_First, _Last, this->_Alval);
1120		}
1121
1122		void _Tidy()
1123		{    // free all storage
1124		if (_Myfirst != 0)
1125		{    // something to free, destroy and deallocate it
1126
1127		#if _HAS_ITERATOR_DEBUGGING
1128		this->_Orphan_all();
1129		#endif /* _HAS_ITERATOR_DEBUGGING */
1130
1131		_Destroy(_Myfirst, _Mylast);
1132		this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
1133		}
1134		_Myfirst = 0, _Mylast = 0, _Myend = 0;
1135		}
1136
1137		template<class _Iter>
1138		pointer _Ucopy(_Iter _First, _Iter _Last, pointer _Ptr)
1139		{    // copy initializing [_First, _Last), using allocator
1140		return (_STDEXT unchecked_uninitialized_copy(_First, _Last,
1141		_Ptr, this->_Alval));
1142		}
1143
1144		template<class _Iter>
1145		pointer _Umove(_Iter _First, _Iter _Last, pointer _Ptr)
1146		{    // move initializing [_First, _Last), using allocator
1147		return (_STDEXT _Unchecked_uninitialized_move(_First, _Last,
1148		_Ptr, this->_Alval));
1149		}
1150
1151		void _Insert_n(const_iterator _Where,
1152		size_type _Count, const _Ty& _Val)
1153		{    // insert _Count * _Val at _Where
1154
1155		#if _HAS_ITERATOR_DEBUGGING
1156		if (_Where._Mycont != this
1157		|| _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr)
1158		_DEBUG_ERROR("vector insert iterator outside range");
1159		#endif /* _HAS_ITERATOR_DEBUGGING */
1160
1161		size_type _Capacity = capacity();
1162
1163		if (_Count == 0)
1164		;
1165		else if (max_size() - size() < _Count)
1166		_Xlen();    // result too long
1167		else if (_Capacity < size() + _Count)
1168		{    // not enough room, reallocate
1169		_Capacity = max_size() - _Capacity / 2 < _Capacity
1170		? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%
1171		if (_Capacity < size() + _Count)
1172		_Capacity = size() + _Count;
1173		pointer _Newvec = this->_Alval.allocate(_Capacity);
1174		size_type _Whereoff = _VEC_ITER_BASE(_Where) - _Myfirst;
1175		int _Ncopied = 0;
1176
1177		_TRY_BEGIN
1178		_Ufill(_Newvec + _Whereoff, _Count, _Val);    // add new stuff
1179		++_Ncopied;
1180		_Umove(this->_Myfirst, _VEC_ITER_BASE(_Where),
1181		_Newvec);    // move prefix
1182		++_Ncopied;
1183		_Umove(_VEC_ITER_BASE(_Where), this->_Mylast,
1184		_Newvec + (_Whereoff + _Count));    // move suffix
1185		_CATCH_ALL
1186		if (1 < _Ncopied)
1187		_Destroy(_Newvec, _Newvec + _Whereoff);
1188		if (0 < _Ncopied)
1189		_Destroy(_Newvec + _Whereoff, _Newvec + _Whereoff + _Count);
1190		this->_Alval.deallocate(_Newvec, _Capacity);
1191		_RERAISE;
1192		_CATCH_END
1193
1194		_Count += size();
1195		if (_Myfirst != 0)
1196		{    // destroy and deallocate old array
1197		_Destroy(_Myfirst, _Mylast);
1198		this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
1199		}
1200
1201		#if _HAS_ITERATOR_DEBUGGING
1202		this->_Orphan_all();
1203		#endif /* _HAS_ITERATOR_DEBUGGING */
1204
1205		_Myend = _Newvec + _Capacity;
1206		_Mylast = _Newvec + _Count;
1207		_Myfirst = _Newvec;
1208		}
1209		else if ((size_type)(_Mylast - _VEC_ITER_BASE(_Where)) < _Count)
1210		{    // new stuff spills off end
1211		_Ty _Tmp = _Val;    // in case _Val is in sequence
1212
1213		_Umove(_VEC_ITER_BASE(_Where), _Mylast,
1214		_VEC_ITER_BASE(_Where) + _Count);    // copy suffix
1215
1216		_TRY_BEGIN
1217		_Ufill(_Mylast, _Count - (_Mylast - _VEC_ITER_BASE(_Where)),
1218		_Tmp);    // insert new stuff off end
1219		_CATCH_ALL
1220		_Destroy(_VEC_ITER_BASE(_Where) + _Count, _Mylast + _Count);
1221		_RERAISE;
1222		_CATCH_END
1223
1224		_Mylast += _Count;
1225
1226		#if _HAS_ITERATOR_DEBUGGING
1227		_Orphan_range(_Where._Myptr, _Mylast);
1228		#endif /* _HAS_ITERATOR_DEBUGGING */
1229
1230		std::fill(_VEC_ITER_BASE(_Where), _Mylast - _Count,
1231		_Tmp);    // insert up to old end
1232		}
1233		else
1234		{    // new stuff can all be assigned
1235		_Ty _Tmp = _Val;    // in case _Val is in sequence
1236
1237		pointer _Oldend = _Mylast;
1238		_Mylast = _Umove(_Oldend - _Count, _Oldend,
1239		_Mylast);    // copy suffix
1240
1241		#if _HAS_ITERATOR_DEBUGGING
1242		_Orphan_range(_Where._Myptr, _Mylast);
1243		#endif /* _HAS_ITERATOR_DEBUGGING */
1244
1245		_STDEXT _Unchecked_move_backward(_VEC_ITER_BASE(_Where), _Oldend - _Count,
1246		_Oldend);    // copy hole
1247		std::fill(_VEC_ITER_BASE(_Where), _VEC_ITER_BASE(_Where) + _Count,
1248		_Tmp);    // insert into hole
1249		}
1250		}
1251
1252		pointer _Ufill(pointer _Ptr, size_type _Count, const _Ty &_Val)
1253		{    // copy initializing _Count * _Val, using allocator
1254		_STDEXT unchecked_uninitialized_fill_n(_Ptr, _Count, _Val, this->_Alval);
1255		return (_Ptr + _Count);
1256		}
1257
1258		static void _Xlen()
1259		{    // report a length_error
1260		_THROW(length_error, "vector<T> too long");
1261		}
1262
1263		static void _Xran()
1264		{    // report an out_of_range error
1265		_THROW(out_of_range, "invalid vector<T> subscript");
1266		}
1267
1268		static void _Xinvarg()
1269		{    // report an invalid_argument error
1270		_THROW(invalid_argument, "invalid vector<T> argument");
1271		}
1272
1273		#if _HAS_ITERATOR_DEBUGGING
1274		void _Orphan_range(pointer _First, pointer _Last) const
1275		{    // orphan iterators within specified (inclusive) range
1276		_Lockit _Lock(_LOCK_DEBUG);
1277		const_iterator **_Pnext = (const_iterator **)&this->_Myfirstiter;
1278		while (*_Pnext != 0)
1279		if ((*_Pnext)->_Myptr < _First || _Last < (*_Pnext)->_Myptr)
1280		_Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter;
1281		else
1282		{    // orphan the iterator
1283		(*_Pnext)->_Mycont = 0;
1284		*_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter;
1285		}
1286		}
1287		#endif /* _HAS_ITERATOR_DEBUGGING */
1288
1289		pointer _Myfirst;    // pointer to beginning of array
1290		pointer _Mylast;    // pointer to current end of sequence
1291		pointer _Myend;    // pointer to end of array
1292		};
1293
1294		// vector implements a performant swap
1295		template <class _Ty, class _Ax>
1296		class _Move_operation_category<vector<_Ty, _Ax> >
1297		{
1298		public:
1299		typedef _Swap_move_tag _Move_cat;
1300		};
1301
1302		// vector TEMPLATE FUNCTIONS
1303		template<class _Ty,
1304		class _Alloc> inline
1305		bool operator==(const vector<_Ty, _Alloc>& _Left,
1306		const vector<_Ty, _Alloc>& _Right)
1307		{    // test for vector equality
1308		return (_Left.size() == _Right.size()
1309		&& equal(_Left.begin(), _Left.end(), _Right.begin()));
1310		}
1311
1312		template<class _Ty,
1313		class _Alloc> inline
1314		bool operator!=(const vector<_Ty, _Alloc>& _Left,
1315		const vector<_Ty, _Alloc>& _Right)
1316		{    // test for vector inequality
1317		return (!(_Left == _Right));
1318		}
1319
1320		template<class _Ty,
1321		class _Alloc> inline
1322		bool operator<(const vector<_Ty, _Alloc>& _Left,
1323		const vector<_Ty, _Alloc>& _Right)
1324		{    // test if _Left < _Right for vectors
1325		return (lexicographical_compare(_Left.begin(), _Left.end(),
1326		_Right.begin(), _Right.end()));
1327		}
1328
1329		template<class _Ty,
1330		class _Alloc> inline
1331		bool operator>(const vector<_Ty, _Alloc>& _Left,
1332		const vector<_Ty, _Alloc>& _Right)
1333		{    // test if _Left > _Right for vectors
1334		return (_Right < _Left);
1335		}
1336
1337		template<class _Ty,
1338		class _Alloc> inline
1339		bool operator<=(const vector<_Ty, _Alloc>& _Left,
1340		const vector<_Ty, _Alloc>& _Right)
1341		{    // test if _Left <= _Right for vectors
1342		return (!(_Right < _Left));
1343		}
1344
1345		template<class _Ty,
1346		class _Alloc> inline
1347		bool operator>=(const vector<_Ty, _Alloc>& _Left,
1348		const vector<_Ty, _Alloc>& _Right)
1349		{    // test if _Left >= _Right for vectors
1350		return (!(_Left < _Right));
1351		}
1352
1353		template<class _Ty,
1354		class _Alloc> inline
1355		void swap(vector<_Ty, _Alloc>& _Left, vector<_Ty, _Alloc>& _Right)
1356		{    // swap _Left and _Right vectors
1357		_Left.swap(_Right);
1358		}
1359
1360		//
1361		// TEMPLATE CLASS vector<bool, Alloc> AND FRIENDS
1362		//
1363		typedef unsigned _Vbase;    // word type for vector<bool> representation
1364		const int _VBITS = 8 * sizeof (_Vbase);    // at least CHAR_BITS bits per word
1365
1366		// CLASS _Vb_iter_base
1367		template<class _Sizet,
1368		class _Difft,
1369		class _MycontTy>
1370		class _Vb_iter_base
1371		: public _Ranit<_Bool, _Difft, bool *, bool>
1372		{    // store information common to reference and iterators
1373		public:
1374		#if _SECURE_SCL
1375		typedef _Range_checked_iterator_tag _Checked_iterator_category;
1376		#endif
1377
1378		_Vb_iter_base()
1379		: _Myptr(0), _Myoff(0)
1380		{    // construct with null pointer
1381		}
1382
1383		#if _HAS_ITERATOR_DEBUGGING
1384		_Vb_iter_base(_Vbase *_Ptr, _Sizet _Off,
1385		const _Container_base *_Mypvbool)
1386		: _Myptr(_Ptr), _Myoff(_Off)
1387		{    // construct with offset and pointer
1388		_SCL_SECURE_VALIDATE(_Mypvbool != NULL);
1389		this->_Adopt(_Mypvbool);
1390		}
1391
1392		#elif _SECURE_SCL
1393		_Vb_iter_base(_Vbase *_Ptr, _Sizet _Off,
1394		const _Container_base *_Mypvbool)
1395		: _Myptr(_Ptr), _Myoff(_Off)
1396		{    // construct with offset and pointer
1397		_SCL_SECURE_VALIDATE(_Mypvbool != NULL);
1398		this->_Set_container(_Mypvbool);
1399		}
1400		#else
1401		_Vb_iter_base(_Vbase *_Ptr, _Sizet _Off)
1402		: _Myptr(_Ptr), _Myoff(_Off)
1403		{    // construct with offset and pointer
1404		}
1405		#endif
1406
1407		_Vbase *_Myptr;
1408		_Sizet _Myoff;
1409
1410		static void _Xlen()
1411		{    // report a length_error
1412		_THROW(length_error, "vector<bool> too long");
1413		}
1414
1415		static void _Xran()
1416		{    // report an out_of_range error
1417		_THROW(out_of_range, "invalid vector<bool> subscript");
1418		}
1419
1420		static void _Xinvarg()
1421		{    // report an invalid_argument error
1422		_THROW(invalid_argument, "invalid vector<bool> argument");
1423		}
1424
1425		#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
1426		_Vbase * _My_cont_begin() const
1427		{
1428		return (_VEC_ITER_BASE(((_MycontTy *)this->
1429		_Getmycont())->_Myvec.begin()));
1430		}
1431
1432		_Sizet _My_actual_offset() const
1433		{
1434		_Sizet _Off = this->_Myoff;
1435		_Off += _VBITS * (this->_Myptr - _My_cont_begin());
1436		return (_Off);
1437		}
1438		#endif
1439		};
1440
1441		// CLASS _Vb_reference
1442		template<class _Sizet,
1443		class _Difft,
1444		class _MycontTy>
1445		class _Vb_reference
1446		: public _Vb_iter_base<_Sizet, _Difft, _MycontTy>
1447		{    // reference to a bit within a base word
1448		public:
1449		typedef _Vb_iter_base<_Sizet, _Difft, _MycontTy> _Mybase;
1450		typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Mytype;
1451
1452		_Vb_reference()
1453		{    // construct with null pointer
1454		}
1455
1456		#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
1457		_Vb_reference(const _Mybase& _Right)
1458		: _Mybase(_Right._Myptr, _Right._Myoff, _Right._Getmycont())
1459		{    // construct with base
1460		}
1461
1462		#else /* _HAS_ITERATOR_DEBUGGING */
1463		_Vb_reference(const _Mybase& _Right)
1464		: _Mybase(_Right._Myptr, _Right._Myoff)
1465		{    // construct with base
1466		}
1467		#endif /* _HAS_ITERATOR_DEBUGGING */
1468
1469		_Mytype& operator=(const _Mytype& _Right)
1470		{    // assign _Vb_reference _Right to bit
1471		return (*this = bool(_Right));
1472		}
1473
1474		_Mytype& operator=(bool _Val)
1475		{    // assign _Val to bit
1476		if (_Val)
1477		*_Getptr() |= _Mask();
1478		else
1479		*_Getptr() &= ~_Mask();
1480		return (*this);
1481		}
1482
1483		void flip()
1484		{    // toggle the bit
1485		*_Getptr() ^= _Mask();
1486		}
1487
1488		bool operator~() const
1489		{    // test if bit is reset
1490		return (!bool(*this));
1491		}
1492
1493		operator bool() const
1494		{    // test if bit is set
1495		return ((*_Getptr() & _Mask()) != 0);
1496		}
1497
1498		_Vbase *_Getptr() const
1499		{    // get pointer to base word
1500
1501		#if _HAS_ITERATOR_DEBUGGING
1502		if (this->_Mycont == 0 || this->_Myptr == 0)
1503		{
1504		_DEBUG_ERROR("vector<bool> iterator not dereferencable");
1505		_SCL_SECURE_OUT_OF_RANGE;
1506		}
1507		#else /* _HAS_ITERATOR_DEBUGGING */
1508		_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL);
1509		_SCL_SECURE_VALIDATE_RANGE(this->_My_actual_offset() < ((_MycontTy *)this->_Getmycont())->_Mysize);
1510		#endif /* _HAS_ITERATOR_DEBUGGING */
1511
1512		return (this->_Myptr);
1513		}
1514
1515		protected:
1516		_Vbase _Mask() const
1517		{    // convert offset to mask
1518		return ((_Vbase)(1 << this->_Myoff));
1519		}
1520		};
1521
1522		template<class _Sizet,
1523		class _Difft,
1524		class _MycontTy>
1525		void swap(_Vb_reference<_Sizet, _Difft, _MycontTy> _Left,
1526		_Vb_reference<_Sizet, _Difft, _MycontTy> _Right)
1527		{    // swap _Left and _Right vector<bool> elements
1528		bool _Val = _Left;
1529		_Left = _Right;
1530		_Right = _Val;
1531		}
1532
1533		// CLASS _Vb_const_iterator
1534		template<class _Sizet,
1535		class _Difft,
1536		class _MycontTy>
1537		class _Vb_const_iterator
1538		: public _Vb_iter_base<_Sizet, _Difft, _MycontTy>
1539		{    // iterator for nonmutable vector<bool>
1540		public:
1541		typedef _Vb_iter_base<_Sizet, _Difft, _MycontTy> _Mybase;
1542		typedef _Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Mytype;
1543
1544		typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Reft;
1545		typedef bool const_reference;
1546
1547		typedef random_access_iterator_tag iterator_category;
1548		typedef _Bool value_type;
1549		typedef _Sizet size_type;
1550		typedef _Difft difference_type;
1551		typedef const_reference *pointer;
1552		typedef const_reference reference;
1553
1554		_Vb_const_iterator()
1555		{    // construct with null reference
1556		}
1557
1558		#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
1559		_Vb_const_iterator(const _Vbase *_Ptr, const _Container_base *_Mypvbool)
1560		: _Mybase((_Vbase *)_Ptr, 0, (_Container_base *)_Mypvbool)
1561
1562		#else
1563		_Vb_const_iterator(const _Vbase *_Ptr)
1564		: _Mybase((_Vbase *)_Ptr, 0)
1565
1566		#endif
1567		{    // construct with offset and pointer
1568		}
1569
1570		const_reference operator*() const
1571		{    // return (reference to) designated object
1572		return (_Reft(*this));
1573		}
1574
1575		_Mytype& operator++()
1576		{    // preincrement
1577		_Inc();
1578		return (*this);
1579		}
1580
1581		_Mytype operator++(int)
1582		{    // postincrement
1583		_Mytype _Tmp = *this;
1584		++*this;
1585		return (_Tmp);
1586		}
1587
1588		_Mytype& operator--()
1589		{    // predecrement
1590		_Dec();
1591		return (*this);
1592		}
1593
1594		_Mytype operator--(int)
1595		{    // postdecrement
1596		_Mytype _Tmp = *this;
1597		--*this;
1598		return (_Tmp);
1599		}
1600
1601		_Mytype& operator+=(difference_type _Off)
1602		{    // increment by integer
1603		if (_Off == 0)
1604		return (*this); // early out
1605		_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL);
1606		if (_Off < 0)
1607		{
1608		_SCL_SECURE_VALIDATE_RANGE(this->_My_actual_offset() >= ((size_type)-_Off));
1609		}
1610		else
1611		{
1612		_SCL_SECURE_VALIDATE_RANGE((this->_My_actual_offset() + _Off) <= ((_MycontTy *)this->_Getmycont())->_Mysize);
1613		}
1614		if (_Off < 0 && this->_Myoff < 0 - (size_type)_Off)
1615		{    /* add negative increment */
1616		this->_Myoff += _Off;
1617		this->_Myptr -= 1 + ((size_type)(-1) - this->_Myoff) / _VBITS;
1618		this->_Myoff %= _VBITS;
1619		}
1620		else
1621		{    /* add non-negative increment */
1622		this->_Myoff += _Off;
1623		this->_Myptr += this->_Myoff / _VBITS;
1624		this->_Myoff %= _VBITS;
1625		}
1626		return (*this);
1627		}
1628
1629		_Mytype operator+(difference_type _Off) const
1630		{    // return this + integer
1631		_Mytype _Tmp = *this;
1632		return (_Tmp += _Off);
1633		}
1634
1635		_Mytype& operator-=(difference_type _Off)
1636		{    // decrement by integer
1637		return (*this += -_Off);
1638		}
1639
1640		_Mytype operator-(difference_type _Off) const
1641		{    // return this - integer
1642		_Mytype _Tmp = *this;
1643		return (_Tmp -= _Off);
1644		}
1645
1646		difference_type operator-(
1647		const _Mytype& _Right) const
1648		{    // return difference of iterators
1649
1650		#if _HAS_ITERATOR_DEBUGGING
1651		_Compat(_Right);
1652		#endif /* _HAS_ITERATOR_DEBUGGING */
1653
1654		return (_VBITS * (this->_Myptr - _Right._Myptr)
1655		+ (difference_type)this->_Myoff
1656		- (difference_type)_Right._Myoff);
1657		}
1658
1659		const_reference operator[](difference_type _Off) const
1660		{    // subscript
1661		return (*(*this + _Off));
1662		}
1663
1664		bool operator==(const _Mytype& _Right) const
1665		{    // test for iterator equality
1666
1667		#if _HAS_ITERATOR_DEBUGGING
1668		_Compat(_Right);
1669		#endif /* _HAS_ITERATOR_DEBUGGING */
1670
1671		return (this->_Myptr == _Right._Myptr
1672		&& this->_Myoff == _Right._Myoff);
1673		}
1674
1675		bool operator!=(const _Mytype& _Right) const
1676		{    // test for iterator inequality
1677		return (!(*this == _Right));
1678		}
1679
1680		bool operator<(const _Mytype& _Right) const
1681		{    // test if this < _Right
1682
1683		#if _HAS_ITERATOR_DEBUGGING
1684		_Compat(_Right);
1685		#endif /* _HAS_ITERATOR_DEBUGGING */
1686
1687		return (this->_Myptr < _Right._Myptr
1688		|| this->_Myptr == _Right._Myptr
1689		&& this->_Myoff < _Right._Myoff);
1690		}
1691
1692		bool operator>(const _Mytype& _Right) const
1693		{    // test if this > _Right
1694		return (_Right < *this);
1695		}
1696
1697		bool operator<=(const _Mytype& _Right) const
1698		{    // test if this <= _Right
1699		return (!(_Right < *this));
1700		}
1701
1702		bool operator>=(const _Mytype& _Right) const
1703		{    // test if this >= _Right
1704		return (!(*this < _Right));
1705		}
1706
1707		protected:
1708
1709		#if _HAS_ITERATOR_DEBUGGING
1710		void _Compat(const _Mytype& _Right) const
1711		{    // test for compatible iterator pair
1712		if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
1713		_DEBUG_ERROR("vector<bool> iterators incompatible");
1714		}
1715		#endif /* _HAS_ITERATOR_DEBUGGING */
1716
1717		void _Dec()
1718		{    // decrement bit position
1719		if (this->_Myoff != 0)
1720		{
1721		--this->_Myoff;
1722		}
1723		else
1724		{
1725		_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL);
1726		_SCL_SECURE_VALIDATE_RANGE(this->_Myptr > this->_My_cont_begin());
1727		--this->_Myptr;
1728		this->_Myoff = _VBITS - 1;
1729		}
1730		}
1731
1732		void _Inc()
1733		{    // increment bit position
1734		_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL);
1735		_SCL_SECURE_VALIDATE_RANGE((this->_My_actual_offset() + 1) <= ((_MycontTy *)this->_Getmycont())->_Mysize);
1736		if (this->_Myoff < _VBITS - 1)
1737		++this->_Myoff;
1738		else
1739		this->_Myoff = 0, ++this->_Myptr;
1740		}
1741		};
1742
1743		template<class _Sizet,
1744		class _Difft,
1745		class _MycontTy>
1746		_Vb_const_iterator<_Sizet, _Difft, _MycontTy> operator+(_Difft _Off,
1747		_Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Right)
1748		{    // return _Right + integer
1749		return (_Right += _Off);
1750		}
1751
1752		// CLASS _Vb_iterator
1753		template<class _Sizet,
1754		class _Difft,
1755		class _MycontTy>
1756		class _Vb_iterator
1757		: public _Vb_const_iterator<_Sizet, _Difft, _MycontTy>
1758		{    // iterator for mutable vector<bool>
1759		public:
1760		typedef _Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Mybase;
1761		typedef _Vb_iterator<_Sizet, _Difft, _MycontTy> _Mytype;
1762
1763		typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Reft;
1764		typedef bool const_reference;
1765
1766		typedef random_access_iterator_tag iterator_category;
1767		typedef _Bool value_type;
1768		typedef _Sizet size_type;
1769		typedef _Difft difference_type;
1770		typedef _Reft *pointer;
1771		typedef _Reft reference;
1772
1773		_Vb_iterator()
1774		{    // construct with null reference
1775		}
1776
1777		#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
1778		_Vb_iterator(_Vbase *_Ptr, _Container_base *_Mypvbool)
1779		: _Mybase(_Ptr, _Mypvbool)
1780
1781		#else
1782		_Vb_iterator( _Vbase *_Ptr)
1783		: _Mybase(_Ptr)
1784		#endif /* _HAS_ITERATOR_DEBUGGING */
1785
1786		{    // construct with offset and pointer
1787		}
1788
1789		reference operator*() const
1790		{    // return (reference to) designated object
1791		return (_Reft(*this));
1792		}
1793
1794		_Mytype& operator++()
1795		{    // preincrement
1796		++*(_Mybase *)this;
1797		return (*this);
1798		}
1799
1800		_Mytype operator++(int)
1801		{    // postincrement
1802		_Mytype _Tmp = *this;
1803		++*this;
1804		return (_Tmp);
1805		}
1806
1807		_Mytype& operator--()
1808		{    // predecrement
1809		--*(_Mybase *)this;
1810		return (*this);
1811		}
1812
1813		_Mytype operator--(int)
1814		{    // postdecrement
1815		_Mytype _Tmp = *this;
1816		--*this;
1817		return (_Tmp);
1818		}
1819
1820		_Mytype& operator+=(difference_type _Off)
1821		{    // increment by integer
1822		*(_Mybase *)this += _Off;
1823		return (*this);
1824		}
1825
1826		_Mytype operator+(difference_type _Off) const
1827		{    // return this + integer
1828		_Mytype _Tmp = *this;
1829		return (_Tmp += _Off);
1830		}
1831
1832		_Mytype& operator-=(difference_type _Off)
1833		{    // decrement by integer
1834		return (*this += -_Off);
1835		}
1836
1837		_Mytype operator-(difference_type _Off) const
1838		{    // return this - integer
1839		_Mytype _Tmp = *this;
1840		return (_Tmp -= _Off);
1841		}
1842
1843		difference_type operator-(const _Mybase& _Right) const
1844		{    // return difference of iterators
1845		return (*(_Mybase *)this - _Right);
1846		}
1847
1848		reference operator[](difference_type _Off) const
1849		{    // subscript
1850		return (*(*this + _Off));
1851		}
1852		};
1853
1854		template<class _Sizet,
1855		class _Difft,
1856		class _MycontTy>
1857		_Vb_iterator<_Sizet, _Difft, _MycontTy> operator+(_Difft _Off,
1858		_Vb_iterator<_Sizet, _Difft, _MycontTy> _Right)
1859		{    // return _Right + integer
1860		return (_Right += _Off);
1861		}
1862
1863		// CLASS vector_bool
1864		template<class _Alloc>
1865		class vector<_Bool, _Alloc>
1866		: public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
1867		{    // varying size array of bits
1868		public:
1869		typedef typename _Alloc::size_type size_type;
1870		typedef typename _Alloc::difference_type _Dift;
1871		typedef std::vector<_Vbase,
1872		typename _Alloc::template rebind<_Vbase>::other>
1873		_Vbtype;
1874		typedef std::vector<_Bool, _Alloc> _Myt;
1875
1876
1877		typedef _Dift difference_type;
1878		typedef _Bool _Ty;
1879		typedef _Alloc allocator_type;
1880
1881		typedef _Vb_reference<size_type, _Dift, _Myt> reference;
1882		typedef bool const_reference;
1883		typedef bool value_type;
1884
1885		typedef reference _Reft;
1886		typedef _Vb_const_iterator<size_type, difference_type, _Myt> const_iterator;
1887		typedef _Vb_iterator<size_type, difference_type, _Myt> iterator;
1888
1889		friend class _Vb_iter_base<size_type, difference_type, _Myt>;
1890		friend class _Vb_reference<size_type, difference_type, _Myt>;
1891		friend class _Vb_const_iterator<size_type, difference_type, _Myt>;
1892		friend class _Vb_iterator<size_type, difference_type, _Myt>;
1893
1894		typedef iterator pointer;
1895		typedef const_iterator const_pointer;
1896		typedef std::reverse_iterator<iterator> reverse_iterator;
1897		typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1898
1899		static const int _VBITS = std::_VBITS;
1900
1901		vector()
1902		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0), _Myvec()
1903		{    // construct empty vector
1904		}
1905
1906		vector(const _Myt& _Right)
1907		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Right.get_allocator()), _Mysize(_Right._Mysize), _Myvec(_Right._Myvec)
1908		{    // copy construct vector; an implicitly defined copy constructor would not create an aux object.
1909		}
1910
1911		explicit vector(const _Alloc& _Al)
1912		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0), _Myvec(_Al)
1913		{    // construct empty vector, with allocator
1914		}
1915
1916		explicit vector(size_type _Count, bool _Val = false)
1917		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0), _Myvec(_Nw(_Count), (_Vbase)(_Val ? -1 : 0))
1918		{    // construct from _Count * _Val
1919		_Trim(_Count);
1920		}
1921
1922		vector(size_type _Count, bool _Val, const _Alloc& _Al)
1923		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0), _Myvec(_Nw(_Count), (_Vbase)(_Val ? -1 : 0), _Al)
1924		{    // construct from _Count * _Val, with allocator
1925		_Trim(_Count);
1926		}
1927
1928		template<class _Iter>
1929		vector(_Iter _First, _Iter _Last)
1930		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0), _Myvec()
1931		{    // construct from [_First, _Last)
1932		_BConstruct(_First, _Last, _Iter_cat(_First));
1933		}
1934
1935		template<class _Iter>
1936		vector(_Iter _First, _Iter _Last, const _Alloc& _Al)
1937		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0), _Myvec(_Al)
1938		{    // construct from [_First, _Last), with allocator
1939		_BConstruct(_First, _Last, _Iter_cat(_First));
1940		}
1941
1942		template<class _Iter>
1943		void _BConstruct(_Iter _Count, _Iter _Val, _Int_iterator_tag)
1944		{    // initialize from _Count * _Val
1945		size_type _Num = (size_type)_Count;
1946		_Myvec.assign(_Num, (_Ty)_Val ? -1 : 0);
1947		_Trim(_Num);
1948		}
1949
1950		template<class _Iter>
1951		void _BConstruct(_Iter _First, _Iter _Last, input_iterator_tag)
1952		{    // initialize from [_First, _Last), input iterators
1953		insert(begin(), _First, _Last);
1954		}
1955
1956		~vector()
1957		{    // destroy the object
1958		_Mysize = 0;
1959		}
1960
1961		void reserve(size_type _Count)
1962		{    // determine new minimum length of allocated storage
1963		_Myvec.reserve(_Nw(_Count));
1964		}
1965
1966		size_type capacity() const
1967		{    // return current length of allocated storage
1968		return (_Myvec.capacity() * _VBITS);
1969		}
1970
1971		#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
1972		iterator begin()
1973		{    // return iterator for beginning of mutable sequence
1974		return (iterator(_VEC_ITER_BASE(_Myvec.begin()), this));
1975		}
1976
1977		const_iterator begin() const
1978		{    // return iterator for beginning of nonmutable sequence
1979		return (const_iterator(_VEC_ITER_BASE(_Myvec.begin()), this));
1980		}
1981
1982		#else
1983		iterator begin()
1984		{    // return iterator for beginning of mutable sequence
1985		return (iterator(_VEC_ITER_BASE(_Myvec.begin())));
1986		}
1987
1988		const_iterator begin() const
1989		{    // return iterator for beginning of nonmutable sequence
1990		return (const_iterator(_VEC_ITER_BASE(_Myvec.begin())));
1991		}
1992		#endif
1993
1994		iterator end()
1995		{    // return iterator for end of mutable sequence
1996		iterator _Tmp = begin();
1997		if (0 < _Mysize)
1998		_Tmp += _Mysize;
1999		return (_Tmp);
2000		}
2001
2002		const_iterator end() const
2003		{    // return iterator for end of nonmutable sequence
2004		const_iterator _Tmp = begin();
2005		if (0 < _Mysize)
2006		_Tmp += _Mysize;
2007		return (_Tmp);
2008		}
2009
2010		iterator _Make_iter(const_iterator _Where)
2011		{    // make iterator from const_iterator
2012		iterator _Tmp = begin();
2013		if (0 < _Mysize)
2014		_Tmp += _Where - begin();
2015		return (_Tmp);
2016		}
2017
2018		reverse_iterator rbegin()
2019		{    // return iterator for beginning of reversed mutable sequence
2020		return (reverse_iterator(end()));
2021		}
2022
2023		const_reverse_iterator rbegin() const
2024		{    // return iterator for beginning of reversed nonmutable sequence
2025		return (const_reverse_iterator(end()));
2026		}
2027
2028		reverse_iterator rend()
2029		{    // return iterator for end of reversed mutable sequence
2030		return (reverse_iterator(begin()));
2031		}
2032
2033		const_reverse_iterator rend() const
2034		{    // return iterator for end of reversed nonmutable sequence
2035		return (const_reverse_iterator(begin()));
2036		}
2037
2038		void resize(size_type _Newsize, bool _Val = false)
2039		{    // determine new length, padding with _Val elements as needed
2040		if (size() < _Newsize)
2041		_Insert_n(end(), _Newsize - size(), _Val);
2042		else if (_Newsize < size())
2043		erase(begin() + _Newsize, end());
2044		}
2045
2046		size_type size() const
2047		{    // return length of sequence
2048		return (_Mysize);
2049		}
2050
2051		size_type max_size() const
2052		{    // return maximum possible length of sequence
2053		const size_type _Maxsize = _Myvec.max_size();
2054		return (_Maxsize < (size_type)(-1) / _VBITS
2055		? _Maxsize * _VBITS : (size_type)(-1));
2056		}
2057
2058		bool empty() const
2059		{    // test if sequence is empty
2060		return (size() == 0);
2061		}
2062
2063		_Alloc get_allocator() const
2064		{    // return allocator object for values
2065		// Work around a BE problem.
2066		_Alloc _Alret = _Myvec.get_allocator();
2067		return (_Alret);
2068		}
2069
2070		const_reference at(size_type _Off) const
2071		{    // subscript nonmutable sequence with checking
2072		if (size() <= _Off)
2073		_Xran();
2074		return (*(begin() + _Off));
2075		}
2076
2077		reference at(size_type _Off)
2078		{    // subscript mutable sequence with checking
2079		if (size() <= _Off)
2080		_Xran();
2081		return (*(begin() + _Off));
2082		}
2083
2084		const_reference operator[](size_type _Off) const
2085		{    // subscript nonmutable sequence
2086		return (*(begin() + _Off));
2087		}
2088
2089		reference operator[](size_type _Off)
2090		{    // subscript mutable sequence
2091		return (*(begin() + _Off));
2092		}
2093
2094		reference front()
2095		{    // return first element of mutable sequence
2096		return (*begin());
2097		}
2098
2099		const_reference front() const
2100		{    // return first element of nonmutable sequence
2101		return (*begin());
2102		}
2103
2104		reference back()
2105		{    // return last element of mutable sequence
2106		return (*(end() - 1));
2107		}
2108
2109		const_reference back() const
2110		{    // return last element of nonmutable sequence
2111		return (*(end() - 1));
2112		}
2113
2114		void push_back(bool _Val)
2115		{    // insert element at end
2116		insert(end(), _Val);
2117		}
2118
2119		void pop_back()
2120		{    // erase element at end
2121		if (!empty())
2122		erase(end() - 1);
2123		}
2124
2125		template<class _Iter>
2126		void assign(_Iter _First, _Iter _Last)
2127		{    // assign [_First, _Last)
2128		_Assign(_First, _Last, _Iter_cat(_First));
2129		}
2130
2131		template<class _Iter>
2132		void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag)
2133		{    // assign _Count * _Val
2134		_Assign_n((size_type)_Count, (bool)_Val);
2135		}
2136
2137		template<class _Iter>
2138		void _Assign(_Iter _First, _Iter _Last, input_iterator_tag)
2139		{    // assign [_First, _Last), input iterators
2140		erase(begin(), end());
2141		insert(begin(), _First, _Last);
2142		}
2143
2144		void assign(size_type _Count, bool _Val)
2145		{    // assign _Count * _Val
2146		_Assign_n(_Count, _Val);
2147		}
2148
2149		iterator insert(const_iterator _Where, bool _Val)
2150		{    // insert _Val at _Where
2151		size_type _Off = _Where - begin();
2152		_Insert_n(_Where, (size_type)1, _Val);
2153		return (begin() + _Off);
2154		}
2155
2156		void insert(const_iterator _Where, size_type _Count, bool _Val)
2157		{    // insert _Count * _Val at _Where
2158		_Insert_n(_Where, _Count, _Val);
2159		}
2160
2161		template<class _Iter>
2162		void insert(const_iterator _Where, _Iter _First, _Iter _Last)
2163		{    // insert [_First, _Last) at _Where
2164		_Insert(_Where, _First, _Last, _Iter_cat(_First));
2165		}
2166
2167		template<class _Iter>
2168		void _Insert(const_iterator _Where, _Iter _Count, _Iter _Val,
2169		_Int_iterator_tag)
2170		{    // insert _Count * _Val at _Where
2171		_Insert_n(_Where, (size_type)_Count, (bool)_Val);
2172		}
2173
2174		template<class _Iter>
2175		void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
2176		input_iterator_tag)
2177		{    // insert [_First, _Last) at _Where, input iterators
2178		size_type _Off = _Where - begin();
2179
2180		for (; _First != _Last; ++_First, ++_Off)
2181		insert(begin() + _Off, *_First);
2182		}
2183
2184		template<class _Iter>
2185		void _Insert(const_iterator _Where,
2186		_Iter _First, _Iter _Last,
2187		forward_iterator_tag)
2188		{    // insert [_First, _Last) at _Where, forward iterators
2189
2190		#if _HAS_ITERATOR_DEBUGGING
2191		_DEBUG_RANGE(_First, _Last);
2192		#endif /* _HAS_ITERATOR_DEBUGGING */
2193
2194		size_type _Count = 0;
2195		_Distance(_First, _Last, _Count);
2196
2197		size_type _Off = _Insert_x(_Where, _Count);
2198		std::copy(_First, _Last, begin() + _Off);
2199		}
2200
2201		iterator erase(const_iterator _Where_arg)
2202		{    // erase element at _Where
2203		iterator _Where = _Make_iter(_Where_arg);
2204		size_type _Off = _Where - begin();
2205
2206		#if _HAS_ITERATOR_DEBUGGING
2207		if (end() <= _Where)
2208		_DEBUG_ERROR("vector<bool> erase iterator outside range");
2209		std::copy(_Where + 1, end(), _Where);
2210		_Orphan_range(_Off, _Mysize);
2211
2212		#else /* _HAS_ITERATOR_DEBUGGING */
2213		std::copy(_Where + 1, end(), _Where);
2214		#endif /* _HAS_ITERATOR_DEBUGGING */
2215
2216		_Trim(_Mysize - 1);
2217		return (begin() + _Off);
2218		}
2219
2220		iterator erase(const_iterator _First_arg, const_iterator _Last_arg)
2221		{    // erase [_First, _Last)
2222		iterator _First = _Make_iter(_First_arg);
2223		iterator _Last = _Make_iter(_Last_arg);
2224		size_type _Off = _First - begin();
2225
2226		#if _HAS_ITERATOR_DEBUGGING
2227		if (_Last < _First || end() < _Last)
2228		_DEBUG_ERROR("vector<bool> erase iterator outside range");
2229		iterator _Next = std::copy(_Last, end(), _First);
2230		size_type _Newsize = _Next - begin();
2231		_Orphan_range(_Newsize, _Mysize);
2232		_Trim(_Newsize);
2233
2234		#else /* _HAS_ITERATOR_DEBUGGING */
2235		iterator _Next = std::copy(_Last, end(), _First);
2236		_Trim(_Next - begin());
2237		#endif /* _HAS_ITERATOR_DEBUGGING */
2238
2239		return (begin() + _Off);
2240		}
2241
2242		void clear()
2243		{    // erase all elements
2244		erase(begin(), end());
2245		}
2246
2247		void flip()
2248		{    // toggle all elements
2249		for (_Vbtype::iterator _Next = _Myvec.begin();
2250		_Next != _Myvec.end(); ++_Next)
2251		*_Next = (_Vbase)~*_Next;
2252		_Trim(_Mysize);
2253		}
2254
2255		void swap(_Myt& _Right)
2256		{    // exchange contents with right
2257		if (this != &_Right)
2258		{    // different, worth swapping
2259
2260		#if _HAS_ITERATOR_DEBUGGING
2261		this->_Swap_all(_Right);
2262		#endif /* _HAS_ITERATOR_DEBUGGING */
2263
2264		this->_Swap_aux(_Right);
2265		_STD swap(_Mysize, _Right._Mysize);
2266		_Myvec.swap(_Right._Myvec);
2267		}
2268		}
2269
2270
2271
2272		static void swap(reference _Left, reference _Right)
2273		{    // swap _Left and _Right vector<bool> elements
2274		bool _Val = _Left;
2275
2276		_Left = _Right;
2277		_Right = _Val;
2278		}
2279
2280
2281		protected:
2282		void _Assign_n(size_type _Count, bool _Val)
2283		{    // assign _Count * _Val
2284		erase(begin(), end());
2285		_Insert_n(begin(), _Count, _Val);
2286		}
2287
2288		void _Insert_n(const_iterator _Where,
2289		size_type _Count, bool _Val)
2290		{    // insert _Count * _Val at _Where
2291		size_type _Off = _Insert_x(_Where, _Count);
2292		std::fill(begin() + _Off, begin() + (_Off + _Count), _Val);
2293		}
2294
2295		size_type _Insert_x(const_iterator _Where, size_type _Count)
2296		{    // make room to insert _Count elements at _Where
2297		size_type _Off = _Where - begin();
2298
2299		#if _HAS_ITERATOR_DEBUGGING
2300		if (end() < _Where)
2301		_DEBUG_ERROR("vector<bool> insert iterator outside range");
2302		bool _Realloc = capacity() - size() < _Count;
2303		#endif /* _HAS_ITERATOR_DEBUGGING */
2304
2305		if (_Count == 0)
2306		;
2307		else if (max_size() - size() < _Count)
2308		_Xlen();    // result too long
2309		else
2310		{    // worth doing
2311		_Myvec.resize(_Nw(size() + _Count), 0);
2312		if (size() == 0)
2313		_Mysize += _Count;
2314		else
2315		{    // make room and copy down suffix
2316		iterator _Oldend = end();
2317		_Mysize += _Count;
2318		std::copy_backward(begin() + _Off, _Oldend, end());
2319		}
2320
2321		#if _HAS_ITERATOR_DEBUGGING
2322		_Orphan_range(_Realloc ? 0 : _Off, _Mysize);
2323		#endif /* _HAS_ITERATOR_DEBUGGING */
2324
2325		}
2326		return (_Off);
2327		}
2328
2329		static size_type _Nw(size_type _Count)
2330		{    // return number of base words from number of bits
2331		return ((_Count + _VBITS - 1) / _VBITS);
2332		}
2333
2334		#if _HAS_ITERATOR_DEBUGGING
2335		void _Orphan_range(size_type _Offlo, size_type _Offhi) const
2336		{    // orphan iterators within specified (inclusive) range
2337		typedef _Vb_iter_base<size_type, difference_type, _Myt> _Myiterbase;
2338
2339		_Lockit _Lock(_LOCK_DEBUG);
2340		_Vbase *_Base = (_Vbase *)_VEC_ITER_BASE(_Myvec.begin());
2341
2342		_Myiterbase **_Pnext =
2343		(_Myiterbase **)&this->_Myfirstiter;
2344		while (*_Pnext != 0)
2345		{    // test offset from beginning of vector
2346		size_type _Off = _VBITS * ((*_Pnext)->_Myptr - _Base)
2347		+ (*_Pnext)->_Myoff;
2348		if (_Off < _Offlo || _Offhi < _Off)
2349		_Pnext = (_Myiterbase **)&(*_Pnext)->_Mynextiter;
2350		else
2351		{    // orphan the iterator
2352		(*_Pnext)->_Mycont = 0;
2353		*_Pnext = (_Myiterbase *)(*_Pnext)->_Mynextiter;
2354		}
2355		}
2356		}
2357		#endif /* _HAS_ITERATOR_DEBUGGING */
2358
2359		void _Trim(size_type _Size)
2360		{    // trim base vector to exact length in bits
2361		if (max_size() < _Size)
2362		_Xlen();    // result too long
2363		size_type _Words = _Nw(_Size);
2364
2365		if (_Words < _Myvec.size())
2366		_Myvec.erase(_Myvec.begin() + _Words, _Myvec.end());
2367		_Mysize = _Size;
2368		_Size %= _VBITS;
2369		if (0 < _Size)
2370		_Myvec[_Words - 1] &= (_Vbase)((1 << _Size) - 1);
2371		}
2372
2373		void _Xlen() const
2374		{    // report a length_error
2375		_THROW(length_error, "vector<bool> too long");
2376		}
2377
2378		void _Xran() const
2379		{    // throw an out_of_range error
2380		_THROW(out_of_range, "invalid vector<bool> subscript");
2381		}
2382
2383		size_type _Mysize;    // current length of sequence
2384		_Vbtype _Myvec;    // base vector of words
2385		};
2386
2387		typedef vector<bool, allocator<bool> > _Bvector;
2388
2389		#if _HAS_TRADITIONAL_STL
2390		typedef _Bvector bit_vector;
2391		#define __vector__    vector
2392		#endif /* _HAS_TRADITIONAL_STL */
2393
2394		_STD_END
2395
2396		#ifdef _MSC_VER
2397		#pragma warning(default: 4244)
2398		#pragma warning(pop)
2399		#pragma pack(pop)
2400		#endif  /* _MSC_VER */
2401
2402		#endif /* RC_INVOKED */
2403		#endif /* _VECTOR_ */
2404
2405		/*
2406		* This file is derived from software bearing the following
2407		* restrictions:
2408		*
2409		* Copyright (c) 1994
2410		* Hewlett-Packard Company
2411		*
2412		* Permission to use, copy, modify, distribute and sell this
2413		* software and its documentation for any purpose is hereby
2414		* granted without fee, provided that the above copyright notice
2415		* appear in all copies and that both that copyright notice and
2416		* this permission notice appear in supporting documentation.
2417		* Hewlett-Packard Company makes no representations about the
2418		* suitability of this software for any purpose. It is provided
2419		* "as is" without express or implied warranty.
2420		*/
2421
2422		/*
2423		* Copyright (c) 1992-2008 by P.J. Plauger.  ALL RIGHTS RESERVED.
2424		* Consult your license regarding permissions and restrictions.
2425		V5.05:0009 */
2426
2427
2428