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 90 : _Vector_const_iterator(_Tptr _Ptr, const _Container_base *_Pvector)
69 : { // construct with pointer _Ptr
70 90 : _SCL_SECURE_VALIDATE(_Pvector == NULL || (((_Myvec *)_Pvector)->_Myfirst <= _Ptr && _Ptr <= ((_Myvec *)_Pvector)->_Mylast));
71 90 : this->_Adopt(_Pvector);
72 90 : _Myptr = _Ptr;
73 90 : }
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 29 : { // return designated object
92 :
93 : #if _HAS_ITERATOR_DEBUGGING
94 : if (this->_Mycont == 0
95 : || _Myptr < ((_Myvec *)this->_Mycont)->_Myfirst
96 29 : || ((_Myvec *)this->_Mycont)->_Mylast <= _Myptr)
97 : {
98 0 : _DEBUG_ERROR("vector iterator not dereferencable");
99 0 : _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 29 : return (*_Myptr);
107 29 : }
108 :
109 : pointer operator->() const
110 0 : { // return pointer to class object
111 0 : return (&**this);
112 0 : }
113 :
114 : _Myt& operator++()
115 28 : { // preincrement
116 28 : _SCL_SECURE_VALIDATE(this->_Has_container());
117 28 : _SCL_SECURE_VALIDATE_RANGE(_Myptr < ((_Myvec *)(this->_Getmycont()))->_Mylast);
118 :
119 : #if _HAS_ITERATOR_DEBUGGING
120 : if (this->_Mycont == 0
121 28 : || ((_Myvec *)this->_Mycont)->_Mylast <= _Myptr)
122 0 : _DEBUG_ERROR("vector iterator not incrementable");
123 : #endif /* _HAS_ITERATOR_DEBUGGING */
124 :
125 28 : ++_Myptr;
126 28 : return (*this);
127 28 : }
128 :
129 : _Myt operator++(int)
130 : { // postincrement
131 : _Myt _Tmp = *this;
132 : ++*this;
133 : return (_Tmp);
134 : }
135 :
136 : _Myt& operator--()
137 0 : { // predecrement
138 0 : _SCL_SECURE_VALIDATE(this->_Has_container());
139 0 : _SCL_SECURE_VALIDATE_RANGE(_Myptr > ((_Myvec *)(this->_Getmycont()))->_Myfirst);
140 :
141 : #if _HAS_ITERATOR_DEBUGGING
142 : if (this->_Mycont == 0
143 0 : || _Myptr == ((_Myvec *)this->_Mycont)->_Myfirst)
144 0 : _DEBUG_ERROR("vector iterator not decrementable");
145 : #endif /* _HAS_ITERATOR_DEBUGGING */
146 :
147 0 : --_Myptr;
148 0 : return (*this);
149 0 : }
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 51 : { // increment by integer
160 51 : _SCL_SECURE_VALIDATE(this->_Has_container());
161 51 : _SCL_SECURE_VALIDATE_RANGE(
162 : _Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast &&
163 0 : _Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst);
164 51 : _Myptr += _Off;
165 51 : return (*this);
166 51 : }
167 :
168 : _Myt operator+(difference_type _Off) const
169 0 : { // return this + integer
170 0 : _Myt _Tmp = *this;
171 0 : return (_Tmp += _Off);
172 0 : }
173 :
174 : _Myt& operator-=(difference_type _Off)
175 0 : { // decrement by integer
176 0 : return (*this += -_Off);
177 0 : }
178 :
179 : _Myt operator-(difference_type _Off) const
180 0 : { // return this - integer
181 0 : _Myt _Tmp = *this;
182 0 : return (_Tmp -= _Off);
183 0 : }
184 :
185 : difference_type operator-(const _Myt& _Right) const
186 30 : { // return difference of iterators
187 :
188 : #if _HAS_ITERATOR_DEBUGGING
189 30 : _Compat(_Right);
190 : #else
191 : _SCL_SECURE_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
192 : #endif /* _HAS_ITERATOR_DEBUGGING */
193 :
194 30 : return (_Myptr - _Right._Myptr);
195 30 : }
196 :
197 : reference operator[](difference_type _Off) const
198 : { // subscript
199 : return (*(*this + _Off));
200 : }
201 :
202 : bool operator==(const _Myt& _Right) const
203 78 : { // test for iterator equality
204 :
205 : #if _HAS_ITERATOR_DEBUGGING
206 78 : _Compat(_Right);
207 : #else
208 : _SCL_SECURE_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
209 : #endif /* _HAS_ITERATOR_DEBUGGING */
210 :
211 78 : return (_Myptr == _Right._Myptr);
212 78 : }
213 :
214 : bool operator!=(const _Myt& _Right) const
215 78 : { // test for iterator inequality
216 78 : return (!(*this == _Right));
217 78 : }
218 :
219 : bool operator<(const _Myt& _Right) const
220 31 : { // test if this < _Right
221 :
222 : #if _HAS_ITERATOR_DEBUGGING
223 31 : _Compat(_Right);
224 : #else
225 : _SCL_SECURE_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
226 : #endif /* _HAS_ITERATOR_DEBUGGING */
227 :
228 31 : return (_Myptr < _Right._Myptr);
229 31 : }
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 89 : { // test for compatible iterator pair
249 89 : if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
250 : {
251 0 : _DEBUG_ERROR("vector iterators incompatible");
252 0 : _SCL_SECURE_INVALID_ARGUMENT;
253 : }
254 89 : }
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 14 : _Vector_iterator(pointer _Ptr, const _Container_base *_Pvector)
320 : : _Mybase(_Ptr, _Pvector)
321 90 : { // construct with pointer _Ptr
322 90 : }
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 9 : { // return designated object
339 9 : return ((reference)**(_Mybase *)this);
340 9 : }
341 :
342 : pointer operator->() const
343 0 : { // return pointer to class object
344 0 : return (&**this);
345 0 : }
346 :
347 : _Myt& operator++()
348 0 : { // preincrement
349 0 : ++(*(_Mybase *)this);
350 0 : return (*this);
351 0 : }
352 :
353 : _Myt operator++(int)
354 : { // postincrement
355 : _Myt _Tmp = *this;
356 : ++*this;
357 : return (_Tmp);
358 : }
359 :
360 : _Myt& operator--()
361 0 : { // predecrement
362 0 : --(*(_Mybase *)this);
363 0 : return (*this);
364 0 : }
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 51 : { // increment by integer
375 51 : (*(_Mybase *)this) += _Off;
376 51 : return (*this);
377 51 : }
378 :
379 : _Myt operator+(difference_type _Off) const
380 51 : { // return this + integer
381 51 : _Myt _Tmp = *this;
382 51 : return (_Tmp += _Off);
383 51 : }
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 100 : { // construct allocator from _Al
426 100 : }
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:
441 : typedef vector<_Ty, _Ax> _Myt;
442 : typedef _Vector_val<_Ty, _Ax> _Mybase;
443 : typedef typename _Mybase::_Alty _Alloc;
444 : typedef _Alloc allocator_type;
445 : typedef typename _Alloc::size_type size_type;
446 : typedef typename _Alloc::difference_type _Dift;
447 : typedef _Dift difference_type;
448 : typedef typename _Alloc::pointer _Tptr;
449 : typedef typename _Alloc::const_pointer _Ctptr;
450 : typedef _Tptr pointer;
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 100 : { // construct empty vector
471 100 : _Buy(0);
472 100 : }
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 1 : { // construct by copying _Right
501 1 : if (_Buy(_Right.size()))
502 1 : _TRY_BEGIN
503 1 : _Mylast = _Ucopy(_Right.begin(), _Right.end(), _Myfirst);
504 : _CATCH_ALL
505 0 : _Tidy();
506 0 : _RERAISE;
507 0 : _CATCH_END
508 1 : }
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 100 : { // destroy the object
559 100 : _Tidy();
560 100 : }
561 :
562 : _Myt& operator=(const _Myt& _Right)
563 0 : { // assign _Right
564 0 : if (this != &_Right)
565 : { // worth doing
566 :
567 : #if _HAS_ITERATOR_DEBUGGING
568 0 : this->_Orphan_all();
569 : #endif /* _HAS_ITERATOR_DEBUGGING */
570 :
571 0 : if (_Right.size() == 0)
572 0 : clear(); // new sequence empty, erase existing sequence
573 0 : else if (_Right.size() <= size())
574 : { // enough elements, copy new and destroy old
575 : pointer _Ptr = _STDEXT unchecked_copy(_Right._Myfirst, _Right._Mylast,
576 0 : _Myfirst); // copy new
577 0 : _Destroy(_Ptr, _Mylast); // destroy old
578 0 : _Mylast = _Myfirst + _Right.size();
579 : }
580 0 : else if (_Right.size() <= capacity())
581 : { // enough room, copy and construct new
582 0 : pointer _Ptr = _Right._Myfirst + size();
583 0 : _STDEXT unchecked_copy(_Right._Myfirst, _Ptr, _Myfirst);
584 0 : _Mylast = _Ucopy(_Ptr, _Right._Mylast, _Mylast);
585 : }
586 0 : else
587 : { // not enough room, allocate new array and construct new
588 0 : if (_Myfirst != 0)
589 : { // discard old array
590 0 : _Destroy(_Myfirst, _Mylast);
591 0 : this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
592 : }
593 0 : if (_Buy(_Right.size()))
594 : _Mylast = _Ucopy(_Right._Myfirst, _Right._Mylast,
595 0 : _Myfirst);
596 : }
597 : }
598 0 : return (*this);
599 0 : }
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 54 : { // return current length of allocated storage
635 54 : return (_Myfirst == 0 ? 0 : _Myend - _Myfirst);
636 54 : }
637 :
638 : #if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL
639 : iterator begin()
640 89 : { // return iterator for beginning of mutable sequence
641 89 : return (iterator(_Myfirst, this));
642 89 : }
643 :
644 : const_iterator begin() const
645 46 : { // return iterator for beginning of nonmutable sequence
646 46 : return (const_iterator(_Myfirst, this));
647 46 : }
648 :
649 : iterator end()
650 90 : { // return iterator for end of mutable sequence
651 90 : return (iterator(_Mylast, this));
652 90 : }
653 :
654 : const_iterator end() const
655 46 : { // return iterator for end of nonmutable sequence
656 46 : return (const_iterator(_Mylast, this));
657 46 : }
658 :
659 : iterator _Make_iter(const_iterator _Where) const
660 31 : { // make iterator from const_iterator
661 31 : return (iterator(_Where._Myptr, this));
662 31 : }
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 9 : { // return iterator for beginning of reversed mutable sequence
693 9 : return (reverse_iterator(end()));
694 9 : }
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 9 : { // return iterator for end of reversed mutable sequence
703 9 : return (reverse_iterator(begin()));
704 9 : }
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 3 : { // determine new length, padding with _Ty() elements as needed
713 3 : resize(_Newsize, _Ty());
714 3 : }
715 :
716 : void resize(size_type _Newsize, _Ty _Val)
717 3 : { // determine new length, padding with _Val elements as needed
718 3 : if (size() < _Newsize)
719 3 : _Insert_n(end(), _Newsize - size(), _Val);
720 0 : else if (_Newsize < size())
721 0 : erase(begin() + _Newsize, end());
722 3 : }
723 :
724 : size_type size() const
725 66 : { // return length of sequence
726 66 : return (_Mylast - _Myfirst);
727 66 : }
728 :
729 : size_type max_size() const
730 54 : { // return maximum possible length of sequence
731 54 : return (this->_Alval.max_size());
732 54 : }
733 :
734 : bool empty() const
735 2 : { // test if sequence is empty
736 2 : return (size() == 0);
737 2 : }
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 0 : { // subscript nonmutable sequence with checking
746 0 : if (size() <= _Pos)
747 0 : _Xran();
748 0 : return (*(begin() + _Pos));
749 0 : }
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 33 : { // subscript nonmutable sequence
760 :
761 : #if _HAS_ITERATOR_DEBUGGING
762 33 : if (size() <= _Pos)
763 : {
764 0 : _DEBUG_ERROR("vector subscript out of range");
765 0 : _SCL_SECURE_OUT_OF_RANGE;
766 : }
767 : #endif /* _HAS_ITERATOR_DEBUGGING */
768 33 : _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
769 :
770 33 : return (*(_Myfirst + _Pos));
771 33 : }
772 :
773 : reference operator[](size_type _Pos)
774 44 : { // subscript mutable sequence
775 :
776 : #if _HAS_ITERATOR_DEBUGGING
777 44 : if (size() <= _Pos)
778 : {
779 0 : _DEBUG_ERROR("vector subscript out of range");
780 0 : _SCL_SECURE_OUT_OF_RANGE;
781 : }
782 : #endif /* _HAS_ITERATOR_DEBUGGING */
783 44 : _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
784 :
785 44 : return (*(_Myfirst + _Pos));
786 44 : }
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 0 : { // return last element of nonmutable sequence
805 0 : return (*(end() - 1));
806 0 : }
807 :
808 : void push_back(const _Ty& _Val)
809 51 : { // insert element at end
810 51 : if (size() < capacity())
811 :
812 : #if _HAS_ITERATOR_DEBUGGING
813 : { // room at end, construct it there
814 13 : _Orphan_range(_Mylast, _Mylast);
815 13 : _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 13 : else
823 51 : insert(end(), _Val);
824 51 : }
825 :
826 : #if _HAS_ITERATOR_DEBUGGING
827 : void pop_back()
828 1 : { // erase element at end
829 1 : if (empty())
830 0 : _DEBUG_ERROR("vector empty before pop");
831 0 : else
832 : { // erase last element
833 1 : _Orphan_range(_Mylast - 1, _Mylast);
834 1 : _Destroy(_Mylast - 1, _Mylast);
835 1 : --_Mylast;
836 : }
837 1 : }
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 51 : { // insert _Val at _Where
876 51 : size_type _Off = size() == 0 ? 0 : _Where - begin();
877 51 : _Insert_n(_Where, (size_type)1, _Val);
878 51 : return (begin() + _Off);
879 51 : }
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 0 : { // erase element at where
1005 : if (_Where._Mycont != this
1006 0 : || _Where._Myptr < _Myfirst || _Mylast <= _Where._Myptr)
1007 0 : _DEBUG_ERROR("vector erase iterator outside range");
1008 0 : _STDEXT unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);
1009 0 : _Destroy(_Mylast - 1, _Mylast);
1010 0 : _Orphan_range(_Where._Myptr, _Mylast);
1011 0 : --_Mylast;
1012 0 : return (iterator(_Where._Myptr, this));
1013 0 : }
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 31 : { // erase [_First, _Last)
1029 31 : iterator _First = _Make_iter(_First_arg);
1030 31 : iterator _Last = _Make_iter(_Last_arg);
1031 :
1032 31 : if (_First != _Last)
1033 : { // worth doing, copy down over hole
1034 :
1035 : #if _HAS_ITERATOR_DEBUGGING
1036 : if (_Last < _First || _First._Mycont != this
1037 3 : || _First._Myptr < _Myfirst || _Mylast < _Last._Myptr)
1038 0 : _DEBUG_ERROR("vector erase iterator outside range");
1039 : pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
1040 3 : _VEC_ITER_BASE(_First));
1041 3 : _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 3 : _Destroy(_Ptr, _Mylast);
1049 3 : _Mylast = _Ptr;
1050 : }
1051 : #if _HAS_ITERATOR_DEBUGGING
1052 31 : return (iterator(_First._Myptr, this));
1053 : #else
1054 : return (_First);
1055 : #endif
1056 31 : }
1057 :
1058 : void clear()
1059 31 : { // erase all
1060 31 : erase(begin(), end());
1061 31 : }
1062 :
1063 : void swap(_Myt& _Right)
1064 1 : { // exchange contents with _Right
1065 1 : if (this == &_Right)
1066 : ; // same object, do nothing
1067 1 : else if (this->_Alval == _Right._Alval)
1068 : { // same allocator, swap control information
1069 :
1070 : #if _HAS_ITERATOR_DEBUGGING
1071 1 : this->_Swap_all(_Right);
1072 : #endif /* _HAS_ITERATOR_DEBUGGING */
1073 :
1074 1 : this->_Swap_aux(_Right);
1075 :
1076 1 : _STD swap(_Myfirst, _Right._Myfirst);
1077 1 : _STD swap(_Mylast, _Right._Mylast);
1078 1 : _STD swap(_Myend, _Right._Myend);
1079 : }
1080 1 : else
1081 : { // different allocator, do multiple assigns
1082 0 : this->_Swap_aux(_Right);
1083 :
1084 0 : _Myt _Ts = *this;
1085 :
1086 0 : *this = _Right;
1087 0 : _Right = _Ts;
1088 0 : }
1089 1 : }
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 100 : { // allocate array with _Capacity elements
1103 100 : _Myfirst = 0, _Mylast = 0, _Myend = 0;
1104 100 : if (_Capacity == 0)
1105 100 : return (false);
1106 1 : else if (max_size() < _Capacity)
1107 0 : _Xlen(); // result too long
1108 0 : else
1109 : { // nonempty array, allocate storage
1110 1 : _Myfirst = this->_Alval.allocate(_Capacity);
1111 1 : _Mylast = _Myfirst;
1112 1 : _Myend = _Myfirst + _Capacity;
1113 : }
1114 1 : return (true);
1115 100 : }
1116 :
1117 : void _Destroy(pointer _First, pointer _Last)
1118 54 : { // destroy [_First, _Last) using allocator
1119 54 : _Destroy_range(_First, _Last, this->_Alval);
1120 54 : }
1121 :
1122 : void _Tidy()
1123 100 : { // free all storage
1124 100 : if (_Myfirst != 0)
1125 : { // something to free, destroy and deallocate it
1126 :
1127 : #if _HAS_ITERATOR_DEBUGGING
1128 54 : this->_Orphan_all();
1129 : #endif /* _HAS_ITERATOR_DEBUGGING */
1130 :
1131 54 : _Destroy(_Myfirst, _Mylast);
1132 54 : this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
1133 : }
1134 100 : _Myfirst = 0, _Mylast = 0, _Myend = 0;
1135 100 : }
1136 :
1137 : template<class _Iter>
1138 1 : pointer _Ucopy(_Iter _First, _Iter _Last, pointer _Ptr)
1139 : { // copy initializing [_First, _Last), using allocator
1140 : return (_STDEXT unchecked_uninitialized_copy(_First, _Last,
1141 1 : _Ptr, this->_Alval));
1142 1 : }
1143 :
1144 : template<class _Iter>
1145 54 : pointer _Umove(_Iter _First, _Iter _Last, pointer _Ptr)
1146 : { // move initializing [_First, _Last), using allocator
1147 : return (_STDEXT _Unchecked_uninitialized_move(_First, _Last,
1148 54 : _Ptr, this->_Alval));
1149 54 : }
1150 :
1151 : void _Insert_n(const_iterator _Where,
1152 : size_type _Count, const _Ty& _Val)
1153 54 : { // insert _Count * _Val at _Where
1154 :
1155 : #if _HAS_ITERATOR_DEBUGGING
1156 : if (_Where._Mycont != this
1157 54 : || _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr)
1158 0 : _DEBUG_ERROR("vector insert iterator outside range");
1159 : #endif /* _HAS_ITERATOR_DEBUGGING */
1160 :
1161 54 : size_type _Capacity = capacity();
1162 :
1163 54 : if (_Count == 0)
1164 : ;
1165 54 : else if (max_size() - size() < _Count)
1166 0 : _Xlen(); // result too long
1167 54 : else if (_Capacity < size() + _Count)
1168 : { // not enough room, reallocate
1169 : _Capacity = max_size() - _Capacity / 2 < _Capacity
1170 54 : ? 0 : _Capacity + _Capacity / 2; // try to grow by 50%
1171 54 : if (_Capacity < size() + _Count)
1172 54 : _Capacity = size() + _Count;
1173 54 : pointer _Newvec = this->_Alval.allocate(_Capacity);
1174 54 : size_type _Whereoff = _VEC_ITER_BASE(_Where) - _Myfirst;
1175 54 : int _Ncopied = 0;
1176 :
1177 54 : _TRY_BEGIN
1178 54 : _Ufill(_Newvec + _Whereoff, _Count, _Val); // add new stuff
1179 54 : ++_Ncopied;
1180 : _Umove(this->_Myfirst, _VEC_ITER_BASE(_Where),
1181 54 : _Newvec); // move prefix
1182 54 : ++_Ncopied;
1183 : _Umove(_VEC_ITER_BASE(_Where), this->_Mylast,
1184 54 : _Newvec + (_Whereoff + _Count)); // move suffix
1185 : _CATCH_ALL
1186 0 : if (1 < _Ncopied)
1187 0 : _Destroy(_Newvec, _Newvec + _Whereoff);
1188 0 : if (0 < _Ncopied)
1189 0 : _Destroy(_Newvec + _Whereoff, _Newvec + _Whereoff + _Count);
1190 0 : this->_Alval.deallocate(_Newvec, _Capacity);
1191 0 : _RERAISE;
1192 0 : _CATCH_END
1193 :
1194 54 : _Count += size();
1195 54 : if (_Myfirst != 0)
1196 : { // destroy and deallocate old array
1197 32 : _Destroy(_Myfirst, _Mylast);
1198 32 : this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
1199 : }
1200 :
1201 : #if _HAS_ITERATOR_DEBUGGING
1202 54 : this->_Orphan_all();
1203 : #endif /* _HAS_ITERATOR_DEBUGGING */
1204 :
1205 54 : _Myend = _Newvec + _Capacity;
1206 54 : _Mylast = _Newvec + _Count;
1207 54 : _Myfirst = _Newvec;
1208 : }
1209 2 : else if ((size_type)(_Mylast - _VEC_ITER_BASE(_Where)) < _Count)
1210 : { // new stuff spills off end
1211 2 : _Ty _Tmp = _Val; // in case _Val is in sequence
1212 :
1213 : _Umove(_VEC_ITER_BASE(_Where), _Mylast,
1214 2 : _VEC_ITER_BASE(_Where) + _Count); // copy suffix
1215 :
1216 2 : _TRY_BEGIN
1217 : _Ufill(_Mylast, _Count - (_Mylast - _VEC_ITER_BASE(_Where)),
1218 2 : _Tmp); // insert new stuff off end
1219 : _CATCH_ALL
1220 0 : _Destroy(_VEC_ITER_BASE(_Where) + _Count, _Mylast + _Count);
1221 0 : _RERAISE;
1222 0 : _CATCH_END
1223 :
1224 2 : _Mylast += _Count;
1225 :
1226 : #if _HAS_ITERATOR_DEBUGGING
1227 2 : _Orphan_range(_Where._Myptr, _Mylast);
1228 : #endif /* _HAS_ITERATOR_DEBUGGING */
1229 :
1230 : std::fill(_VEC_ITER_BASE(_Where), _Mylast - _Count,
1231 2 : _Tmp); // insert up to old end
1232 0 : }
1233 2 : else
1234 : { // new stuff can all be assigned
1235 0 : _Ty _Tmp = _Val; // in case _Val is in sequence
1236 :
1237 0 : pointer _Oldend = _Mylast;
1238 : _Mylast = _Umove(_Oldend - _Count, _Oldend,
1239 0 : _Mylast); // copy suffix
1240 :
1241 : #if _HAS_ITERATOR_DEBUGGING
1242 0 : _Orphan_range(_Where._Myptr, _Mylast);
1243 : #endif /* _HAS_ITERATOR_DEBUGGING */
1244 :
1245 : _STDEXT _Unchecked_move_backward(_VEC_ITER_BASE(_Where), _Oldend - _Count,
1246 0 : _Oldend); // copy hole
1247 : std::fill(_VEC_ITER_BASE(_Where), _VEC_ITER_BASE(_Where) + _Count,
1248 0 : _Tmp); // insert into hole
1249 0 : }
1250 54 : }
1251 :
1252 : pointer _Ufill(pointer _Ptr, size_type _Count, const _Ty &_Val)
1253 54 : { // copy initializing _Count * _Val, using allocator
1254 54 : _STDEXT unchecked_uninitialized_fill_n(_Ptr, _Count, _Val, this->_Alval);
1255 54 : return (_Ptr + _Count);
1256 54 : }
1257 :
1258 : static void _Xlen()
1259 0 : { // report a length_error
1260 0 : _THROW(length_error, "vector<T> too long");
1261 0 : }
1262 :
1263 : static void _Xran()
1264 0 : { // report an out_of_range error
1265 0 : _THROW(out_of_range, "invalid vector<T> subscript");
1266 0 : }
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 15 : { // orphan iterators within specified (inclusive) range
1276 15 : _Lockit _Lock(_LOCK_DEBUG);
1277 15 : const_iterator **_Pnext = (const_iterator **)&this->_Myfirstiter;
1278 15 : while (*_Pnext != 0)
1279 3 : if ((*_Pnext)->_Myptr < _First || _Last < (*_Pnext)->_Myptr)
1280 0 : _Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter;
1281 0 : else
1282 : { // orphan the iterator
1283 3 : (*_Pnext)->_Mycont = 0;
1284 3 : *_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter;
1285 3 : }
1286 15 : }
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 1 : { // swap _Left and _Right vectors
1357 1 : _Left.swap(_Right);
1358 1 : }
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 :
|