1 /*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
13 *
14 *
15 * Copyright (c) 1997
16 * Silicon Graphics Computer Systems, Inc.
17 *
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
25 */
26
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
29 */
30
31 #ifndef __SGI_STL_INTERNAL_DEQUE_H
32 #define __SGI_STL_INTERNAL_DEQUE_H
33
34 /* Class invariants:
35 * For any nonsingular iterator i:
36 * i.node is the address of an element in the map array. The
37 * contents of i.node is a pointer to the beginning of a node.
38 * i.first == *(i.node)
39 * i.last == i.first + node_size
40 * i.cur is a pointer in the range [i.first, i.last). NOTE:
41 * the implication of this is that i.cur is always a dereferenceable
42 * pointer, even if i is a past-the-end iterator.
43 * Start and Finish are always nonsingular iterators. NOTE: this means
44 * that an empty deque must have one node, and that a deque
45 * with N elements, where N is the buffer size, must have two nodes.
46 * For every node other than start.node and finish.node, every element
47 * in the node is an initialized object. If start.node == finish.node,
48 * then [start.cur, finish.cur) are initialized objects, and
49 * the elements outside that range are uninitialized storage. Otherwise,
50 * [start.cur, start.last) and [finish.first, finish.cur) are initialized
51 * objects, and [start.first, start.cur) and [finish.cur, finish.last)
52 * are uninitialized storage.
53 * [map, map + map_size) is a valid, non-empty range.
54 * [start.node, finish.node] is a valid range contained within
55 * [map, map + map_size).
56 * A pointer in the range [map, map + map_size) points to an allocated node
57 * if and only if the pointer is in the range [start.node, finish.node].
58 */
59
60
61 /*
62 * In previous versions of deque, node_size was fixed by the
63 * implementation. In this version, however, users can select
64 * the node size. Deque has three template parameters; the third,
65 * a number of type size_t, is the number of elements per node.
66 * If the third template parameter is 0 (which is the default),
67 * then deque will use a default node size.
68 *
69 * The only reason for using an alternate node size is if your application
70 * requires a different performance tradeoff than the default. If,
71 * for example, your program contains many deques each of which contains
72 * only a few elements, then you might want to save memory (possibly
73 * by sacrificing some speed) by using smaller nodes.
74 *
75 * Unfortunately, some compilers have trouble with non-type template
76 * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if
77 * that is the case. If your compiler is one of them, then you will
78 * not be able to use alternate node sizes; you will have to use the
79 * default value.
80 */
81
82 __STL_BEGIN_NAMESPACE
83
84 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
85 #pragma set woff 1174
86 #pragma set woff 1375
87 #endif
88
89 // Note: this function is simply a kludge to work around several compilers'
90 // bugs in handling constant expressions.
91 inline size_t
__deque_buf_size(size_t __n,size_t __size)92 __deque_buf_size(size_t __n, size_t __size)
93 {
94 return __n != 0 ? __n : (__size < 512 ? size_t(512 / __size) : size_t(1));
95 }
96
97 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
98 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
99 struct _Deque_iterator {
100 typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator;
101 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*,__bufsiz> const_iterator;
102 static size_t
_S_buffer_size_Deque_iterator103 _S_buffer_size() { return __deque_buf_size(__bufsiz, sizeof(_Tp)); }
104 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
105 template <class _Tp, class _Ref, class _Ptr>
106 struct _Deque_iterator {
107 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
108 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
109 static size_t
110 _S_buffer_size() { return __deque_buf_size(0, sizeof(_Tp)); }
111 #endif
112
113 typedef random_access_iterator_tag iterator_category;
114 typedef _Tp value_type;
115 typedef _Ptr pointer;
116 typedef _Ref reference;
117 typedef size_t size_type;
118 typedef ptrdiff_t difference_type;
119 typedef _Tp** _Map_pointer;
120
121 typedef _Deque_iterator _Self;
122
123 _Tp* _M_cur;
124 _Tp* _M_first;
125 _Tp* _M_last;
126 _Map_pointer _M_node;
127
_Deque_iterator_Deque_iterator128 _Deque_iterator(_Tp* __x, _Map_pointer __y)
129 : _M_cur(__x), _M_first(*__y),
130 _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
_Deque_iterator_Deque_iterator131 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
_Deque_iterator_Deque_iterator132 _Deque_iterator(const iterator& __x)
133 : _M_cur(__x._M_cur), _M_first(__x._M_first),
134 _M_last(__x._M_last), _M_node(__x._M_node) {}
135
136 reference operator*() const { return *_M_cur; }
137 #ifndef __SGI_STL_NO_ARROW_OPERATOR
138 pointer operator->() const { return _M_cur; }
139 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
140
141 difference_type operator-(const _Self& __x) const {
142 return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
143 (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
144 }
145
146 _Self& operator++() {
147 ++_M_cur;
148 if (_M_cur == _M_last) {
149 _M_set_node(_M_node + 1);
150 _M_cur = _M_first;
151 }
152 return *this;
153 }
154 _Self operator++(int) {
155 _Self __tmp = *this;
156 ++*this;
157 return __tmp;
158 }
159
160 _Self& operator--() {
161 if (_M_cur == _M_first) {
162 _M_set_node(_M_node - 1);
163 _M_cur = _M_last;
164 }
165 --_M_cur;
166 return *this;
167 }
168 _Self operator--(int) {
169 _Self __tmp = *this;
170 --*this;
171 return __tmp;
172 }
173
174 _Self& operator+=(difference_type __n)
175 {
176 difference_type __offset = __n + (_M_cur - _M_first);
177 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
178 _M_cur += __n;
179 else {
180 difference_type __node_offset =
181 __offset > 0 ? __offset / difference_type(_S_buffer_size())
182 : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
183 _M_set_node(_M_node + __node_offset);
184 _M_cur = _M_first +
185 (__offset - __node_offset * difference_type(_S_buffer_size()));
186 }
187 return *this;
188 }
189
190 _Self operator+(difference_type __n) const
191 {
192 _Self __tmp = *this;
193 return __tmp += __n;
194 }
195
196 _Self& operator-=(difference_type __n) { return *this += -__n; }
197
198 _Self operator-(difference_type __n) const {
199 _Self __tmp = *this;
200 return __tmp -= __n;
201 }
202
203 reference operator[](difference_type __n) const { return *(*this + __n); }
204
205 bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
206 bool operator!=(const _Self& __x) const { return !(*this == __x); }
207 bool operator<(const _Self& __x) const {
208 return (_M_node == __x._M_node) ?
209 (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
210 }
211
_M_set_node_Deque_iterator212 void _M_set_node(_Map_pointer __new_node) {
213 _M_node = __new_node;
214 _M_first = *__new_node;
215 _M_last = _M_first + difference_type(_S_buffer_size());
216 }
217 };
218
219 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
220
221 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
222
223 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
224 inline random_access_iterator_tag
iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz> &)225 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
226 return random_access_iterator_tag();
227 }
228
229 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
230 inline _Tp*
value_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz> &)231 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
232 return 0;
233 }
234
235 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
236 inline ptrdiff_t*
distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz> &)237 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
238 return 0;
239 }
240
241 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
242
243 template <class _Tp, class _Ref, class _Ptr>
244 inline random_access_iterator_tag
iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr> &)245 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&)
246 {
247 return random_access_iterator_tag();
248 }
249
250 template <class _Tp, class _Ref, class _Ptr>
251 inline _Tp*
value_type(const _Deque_iterator<_Tp,_Ref,_Ptr> &)252 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; }
253
254 template <class _Tp, class _Ref, class _Ptr>
255 inline ptrdiff_t*
distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr> &)256 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) {
257 return 0;
258 }
259
260 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
261
262 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
263
264 // Deque base class. It has two purposes. First, its constructor
265 // and destructor allocate (but don't initialize) storage. This makes
266 // exception safety easier. Second, the base class encapsulates all of
267 // the differences between SGI-style allocators and standard-conforming
268 // allocators.
269
270 #ifdef __STL_USE_STD_ALLOCATORS
271
272 // Base class for ordinary allocators.
273 template <class _Tp, class _Alloc, size_t __bufsiz, bool __is_static>
274 class _Deque_alloc_base {
275 public:
276 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
get_allocator()277 allocator_type get_allocator() const { return node_allocator; }
278
_Deque_alloc_base(const allocator_type & __a)279 _Deque_alloc_base(const allocator_type& __a)
280 : node_allocator(__a), map_allocator(__a), _M_map(0), _M_map_size(0)
281 {}
282
283 protected:
284 typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
285 map_allocator_type;
286
287 allocator_type node_allocator;
288 map_allocator_type map_allocator;
289
_M_allocate_node()290 _Tp* _M_allocate_node() {
291 return node_allocator.allocate(__deque_buf_size(__bufsiz,sizeof(_Tp)));
292 }
_M_deallocate_node(_Tp * __p)293 void _M_deallocate_node(_Tp* __p) {
294 node_allocator.deallocate(__p, __deque_buf_size(__bufsiz,sizeof(_Tp)));
295 }
_M_allocate_map(size_t __n)296 _Tp** _M_allocate_map(size_t __n)
297 { return map_allocator.allocate(__n); }
_M_deallocate_map(_Tp ** __p,size_t __n)298 void _M_deallocate_map(_Tp** __p, size_t __n)
299 { map_allocator.deallocate(__p, __n); }
300
301 _Tp** _M_map;
302 size_t _M_map_size;
303 };
304
305 // Specialization for instanceless allocators.
306 template <class _Tp, class _Alloc, size_t __bufsiz>
307 class _Deque_alloc_base<_Tp, _Alloc, __bufsiz, true>
308 {
309 public:
310 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
get_allocator()311 allocator_type get_allocator() const { return allocator_type(); }
312
_Deque_alloc_base(const allocator_type &)313 _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
314
315 protected:
316 typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
317 typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
318
_M_allocate_node()319 _Tp* _M_allocate_node()
320 { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz,
321 sizeof(_Tp))); }
_M_deallocate_node(_Tp * __p)322 void _M_deallocate_node(_Tp* __p)
323 { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz,
324 sizeof(_Tp))); }
_M_allocate_map(size_t __n)325 _Tp** _M_allocate_map(size_t __n)
326 { return _Map_alloc_type::allocate(__n); }
_M_deallocate_map(_Tp ** __p,size_t __n)327 void _M_deallocate_map(_Tp** __p, size_t __n)
328 { _Map_alloc_type::deallocate(__p, __n); }
329
330 _Tp** _M_map;
331 size_t _M_map_size;
332 };
333
334 template <class _Tp, class _Alloc, size_t __bufsiz>
335 class _Deque_base
336 : public _Deque_alloc_base<_Tp,_Alloc,__bufsiz,
337 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
338 {
339 public:
340 typedef _Deque_alloc_base<_Tp,_Alloc,__bufsiz,
341 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
342 _Base;
343 typedef typename _Base::allocator_type allocator_type;
344 typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator;
345 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator;
346
_Deque_base(const allocator_type & __a,size_t __num_elements)347 _Deque_base(const allocator_type& __a, size_t __num_elements)
348 : _Base(__a), _M_start(), _M_finish()
349 { _M_initialize_map(__num_elements); }
_Deque_base(const allocator_type & __a)350 _Deque_base(const allocator_type& __a)
351 : _Base(__a), _M_start(), _M_finish() {}
352 ~_Deque_base();
353
354 protected:
355 void _M_initialize_map(size_t);
356 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
357 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
358 enum { _S_initial_map_size = 8 };
359
360 protected:
361 iterator _M_start;
362 iterator _M_finish;
363 };
364
365 #else /* __STL_USE_STD_ALLOCATORS */
366
367 template <class _Tp, class _Alloc, size_t __bufsiz>
368 class _Deque_base {
369 public:
370 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
371 typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator;
372 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator;
373 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
374 typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
375 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
376 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
377
378 typedef _Alloc allocator_type;
get_allocator()379 allocator_type get_allocator() const { return allocator_type(); }
380
_Deque_base(const allocator_type &,size_t __num_elements)381 _Deque_base(const allocator_type&, size_t __num_elements)
382 : _M_map(0), _M_map_size(0), _M_start(), _M_finish() {
383 _M_initialize_map(__num_elements);
384 }
_Deque_base(const allocator_type &)385 _Deque_base(const allocator_type&)
386 : _M_map(0), _M_map_size(0), _M_start(), _M_finish() {}
387 ~_Deque_base();
388
389 protected:
390 void _M_initialize_map(size_t);
391 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
392 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
393 enum { _S_initial_map_size = 8 };
394
395 protected:
396 _Tp** _M_map;
397 size_t _M_map_size;
398 iterator _M_start;
399 iterator _M_finish;
400
401 typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type;
402 typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
403
_M_allocate_node()404 _Tp* _M_allocate_node()
405 { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz,
406 sizeof(_Tp))); }
_M_deallocate_node(_Tp * __p)407 void _M_deallocate_node(_Tp* __p)
408 { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz,
409 sizeof(_Tp))); }
_M_allocate_map(size_t __n)410 _Tp** _M_allocate_map(size_t __n)
411 { return _Map_alloc_type::allocate(__n); }
_M_deallocate_map(_Tp ** __p,size_t __n)412 void _M_deallocate_map(_Tp** __p, size_t __n)
413 { _Map_alloc_type::deallocate(__p, __n); }
414 };
415
416 #endif /* __STL_USE_STD_ALLOCATORS */
417
418 // Non-inline member functions from _Deque_base.
419
420 template <class _Tp, class _Alloc, size_t __bufsiz>
~_Deque_base()421 _Deque_base<_Tp,_Alloc,__bufsiz>::~_Deque_base() {
422 if (_M_map) {
423 _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
424 _M_deallocate_map(_M_map, _M_map_size);
425 }
426 }
427
428 template <class _Tp, class _Alloc, size_t __bufsiz>
429 void
_M_initialize_map(size_t __num_elements)430 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_initialize_map(size_t __num_elements)
431 {
432 size_t __num_nodes =
433 __num_elements / __deque_buf_size(__bufsiz, sizeof(_Tp)) + 1;
434
435 _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
436 _M_map = _M_allocate_map(_M_map_size);
437
438 _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
439 _Tp** __nfinish = __nstart + __num_nodes;
440
441 __STL_TRY {
442 _M_create_nodes(__nstart, __nfinish);
443 }
444 __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
445 _M_map = 0, _M_map_size = 0));
446 _M_start._M_set_node(__nstart);
447 _M_finish._M_set_node(__nfinish - 1);
448 _M_start._M_cur = _M_start._M_first;
449 _M_finish._M_cur = _M_finish._M_first +
450 __num_elements % __deque_buf_size(__bufsiz, sizeof(_Tp));
451 }
452
453 template <class _Tp, class _Alloc, size_t __bufsiz>
454 void
_M_create_nodes(_Tp ** __nstart,_Tp ** __nfinish)455 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_create_nodes(_Tp** __nstart,
456 _Tp** __nfinish)
457 {
458 _Tp** __cur;
459 __STL_TRY {
460 for (__cur = __nstart; __cur < __nfinish; ++__cur)
461 *__cur = _M_allocate_node();
462 }
463 __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
464 }
465
466 template <class _Tp, class _Alloc, size_t __bufsiz>
467 void
_M_destroy_nodes(_Tp ** __nstart,_Tp ** __nfinish)468 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_destroy_nodes(_Tp** __nstart,
469 _Tp** __nfinish)
470 {
471 for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
472 _M_deallocate_node(*__n);
473 }
474
475 // See __deque_buf_size(). The only reason that the default value is 0
476 // is as a workaround for bugs in the way that some compilers handle
477 // constant expressions.
478 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp),
479 size_t __bufsiz = 0>
480 class deque : protected _Deque_base<_Tp, _Alloc, __bufsiz> {
481 typedef _Deque_base<_Tp, _Alloc, __bufsiz> _Base;
482 public: // Basic types
483 typedef _Tp value_type;
484 typedef value_type* pointer;
485 typedef const value_type* const_pointer;
486 typedef value_type& reference;
487 typedef const value_type& const_reference;
488 typedef size_t size_type;
489 typedef ptrdiff_t difference_type;
490
491 typedef typename _Base::allocator_type allocator_type;
get_allocator()492 allocator_type get_allocator() const { return _Base::get_allocator(); }
493
494 public: // Iterators
495 typedef typename _Base::iterator iterator;
496 typedef typename _Base::const_iterator const_iterator;
497
498 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
499 typedef reverse_iterator<const_iterator> const_reverse_iterator;
500 typedef reverse_iterator<iterator> reverse_iterator;
501 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
502 typedef reverse_iterator<const_iterator, value_type, const_reference,
503 difference_type>
504 const_reverse_iterator;
505 typedef reverse_iterator<iterator, value_type, reference, difference_type>
506 reverse_iterator;
507 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
508
509 protected: // Internal typedefs
510 typedef pointer* _Map_pointer;
_S_buffer_size()511 static size_t _S_buffer_size()
512 { return __deque_buf_size(__bufsiz, sizeof(_Tp)); }
513
514 protected:
515 #ifdef __STL_USE_NAMESPACES
516 using _Base::_M_initialize_map;
517 using _Base::_M_create_nodes;
518 using _Base::_M_destroy_nodes;
519 using _Base::_M_allocate_node;
520 using _Base::_M_deallocate_node;
521 using _Base::_M_allocate_map;
522 using _Base::_M_deallocate_map;
523
524 using _Base::_M_map;
525 using _Base::_M_map_size;
526 using _Base::_M_start;
527 using _Base::_M_finish;
528 #endif /* __STL_USE_NAMESPACES */
529
530 public: // Basic accessors
begin()531 iterator begin() { return _M_start; }
end()532 iterator end() { return _M_finish; }
begin()533 const_iterator begin() const { return _M_start; }
end()534 const_iterator end() const { return _M_finish; }
535
rbegin()536 reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
rend()537 reverse_iterator rend() { return reverse_iterator(_M_start); }
rbegin()538 const_reverse_iterator rbegin() const
539 { return const_reverse_iterator(_M_finish); }
rend()540 const_reverse_iterator rend() const
541 { return const_reverse_iterator(_M_start); }
542
543 reference operator[](size_type __n)
544 { return _M_start[difference_type(__n)]; }
545 const_reference operator[](size_type __n) const
546 { return _M_start[difference_type(__n)]; }
547
front()548 reference front() { return *_M_start; }
back()549 reference back() {
550 iterator __tmp = _M_finish;
551 --__tmp;
552 return *__tmp;
553 }
front()554 const_reference front() const { return *_M_start; }
back()555 const_reference back() const {
556 const_iterator __tmp = _M_finish;
557 --__tmp;
558 return *__tmp;
559 }
560
size()561 size_type size() const { return _M_finish - _M_start;; }
max_size()562 size_type max_size() const { return size_type(-1); }
empty()563 bool empty() const { return _M_finish == _M_start; }
564
565 public: // Constructor, destructor.
566 explicit deque(const allocator_type& __a = allocator_type())
567 : _Base(__a, 0) {}
deque(const deque & __x)568 deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
569 { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
570 deque(size_type __n, const value_type& __value,
_Base(__a,__n)571 const allocator_type& __a = allocator_type()) : _Base(__a, __n)
572 { _M_fill_initialize(__value); }
deque(size_type __n)573 explicit deque(size_type __n) : _Base(allocator_type(), __n)
574 { _M_fill_initialize(value_type()); }
575
576 #ifdef __STL_MEMBER_TEMPLATES
577
578 // Check whether it's an integral type. If so, it's not an iterator.
579 template <class _InputIterator>
580 deque(_InputIterator __first, _InputIterator __last,
_Base(__a)581 const allocator_type& __a = allocator_type()) : _Base(__a) {
582 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
583 _M_initialize_dispatch(__first, __last, _Integral());
584 }
585
586 template <class _Integer>
_M_initialize_dispatch(_Integer __n,_Integer __x,__true_type)587 void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
588 _M_initialize_map(__n);
589 _M_fill_initialize(__x);
590 }
591
592 template <class _InputIter>
_M_initialize_dispatch(_InputIter __first,_InputIter __last,__false_type)593 void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
594 __false_type) {
595 _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
596 }
597
598 #else /* __STL_MEMBER_TEMPLATES */
599
600 deque(const value_type* __first, const value_type* __last,
601 const allocator_type& __a = allocator_type())
602 : _Base(__a, __last - __first)
603 { uninitialized_copy(__first, __last, _M_start); }
604 deque(const_iterator __first, const_iterator __last,
605 const allocator_type& __a = allocator_type())
606 : _Base(__a, __last - __first)
607 { uninitialized_copy(__first, __last, _M_start); }
608
609 #endif /* __STL_MEMBER_TEMPLATES */
610
~deque()611 ~deque() { destroy(_M_start, _M_finish); }
612
613 deque& operator= (const deque& __x) {
614 const size_type __len = size();
615 if (&__x != this) {
616 if (__len >= __x.size())
617 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
618 else {
619 const_iterator __mid = __x.begin() + difference_type(__len);
620 copy(__x.begin(), __mid, _M_start);
621 insert(_M_finish, __mid, __x.end());
622 }
623 }
624 return *this;
625 }
626
swap(deque & __x)627 void swap(deque& __x) {
628 __STD::swap(_M_start, __x._M_start);
629 __STD::swap(_M_finish, __x._M_finish);
630 __STD::swap(_M_map, __x._M_map);
631 __STD::swap(_M_map_size, __x._M_map_size);
632 }
633
634 public:
635 // assign(), a generalized assignment member function. Two
636 // versions: one that takes a count, and one that takes a range.
637 // The range version is a member template, so we dispatch on whether
638 // or not the type is an integer.
639
assign(size_type __n,const _Tp & __val)640 void assign(size_type __n, const _Tp& __val) {
641 if (__n > size()) {
642 fill(begin(), end(), __val);
643 insert(end(), __n - size(), __val);
644 }
645 else {
646 erase(begin() + __n, end());
647 fill(begin(), end(), __val);
648 }
649 }
650
651 #ifdef __STL_MEMBER_TEMPLATES
652
653 template <class _InputIterator>
assign(_InputIterator __first,_InputIterator __last)654 void assign(_InputIterator __first, _InputIterator __last) {
655 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
656 _M_assign_dispatch(__first, __last, _Integral());
657 }
658
659 private: // helper functions for assign()
660
661 template <class _Integer>
_M_assign_dispatch(_Integer __n,_Integer __val,__true_type)662 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
663 { assign((size_type) __n, (_Tp) __val); }
664
665 template <class _InputIterator>
_M_assign_dispatch(_InputIterator __first,_InputIterator __last,__false_type)666 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
667 __false_type) {
668 _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
669 }
670
671 template <class _InputIterator>
672 void _M_assign_aux(_InputIterator __first, _InputIterator __last,
673 input_iterator_tag);
674
675 template <class _ForwardIterator>
_M_assign_aux(_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)676 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
677 forward_iterator_tag) {
678 size_type __len = 0;
679 distance(__first, __last, __len);
680 if (__len > size()) {
681 _ForwardIterator __mid = __first;
682 advance(__mid, size());
683 copy(__first, __mid, begin());
684 insert(end(), __mid, __last);
685 }
686 else
687 erase(copy(__first, __last, begin()), end());
688 }
689
690 #endif /* __STL_MEMBER_TEMPLATES */
691
692 public: // push_* and pop_*
693
push_back(const value_type & __t)694 void push_back(const value_type& __t) {
695 if (_M_finish._M_cur != _M_finish._M_last - 1) {
696 construct(_M_finish._M_cur, __t);
697 ++_M_finish._M_cur;
698 }
699 else
700 _M_push_back_aux(__t);
701 }
702
push_back()703 void push_back() {
704 if (_M_finish._M_cur != _M_finish._M_last - 1) {
705 construct(_M_finish._M_cur);
706 ++_M_finish._M_cur;
707 }
708 else
709 _M_push_back_aux();
710 }
711
push_front(const value_type & __t)712 void push_front(const value_type& __t) {
713 if (_M_start._M_cur != _M_start._M_first) {
714 construct(_M_start._M_cur - 1, __t);
715 --_M_start._M_cur;
716 }
717 else
718 _M_push_front_aux(__t);
719 }
720
push_front()721 void push_front() {
722 if (_M_start._M_cur != _M_start._M_first) {
723 construct(_M_start._M_cur - 1);
724 --_M_start._M_cur;
725 }
726 else
727 _M_push_front_aux();
728 }
729
730
pop_back()731 void pop_back() {
732 if (_M_finish._M_cur != _M_finish._M_first) {
733 --_M_finish._M_cur;
734 destroy(_M_finish._M_cur);
735 }
736 else
737 _M_pop_back_aux();
738 }
739
pop_front()740 void pop_front() {
741 if (_M_start._M_cur != _M_start._M_last - 1) {
742 destroy(_M_start._M_cur);
743 ++_M_start._M_cur;
744 }
745 else
746 _M_pop_front_aux();
747 }
748
749 public: // Insert
750
insert(iterator position,const value_type & __x)751 iterator insert(iterator position, const value_type& __x) {
752 if (position._M_cur == _M_start._M_cur) {
753 push_front(__x);
754 return _M_start;
755 }
756 else if (position._M_cur == _M_finish._M_cur) {
757 push_back(__x);
758 iterator __tmp = _M_finish;
759 --__tmp;
760 return __tmp;
761 }
762 else {
763 return _M_insert_aux(position, __x);
764 }
765 }
766
insert(iterator __position)767 iterator insert(iterator __position)
768 { return insert(__position, value_type()); }
769
770 void insert(iterator __pos, size_type __n, const value_type& __x);
771
772 #ifdef __STL_MEMBER_TEMPLATES
773
774 // Check whether it's an integral type. If so, it's not an iterator.
775 template <class _InputIterator>
insert(iterator __pos,_InputIterator __first,_InputIterator __last)776 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
777 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
778 _M_insert_dispatch(__pos, __first, __last, _Integral());
779 }
780
781 template <class _Integer>
_M_insert_dispatch(iterator __pos,_Integer __n,_Integer __x,__true_type)782 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
783 __true_type) {
784 insert(__pos, (size_type) __n, (value_type) __x);
785 }
786
787 template <class _InputIterator>
_M_insert_dispatch(iterator __pos,_InputIterator __first,_InputIterator __last,__false_type)788 void _M_insert_dispatch(iterator __pos,
789 _InputIterator __first, _InputIterator __last,
790 __false_type) {
791 insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
792 }
793
794 #else /* __STL_MEMBER_TEMPLATES */
795
796 void insert(iterator __pos,
797 const value_type* __first, const value_type* __last);
798 void insert(iterator __pos,
799 const_iterator __first, const_iterator __last);
800
801 #endif /* __STL_MEMBER_TEMPLATES */
802
resize(size_type __new_size,const value_type & __x)803 void resize(size_type __new_size, const value_type& __x) {
804 const size_type __len = size();
805 if (__new_size < __len)
806 erase(_M_start + __new_size, _M_finish);
807 else
808 insert(_M_finish, __new_size - __len, __x);
809 }
810
resize(size_type new_size)811 void resize(size_type new_size) { resize(new_size, value_type()); }
812
813 public: // Erase
erase(iterator __pos)814 iterator erase(iterator __pos) {
815 iterator __next = __pos;
816 ++__next;
817 difference_type __index = __pos - _M_start;
818 if (static_cast<size_type>(__index) < (size() >> 1)) {
819 copy_backward(_M_start, __pos, __next);
820 pop_front();
821 }
822 else {
823 copy(__next, _M_finish, __pos);
824 pop_back();
825 }
826 return _M_start + __index;
827 }
828
829 iterator erase(iterator __first, iterator __last);
830 void clear();
831
832 protected: // Internal construction/destruction
833
834 void _M_fill_initialize(const value_type& __value);
835
836 #ifdef __STL_MEMBER_TEMPLATES
837
838 template <class _InputIterator>
839 void _M_range_initialize(_InputIterator __first, _InputIterator __last,
840 input_iterator_tag);
841
842 template <class _ForwardIterator>
843 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
844 forward_iterator_tag);
845
846 #endif /* __STL_MEMBER_TEMPLATES */
847
848 protected: // Internal push_* and pop_*
849
850 void _M_push_back_aux(const value_type&);
851 void _M_push_back_aux();
852 void _M_push_front_aux(const value_type&);
853 void _M_push_front_aux();
854 void _M_pop_back_aux();
855 void _M_pop_front_aux();
856
857 protected: // Internal insert functions
858
859 #ifdef __STL_MEMBER_TEMPLATES
860
861 template <class _InputIterator>
862 void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
863 input_iterator_tag);
864
865 template <class _ForwardIterator>
866 void insert(iterator __pos,
867 _ForwardIterator __first, _ForwardIterator __last,
868 forward_iterator_tag);
869
870 #endif /* __STL_MEMBER_TEMPLATES */
871
872 iterator _M_insert_aux(iterator __pos, const value_type& __x);
873 iterator _M_insert_aux(iterator __pos);
874 void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
875
876 #ifdef __STL_MEMBER_TEMPLATES
877
878 template <class _ForwardIterator>
879 void _M_insert_aux(iterator __pos,
880 _ForwardIterator __first, _ForwardIterator __last,
881 size_type __n);
882
883 #else /* __STL_MEMBER_TEMPLATES */
884
885 void _M_insert_aux(iterator __pos,
886 const value_type* __first, const value_type* __last,
887 size_type __n);
888
889 void _M_insert_aux(iterator __pos,
890 const_iterator __first, const_iterator __last,
891 size_type __n);
892
893 #endif /* __STL_MEMBER_TEMPLATES */
894
_M_reserve_elements_at_front(size_type __n)895 iterator _M_reserve_elements_at_front(size_type __n) {
896 size_type __vacancies = _M_start._M_cur - _M_start._M_first;
897 if (__n > __vacancies)
898 _M_new_elements_at_front(__n - __vacancies);
899 return _M_start - difference_type(__n);
900 }
901
_M_reserve_elements_at_back(size_type __n)902 iterator _M_reserve_elements_at_back(size_type __n) {
903 size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
904 if (__n > __vacancies)
905 _M_new_elements_at_back(__n - __vacancies);
906 return _M_finish + difference_type(__n);
907 }
908
909 void _M_new_elements_at_front(size_type __new_elements);
910 void _M_new_elements_at_back(size_type __new_elements);
911
912 protected: // Allocation of _M_map and nodes
913
914 // Makes sure the _M_map has space for new nodes. Does not actually
915 // add the nodes. Can invalidate _M_map pointers. (And consequently,
916 // deque iterators.)
917
918 void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
919 if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
920 _M_reallocate_map(__nodes_to_add, false);
921 }
922
923 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
924 if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
925 _M_reallocate_map(__nodes_to_add, true);
926 }
927
928 void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
929
930 #ifdef __STL_NON_TYPE_TMPL_PARAM_BUG
931 public:
932 bool operator==(const deque<_Tp,_Alloc,0>& __x) const {
933 return size() == __x.size() && equal(begin(), end(), __x.begin());
934 }
935 bool operator!=(const deque<_Tp,_Alloc,0>& __x) const {
936 return size() != __x.size() || !equal(begin(), end(), __x.begin());
937 }
938 bool operator<(const deque<_Tp,_Alloc,0>& __x) const {
939 return lexicographical_compare(begin(), end(), __x.begin(), __x.end());
940 }
941 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
942 };
943
944 // Non-inline member functions
945
946 #ifdef __STL_MEMBER_TEMPLATES
947
948 template <class _Tp, class _Alloc, size_t __bufsize>
949 template <class _InputIter>
950 void deque<_Tp, _Alloc, __bufsize>
_M_assign_aux(_InputIter __first,_InputIter __last,input_iterator_tag)951 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
952 {
953 iterator __cur = begin();
954 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
955 *__cur = *__first;
956 if (__first == __last)
957 erase(__cur, end());
958 else
959 insert(end(), __first, __last);
960 }
961
962 #endif /* __STL_MEMBER_TEMPLATES */
963
964 template <class _Tp, class _Alloc, size_t __bufsize>
965 void
insert(iterator __pos,size_type __n,const value_type & __x)966 deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos,
967 size_type __n, const value_type& __x)
968 {
969 if (__pos._M_cur == _M_start._M_cur) {
970 iterator __new_start = _M_reserve_elements_at_front(__n);
971 uninitialized_fill(__new_start, _M_start, __x);
972 _M_start = __new_start;
973 }
974 else if (__pos._M_cur == _M_finish._M_cur) {
975 iterator __new_finish = _M_reserve_elements_at_back(__n);
976 uninitialized_fill(_M_finish, __new_finish, __x);
977 _M_finish = __new_finish;
978 }
979 else
980 _M_insert_aux(__pos, __n, __x);
981 }
982
983 #ifndef __STL_MEMBER_TEMPLATES
984
985 template <class _Tp, class _Alloc, size_t __bufsize>
insert(iterator __pos,const value_type * __first,const value_type * __last)986 void deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos,
987 const value_type* __first,
988 const value_type* __last) {
989 size_type __n = __last - __first;
990 if (__pos._M_cur == _M_start._M_cur) {
991 iterator __new_start = _M_reserve_elements_at_front(__n);
992 __STL_TRY {
993 uninitialized_copy(__first, __last, __new_start);
994 _M_start = __new_start;
995 }
996 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
997 }
998 else if (__pos._M_cur == _M_finish._M_cur) {
999 iterator __new_finish = _M_reserve_elements_at_back(__n);
1000 __STL_TRY {
1001 uninitialized_copy(__first, __last, _M_finish);
1002 _M_finish = __new_finish;
1003 }
1004 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1005 __new_finish._M_node + 1));
1006 }
1007 else
1008 _M_insert_aux(__pos, __first, __last, __n);
1009 }
1010
1011 template <class _Tp, class _Alloc, size_t __bufsize>
insert(iterator __pos,const_iterator __first,const_iterator __last)1012 void deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
1013 const_iterator __first,
1014 const_iterator __last)
1015 {
1016 size_type __n = __last - __first;
1017 if (__pos._M_cur == _M_start._M_cur) {
1018 iterator __new_start = _M_reserve_elements_at_front(__n);
1019 __STL_TRY {
1020 uninitialized_copy(__first, __last, __new_start);
1021 _M_start = __new_start;
1022 }
1023 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1024 }
1025 else if (__pos._M_cur == _M_finish._M_cur) {
1026 iterator __new_finish = _M_reserve_elements_at_back(__n);
1027 __STL_TRY {
1028 uninitialized_copy(__first, __last, _M_finish);
1029 _M_finish = __new_finish;
1030 }
1031 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1032 __new_finish._M_node + 1));
1033 }
1034 else
1035 _M_insert_aux(__pos, __first, __last, __n);
1036 }
1037
1038 #endif /* __STL_MEMBER_TEMPLATES */
1039
1040 template <class _Tp, class _Alloc, size_t __bufsize>
1041 deque<_Tp,_Alloc,__bufsize>::iterator
erase(iterator __first,iterator __last)1042 deque<_Tp,_Alloc,__bufsize>::erase(iterator __first, iterator __last)
1043 {
1044 if (__first == _M_start && __last == _M_finish) {
1045 clear();
1046 return _M_finish;
1047 }
1048 else {
1049 difference_type __n = __last - __first;
1050 difference_type __elems_before = __first - _M_start;
1051 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
1052 copy_backward(_M_start, __first, __last);
1053 iterator __new_start = _M_start + __n;
1054 destroy(_M_start, __new_start);
1055 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
1056 _M_start = __new_start;
1057 }
1058 else {
1059 copy(__last, _M_finish, __first);
1060 iterator __new_finish = _M_finish - __n;
1061 destroy(__new_finish, _M_finish);
1062 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
1063 _M_finish = __new_finish;
1064 }
1065 return _M_start + __elems_before;
1066 }
1067 }
1068
1069 template <class _Tp, class _Alloc, size_t __bufsize>
clear()1070 void deque<_Tp,_Alloc,__bufsize>::clear()
1071 {
1072 for (_Map_pointer __node = _M_start._M_node + 1;
1073 __node < _M_finish._M_node;
1074 ++__node) {
1075 destroy(*__node, *__node + _S_buffer_size());
1076 _M_deallocate_node(*__node);
1077 }
1078
1079 if (_M_start._M_node != _M_finish._M_node) {
1080 destroy(_M_start._M_cur, _M_start._M_last);
1081 destroy(_M_finish._M_first, _M_finish._M_cur);
1082 _M_deallocate_node(_M_finish._M_first);
1083 }
1084 else
1085 destroy(_M_start._M_cur, _M_finish._M_cur);
1086
1087 _M_finish = _M_start;
1088 }
1089
1090 // Precondition: _M_start and _M_finish have already been initialized,
1091 // but none of the deque's elements have yet been constructed.
1092 template <class _Tp, class _Alloc, size_t __bufsize>
1093 void
_M_fill_initialize(const value_type & __value)1094 deque<_Tp,_Alloc,__bufsize>::_M_fill_initialize(const value_type& __value) {
1095 _Map_pointer __cur;
1096 __STL_TRY {
1097 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
1098 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
1099 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
1100 }
1101 __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
1102 }
1103
1104 #ifdef __STL_MEMBER_TEMPLATES
1105
1106 template <class _Tp, class _Alloc, size_t __bufsize>
1107 template <class _InputIterator>
1108 void
_M_range_initialize(_InputIterator __first,_InputIterator __last,input_iterator_tag)1109 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_InputIterator __first,
1110 _InputIterator __last,
1111 input_iterator_tag)
1112 {
1113 _M_initialize_map(0);
1114 for ( ; __first != __last; ++__first)
1115 push_back(*__first);
1116 }
1117
1118 template <class _Tp, class _Alloc, size_t __bufsize>
1119 template <class _ForwardIterator>
1120 void
_M_range_initialize(_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)1121 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_ForwardIterator __first,
1122 _ForwardIterator __last,
1123 forward_iterator_tag)
1124 {
1125 size_type __n = 0;
1126 distance(__first, __last, __n);
1127 _M_initialize_map(__n);
1128
1129 _Map_pointer __cur_node;
1130 __STL_TRY {
1131 for (__cur_node = _M_start._M_node;
1132 __cur_node < _M_finish._M_node;
1133 ++__cur_node) {
1134 _ForwardIterator __mid = __first;
1135 advance(__mid, _S_buffer_size());
1136 uninitialized_copy(__first, __mid, *__cur_node);
1137 __first = __mid;
1138 }
1139 uninitialized_copy(__first, __last, _M_finish._M_first);
1140 }
1141 __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
1142 }
1143
1144 #endif /* __STL_MEMBER_TEMPLATES */
1145
1146 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1147 template <class _Tp, class _Alloc, size_t __bufsize>
1148 void
_M_push_back_aux(const value_type & __t)1149 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux(const value_type& __t)
1150 {
1151 value_type __t_copy = __t;
1152 _M_reserve_map_at_back();
1153 *(_M_finish._M_node + 1) = _M_allocate_node();
1154 __STL_TRY {
1155 construct(_M_finish._M_cur, __t_copy);
1156 _M_finish._M_set_node(_M_finish._M_node + 1);
1157 _M_finish._M_cur = _M_finish._M_first;
1158 }
1159 __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
1160 }
1161
1162 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1163 template <class _Tp, class _Alloc, size_t __bufsize>
1164 void
_M_push_back_aux()1165 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux()
1166 {
1167 _M_reserve_map_at_back();
1168 *(_M_finish._M_node + 1) = _M_allocate_node();
1169 __STL_TRY {
1170 construct(_M_finish._M_cur);
1171 _M_finish._M_set_node(_M_finish._M_node + 1);
1172 _M_finish._M_cur = _M_finish._M_first;
1173 }
1174 __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
1175 }
1176
1177 // Called only if _M_start._M_cur == _M_start._M_first.
1178 template <class _Tp, class _Alloc, size_t __bufsize>
1179 void
_M_push_front_aux(const value_type & __t)1180 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux(const value_type& __t)
1181 {
1182 value_type __t_copy = __t;
1183 _M_reserve_map_at_front();
1184 *(_M_start._M_node - 1) = _M_allocate_node();
1185 __STL_TRY {
1186 _M_start._M_set_node(_M_start._M_node - 1);
1187 _M_start._M_cur = _M_start._M_last - 1;
1188 construct(_M_start._M_cur, __t_copy);
1189 }
1190 __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
1191 }
1192
1193 // Called only if _M_start._M_cur == _M_start._M_first.
1194 template <class _Tp, class _Alloc, size_t __bufsize>
1195 void
_M_push_front_aux()1196 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux()
1197 {
1198 _M_reserve_map_at_front();
1199 *(_M_start._M_node - 1) = _M_allocate_node();
1200 __STL_TRY {
1201 _M_start._M_set_node(_M_start._M_node - 1);
1202 _M_start._M_cur = _M_start._M_last - 1;
1203 construct(_M_start._M_cur);
1204 }
1205 __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
1206 }
1207
1208 // Called only if _M_finish._M_cur == _M_finish._M_first.
1209 template <class _Tp, class _Alloc, size_t __bufsize>
1210 void
_M_pop_back_aux()1211 deque<_Tp,_Alloc,__bufsize>::_M_pop_back_aux()
1212 {
1213 _M_deallocate_node(_M_finish._M_first);
1214 _M_finish._M_set_node(_M_finish._M_node - 1);
1215 _M_finish._M_cur = _M_finish._M_last - 1;
1216 destroy(_M_finish._M_cur);
1217 }
1218
1219 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
1220 // if the deque has at least one element (a precondition for this member
1221 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
1222 // must have at least two nodes.
1223 template <class _Tp, class _Alloc, size_t __bufsize>
1224 void
_M_pop_front_aux()1225 deque<_Tp,_Alloc,__bufsize>::_M_pop_front_aux()
1226 {
1227 destroy(_M_start._M_cur);
1228 _M_deallocate_node(_M_start._M_first);
1229 _M_start._M_set_node(_M_start._M_node + 1);
1230 _M_start._M_cur = _M_start._M_first;
1231 }
1232
1233 #ifdef __STL_MEMBER_TEMPLATES
1234
1235 template <class _Tp, class _Alloc, size_t __bufsize>
1236 template <class _InputIterator>
1237 void
insert(iterator __pos,_InputIterator __first,_InputIterator __last,input_iterator_tag)1238 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
1239 _InputIterator __first,
1240 _InputIterator __last,
1241 input_iterator_tag)
1242 {
1243 copy(__first, __last, inserter(*this, __pos));
1244 }
1245
1246 template <class _Tp, class _Alloc, size_t __bufsize>
1247 template <class _ForwardIterator>
1248 void
insert(iterator __pos,_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)1249 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
1250 _ForwardIterator __first,
1251 _ForwardIterator __last,
1252 forward_iterator_tag) {
1253 size_type __n = 0;
1254 distance(__first, __last, __n);
1255 if (__pos._M_cur == _M_start._M_cur) {
1256 iterator __new_start = _M_reserve_elements_at_front(__n);
1257 __STL_TRY {
1258 uninitialized_copy(__first, __last, __new_start);
1259 _M_start = __new_start;
1260 }
1261 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1262 }
1263 else if (__pos._M_cur == _M_finish._M_cur) {
1264 iterator __new_finish = _M_reserve_elements_at_back(__n);
1265 __STL_TRY {
1266 uninitialized_copy(__first, __last, _M_finish);
1267 _M_finish = __new_finish;
1268 }
1269 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1270 __new_finish._M_node + 1));
1271 }
1272 else
1273 _M_insert_aux(__pos, __first, __last, __n);
1274 }
1275
1276 #endif /* __STL_MEMBER_TEMPLATES */
1277
1278 template <class _Tp, class _Alloc, size_t __bufsize>
1279 typename deque<_Tp, _Alloc, __bufsize>::iterator
_M_insert_aux(iterator __pos,const value_type & __x)1280 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1281 const value_type& __x)
1282 {
1283 difference_type __index = __pos - _M_start;
1284 value_type __x_copy = __x;
1285 if (static_cast<size_type>(__index) < size() / 2) {
1286 push_front(front());
1287 iterator __front1 = _M_start;
1288 ++__front1;
1289 iterator __front2 = __front1;
1290 ++__front2;
1291 __pos = _M_start + __index;
1292 iterator __pos1 = __pos;
1293 ++__pos1;
1294 copy(__front2, __pos1, __front1);
1295 }
1296 else {
1297 push_back(back());
1298 iterator __back1 = _M_finish;
1299 --__back1;
1300 iterator __back2 = __back1;
1301 --__back2;
1302 __pos = _M_start + __index;
1303 copy_backward(__pos, __back2, __back1);
1304 }
1305 *__pos = __x_copy;
1306 return __pos;
1307 }
1308
1309 template <class _Tp, class _Alloc, size_t __bufsize>
1310 typename deque<_Tp,_Alloc,__bufsize>::iterator
_M_insert_aux(iterator __pos)1311 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos)
1312 {
1313 difference_type __index = __pos - _M_start;
1314 if (static_cast<size_type>(__index) < size() / 2) {
1315 push_front(front());
1316 iterator __front1 = _M_start;
1317 ++__front1;
1318 iterator __front2 = __front1;
1319 ++__front2;
1320 __pos = _M_start + __index;
1321 iterator __pos1 = __pos;
1322 ++__pos1;
1323 copy(__front2, __pos1, __front1);
1324 }
1325 else {
1326 push_back(back());
1327 iterator __back1 = _M_finish;
1328 --__back1;
1329 iterator __back2 = __back1;
1330 --__back2;
1331 __pos = _M_start + __index;
1332 copy_backward(__pos, __back2, __back1);
1333 }
1334 *__pos = value_type();
1335 return __pos;
1336 }
1337
1338 template <class _Tp, class _Alloc, size_t __bufsize>
1339 void
_M_insert_aux(iterator __pos,size_type __n,const value_type & __x)1340 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1341 size_type __n,
1342 const value_type& __x)
1343 {
1344 const difference_type __elems_before = __pos - _M_start;
1345 size_type __length = size();
1346 value_type __x_copy = __x;
1347 if (static_cast<size_type>(__elems_before) < __length / 2) {
1348 iterator __new_start = _M_reserve_elements_at_front(__n);
1349 iterator __old_start = _M_start;
1350 __pos = _M_start + __elems_before;
1351 __STL_TRY {
1352 if (__elems_before >= difference_type(__n)) {
1353 iterator __start_n = _M_start + difference_type(__n);
1354 uninitialized_copy(_M_start, __start_n, __new_start);
1355 _M_start = __new_start;
1356 copy(__start_n, __pos, __old_start);
1357 fill(__pos - difference_type(__n), __pos, __x_copy);
1358 }
1359 else {
1360 __uninitialized_copy_fill(_M_start, __pos, __new_start,
1361 _M_start, __x_copy);
1362 _M_start = __new_start;
1363 fill(__old_start, __pos, __x_copy);
1364 }
1365 }
1366 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1367 }
1368 else {
1369 iterator __new_finish = _M_reserve_elements_at_back(__n);
1370 iterator __old_finish = _M_finish;
1371 const difference_type __elems_after =
1372 difference_type(__length) - __elems_before;
1373 __pos = _M_finish - __elems_after;
1374 __STL_TRY {
1375 if (__elems_after > difference_type(__n)) {
1376 iterator __finish_n = _M_finish - difference_type(__n);
1377 uninitialized_copy(__finish_n, _M_finish, _M_finish);
1378 _M_finish = __new_finish;
1379 copy_backward(__pos, __finish_n, __old_finish);
1380 fill(__pos, __pos + difference_type(__n), __x_copy);
1381 }
1382 else {
1383 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
1384 __x_copy, __pos, _M_finish);
1385 _M_finish = __new_finish;
1386 fill(__pos, __old_finish, __x_copy);
1387 }
1388 }
1389 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1390 __new_finish._M_node + 1));
1391 }
1392 }
1393
1394 #ifdef __STL_MEMBER_TEMPLATES
1395
1396 template <class _Tp, class _Alloc, size_t __bufsize>
1397 template <class _ForwardIterator>
1398 void
_M_insert_aux(iterator __pos,_ForwardIterator __first,_ForwardIterator __last,size_type __n)1399 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1400 _ForwardIterator __first,
1401 _ForwardIterator __last,
1402 size_type __n)
1403 {
1404 const difference_type __elemsbefore = __pos - _M_start;
1405 size_type __length = size();
1406 if (static_cast<size_type>(__elemsbefore) < __length / 2) {
1407 iterator __new_start = _M_reserve_elements_at_front(__n);
1408 iterator __old_start = _M_start;
1409 __pos = _M_start + __elemsbefore;
1410 __STL_TRY {
1411 if (__elemsbefore >= difference_type(__n)) {
1412 iterator __start_n = _M_start + difference_type(__n);
1413 uninitialized_copy(_M_start, __start_n, __new_start);
1414 _M_start = __new_start;
1415 copy(__start_n, __pos, __old_start);
1416 copy(__first, __last, __pos - difference_type(__n));
1417 }
1418 else {
1419 _ForwardIterator __mid = __first;
1420 advance(__mid, difference_type(__n) - __elemsbefore);
1421 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1422 __new_start);
1423 _M_start = __new_start;
1424 copy(__mid, __last, __old_start);
1425 }
1426 }
1427 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1428 }
1429 else {
1430 iterator __new_finish = _M_reserve_elements_at_back(__n);
1431 iterator __old_finish = _M_finish;
1432 const difference_type __elemsafter =
1433 difference_type(__length) - __elemsbefore;
1434 __pos = _M_finish - __elemsafter;
1435 __STL_TRY {
1436 if (__elemsafter > difference_type(__n)) {
1437 iterator __finish_n = _M_finish - difference_type(__n);
1438 uninitialized_copy(__finish_n, _M_finish, _M_finish);
1439 _M_finish = __new_finish;
1440 copy_backward(__pos, __finish_n, __old_finish);
1441 copy(__first, __last, __pos);
1442 }
1443 else {
1444 _ForwardIterator __mid = __first;
1445 advance(__mid, __elemsafter);
1446 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1447 _M_finish = __new_finish;
1448 copy(__first, __mid, __pos);
1449 }
1450 }
1451 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1452 __new_finish._M_node + 1));
1453 }
1454 }
1455
1456 #else /* __STL_MEMBER_TEMPLATES */
1457
1458 template <class _Tp, class _Alloc, size_t __bufsize>
1459 void
_M_insert_aux(iterator __pos,const value_type * __first,const value_type * __last,size_type __n)1460 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1461 const value_type* __first,
1462 const value_type* __last,
1463 size_type __n)
1464 {
1465 const difference_type __elemsbefore = __pos - _M_start;
1466 size_type __length = size();
1467 if (__elemsbefore < __length / 2) {
1468 iterator __new_start = _M_reserve_elements_at_front(__n);
1469 iterator __old_start = _M_start;
1470 __pos = _M_start + __elemsbefore;
1471 __STL_TRY {
1472 if (__elemsbefore >= difference_type(__n)) {
1473 iterator __start_n = _M_start + difference_type(__n);
1474 uninitialized_copy(_M_start, __start_n, __new_start);
1475 _M_start = __new_start;
1476 copy(__start_n, __pos, __old_start);
1477 copy(__first, __last, __pos - difference_type(__n));
1478 }
1479 else {
1480 const value_type* __mid =
1481 __first + (difference_type(__n) - __elemsbefore);
1482 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1483 __new_start);
1484 _M_start = __new_start;
1485 copy(__mid, __last, __old_start);
1486 }
1487 }
1488 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1489 }
1490 else {
1491 iterator __new_finish = _M_reserve_elements_at_back(__n);
1492 iterator __old_finish = _M_finish;
1493 const difference_type __elemsafter =
1494 difference_type(__length) - __elemsbefore;
1495 __pos = _M_finish - __elemsafter;
1496 __STL_TRY {
1497 if (__elemsafter > difference_type(__n)) {
1498 iterator __finish_n = _M_finish - difference_type(__n);
1499 uninitialized_copy(__finish_n, _M_finish, _M_finish);
1500 _M_finish = __new_finish;
1501 copy_backward(__pos, __finish_n, __old_finish);
1502 copy(__first, __last, __pos);
1503 }
1504 else {
1505 const value_type* __mid = __first + __elemsafter;
1506 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1507 _M_finish = __new_finish;
1508 copy(__first, __mid, __pos);
1509 }
1510 }
1511 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1512 __new_finish._M_node + 1));
1513 }
1514 }
1515
1516 template <class _Tp, class _Alloc, size_t __bufsize>
1517 void
_M_insert_aux(iterator __pos,const_iterator __first,const_iterator __last,size_type __n)1518 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1519 const_iterator __first,
1520 const_iterator __last,
1521 size_type __n)
1522 {
1523 const difference_type __elemsbefore = __pos - _M_start;
1524 size_type __length = size();
1525 if (__elemsbefore < __length / 2) {
1526 iterator __new_start = _M_reserve_elements_at_front(__n);
1527 iterator __old_start = _M_start;
1528 __pos = _M_start + __elemsbefore;
1529 __STL_TRY {
1530 if (__elemsbefore >= __n) {
1531 iterator __start_n = _M_start + __n;
1532 uninitialized_copy(_M_start, __start_n, __new_start);
1533 _M_start = __new_start;
1534 copy(__start_n, __pos, __old_start);
1535 copy(__first, __last, __pos - difference_type(__n));
1536 }
1537 else {
1538 const_iterator __mid = __first + (__n - __elemsbefore);
1539 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1540 __new_start);
1541 _M_start = __new_start;
1542 copy(__mid, __last, __old_start);
1543 }
1544 }
1545 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1546 }
1547 else {
1548 iterator __new_finish = _M_reserve_elements_at_back(__n);
1549 iterator __old_finish = _M_finish;
1550 const difference_type __elemsafter = __length - __elemsbefore;
1551 __pos = _M_finish - __elemsafter;
1552 __STL_TRY {
1553 if (__elemsafter > __n) {
1554 iterator __finish_n = _M_finish - difference_type(__n);
1555 uninitialized_copy(__finish_n, _M_finish, _M_finish);
1556 _M_finish = __new_finish;
1557 copy_backward(__pos, __finish_n, __old_finish);
1558 copy(__first, __last, __pos);
1559 }
1560 else {
1561 const_iterator __mid = __first + __elemsafter;
1562 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1563 _M_finish = __new_finish;
1564 copy(__first, __mid, __pos);
1565 }
1566 }
1567 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1568 __new_finish._M_node + 1));
1569 }
1570 }
1571
1572 #endif /* __STL_MEMBER_TEMPLATES */
1573
1574 template <class _Tp, class _Alloc, size_t __bufsize>
1575 void
_M_new_elements_at_front(size_type __new_elems)1576 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_front(size_type __new_elems)
1577 {
1578 size_type __new_nodes
1579 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1580 _M_reserve_map_at_front(__new_nodes);
1581 size_type __i;
1582 __STL_TRY {
1583 for (__i = 1; __i <= __new_nodes; ++__i)
1584 *(_M_start._M_node - __i) = _M_allocate_node();
1585 }
1586 # ifdef __STL_USE_EXCEPTIONS
1587 catch(...) {
1588 for (size_type __j = 1; __j < __i; ++__j)
1589 _M_deallocate_node(*(_M_start._M_node - __j));
1590 throw;
1591 }
1592 # endif /* __STL_USE_EXCEPTIONS */
1593 }
1594
1595 template <class _Tp, class _Alloc, size_t __bufsize>
1596 void
_M_new_elements_at_back(size_type __new_elems)1597 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_back(size_type __new_elems)
1598 {
1599 size_type __new_nodes
1600 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1601 _M_reserve_map_at_back(__new_nodes);
1602 size_type __i;
1603 __STL_TRY {
1604 for (__i = 1; __i <= __new_nodes; ++__i)
1605 *(_M_finish._M_node + __i) = _M_allocate_node();
1606 }
1607 # ifdef __STL_USE_EXCEPTIONS
1608 catch(...) {
1609 for (size_type __j = 1; __j < __i; ++__j)
1610 _M_deallocate_node(*(_M_finish._M_node + __j));
1611 throw;
1612 }
1613 # endif /* __STL_USE_EXCEPTIONS */
1614 }
1615
1616 template <class _Tp, class _Alloc, size_t __bufsize>
1617 void
_M_reallocate_map(size_type __nodes_to_add,bool __add_at_front)1618 deque<_Tp,_Alloc,__bufsize>::_M_reallocate_map(size_type __nodes_to_add,
1619 bool __add_at_front)
1620 {
1621 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
1622 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
1623
1624 _Map_pointer __new_nstart;
1625 if (_M_map_size > 2 * __new_num_nodes) {
1626 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
1627 + (__add_at_front ? __nodes_to_add : 0);
1628 if (__new_nstart < _M_start._M_node)
1629 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1630 else
1631 copy_backward(_M_start._M_node, _M_finish._M_node + 1,
1632 __new_nstart + __old_num_nodes);
1633 }
1634 else {
1635 size_type __new_map_size =
1636 _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
1637
1638 _Map_pointer __new_map = _M_allocate_map(__new_map_size);
1639 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
1640 + (__add_at_front ? __nodes_to_add : 0);
1641 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1642 _M_deallocate_map(_M_map, _M_map_size);
1643
1644 _M_map = __new_map;
1645 _M_map_size = __new_map_size;
1646 }
1647
1648 _M_start._M_set_node(__new_nstart);
1649 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
1650 }
1651
1652
1653 // Nonmember functions.
1654
1655 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
1656
1657 template <class _Tp, class _Alloc, size_t __bufsiz>
1658 bool operator==(const deque<_Tp, _Alloc, __bufsiz>& __x,
1659 const deque<_Tp, _Alloc, __bufsiz>& __y)
1660 {
1661 return __x.size() == __y.size() &&
1662 equal(__x.begin(), __x.end(), __y.begin());
1663 }
1664
1665 template <class _Tp, class _Alloc, size_t __bufsiz>
1666 bool operator<(const deque<_Tp, _Alloc, __bufsiz>& __x,
1667 const deque<_Tp, _Alloc, __bufsiz>& __y)
1668 {
1669 return lexicographical_compare(__x.begin(), __x.end(),
1670 __y.begin(), __y.end());
1671 }
1672
1673 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
1674
1675 #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER) && \
1676 !defined(__STL_NON_TYPE_TMPL_PARAM_BUG)
1677
1678 template <class _Tp, class _Alloc, size_t __bufsiz>
1679 inline void
swap(deque<_Tp,_Alloc,__bufsiz> & __x,deque<_Tp,_Alloc,__bufsiz> & __y)1680 swap(deque<_Tp,_Alloc,__bufsiz>& __x, deque<_Tp,_Alloc,__bufsiz>& __y)
1681 {
1682 __x.swap(__y);
1683 }
1684
1685 #endif
1686
1687 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
1688 #pragma reset woff 1174
1689 #pragma reset woff 1375
1690 #endif
1691
1692 __STL_END_NAMESPACE
1693
1694 #endif /* __SGI_STL_INTERNAL_DEQUE_H */
1695
1696 // Local Variables:
1697 // mode:C++
1698 // End:
1699