|
|
|
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) |
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 |
|
|
|
|
|