1 : // deque standard header
2 : #pragma once
3 : #ifndef _DEQUE_
4 : #define _DEQUE_
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 : #endif /* _MSC_VER */
13 :
14 : _STD_BEGIN
15 : // DEQUE PARAMETERS
16 : #define _DEQUEMAPSIZ 8 /* minimum map size, at least 1 */
17 : #define _DEQUESIZ (sizeof (_Ty) <= 1 ? 16 \
18 : : sizeof (_Ty) <= 2 ? 8 \
19 : : sizeof (_Ty) <= 4 ? 4 \
20 : : sizeof (_Ty) <= 8 ? 2 : 1) /* elements per block (a power of 2) */
21 :
22 : template<class _Ty,
23 : class _Ax = allocator<_Ty> >
24 : class deque;
25 :
26 : // TEMPLATE CLASS _Deque_const_iterator
27 : template<class _Ty, class _Alloc, bool _SECURE_VALIDATION>
28 : class _Deque_const_iterator
29 : #if !defined(_DEBUG) && !_SECURE_SCL
30 : : public _Ranit_base<_Ty, typename _Alloc::difference_type,
31 : typename _Alloc::const_pointer, typename _Alloc::const_reference, _Iterator_base_aux>
32 : #else
33 : : public _Ranit<_Ty, typename _Alloc::difference_type,
34 : typename _Alloc::const_pointer, typename _Alloc::const_reference>
35 : #endif
36 : { // iterator for nonmutable vector
37 : public:
38 : // helper data used by the expression evaluator
39 : enum { _EEN_HID = _HAS_ITERATOR_DEBUGGING };
40 :
41 : typedef _Deque_const_iterator<_Ty, _Alloc, _SECURE_VALIDATION> _Myt;
42 : typedef deque<_Ty, _Alloc> _Mydeque;
43 :
44 : #if !defined(_DEBUG) && !_SECURE_SCL
45 : typedef _Container_base_aux _Mydequebase;
46 : #else
47 : typedef _Container_base _Mydequebase;
48 : #endif
49 :
50 : typedef random_access_iterator_tag iterator_category;
51 : typedef _Ty value_type;
52 : typedef typename _Alloc::difference_type difference_type;
53 : typedef typename _Alloc::const_pointer pointer;
54 : typedef typename _Alloc::const_reference reference;
55 :
56 : typedef typename _Alloc::size_type size_type;
57 :
58 : #if _SECURE_SCL
59 : typedef typename _Secure_validation_helper<_SECURE_VALIDATION>::_Checked_iterator_category _Checked_iterator_category;
60 : typedef typename _If<_SECURE_VALIDATION,
61 : _Deque_const_iterator<_Ty, _Alloc, false>,
62 : _Unchanged_checked_iterator_base_type_tag>::_Result _Checked_iterator_base_type;
63 :
64 : friend _Deque_const_iterator<_Ty, _Alloc, false>;
65 : friend _Deque_const_iterator<_Ty, _Alloc, true>;
66 :
67 : _Deque_const_iterator<_Ty, _Alloc, false> _Checked_iterator_base() const
68 : {
69 : _Deque_const_iterator<_Ty, _Alloc, false> _Base(this->_Myoff, this->_Getmycont());
70 : return _Base;
71 : }
72 :
73 : void _Checked_iterator_assign_from_base(_Deque_const_iterator<_Ty, _Alloc, false> _Base)
74 : {
75 : _SCL_SECURE_VALIDATE(this->_Same_container(_Base));
76 : this->_Myoff = _Base._Myoff;
77 : }
78 : #endif
79 :
80 : #if _HAS_ITERATOR_DEBUGGING
81 : _Deque_const_iterator()
82 : { // construct with null deque pointer
83 : _Myoff = 0;
84 : }
85 :
86 : _Deque_const_iterator(const _Myt& _Right)
87 : : _Myoff(_Right._Myoff)
88 0 : { // construct with copy of _Right
89 0 : this->_Adopt(_Right._Mycont);
90 0 : }
91 :
92 0 : _Deque_const_iterator(size_type _Off, const _Mydequebase *_Pdeque)
93 : { // construct with offset _Off in *_Pdeque
94 : _SCL_SECURE_TRAITS_VALIDATE(
95 : _Pdeque != NULL &&
96 0 : ((_Mydeque *)_Pdeque)->_Myoff <= _Off && _Off <= (((_Mydeque *)_Pdeque)->_Myoff + ((_Mydeque *)_Pdeque)->_Mysize));
97 :
98 0 : this->_Adopt(_Pdeque);
99 0 : _Myoff = _Off;
100 0 : }
101 :
102 : reference operator*() const
103 0 : { // return designated object
104 0 : size_type _Block = _Myoff / _DEQUESIZ;
105 0 : size_type _Off = _Myoff & (_DEQUESIZ - 1); // assume power of 2
106 : if (this->_Mycont == 0
107 : || _Myoff < ((_Mydeque *)this->_Mycont)->_Myoff
108 : || ((_Mydeque *)this->_Mycont)->_Myoff
109 0 : + ((_Mydeque *)this->_Mycont)->_Mysize <= _Myoff)
110 : {
111 0 : _DEBUG_ERROR("deque iterator not dereferencable");
112 0 : _SCL_SECURE_TRAITS_OUT_OF_RANGE;
113 : }
114 0 : if (((_Mydeque *)this->_Mycont)->_Mapsize <= _Block)
115 0 : _Block -= ((_Mydeque *)this->_Mycont)->_Mapsize;
116 0 : return ((((_Mydeque *)this->_Mycont)->_Map)[_Block][_Off]);
117 0 : }
118 :
119 : #else /* _HAS_ITERATOR_DEBUGGING */
120 : _Deque_const_iterator()
121 : { // construct with null deque pointer
122 : _Myoff = 0;
123 : }
124 :
125 : _Deque_const_iterator(size_type _Off, const _Mydequebase *_Pdeque)
126 : { // construct with offset _Off in *_Pdeque
127 : _SCL_SECURE_TRAITS_VALIDATE(
128 : _Pdeque != NULL &&
129 : ((_Mydeque *)_Pdeque)->_Myoff <= _Off && _Off <= (((_Mydeque *)_Pdeque)->_Myoff + ((_Mydeque *)_Pdeque)->_Mysize));
130 :
131 : this->_Set_container(_Pdeque);
132 : _Myoff = _Off;
133 : }
134 :
135 : reference operator*() const
136 : { // return designated object
137 : size_type _Block = _Myoff / _DEQUESIZ;
138 : size_type _Off = _Myoff & (_DEQUESIZ - 1); // assume power of 2
139 : _SCL_SECURE_VALIDATE(this->_Has_container());
140 : _SCL_SECURE_VALIDATE_RANGE(_Myoff < ((_Mydeque *)(this->_Getmycont()))->_Myoff + ((_Mydeque *)(this->_Getmycont()))->_Mysize);
141 : if (static_cast<const _Mydeque *>(this->_Getmycont())->_Mapsize <= _Block)
142 : _Block -= static_cast<const _Mydeque *>(this->_Getmycont())->_Mapsize;
143 : return ((static_cast<const _Mydeque *>(this->_Getmycont())->_Map)[_Block][_Off]);
144 : }
145 : #endif /* _HAS_ITERATOR_DEBUGGING */
146 :
147 : pointer operator->() const
148 : { // return pointer to class object
149 : return (&**this);
150 : }
151 :
152 : _Myt& operator++()
153 : { // preincrement
154 : _SCL_SECURE_TRAITS_VALIDATE(this->_Has_container());
155 : _SCL_SECURE_TRAITS_VALIDATE_RANGE(_Myoff < ((_Mydeque *)(this->_Getmycont()))->_Myoff + ((_Mydeque *)(this->_Getmycont()))->_Mysize);
156 :
157 : #if _HAS_ITERATOR_DEBUGGING
158 : if (this->_Mycont == 0
159 : || ((_Mydeque *)this->_Mycont)->_Myoff
160 : + ((_Mydeque *)this->_Mycont)->_Mysize == _Myoff)
161 : _DEBUG_ERROR("deque iterator not incrementable");
162 : #endif /* _HAS_ITERATOR_DEBUGGING */
163 :
164 : ++_Myoff;
165 : return (*this);
166 : }
167 :
168 : _Myt operator++(int)
169 : { // postincrement
170 : _Myt _Tmp = *this;
171 : ++*this;
172 : return (_Tmp);
173 : }
174 :
175 : _Myt& operator--()
176 : { // predecrement
177 : _SCL_SECURE_TRAITS_VALIDATE(this->_Has_container());
178 : _SCL_SECURE_TRAITS_VALIDATE_RANGE(_Myoff > ((_Mydeque *)(this->_Getmycont()))->_Myoff);
179 :
180 : #if _HAS_ITERATOR_DEBUGGING
181 : if (this->_Mycont == 0
182 : || _Myoff == ((_Mydeque *)this->_Mycont)->_Myoff)
183 : _DEBUG_ERROR("deque iterator not decrementable");
184 : #endif /* _HAS_ITERATOR_DEBUGGING */
185 :
186 : --_Myoff;
187 : return (*this);
188 : }
189 :
190 : _Myt operator--(int)
191 : { // postdecrement
192 : _Myt _Tmp = *this;
193 : --*this;
194 : return (_Tmp);
195 : }
196 :
197 : _Myt& operator+=(difference_type _Off)
198 0 : { // increment by integer
199 0 : _SCL_SECURE_TRAITS_VALIDATE(this->_Has_container());
200 : _SCL_SECURE_TRAITS_VALIDATE_RANGE(
201 : _Myoff + _Off <= ((_Mydeque *)(this->_Getmycont()))->_Myoff + ((_Mydeque *)(this->_Getmycont()))->_Mysize &&
202 0 : _Myoff + _Off >= ((_Mydeque *)(this->_Getmycont()))->_Myoff);
203 0 : _Myoff += _Off;
204 0 : return (*this);
205 0 : }
206 :
207 : _Myt operator+(difference_type _Off) const
208 : { // return this + integer
209 : _Myt _Tmp = *this;
210 : return (_Tmp += _Off);
211 : }
212 :
213 : _Myt& operator-=(difference_type _Off)
214 : { // decrement by integer
215 : return (*this += -_Off);
216 : }
217 :
218 : _Myt operator-(difference_type _Off) const
219 : { // return this - integer
220 : _Myt _Tmp = *this;
221 : return (_Tmp -= _Off);
222 : }
223 :
224 : difference_type operator-(const _Myt& _Right) const
225 : { // return difference of iterators
226 :
227 : #if _HAS_ITERATOR_DEBUGGING
228 : _Compat(_Right);
229 : #else
230 : _SCL_SECURE_TRAITS_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
231 : #endif /* _HAS_ITERATOR_DEBUGGING */
232 :
233 : return (_Right._Myoff <= _Myoff ? _Myoff - _Right._Myoff
234 : : -(difference_type)(_Right._Myoff - _Myoff));
235 : }
236 :
237 : reference operator[](difference_type _Off) const
238 : { // subscript
239 : return (*(*this + _Off));
240 : }
241 :
242 : bool operator==(const _Myt& _Right) const
243 : { // test for iterator equality
244 :
245 : #if _HAS_ITERATOR_DEBUGGING
246 : _Compat(_Right);
247 : return (_Myoff == _Right._Myoff);
248 : }
249 :
250 : #elif _SECURE_SCL
251 : _SCL_SECURE_TRAITS_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
252 : return (_Myoff == _Right._Myoff);
253 : }
254 :
255 : #else
256 : return (this->_Same_container(_Right) && _Myoff == _Right._Myoff);
257 : }
258 : #endif /* _HAS_ITERATOR_DEBUGGING */
259 :
260 : bool operator!=(const _Myt& _Right) const
261 : { // test for iterator inequality
262 : return (!(*this == _Right));
263 : }
264 :
265 : bool operator<(const _Myt& _Right) const
266 : { // test if this < _Right
267 :
268 : #if _HAS_ITERATOR_DEBUGGING
269 : _Compat(_Right);
270 : return (_Myoff < _Right._Myoff);
271 : }
272 :
273 : #elif _SECURE_SCL
274 : _SCL_SECURE_TRAITS_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
275 : return (_Myoff < _Right._Myoff);
276 : }
277 :
278 : #else
279 : return (this->_Same_container(_Right) && _Myoff < _Right._Myoff);
280 : }
281 : #endif /* _HAS_ITERATOR_DEBUGGING */
282 :
283 : bool operator>(const _Myt& _Right) const
284 : { // test if this > _Right
285 : return (_Right < *this);
286 : }
287 :
288 : bool operator<=(const _Myt& _Right) const
289 : { // test if this <= _Right
290 : return (!(_Right < *this));
291 : }
292 :
293 : bool operator>=(const _Myt& _Right) const
294 : { // test if this >= _Right
295 : return (!(*this < _Right));
296 : }
297 :
298 : static void _Xlen()
299 : { // report length error
300 : _THROW(length_error, "deque<T> too long");
301 : }
302 :
303 : static void _Xinvarg()
304 : { // report an invalid_argument error
305 : _THROW(invalid_argument, "invalid deque <T> argument");
306 : }
307 :
308 : static void _Xran()
309 : { // report an out_of_range error
310 : _THROW(out_of_range, "invalid deque <T> subscript");
311 : }
312 :
313 : #if _HAS_ITERATOR_DEBUGGING
314 : void _Compat(const _Myt& _Right) const
315 : { // test for compatible iterator pair
316 : if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
317 : {
318 : _DEBUG_ERROR("deque iterators incompatible");
319 : _SCL_SECURE_TRAITS_INVALID_ARGUMENT;
320 : }
321 : }
322 : #endif /* _HAS_ITERATOR_DEBUGGING */
323 :
324 : size_type _Myoff; // offset of element in deque
325 : };
326 :
327 : template<class _Ty, class _Alloc, bool _SECURE_VALIDATION>
328 : inline
329 : _Deque_const_iterator<_Ty, _Alloc, _SECURE_VALIDATION> operator+(
330 : typename _Deque_const_iterator<_Ty, _Alloc, _SECURE_VALIDATION>::difference_type _Off,
331 : _Deque_const_iterator<_Ty, _Alloc, _SECURE_VALIDATION> _Next)
332 : { // add offset to iterator
333 : return (_Next += _Off);
334 : }
335 :
336 : // TEMPLATE CLASS _Deque_iterator
337 : template<class _Ty, class _Alloc, bool _SECURE_VALIDATION>
338 : class _Deque_iterator
339 : : public _Deque_const_iterator<_Ty, _Alloc, _SECURE_VALIDATION>
340 : { // iterator for mutable vector
341 : public:
342 : typedef _Deque_iterator<_Ty, _Alloc, _SECURE_VALIDATION> _Myt;
343 : typedef _Deque_const_iterator<_Ty, _Alloc, _SECURE_VALIDATION> _Mybase;
344 : typedef deque<_Ty, _Alloc> _Mydeque;
345 :
346 : typedef random_access_iterator_tag iterator_category;
347 : typedef _Ty value_type;
348 : typedef typename _Alloc::difference_type difference_type;
349 : typedef typename _Alloc::pointer pointer;
350 : typedef typename _Alloc::reference reference;
351 :
352 : typedef typename _Alloc::size_type size_type;
353 :
354 : #if _SECURE_SCL
355 : typedef typename _If<_SECURE_VALIDATION,
356 : _Deque_iterator<_Ty, _Alloc, false>,
357 : _Unchanged_checked_iterator_base_type_tag>::_Result _Checked_iterator_base_type;
358 :
359 : friend _Deque_iterator<_Ty, _Alloc, false>;
360 : friend _Deque_iterator<_Ty, _Alloc, true>;
361 :
362 : _Deque_iterator<_Ty, _Alloc, false> _Checked_iterator_base() const
363 : {
364 : _Deque_iterator<_Ty, _Alloc, false> _Base(this->_Myoff, this->_Getmycont());
365 : return _Base;
366 : }
367 :
368 : void _Checked_iterator_assign_from_base(_Deque_iterator<_Ty, _Alloc, false> _Base)
369 : {
370 : _SCL_SECURE_VALIDATE(this->_Same_container(_Base));
371 : this->_Myoff = _Base._Myoff;
372 : }
373 : #endif
374 :
375 : _Deque_iterator()
376 : { // construct with null vector pointer
377 : }
378 :
379 : _Deque_iterator(size_type _Off, const _Mybase::_Mydequebase *_Pdeque)
380 : : _Mybase(_Off, _Pdeque)
381 0 : { // construct with offset _Off in *_Pdeque
382 0 : }
383 :
384 : reference operator*() const
385 0 : { // return designated object
386 0 : return ((reference)**(_Mybase *)this);
387 0 : }
388 :
389 : pointer operator->() const
390 : { // return pointer to class object
391 : return (&**this);
392 : }
393 :
394 : _Myt& operator++()
395 : { // preincrement
396 : ++*(_Mybase *)this;
397 : return (*this);
398 : }
399 :
400 : _Myt operator++(int)
401 : { // postincrement
402 : _Myt _Tmp = *this;
403 : ++*this;
404 : return (_Tmp);
405 : }
406 :
407 : _Myt& operator--()
408 : { // predecrement
409 : --*(_Mybase *)this;
410 : return (*this);
411 : }
412 :
413 : _Myt operator--(int)
414 : { // postdecrement
415 : _Myt _Tmp = *this;
416 : --*this;
417 : return (_Tmp);
418 : }
419 :
420 : _Myt& operator+=(difference_type _Off)
421 0 : { // increment by integer
422 0 : *(_Mybase *)this += _Off;
423 0 : return (*this);
424 0 : }
425 :
426 : _Myt operator+(difference_type _Off) const
427 : { // return this + integer
428 : _Myt _Tmp = *this;
429 : return (_Tmp += _Off);
430 : }
431 :
432 : _Myt& operator-=(difference_type _Off)
433 0 : { // decrement by integer
434 0 : return (*this += -_Off);
435 0 : }
436 :
437 : _Myt operator-(difference_type _Off) const
438 0 : { // return this - integer
439 0 : _Myt _Tmp = *this;
440 0 : return (_Tmp -= _Off);
441 0 : }
442 :
443 : difference_type operator-(const _Mybase& _Right) const
444 : { // return difference of iterators
445 : return (*(_Mybase *)this - _Right);
446 : }
447 :
448 : reference operator[](difference_type _Off) const
449 : { // subscript
450 : return (*(*this + _Off));
451 : }
452 : };
453 :
454 : template<class _Ty, class _Alloc, bool _SECURE_VALIDATION>
455 : inline
456 : _Deque_iterator<_Ty, _Alloc, _SECURE_VALIDATION> operator+(
457 : typename _Deque_iterator<_Ty, _Alloc, _SECURE_VALIDATION>::difference_type _Off,
458 : _Deque_iterator<_Ty, _Alloc, _SECURE_VALIDATION> _Next)
459 : { // add offset to iterator
460 : return (_Next += _Off);
461 : }
462 :
463 : #if !defined(_DEBUG) && !_SECURE_SCL
464 : #define _DEQUE_BASE _Container_base_aux_alloc_real<_Alloc>
465 : #else
466 : #define _DEQUE_BASE _CONTAINER_BASE_AUX_ALLOC<_Alloc>
467 : #endif
468 :
469 : // TEMPLATE CLASS _Deque_map
470 : template<class _Ty,
471 : class _Alloc>
472 : class _Deque_map
473 : : public _DEQUE_BASE
474 : { // ultimate base class for deque to hold allocator _Almap
475 : protected:
476 : _Deque_map(_Alloc _Al)
477 : : _DEQUE_BASE(_Al), _Almap(_Al)
478 0 : { // construct allocator from _Al
479 0 : }
480 :
481 : typedef typename _Alloc::template rebind<_Ty>::other _Ty_alloc;
482 : typedef typename _Ty_alloc::pointer _Tptr;
483 :
484 : typedef typename _Alloc::template rebind<_Tptr>::other
485 : _Tptr_alloc;
486 : typedef typename _Tptr_alloc::pointer _Mptr;
487 :
488 : _Tptr_alloc _Almap; // allocator object for maps
489 : };
490 :
491 : // TEMPLATE CLASS _Deque_val
492 : template<class _Ty,
493 : class _Alloc>
494 : class _Deque_val
495 : : public _Deque_map<_Ty, _Alloc>
496 : { // base class for deque to hold allocator _Alval
497 : protected:
498 : _Deque_val(_Alloc _Al = _Alloc())
499 : : _Deque_map<_Ty, _Alloc>(_Al), _Alval(_Al)
500 0 : { // construct allocator and base from _Al
501 0 : }
502 :
503 : typedef _Deque_map<_Ty, _Alloc> _Mybase;
504 : typedef typename _Alloc::template rebind<_Ty>::other _Alty;
505 :
506 : _Alty _Alval; // allocator object for stored elements
507 : };
508 :
509 : // TEMPLATE CLASS deque
510 : template<class _Ty,
511 : class _Ax>
512 : class deque
513 : : public _Deque_val<_Ty, _Ax>
514 : { // circular queue of pointers to blocks
515 : public:
516 :
517 : // helper data used by the expression evaluator
518 : static const int _EEM_DS = _DEQUESIZ;
519 : enum { _EEN_DS = _DEQUESIZ };
520 :
521 : typedef deque<_Ty, _Ax> _Myt;
522 : typedef _Deque_val<_Ty, _Ax> _Mybase;
523 : typedef typename _Mybase::_Alty _Alloc;
524 : typedef _Alloc allocator_type;
525 : typedef typename _Mybase::_Tptr_alloc _Tptr_alloc;
526 : typedef typename _Alloc::size_type size_type;
527 : typedef typename _Alloc::difference_type _Dift;
528 : typedef _Dift difference_type;
529 : typedef typename _Alloc::pointer _Tptr;
530 : typedef typename _Alloc::const_pointer _Ctptr;
531 : typedef _Tptr pointer;
532 : typedef _Ctptr const_pointer;
533 : typedef typename _Mybase::_Mptr _Mapptr;
534 : typedef typename _Alloc::reference _Reft;
535 : typedef _Reft reference;
536 : typedef typename _Alloc::const_reference const_reference;
537 : typedef typename _Alloc::value_type value_type;
538 :
539 : typedef _Deque_iterator<_Ty, _Alloc, _SECURE_VALIDATION_DEFAULT> iterator;
540 : typedef _Deque_const_iterator<_Ty, _Alloc, _SECURE_VALIDATION_DEFAULT> const_iterator;
541 :
542 : // friend class _Deque_iterator<_Ty, _Alloc>;
543 : friend class _Deque_const_iterator<_Ty, _Alloc, false>;
544 : #if _SECURE_SCL
545 : friend class _Deque_const_iterator<_Ty, _Alloc, true>;
546 : #endif
547 :
548 : typedef std::reverse_iterator<iterator> reverse_iterator;
549 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
550 :
551 : deque()
552 : : _Mybase(), _Map(0),
553 : _Mapsize(0), _Myoff(0), _Mysize(0)
554 0 : { // construct empty deque
555 0 : }
556 :
557 : explicit deque(const _Alloc& _Al)
558 : : _Mybase(_Al), _Map(0),
559 : _Mapsize(0), _Myoff(0), _Mysize(0)
560 : { // construct empty deque with allocator
561 : }
562 :
563 : explicit deque(size_type _Count)
564 : : _Mybase(), _Map(0),
565 : _Mapsize(0), _Myoff(0), _Mysize(0)
566 : { // construct from _Count * _Ty()
567 : _Construct_n(_Count, _Ty());
568 : }
569 :
570 : deque(size_type _Count, const _Ty& _Val)
571 : : _Mybase(), _Map(0),
572 : _Mapsize(0), _Myoff(0), _Mysize(0)
573 : { // construct from _Count * _Val
574 : _Construct_n(_Count, _Val);
575 : }
576 :
577 : deque(size_type _Count, const _Ty& _Val, const _Alloc& _Al)
578 : : _Mybase(_Al), _Map(0),
579 : _Mapsize(0), _Myoff(0), _Mysize(0)
580 : { // construct from _Count * _Val with allocator
581 : _Construct_n(_Count, _Val);
582 : }
583 :
584 : deque(const _Myt& _Right)
585 : : _Mybase(_Right._Alval), _Map(0),
586 : _Mapsize(0), _Myoff(0), _Mysize(0)
587 : { // construct by copying _Right
588 : _TRY_BEGIN
589 : insert(begin(), _Right.begin(), _Right.end());
590 : _CATCH_ALL
591 : _Tidy();
592 : _RERAISE;
593 : _CATCH_END
594 : }
595 :
596 : template<class _It>
597 : deque(_It _First, _It _Last)
598 : : _Mybase(), _Map(0),
599 : _Mapsize(0), _Myoff(0), _Mysize(0)
600 : { // construct from [_First, _Last)
601 : _Construct(_First, _Last, _Iter_cat(_First));
602 : }
603 :
604 : template<class _It>
605 : deque(_It _First, _It _Last, const _Alloc& _Al)
606 : : _Mybase(_Al), _Map(0),
607 : _Mapsize(0), _Myoff(0), _Mysize(0)
608 : { // construct from [_First, _Last) with allocator
609 : _Construct(_First, _Last, _Iter_cat(_First));
610 : }
611 :
612 : template<class _It>
613 : void _Construct(_It _Count, _It _Val, _Int_iterator_tag)
614 : { // initialize from _Count * _Val
615 : _Construct_n((size_type)_Count, (_Ty)_Val);
616 : }
617 :
618 : template<class _It>
619 : void _Construct(_It _First, _It _Last, input_iterator_tag)
620 : { // initialize from [_First, _Last), input iterators
621 : _TRY_BEGIN
622 : insert(begin(), _First, _Last);
623 : _CATCH_ALL
624 : _Tidy();
625 : _RERAISE;
626 : _CATCH_END
627 : }
628 :
629 : void _Construct_n(size_type _Count, const _Ty& _Val)
630 : { // construct from _Count * _Val
631 : _TRY_BEGIN
632 : _Insert_n(begin(), _Count, _Val);
633 : _CATCH_ALL
634 : _Tidy();
635 : _RERAISE;
636 : _CATCH_END
637 : }
638 :
639 : ~deque()
640 0 : { // destroy the deque
641 0 : _Tidy();
642 0 : }
643 :
644 : _Myt& operator=(const _Myt& _Right)
645 : { // assign _Right
646 : if (this == &_Right)
647 : ;
648 : else if (_Right._Mysize == 0)
649 : clear();
650 : else if (_Right._Mysize <= _Mysize)
651 : { // new sequence not longer, assign elements and erase unused
652 : iterator _Mid = std::copy(_Right.begin(), _Right.end(), begin());
653 : erase(_Mid, end());
654 : }
655 : else
656 : { // new sequence longer, assign elements and append rest
657 : const_iterator _Mid = _Right.begin() + _Mysize;
658 : std::copy(_Right.begin(), _Mid, begin());
659 : insert(end(), _Mid, _Right.end());
660 : }
661 : return (*this);
662 : }
663 :
664 : iterator begin()
665 : { // return iterator for beginning of mutable sequence
666 : return (iterator(_Myoff, this));
667 : }
668 :
669 : const_iterator begin() const
670 : { // return iterator for beginning of nonmutable sequence
671 : return (const_iterator(_Myoff, this));
672 : }
673 :
674 : iterator end()
675 0 : { // return iterator for end of mutable sequence
676 0 : return (iterator(_Myoff + _Mysize, this));
677 0 : }
678 :
679 : const_iterator end() const
680 : { // return iterator for end of nonmutable sequence
681 : return (const_iterator(_Myoff + _Mysize, this));
682 : }
683 :
684 : iterator _Make_iter(const_iterator _Where) const
685 : { // make iterator from const_iterator
686 : return (iterator(_Where._Myoff, this));
687 : }
688 :
689 : reverse_iterator rbegin()
690 : { // return iterator for beginning of reversed mutable sequence
691 : return (reverse_iterator(end()));
692 : }
693 :
694 : const_reverse_iterator rbegin() const
695 : { // return iterator for beginning of reversed nonmutable sequence
696 : return (const_reverse_iterator(end()));
697 : }
698 :
699 : reverse_iterator rend()
700 : { // return iterator for end of reversed mutable sequence
701 : return (reverse_iterator(begin()));
702 : }
703 :
704 : const_reverse_iterator rend() const
705 : { // return iterator for end of reversed nonmutable sequence
706 : return (const_reverse_iterator(begin()));
707 : }
708 :
709 : void resize(size_type _Newsize)
710 : { // determine new length, padding with _Ty() elements as needed
711 : resize(_Newsize, _Ty());
712 : }
713 :
714 : void resize(size_type _Newsize, _Ty _Val)
715 : { // determine new length, padding with _Val elements as needed
716 : if (_Mysize < _Newsize)
717 : _Insert_n(end(), _Newsize - _Mysize, _Val);
718 : else if (_Newsize < _Mysize)
719 : erase(begin() + _Newsize, end());
720 : }
721 :
722 : size_type size() const
723 0 : { // return length of sequence
724 0 : return (_Mysize);
725 0 : }
726 :
727 : size_type max_size() const
728 0 : { // return maximum possible length of sequence
729 0 : return (this->_Alval.max_size());
730 0 : }
731 :
732 : bool empty() const
733 0 : { // test if sequence is empty
734 0 : return (_Mysize == 0);
735 0 : }
736 :
737 : allocator_type get_allocator() const
738 : { // return allocator object for values
739 : return (this->_Alval);
740 : }
741 :
742 : const_reference at(size_type _Pos) const
743 : { // subscript nonmutable sequence with checking
744 : if (_Mysize <= _Pos)
745 : _Xran();
746 : return (*(begin() + _Pos));
747 : }
748 :
749 : reference at(size_type _Pos)
750 : { // subscript mutable sequence with checking
751 : if (_Mysize <= _Pos)
752 : _Xran();
753 : return (*(begin() + _Pos));
754 : }
755 :
756 : const_reference operator[](size_type _Pos) const
757 : { // subscript nonmutable sequence
758 :
759 : #if _HAS_ITERATOR_DEBUGGING
760 : if (_Mysize <= _Pos)
761 : _DEBUG_ERROR("deque subscript out of range");
762 : #endif /* _HAS_ITERATOR_DEBUGGING */
763 :
764 : return (*(begin() + _Pos));
765 : }
766 :
767 : reference operator[](size_type _Pos)
768 : { // subscript mutable sequence
769 :
770 : #if _HAS_ITERATOR_DEBUGGING
771 : if (_Mysize <= _Pos)
772 : _DEBUG_ERROR("deque subscript out of range");
773 : #endif /* _HAS_ITERATOR_DEBUGGING */
774 :
775 : return (*(begin() + _Pos));
776 : }
777 :
778 : reference front()
779 : { // return first element of mutable sequence
780 : return (*begin());
781 : }
782 :
783 : const_reference front() const
784 : { // return first element of nonmutable sequence
785 : return (*begin());
786 : }
787 :
788 : reference back()
789 0 : { // return last element of mutable sequence
790 0 : return (*(end() - 1));
791 0 : }
792 :
793 : const_reference back() const
794 : { // return last element of nonmutable sequence
795 : return (*(end() - 1));
796 : }
797 :
798 : void push_front(const _Ty& _Val)
799 : { // insert element at beginning
800 :
801 : #if _HAS_ITERATOR_DEBUGGING
802 : this->_Orphan_all();
803 : #endif /* _HAS_ITERATOR_DEBUGGING */
804 :
805 : if (_Myoff % _DEQUESIZ == 0
806 : && _Mapsize <= (_Mysize + _DEQUESIZ) / _DEQUESIZ)
807 : _Growmap(1);
808 : size_type _Newoff = _Myoff != 0 ? _Myoff
809 : : _Mapsize * _DEQUESIZ;
810 : size_type _Block = --_Newoff / _DEQUESIZ;
811 : if (_Map[_Block] == 0)
812 : _Map[_Block] = this->_Alval.allocate(_DEQUESIZ);
813 : this->_Alval.construct(_Map[_Block] + _Newoff % _DEQUESIZ, _Val);
814 : _Myoff = _Newoff;
815 : ++_Mysize;
816 : }
817 :
818 : void pop_front()
819 : { // erase element at beginning
820 :
821 : #if _HAS_ITERATOR_DEBUGGING
822 : if (empty())
823 : _DEBUG_ERROR("deque empty before pop");
824 : else
825 : { // something to erase, do it
826 : _Orphan_off(_Myoff);
827 :
828 : #else /* _HAS_ITERATOR_DEBUGGING */
829 : if (!empty())
830 : { // something to erase, do it
831 : #endif /* _HAS_ITERATOR_DEBUGGING */
832 :
833 : size_type _Block = _Myoff / _DEQUESIZ;
834 : this->_Alval.destroy(_Map[_Block] + _Myoff % _DEQUESIZ);
835 : if (_Mapsize * _DEQUESIZ <= ++_Myoff)
836 : _Myoff = 0;
837 : if (--_Mysize == 0)
838 : _Myoff = 0;
839 : }
840 : }
841 :
842 : void push_back(const _Ty& _Val)
843 0 : { // insert element at end
844 :
845 : #if _HAS_ITERATOR_DEBUGGING
846 0 : this->_Orphan_all();
847 : #endif /* _HAS_ITERATOR_DEBUGGING */
848 :
849 : if ((_Myoff + _Mysize) % _DEQUESIZ == 0
850 0 : && _Mapsize <= (_Mysize + _DEQUESIZ) / _DEQUESIZ)
851 0 : _Growmap(1);
852 0 : size_type _Newoff = _Myoff + _Mysize;
853 0 : size_type _Block = _Newoff / _DEQUESIZ;
854 0 : if (_Mapsize <= _Block)
855 0 : _Block -= _Mapsize;
856 0 : if (_Map[_Block] == 0)
857 0 : _Map[_Block] = this->_Alval.allocate(_DEQUESIZ);
858 0 : this->_Alval.construct(_Map[_Block] + _Newoff % _DEQUESIZ, _Val);
859 0 : ++_Mysize;
860 0 : }
861 :
862 : void pop_back()
863 0 : { // erase element at end
864 :
865 : #if _HAS_ITERATOR_DEBUGGING
866 0 : if (empty())
867 0 : _DEBUG_ERROR("deque empty before pop");
868 0 : else
869 : { // something to erase, do it
870 0 : _Orphan_off(_Myoff + _Mysize - 1);
871 :
872 : #else /* _HAS_ITERATOR_DEBUGGING */
873 : if (!empty())
874 : { // something to erase, do it
875 : #endif /* _HAS_ITERATOR_DEBUGGING */
876 :
877 0 : size_type _Newoff = _Mysize + _Myoff - 1;
878 0 : size_type _Block = _Newoff / _DEQUESIZ;
879 0 : if (_Mapsize <= _Block)
880 0 : _Block -= _Mapsize;
881 0 : this->_Alval.destroy(_Map[_Block] + _Newoff % _DEQUESIZ);
882 0 : if (--_Mysize == 0)
883 0 : _Myoff = 0;
884 : }
885 0 : }
886 :
887 : template<class _It>
888 : void assign(_It _First, _It _Last)
889 : { // assign [_First, _Last)
890 : _Assign(_First, _Last, _Iter_cat(_First));
891 : }
892 :
893 : template<class _It>
894 : void _Assign(_It _Count, _It _Val, _Int_iterator_tag)
895 : { // assign _Count * _Val
896 : _Assign_n((size_type)_Count, (_Ty)_Val);
897 : }
898 :
899 : template<class _It>
900 : void _Assign(_It _First, _It _Last, input_iterator_tag)
901 : { // assign [_First, _Last), input iterators
902 : erase(begin(), end());
903 : insert(begin(), _First, _Last);
904 : }
905 :
906 : void assign(size_type _Count, const _Ty& _Val)
907 : { // assign _Count * _Val
908 : _Assign_n(_Count, _Val);
909 : }
910 :
911 : iterator insert(const_iterator _Where, const _Ty& _Val)
912 : { // insert _Val at _Where
913 : if (_Where == begin())
914 : { // insert at front
915 : push_front(_Val);
916 : return (begin());
917 : }
918 : else if (_Where == end())
919 : { // insert at back
920 : push_back(_Val);
921 : return (end() - 1);
922 : }
923 : else
924 : { // insert inside sequence
925 : iterator _Mid;
926 : size_type _Off = _Where - begin();
927 : _Ty _Tmp = _Val; // in case _Val is in sequence
928 :
929 : #if _HAS_ITERATOR_DEBUGGING
930 : if (_Mysize < _Off)
931 : _DEBUG_ERROR("deque insert iterator outside range");
932 : #endif /* _HAS_ITERATOR_DEBUGGING */
933 :
934 : if (_Off < _Mysize / 2)
935 : { // closer to front, push to front then copy
936 : push_front(front());
937 : _Mid = begin() + _Off;
938 : std::copy(begin() + 2, _Mid + 1, begin() + 1);
939 : }
940 : else
941 : { // closer to back, push to back then copy
942 : push_back(back());
943 : _Mid = begin() + _Off;
944 : std::copy_backward(_Mid, end() - 2, end() - 1);
945 : }
946 :
947 : *_Mid = _Tmp; // store inserted value
948 : return (_Make_iter(_Mid));
949 : }
950 : }
951 :
952 : void insert(const_iterator _Where, size_type _Count, const _Ty& _Val)
953 : { // insert _Count * _Val at _Where
954 : _Insert_n(_Where, _Count, _Val);
955 : }
956 :
957 : template<class _It>
958 : void insert(const_iterator _Where, _It _First, _It _Last)
959 : { // insert [_First, _Last) at _Where
960 : _Insert(_Where, _First, _Last, _Iter_cat(_First));
961 : }
962 :
963 : template<class _It>
964 : void _Insert(const_iterator _Where, _It _Count, _It _Val,
965 : _Int_iterator_tag)
966 : { // insert _Count * _Val at _Where
967 : _Insert_n(_Where, (size_type)_Count, (_Ty)_Val);
968 : }
969 :
970 : template<class _It>
971 : void _Insert(const_iterator _Where,
972 : _It _First, _It _Last, input_iterator_tag)
973 : { // insert [_First, _Last) at _Where, input iterators
974 : size_type _Off = _Where - begin();
975 :
976 : #if _HAS_ITERATOR_DEBUGGING
977 : if (_Mysize < _Off)
978 : _DEBUG_ERROR("deque insert iterator outside range");
979 : _DEBUG_RANGE(_First, _Last);
980 : #endif /* _HAS_ITERATOR_DEBUGGING */
981 :
982 : size_type _Rem = _Mysize - _Off;
983 : size_type _Oldsize = _Mysize;
984 :
985 : if (_First == _Last)
986 : ;
987 : else if (_Off < _Rem)
988 : { // closer to front
989 : _TRY_BEGIN
990 : for (; _First != _Last; ++_First)
991 : push_front((value_type)*_First); // prepend flipped
992 :
993 : _CATCH_ALL
994 : for (; _Oldsize < _Mysize; )
995 : pop_front(); // restore old size, at least
996 : _RERAISE;
997 : _CATCH_END
998 :
999 : size_type _Num = _Mysize - _Oldsize;
1000 :
1001 : if (0 < _Off)
1002 : { // insert not at beginning, flip new stuff into place
1003 : _Reverse(_Num, _Num + _Off);
1004 : _Reverse(0, _Num + _Off);
1005 : }
1006 : else
1007 : _Reverse(0, _Num); // flip new stuff in place
1008 : }
1009 : else
1010 : { // closer to back
1011 : _TRY_BEGIN
1012 : for (; _First != _Last; ++_First)
1013 : push_back((value_type)*_First); // append
1014 :
1015 : _CATCH_ALL
1016 : for (; _Oldsize < _Mysize; )
1017 : pop_back(); // restore old size, at least
1018 : _RERAISE;
1019 : _CATCH_END
1020 :
1021 : if (_Off < _Oldsize)
1022 : { // insert not at end, flip new stuff into place
1023 : _Reverse(_Off, _Oldsize);
1024 : _Reverse(_Oldsize, _Mysize);
1025 : _Reverse(_Off, _Mysize);
1026 : }
1027 : }
1028 : }
1029 :
1030 : void _Reverse(size_type _First, size_type _Last)
1031 : { // reverse a subrange
1032 : iterator _Start = begin();
1033 : for (; _First != _Last && _First != --_Last; ++_First)
1034 : _STD _Swap_adl(_Start[_First], _Start[_Last]);
1035 : }
1036 :
1037 : iterator erase(const_iterator _Where)
1038 : { // erase element at _Where
1039 : return (erase(_Where, _Where + 1));
1040 : }
1041 :
1042 : iterator erase(const_iterator _First_arg,
1043 : const_iterator _Last_arg)
1044 : { // erase [_First, _Last)
1045 : iterator _First = _Make_iter(_First_arg);
1046 : iterator _Last = _Make_iter(_Last_arg);
1047 :
1048 : #if _HAS_ITERATOR_DEBUGGING
1049 : if (_Last < _First
1050 : || _First < begin() || end() < _Last)
1051 : _DEBUG_ERROR("deque erase iterator outside range");
1052 : _DEBUG_RANGE(_First, _Last);
1053 :
1054 : size_type _Off = _First - begin();
1055 : size_type _Count = _Last - _First;
1056 : bool _Moved = 0 < _Off && _Off + _Count < _Mysize;
1057 :
1058 : #else /* _HAS_ITERATOR_DEBUGGING */
1059 : size_type _Off = _First - begin();
1060 : size_type _Count = _Last - _First;
1061 : #endif /* _HAS_ITERATOR_DEBUGGING */
1062 :
1063 : if (_Off < (size_type)(end() - _Last))
1064 : { // closer to front
1065 : std::copy_backward(begin(), _First, _Last); // copy over hole
1066 : for (; 0 < _Count; --_Count)
1067 : pop_front(); // pop copied elements
1068 : }
1069 : else
1070 : { // closer to back
1071 : std::copy(_Last, end(), _First); // copy over hole
1072 : for (; 0 < _Count; --_Count)
1073 : pop_back(); // pop copied elements
1074 : }
1075 :
1076 : #if _HAS_ITERATOR_DEBUGGING
1077 : if (_Moved)
1078 : this->_Orphan_all();
1079 : #endif /* _HAS_ITERATOR_DEBUGGING */
1080 :
1081 : return (begin() + _Off);
1082 : }
1083 :
1084 : void clear()
1085 : { // erase all
1086 : _Tidy();
1087 : }
1088 :
1089 : void swap(_Myt& _Right)
1090 : { // exchange contents with _Right
1091 : if (this == &_Right)
1092 : ; // same object, do nothing
1093 : else if (this->_Alval == _Right._Alval)
1094 : { // same allocator, swap control information
1095 :
1096 : #if _HAS_ITERATOR_DEBUGGING
1097 : this->_Swap_all(_Right);
1098 : #endif /* _HAS_ITERATOR_DEBUGGING */
1099 :
1100 : this->_Swap_aux(_Right);
1101 :
1102 : _STD _Swap_adl(_Map, _Right._Map);
1103 : _STD swap(_Mapsize, _Right._Mapsize);
1104 : _STD swap(_Myoff, _Right._Myoff);
1105 : _STD swap(_Mysize, _Right._Mysize);
1106 : }
1107 : else
1108 : { // different allocator, do multiple assigns
1109 : this->_Swap_aux(_Right);
1110 :
1111 : _Myt _Ts = *this;
1112 :
1113 : *this = _Right;
1114 : _Right = _Ts;
1115 : }
1116 : }
1117 :
1118 :
1119 :
1120 : protected:
1121 : void _Assign_n(size_type _Count, const _Ty& _Val)
1122 : { // assign _Count * _Val
1123 : _Ty _Tmp = _Val; // in case _Val is in sequence
1124 : erase(begin(), end());
1125 : _Insert_n(begin(), _Count, _Tmp);
1126 : }
1127 :
1128 : void _Insert_n(const_iterator _Where,
1129 : size_type _Count, const _Ty& _Val)
1130 : { // insert _Count * _Val at _Where
1131 : iterator _Mid;
1132 : size_type _Num;
1133 : size_type _Off = _Where - begin();
1134 : size_type _Rem = _Mysize - _Off;
1135 : size_type _Oldsize = _Mysize;
1136 :
1137 : #if _HAS_ITERATOR_DEBUGGING
1138 : if (_Mysize < _Off)
1139 : _DEBUG_ERROR("deque insert iterator outside range");
1140 : #endif /* _HAS_ITERATOR_DEBUGGING */
1141 :
1142 : if (_Off < _Rem)
1143 : { // closer to front
1144 : _TRY_BEGIN
1145 : if (_Off < _Count)
1146 : { // insert longer than prefix
1147 : for (_Num = _Count - _Off; 0 < _Num; --_Num)
1148 : push_front(_Val); // push excess values
1149 : for (_Num = _Off; 0 < _Num; --_Num)
1150 : push_front(begin()[_Count - 1]); // push prefix
1151 :
1152 : _Mid = begin() + _Count;
1153 : std::fill(_Mid, _Mid + _Off,
1154 : _Val); // fill in rest of values
1155 : }
1156 : else
1157 : { // insert not longer than prefix
1158 : for (_Num = _Count; 0 < _Num; --_Num)
1159 : push_front(begin()[_Count - 1]); // push part of prefix
1160 :
1161 : _Mid = begin() + _Count;
1162 : _Ty _Tmp = _Val; // in case _Val is in sequence
1163 : std::copy(_Mid + _Count, _Mid + _Off,
1164 : _Mid); // copy rest of prefix
1165 : std::fill(begin() + _Off, _Mid + _Off,
1166 : _Tmp); // fill in values
1167 : }
1168 : _CATCH_ALL
1169 : for (; _Oldsize < _Mysize; )
1170 : pop_front(); // restore old size, at least
1171 : _RERAISE;
1172 : _CATCH_END
1173 : }
1174 : else
1175 : { // closer to back
1176 : _TRY_BEGIN
1177 : if (_Rem < _Count)
1178 : { // insert longer than suffix
1179 : for (_Num = _Count - _Rem; 0 < _Num; --_Num)
1180 : push_back(_Val); // push excess values
1181 : for (_Num = 0; _Num < _Rem; ++_Num)
1182 : push_back(begin()[_Off + _Num]); // push suffix
1183 :
1184 : _Mid = begin() + _Off;
1185 : std::fill(_Mid, _Mid + _Rem,
1186 : _Val); // fill in rest of values
1187 : }
1188 : else
1189 : { // insert not longer than prefix
1190 : for (_Num = 0; _Num < _Count; ++_Num)
1191 : push_back(begin()[_Off + _Rem
1192 : - _Count + _Num]); // push part of prefix
1193 :
1194 : _Mid = begin() + _Off;
1195 : _Ty _Tmp = _Val; // in case _Val is in sequence
1196 : std::copy_backward(_Mid, _Mid + _Rem - _Count,
1197 : _Mid + _Rem); // copy rest of prefix
1198 : std::fill(_Mid, _Mid + _Count,
1199 : _Tmp); // fill in values
1200 : }
1201 : _CATCH_ALL
1202 : for (; _Oldsize < _Mysize; )
1203 : pop_back(); // restore old size, at least
1204 : _RERAISE;
1205 : _CATCH_END
1206 : }
1207 : }
1208 :
1209 : static void _Xlen()
1210 0 : { // report length error
1211 0 : _THROW(length_error, "deque<T> too long");
1212 0 : }
1213 :
1214 : static void _Xinvarg()
1215 : { // report an invalid_argument error
1216 : _THROW(invalid_argument, "invalid deque <T> argument");
1217 : }
1218 :
1219 : static void _Xran()
1220 : { // report an out_of_range error
1221 : _THROW(out_of_range, "invalid deque <T> subscript");
1222 : }
1223 :
1224 : void _Growmap(size_type _Count)
1225 0 : { // grow map by _Count pointers
1226 0 : if (max_size() / _DEQUESIZ - _Mapsize < _Count)
1227 0 : _Xlen(); // result too long
1228 :
1229 0 : size_type _Inc = _Mapsize / 2; // try to grow by 50%
1230 0 : if (_Inc < _DEQUEMAPSIZ)
1231 0 : _Inc = _DEQUEMAPSIZ;
1232 0 : if (_Count < _Inc && _Mapsize <= max_size() / _DEQUESIZ - _Inc)
1233 0 : _Count = _Inc;
1234 0 : size_type _Myboff = _Myoff / _DEQUESIZ;
1235 0 : _Mapptr _Newmap = this->_Almap.allocate(_Mapsize + _Count);
1236 0 : _Mapptr _Myptr = _Newmap + _Myboff;
1237 :
1238 : _Myptr = _STDEXT unchecked_uninitialized_copy(_Map + _Myboff,
1239 0 : _Map + _Mapsize, _Myptr, this->_Almap); // copy initial to end
1240 0 : if (_Myboff <= _Count)
1241 : { // increment greater than offset of initial block
1242 : _Myptr = _STDEXT unchecked_uninitialized_copy(_Map,
1243 0 : _Map + _Myboff, _Myptr, this->_Almap); // copy rest of old
1244 : _STDEXT unchecked_uninitialized_fill_n(_Myptr, _Count - _Myboff,
1245 0 : (_Tptr)0, this->_Almap); // clear suffix of new
1246 : _STDEXT unchecked_uninitialized_fill_n(_Newmap, _Myboff,
1247 0 : (_Tptr)0, this->_Almap); // clear prefix of new
1248 : }
1249 0 : else
1250 : { // increment not greater than offset of initial block
1251 : _STDEXT unchecked_uninitialized_copy(_Map,
1252 0 : _Map + _Count, _Myptr, this->_Almap); // copy more old
1253 : _Myptr = _STDEXT unchecked_uninitialized_copy(_Map + _Count,
1254 0 : _Map + _Myboff, _Newmap, this->_Almap); // copy rest of old
1255 : _STDEXT unchecked_uninitialized_fill_n(_Myptr, _Count,
1256 0 : (_Tptr)0, this->_Almap); // clear rest to initial block
1257 : }
1258 :
1259 0 : _Destroy_range(_Map + _Myboff, _Map + _Mapsize, this->_Almap);
1260 0 : if (_Map)
1261 0 : this->_Almap.deallocate(_Map, _Mapsize); // free storage for old
1262 :
1263 0 : _Map = _Newmap; // point at new
1264 0 : _Mapsize += _Count;
1265 0 : }
1266 :
1267 : void _Tidy()
1268 0 : { // free all storage
1269 0 : while (!empty())
1270 0 : pop_back();
1271 0 : for (size_type _Count = _Mapsize; 0 < _Count; )
1272 : { // free storage for a block and destroy pointer
1273 0 : if (*(_Map + --_Count) != 0)
1274 0 : this->_Alval.deallocate(*(_Map + _Count), _DEQUESIZ);
1275 0 : this->_Almap.destroy(_Map + _Count);
1276 0 : }
1277 :
1278 0 : if (_Map)
1279 0 : this->_Almap.deallocate(_Map, _Mapsize); // free storage for map
1280 0 : _Mapsize = 0;
1281 0 : _Map = 0;
1282 0 : }
1283 :
1284 : #if _HAS_ITERATOR_DEBUGGING
1285 : void _Orphan_off(size_type _Offlo) const
1286 0 : { // orphan iterators with specified offset(s)
1287 0 : if (_Mysize == 0)
1288 0 : _DEBUG_ERROR("deque empty before pop");
1289 : size_type _Offhigh = _Myoff + _Mysize <= _Offlo + 1
1290 0 : ? (size_type)(-1) : _Offlo;
1291 0 : if (_Offlo == _Myoff)
1292 0 : _Offlo = 0;
1293 :
1294 0 : _Lockit _Lock(_LOCK_DEBUG);
1295 0 : const_iterator **_Pnext = (const_iterator **)&this->_Myfirstiter;
1296 0 : while (*_Pnext != 0)
1297 0 : if ((*_Pnext)->_Myoff < _Offlo || _Offhigh < (*_Pnext)->_Myoff)
1298 0 : _Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter;
1299 0 : else
1300 : { // orphan the iterator
1301 0 : (*_Pnext)->_Mycont = 0;
1302 0 : *_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter;
1303 0 : }
1304 0 : }
1305 : #endif /* _HAS_ITERATOR_DEBUGGING */
1306 :
1307 : _Mapptr _Map; // pointer to array of pointers to blocks
1308 : size_type _Mapsize; // size of map array
1309 : size_type _Myoff; // offset of initial element
1310 : size_type _Mysize; // current length of sequence
1311 : };
1312 :
1313 : // deque implements a performant swap
1314 : template <class _Ty, class _Ax>
1315 : class _Move_operation_category<deque<_Ty, _Ax> >
1316 : {
1317 : public:
1318 : typedef _Swap_move_tag _Move_cat;
1319 : };
1320 :
1321 : // deque TEMPLATE OPERATORS
1322 :
1323 : template<class _Ty,
1324 : class _Alloc> inline
1325 : void swap(deque<_Ty, _Alloc>& _Left, deque<_Ty, _Alloc>& _Right)
1326 : { // swap _Left and _Right deques
1327 : _Left.swap(_Right);
1328 : }
1329 :
1330 : template<class _Ty,
1331 : class _Alloc> inline
1332 : bool operator==(const deque<_Ty, _Alloc>& _Left,
1333 : const deque<_Ty, _Alloc>& _Right)
1334 : { // test for deque equality
1335 : return (_Left.size() == _Right.size()
1336 : && equal(_Left.begin(), _Left.end(), _Right.begin()));
1337 : }
1338 :
1339 : template<class _Ty,
1340 : class _Alloc> inline
1341 : bool operator!=(const deque<_Ty, _Alloc>& _Left,
1342 : const deque<_Ty, _Alloc>& _Right)
1343 : { // test for deque inequality
1344 : return (!(_Left == _Right));
1345 : }
1346 :
1347 : template<class _Ty,
1348 : class _Alloc> inline
1349 : bool operator<(const deque<_Ty, _Alloc>& _Left,
1350 : const deque<_Ty, _Alloc>& _Right)
1351 : { // test if _Left < _Right for deques
1352 : return (lexicographical_compare(_Left.begin(), _Left.end(),
1353 : _Right.begin(), _Right.end()));
1354 : }
1355 :
1356 : template<class _Ty,
1357 : class _Alloc> inline
1358 : bool operator<=(const deque<_Ty, _Alloc>& _Left,
1359 : const deque<_Ty, _Alloc>& _Right)
1360 : { // test if _Left <= _Right for deques
1361 : return (!(_Right < _Left));
1362 : }
1363 :
1364 : template<class _Ty,
1365 : class _Alloc> inline
1366 : bool operator>(const deque<_Ty, _Alloc>& _Left,
1367 : const deque<_Ty, _Alloc>& _Right)
1368 : { // test if _Left > _Right for deques
1369 : return (_Right < _Left);
1370 : }
1371 :
1372 : template<class _Ty,
1373 : class _Alloc> inline
1374 : bool operator>=(const deque<_Ty, _Alloc>& _Left,
1375 : const deque<_Ty, _Alloc>& _Right)
1376 : { // test if _Left >= _Right for deques
1377 : return (!(_Left < _Right));
1378 : }
1379 : _STD_END
1380 :
1381 : #pragma warning(default:4284)
1382 :
1383 : #if _HAS_TRADITIONAL_STL
1384 : #define __deque__ deque
1385 : #endif /* _HAS_TRADITIONAL_STL */
1386 :
1387 : #ifdef _MSC_VER
1388 : #pragma warning(pop)
1389 : #pragma pack(pop)
1390 : #endif /* _MSC_VER */
1391 :
1392 : #endif /* RC_INVOKED */
1393 : #endif /* _DEQUE_ */
1394 :
1395 : /*
1396 : * This file is derived from software bearing the following
1397 : * restrictions:
1398 : *
1399 : * Copyright (c) 1994
1400 : * Hewlett-Packard Company
1401 : *
1402 : * Permission to use, copy, modify, distribute and sell this
1403 : * software and its documentation for any purpose is hereby
1404 : * granted without fee, provided that the above copyright notice
1405 : * appear in all copies and that both that copyright notice and
1406 : * this permission notice appear in supporting documentation.
1407 : * Hewlett-Packard Company makes no representations about the
1408 : * suitability of this software for any purpose. It is provided
1409 : * "as is" without express or implied warranty.
1410 : */
1411 :
1412 : /*
1413 : * Copyright (c) 1992-2007 by P.J. Plauger. ALL RIGHTS RESERVED.
1414 : * Consult your license regarding permissions and restrictions.
1415 : V5.03:0009 */
1416 :
1417 :
|
