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		{    // construct with copy of _Right
89		this->_Adopt(_Right._Mycont);
90		}
91
92		_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		((_Mydeque *)_Pdeque)->_Myoff <= _Off && _Off <= (((_Mydeque *)_Pdeque)->_Myoff + ((_Mydeque *)_Pdeque)->_Mysize));
97
98		this->_Adopt(_Pdeque);
99		_Myoff = _Off;
100		}
101
102		reference operator*() const
103		{    // return designated object
104		size_type _Block = _Myoff / _DEQUESIZ;
105		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		+ ((_Mydeque *)this->_Mycont)->_Mysize <= _Myoff)
110		{
111		_DEBUG_ERROR("deque iterator not dereferencable");
112		_SCL_SECURE_TRAITS_OUT_OF_RANGE;
113		}
114		if (((_Mydeque *)this->_Mycont)->_Mapsize <= _Block)
115		_Block -= ((_Mydeque *)this->_Mycont)->_Mapsize;
116		return ((((_Mydeque *)this->_Mycont)->_Map)[_Block][_Off]);
117		}
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		{    // increment by integer
199		_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		_Myoff + _Off >= ((_Mydeque *)(this->_Getmycont()))->_Myoff);
203		_Myoff += _Off;
204		return (*this);
205		}
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		{    // construct with offset _Off in *_Pdeque
382		}
383
384		reference operator*() const
385		{    // return designated object
386		return ((reference)**(_Mybase *)this);
387		}
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		{    // increment by integer
422		*(_Mybase *)this += _Off;
423		return (*this);
424		}
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		{    // decrement by integer
434		return (*this += -_Off);
435		}
436
437		_Myt operator-(difference_type _Off) const
438		{    // return this - integer
439		_Myt _Tmp = *this;
440		return (_Tmp -= _Off);
441		}
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		{    // construct allocator from _Al
479		}
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		{    // construct allocator and base from _Al
501		}
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		{    // construct empty deque
555		}
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		{    // destroy the deque
641		_Tidy();
642		}
643
644		_Myt& operator=(const _Myt& _Right)
645		{    // assign _Right
646		if (this == &_Right)

Lines 647 ... 656 are skipped.

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		{    // return iterator for end of mutable sequence
676		return (iterator(_Myoff + _Mysize, this));
677		}
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		{    // return length of sequence
724		return (_Mysize);
725		}
726
727		size_type max_size() const
728		{    // return maximum possible length of sequence
729		return (this->_Alval.max_size());
730		}
731
732		bool empty() const
733		{    // test if sequence is empty
734		return (_Mysize == 0);
735		}
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		{    // return last element of mutable sequence
790		return (*(end() - 1));
791		}
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		{    // insert element at end
844
845		#if _HAS_ITERATOR_DEBUGGING
846		this->_Orphan_all();
847		#endif /* _HAS_ITERATOR_DEBUGGING */
848
849		if ((_Myoff + _Mysize) % _DEQUESIZ == 0
850		&& _Mapsize <= (_Mysize + _DEQUESIZ) / _DEQUESIZ)
851		_Growmap(1);
852		size_type _Newoff = _Myoff + _Mysize;
853		size_type _Block = _Newoff / _DEQUESIZ;
854		if (_Mapsize <= _Block)
855		_Block -= _Mapsize;
856		if (_Map[_Block] == 0)
857		_Map[_Block] = this->_Alval.allocate(_DEQUESIZ);
858		this->_Alval.construct(_Map[_Block] + _Newoff % _DEQUESIZ, _Val);
859		++_Mysize;
860		}
861
862		void pop_back()
863		{    // erase element at end
864
865		#if _HAS_ITERATOR_DEBUGGING
866		if (empty())
867		_DEBUG_ERROR("deque empty before pop");
868		else
869		{    // something to erase, do it
870		_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		size_type _Newoff = _Mysize + _Myoff - 1;
878		size_type _Block = _Newoff / _DEQUESIZ;
879		if (_Mapsize <= _Block)
880		_Block -= _Mapsize;
881		this->_Alval.destroy(_Map[_Block] + _Newoff % _DEQUESIZ);
882		if (--_Mysize == 0)
883		_Myoff = 0;
884		}
885		}
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		{    // report length error
1211		_THROW(length_error, "deque<T> too long");
1212		}
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		{    // grow map by _Count pointers
1226		if (max_size() / _DEQUESIZ - _Mapsize < _Count)
1227		_Xlen();    // result too long
1228
1229		size_type _Inc = _Mapsize / 2;    // try to grow by 50%
1230		if (_Inc < _DEQUEMAPSIZ)
1231		_Inc = _DEQUEMAPSIZ;
1232		if (_Count < _Inc && _Mapsize <= max_size() / _DEQUESIZ - _Inc)
1233		_Count = _Inc;
1234		size_type _Myboff = _Myoff / _DEQUESIZ;
1235		_Mapptr _Newmap = this->_Almap.allocate(_Mapsize + _Count);
1236		_Mapptr _Myptr = _Newmap + _Myboff;
1237
1238		_Myptr = _STDEXT unchecked_uninitialized_copy(_Map + _Myboff,
1239		_Map + _Mapsize, _Myptr, this->_Almap);    // copy initial to end
1240		if (_Myboff <= _Count)
1241		{    // increment greater than offset of initial block
1242		_Myptr = _STDEXT unchecked_uninitialized_copy(_Map,
1243		_Map + _Myboff, _Myptr, this->_Almap);    // copy rest of old
1244		_STDEXT unchecked_uninitialized_fill_n(_Myptr, _Count - _Myboff,
1245		(_Tptr)0, this->_Almap);    // clear suffix of new
1246		_STDEXT unchecked_uninitialized_fill_n(_Newmap, _Myboff,
1247		(_Tptr)0, this->_Almap);    // clear prefix of new
1248		}
1249		else
1250		{    // increment not greater than offset of initial block
1251		_STDEXT unchecked_uninitialized_copy(_Map,
1252		_Map + _Count, _Myptr, this->_Almap);    // copy more old
1253		_Myptr = _STDEXT unchecked_uninitialized_copy(_Map + _Count,
1254		_Map + _Myboff, _Newmap, this->_Almap);    // copy rest of old
1255		_STDEXT unchecked_uninitialized_fill_n(_Myptr, _Count,
1256		(_Tptr)0, this->_Almap);    // clear rest to initial block
1257		}
1258
1259		_Destroy_range(_Map + _Myboff, _Map + _Mapsize, this->_Almap);
1260		if (_Map)
1261		this->_Almap.deallocate(_Map, _Mapsize);    // free storage for old
1262
1263		_Map = _Newmap;    // point at new
1264		_Mapsize += _Count;
1265		}
1266
1267		void _Tidy()
1268		{    // free all storage
1269		while (!empty())
1270		pop_back();
1271		for (size_type _Count = _Mapsize; 0 < _Count; )
1272		{    // free storage for a block and destroy pointer
1273		if (*(_Map + --_Count) != 0)
1274		this->_Alval.deallocate(*(_Map + _Count), _DEQUESIZ);
1275		this->_Almap.destroy(_Map + _Count);
1276		}
1277
1278		if (_Map)
1279		this->_Almap.deallocate(_Map, _Mapsize);    // free storage for map
1280		_Mapsize = 0;
1281		_Map = 0;
1282		}
1283
1284		#if _HAS_ITERATOR_DEBUGGING
1285		void _Orphan_off(size_type _Offlo) const
1286		{    // orphan iterators with specified offset(s)
1287		if (_Mysize == 0)
1288		_DEBUG_ERROR("deque empty before pop");
1289		size_type _Offhigh = _Myoff + _Mysize <= _Offlo + 1
1290		? (size_type)(-1) : _Offlo;
1291		if (_Offlo == _Myoff)
1292		_Offlo = 0;
1293
1294		_Lockit _Lock(_LOCK_DEBUG);
1295		const_iterator **_Pnext = (const_iterator **)&this->_Myfirstiter;
1296		while (*_Pnext != 0)
1297		if ((*_Pnext)->_Myoff < _Offlo || _Offhigh < (*_Pnext)->_Myoff)
1298		_Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter;
1299		else
1300		{    // orphan the iterator
1301		(*_Pnext)->_Mycont = 0;
1302		*_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter;
1303		}
1304		}
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
1418