1 : // Deque implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 2, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // You should have received a copy of the GNU General Public License along
17 : // with this library; see the file COPYING. If not, write to the Free
18 : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19 : // USA.
20 :
21 : // As a special exception, you may use this file as part of a free software
22 : // library without restriction. Specifically, if other files instantiate
23 : // templates or use macros or inline functions from this file, or you compile
24 : // this file and link it with other files to produce an executable, this
25 : // file does not by itself cause the resulting executable to be covered by
26 : // the GNU General Public License. This exception does not however
27 : // invalidate any other reasons why the executable file might be covered by
28 : // the GNU General Public License.
29 :
30 : /*
31 : *
32 : * Copyright (c) 1994
33 : * Hewlett-Packard Company
34 : *
35 : * Permission to use, copy, modify, distribute and sell this software
36 : * and its documentation for any purpose is hereby granted without fee,
37 : * provided that the above copyright notice appear in all copies and
38 : * that both that copyright notice and this permission notice appear
39 : * in supporting documentation. Hewlett-Packard Company makes no
40 : * representations about the suitability of this software for any
41 : * purpose. It is provided "as is" without express or implied warranty.
42 : *
43 : *
44 : * Copyright (c) 1997
45 : * Silicon Graphics Computer Systems, Inc.
46 : *
47 : * Permission to use, copy, modify, distribute and sell this software
48 : * and its documentation for any purpose is hereby granted without fee,
49 : * provided that the above copyright notice appear in all copies and
50 : * that both that copyright notice and this permission notice appear
51 : * in supporting documentation. Silicon Graphics makes no
52 : * representations about the suitability of this software for any
53 : * purpose. It is provided "as is" without express or implied warranty.
54 : */
55 :
56 : /** @file stl_deque.h
57 : * This is an internal header file, included by other library headers.
58 : * You should not attempt to use it directly.
59 : */
60 :
61 : #ifndef _DEQUE_H
62 : #define _DEQUE_H 1
63 :
64 : #include <bits/concept_check.h>
65 : #include <bits/stl_iterator_base_types.h>
66 : #include <bits/stl_iterator_base_funcs.h>
67 :
68 : namespace _GLIBCXX_STD
69 : {
70 : /**
71 : * @if maint
72 : * @brief This function controls the size of memory nodes.
73 : * @param size The size of an element.
74 : * @return The number (not byte size) of elements per node.
75 : *
76 : * This function started off as a compiler kludge from SGI, but seems to
77 : * be a useful wrapper around a repeated constant expression. The '512' is
78 : * tuneable (and no other code needs to change), but no investigation has
79 : * been done since inheriting the SGI code.
80 : * @endif
81 : */
82 : inline size_t
83 23502066 : __deque_buf_size(size_t __size)
84 23502066 : { return __size < 512 ? size_t(512 / __size) : size_t(1); }
85 :
86 :
87 : /**
88 : * @brief A deque::iterator.
89 : *
90 : * Quite a bit of intelligence here. Much of the functionality of
91 : * deque is actually passed off to this class. A deque holds two
92 : * of these internally, marking its valid range. Access to
93 : * elements is done as offsets of either of those two, relying on
94 : * operator overloading in this class.
95 : *
96 : * @if maint
97 : * All the functions are op overloads except for _M_set_node.
98 : * @endif
99 : */
100 : template<typename _Tp, typename _Ref, typename _Ptr>
101 : struct _Deque_iterator
102 : {
103 : typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
104 : typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
105 :
106 10072314 : static size_t _S_buffer_size()
107 10072314 : { return __deque_buf_size(sizeof(_Tp)); }
108 :
109 : typedef std::random_access_iterator_tag iterator_category;
110 : typedef _Tp value_type;
111 : typedef _Ptr pointer;
112 : typedef _Ref reference;
113 : typedef size_t size_type;
114 : typedef ptrdiff_t difference_type;
115 : typedef _Tp** _Map_pointer;
116 : typedef _Deque_iterator _Self;
117 :
118 : _Tp* _M_cur;
119 : _Tp* _M_first;
120 : _Tp* _M_last;
121 : _Map_pointer _M_node;
122 :
123 : _Deque_iterator(_Tp* __x, _Map_pointer __y)
124 : : _M_cur(__x), _M_first(*__y),
125 : _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
126 :
127 6714876 : _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
128 :
129 44304973 : _Deque_iterator(const iterator& __x)
130 : : _M_cur(__x._M_cur), _M_first(__x._M_first),
131 44304973 : _M_last(__x._M_last), _M_node(__x._M_node) {}
132 :
133 : reference
134 7373155 : operator*() const
135 7373155 : { return *_M_cur; }
136 :
137 : pointer
138 : operator->() const
139 : { return _M_cur; }
140 :
141 : _Self&
142 0 : operator++()
143 : {
144 0 : ++_M_cur;
145 0 : if (_M_cur == _M_last)
146 : {
147 0 : _M_set_node(_M_node + 1);
148 0 : _M_cur = _M_first;
149 : }
150 0 : return *this;
151 : }
152 :
153 : _Self
154 : operator++(int)
155 : {
156 : _Self __tmp = *this;
157 : ++*this;
158 : return __tmp;
159 : }
160 :
161 : _Self&
162 7373155 : operator--()
163 : {
164 7373155 : if (_M_cur == _M_first)
165 : {
166 0 : _M_set_node(_M_node - 1);
167 0 : _M_cur = _M_last;
168 : }
169 7373155 : --_M_cur;
170 7373155 : return *this;
171 : }
172 :
173 : _Self
174 : operator--(int)
175 : {
176 : _Self __tmp = *this;
177 : --*this;
178 : return __tmp;
179 : }
180 :
181 : _Self&
182 : operator+=(difference_type __n)
183 : {
184 : const difference_type __offset = __n + (_M_cur - _M_first);
185 : if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
186 : _M_cur += __n;
187 : else
188 : {
189 : const difference_type __node_offset =
190 : __offset > 0 ? __offset / difference_type(_S_buffer_size())
191 : : -difference_type((-__offset - 1)
192 : / _S_buffer_size()) - 1;
193 : _M_set_node(_M_node + __node_offset);
194 : _M_cur = _M_first + (__offset - __node_offset
195 : * difference_type(_S_buffer_size()));
196 : }
197 : return *this;
198 : }
199 :
200 : _Self
201 : operator+(difference_type __n) const
202 : {
203 : _Self __tmp = *this;
204 : return __tmp += __n;
205 : }
206 :
207 : _Self&
208 : operator-=(difference_type __n)
209 : { return *this += -__n; }
210 :
211 : _Self
212 : operator-(difference_type __n) const
213 : {
214 : _Self __tmp = *this;
215 : return __tmp -= __n;
216 : }
217 :
218 : reference
219 : operator[](difference_type __n) const
220 : { return *(*this + __n); }
221 :
222 : /** @if maint
223 : * Prepares to traverse new_node. Sets everything except
224 : * _M_cur, which should therefore be set by the caller
225 : * immediately afterwards, based on _M_first and _M_last.
226 : * @endif
227 : */
228 : void
229 6714876 : _M_set_node(_Map_pointer __new_node)
230 : {
231 6714876 : _M_node = __new_node;
232 6714876 : _M_first = *__new_node;
233 6714876 : _M_last = _M_first + difference_type(_S_buffer_size());
234 : }
235 : };
236 :
237 : // Note: we also provide overloads whose operands are of the same type in
238 : // order to avoid ambiguous overload resolution when std::rel_ops operators
239 : // are in scope (for additional details, see libstdc++/3628)
240 : template<typename _Tp, typename _Ref, typename _Ptr>
241 : inline bool
242 : operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
243 7373155 : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
244 7373155 : { return __x._M_cur == __y._M_cur; }
245 :
246 : template<typename _Tp, typename _RefL, typename _PtrL,
247 : typename _RefR, typename _PtrR>
248 : inline bool
249 : operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
250 : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
251 : { return __x._M_cur == __y._M_cur; }
252 :
253 : template<typename _Tp, typename _Ref, typename _Ptr>
254 : inline bool
255 : operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
256 : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
257 : { return !(__x == __y); }
258 :
259 : template<typename _Tp, typename _RefL, typename _PtrL,
260 : typename _RefR, typename _PtrR>
261 : inline bool
262 : operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
263 : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
264 : { return !(__x == __y); }
265 :
266 : template<typename _Tp, typename _Ref, typename _Ptr>
267 : inline bool
268 : operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
269 : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
270 : { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
271 : : (__x._M_node < __y._M_node); }
272 :
273 : template<typename _Tp, typename _RefL, typename _PtrL,
274 : typename _RefR, typename _PtrR>
275 : inline bool
276 : operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
277 : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
278 : { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
279 : : (__x._M_node < __y._M_node); }
280 :
281 : template<typename _Tp, typename _Ref, typename _Ptr>
282 : inline bool
283 : operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
284 : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
285 : { return __y < __x; }
286 :
287 : template<typename _Tp, typename _RefL, typename _PtrL,
288 : typename _RefR, typename _PtrR>
289 : inline bool
290 : operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
291 : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
292 : { return __y < __x; }
293 :
294 : template<typename _Tp, typename _Ref, typename _Ptr>
295 : inline bool
296 : operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
297 : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
298 : { return !(__y < __x); }
299 :
300 : template<typename _Tp, typename _RefL, typename _PtrL,
301 : typename _RefR, typename _PtrR>
302 : inline bool
303 : operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
304 : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
305 : { return !(__y < __x); }
306 :
307 : template<typename _Tp, typename _Ref, typename _Ptr>
308 : inline bool
309 : operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
310 : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
311 : { return !(__x < __y); }
312 :
313 : template<typename _Tp, typename _RefL, typename _PtrL,
314 : typename _RefR, typename _PtrR>
315 : inline bool
316 : operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
317 : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
318 : { return !(__x < __y); }
319 :
320 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
321 : // According to the resolution of DR179 not only the various comparison
322 : // operators but also operator- must accept mixed iterator/const_iterator
323 : // parameters.
324 : template<typename _Tp, typename _RefL, typename _PtrL,
325 : typename _RefR, typename _PtrR>
326 : inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
327 : operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
328 3357438 : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
329 : {
330 : return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
331 : (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
332 : * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
333 3357438 : + (__y._M_last - __y._M_cur);
334 : }
335 :
336 : template<typename _Tp, typename _Ref, typename _Ptr>
337 : inline _Deque_iterator<_Tp, _Ref, _Ptr>
338 : operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
339 : { return __x + __n; }
340 :
341 : /**
342 : * @if maint
343 : * Deque base class. This class provides the unified face for %deque's
344 : * allocation. This class's constructor and destructor allocate and
345 : * deallocate (but do not initialize) storage. This makes %exception
346 : * safety easier.
347 : *
348 : * Nothing in this class ever constructs or destroys an actual Tp element.
349 : * (Deque handles that itself.) Only/All memory management is performed
350 : * here.
351 : * @endif
352 : */
353 : template<typename _Tp, typename _Alloc>
354 : class _Deque_base
355 : {
356 : public:
357 : typedef _Alloc allocator_type;
358 :
359 : allocator_type
360 1678719 : get_allocator() const
361 1678719 : { return _M_get_Tp_allocator(); }
362 :
363 : typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
364 : typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
365 :
366 3357438 : _Deque_base(const allocator_type& __a, size_t __num_elements)
367 3357438 : : _M_impl(__a)
368 3357438 : { _M_initialize_map(__num_elements); }
369 :
370 : _Deque_base(const allocator_type& __a)
371 : : _M_impl(__a)
372 : { }
373 :
374 : ~_Deque_base();
375 :
376 : protected:
377 : //This struct encapsulates the implementation of the std::deque
378 : //standard container and at the same time makes use of the EBO
379 : //for empty allocators.
380 : typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
381 :
382 : typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
383 :
384 : struct _Deque_impl
385 : : public _Tp_alloc_type
386 3357438 : {
387 : _Tp** _M_map;
388 : size_t _M_map_size;
389 : iterator _M_start;
390 : iterator _M_finish;
391 :
392 3357438 : _Deque_impl(const _Tp_alloc_type& __a)
393 : : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
394 3357438 : _M_start(), _M_finish()
395 3357438 : { }
396 : };
397 :
398 : _Tp_alloc_type&
399 5036157 : _M_get_Tp_allocator()
400 5036157 : { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
401 :
402 : const _Tp_alloc_type&
403 8393595 : _M_get_Tp_allocator() const
404 8393595 : { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
405 :
406 : _Map_alloc_type
407 6714876 : _M_get_map_allocator() const
408 6714876 : { return _M_get_Tp_allocator(); }
409 :
410 : _Tp*
411 3357438 : _M_allocate_node()
412 : {
413 3357438 : return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
414 : }
415 :
416 : void
417 3357438 : _M_deallocate_node(_Tp* __p)
418 : {
419 3357438 : _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
420 : }
421 :
422 : _Tp**
423 3357438 : _M_allocate_map(size_t __n)
424 3357438 : { return _M_get_map_allocator().allocate(__n); }
425 :
426 : void
427 3357438 : _M_deallocate_map(_Tp** __p, size_t __n)
428 3357438 : { _M_get_map_allocator().deallocate(__p, __n); }
429 :
430 : protected:
431 : void _M_initialize_map(size_t);
432 : void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
433 : void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
434 : enum { _S_initial_map_size = 8 };
435 :
436 : _Deque_impl _M_impl;
437 : };
438 :
439 : template<typename _Tp, typename _Alloc>
440 : _Deque_base<_Tp, _Alloc>::
441 3357438 : ~_Deque_base()
442 : {
443 3357438 : if (this->_M_impl._M_map)
444 : {
445 3357438 : _M_destroy_nodes(this->_M_impl._M_start._M_node,
446 : this->_M_impl._M_finish._M_node + 1);
447 3357438 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
448 : }
449 : }
450 :
451 : /**
452 : * @if maint
453 : * @brief Layout storage.
454 : * @param num_elements The count of T's for which to allocate space
455 : * at first.
456 : * @return Nothing.
457 : *
458 : * The initial underlying memory layout is a bit complicated...
459 : * @endif
460 : */
461 : template<typename _Tp, typename _Alloc>
462 : void
463 : _Deque_base<_Tp, _Alloc>::
464 3357438 : _M_initialize_map(size_t __num_elements)
465 : {
466 : const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
467 3357438 : + 1);
468 :
469 3357438 : this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
470 : size_t(__num_nodes + 2));
471 3357438 : this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
472 :
473 : // For "small" maps (needing less than _M_map_size nodes), allocation
474 : // starts in the middle elements and grows outwards. So nstart may be
475 : // the beginning of _M_map, but for small maps it may be as far in as
476 : // _M_map+3.
477 :
478 : _Tp** __nstart = (this->_M_impl._M_map
479 3357438 : + (this->_M_impl._M_map_size - __num_nodes) / 2);
480 3357438 : _Tp** __nfinish = __nstart + __num_nodes;
481 :
482 : try
483 3357438 : { _M_create_nodes(__nstart, __nfinish); }
484 0 : catch(...)
485 : {
486 0 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
487 0 : this->_M_impl._M_map = 0;
488 0 : this->_M_impl._M_map_size = 0;
489 0 : __throw_exception_again;
490 : }
491 :
492 3357438 : this->_M_impl._M_start._M_set_node(__nstart);
493 3357438 : this->_M_impl._M_finish._M_set_node(__nfinish - 1);
494 3357438 : this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
495 3357438 : this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
496 : + __num_elements
497 : % __deque_buf_size(sizeof(_Tp)));
498 : }
499 :
500 : template<typename _Tp, typename _Alloc>
501 : void
502 : _Deque_base<_Tp, _Alloc>::
503 3357438 : _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
504 : {
505 : _Tp** __cur;
506 : try
507 : {
508 6714876 : for (__cur = __nstart; __cur < __nfinish; ++__cur)
509 3357438 : *__cur = this->_M_allocate_node();
510 : }
511 0 : catch(...)
512 : {
513 0 : _M_destroy_nodes(__nstart, __cur);
514 3357438 : __throw_exception_again;
515 : }
516 : }
517 :
518 : template<typename _Tp, typename _Alloc>
519 : void
520 : _Deque_base<_Tp, _Alloc>::
521 3357438 : _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
522 : {
523 6714876 : for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
524 6714876 : _M_deallocate_node(*__n);
525 : }
526 :
527 : /**
528 : * @brief A standard container using fixed-size memory allocation and
529 : * constant-time manipulation of elements at either end.
530 : *
531 : * @ingroup Containers
532 : * @ingroup Sequences
533 : *
534 : * Meets the requirements of a <a href="tables.html#65">container</a>, a
535 : * <a href="tables.html#66">reversible container</a>, and a
536 : * <a href="tables.html#67">sequence</a>, including the
537 : * <a href="tables.html#68">optional sequence requirements</a>.
538 : *
539 : * In previous HP/SGI versions of deque, there was an extra template
540 : * parameter so users could control the node size. This extension turned
541 : * out to violate the C++ standard (it can be detected using template
542 : * template parameters), and it was removed.
543 : *
544 : * @if maint
545 : * Here's how a deque<Tp> manages memory. Each deque has 4 members:
546 : *
547 : * - Tp** _M_map
548 : * - size_t _M_map_size
549 : * - iterator _M_start, _M_finish
550 : *
551 : * map_size is at least 8. %map is an array of map_size
552 : * pointers-to-"nodes". (The name %map has nothing to do with the
553 : * std::map class, and "nodes" should not be confused with
554 : * std::list's usage of "node".)
555 : *
556 : * A "node" has no specific type name as such, but it is referred
557 : * to as "node" in this file. It is a simple array-of-Tp. If Tp
558 : * is very large, there will be one Tp element per node (i.e., an
559 : * "array" of one). For non-huge Tp's, node size is inversely
560 : * related to Tp size: the larger the Tp, the fewer Tp's will fit
561 : * in a node. The goal here is to keep the total size of a node
562 : * relatively small and constant over different Tp's, to improve
563 : * allocator efficiency.
564 : *
565 : * Not every pointer in the %map array will point to a node. If
566 : * the initial number of elements in the deque is small, the
567 : * /middle/ %map pointers will be valid, and the ones at the edges
568 : * will be unused. This same situation will arise as the %map
569 : * grows: available %map pointers, if any, will be on the ends. As
570 : * new nodes are created, only a subset of the %map's pointers need
571 : * to be copied "outward".
572 : *
573 : * Class invariants:
574 : * - For any nonsingular iterator i:
575 : * - i.node points to a member of the %map array. (Yes, you read that
576 : * correctly: i.node does not actually point to a node.) The member of
577 : * the %map array is what actually points to the node.
578 : * - i.first == *(i.node) (This points to the node (first Tp element).)
579 : * - i.last == i.first + node_size
580 : * - i.cur is a pointer in the range [i.first, i.last). NOTE:
581 : * the implication of this is that i.cur is always a dereferenceable
582 : * pointer, even if i is a past-the-end iterator.
583 : * - Start and Finish are always nonsingular iterators. NOTE: this
584 : * means that an empty deque must have one node, a deque with <N
585 : * elements (where N is the node buffer size) must have one node, a
586 : * deque with N through (2N-1) elements must have two nodes, etc.
587 : * - For every node other than start.node and finish.node, every
588 : * element in the node is an initialized object. If start.node ==
589 : * finish.node, then [start.cur, finish.cur) are initialized
590 : * objects, and the elements outside that range are uninitialized
591 : * storage. Otherwise, [start.cur, start.last) and [finish.first,
592 : * finish.cur) are initialized objects, and [start.first, start.cur)
593 : * and [finish.cur, finish.last) are uninitialized storage.
594 : * - [%map, %map + map_size) is a valid, non-empty range.
595 : * - [start.node, finish.node] is a valid range contained within
596 : * [%map, %map + map_size).
597 : * - A pointer in the range [%map, %map + map_size) points to an allocated
598 : * node if and only if the pointer is in the range
599 : * [start.node, finish.node].
600 : *
601 : * Here's the magic: nothing in deque is "aware" of the discontiguous
602 : * storage!
603 : *
604 : * The memory setup and layout occurs in the parent, _Base, and the iterator
605 : * class is entirely responsible for "leaping" from one node to the next.
606 : * All the implementation routines for deque itself work only through the
607 : * start and finish iterators. This keeps the routines simple and sane,
608 : * and we can use other standard algorithms as well.
609 : * @endif
610 : */
611 : template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
612 : class deque : protected _Deque_base<_Tp, _Alloc>
613 : {
614 : // concept requirements
615 : typedef typename _Alloc::value_type _Alloc_value_type;
616 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
617 : __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
618 :
619 : typedef _Deque_base<_Tp, _Alloc> _Base;
620 : typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
621 :
622 : public:
623 : typedef _Tp value_type;
624 : typedef typename _Tp_alloc_type::pointer pointer;
625 : typedef typename _Tp_alloc_type::const_pointer const_pointer;
626 : typedef typename _Tp_alloc_type::reference reference;
627 : typedef typename _Tp_alloc_type::const_reference const_reference;
628 : typedef typename _Base::iterator iterator;
629 : typedef typename _Base::const_iterator const_iterator;
630 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
631 : typedef std::reverse_iterator<iterator> reverse_iterator;
632 : typedef size_t size_type;
633 : typedef ptrdiff_t difference_type;
634 : typedef _Alloc allocator_type;
635 :
636 : protected:
637 : typedef pointer* _Map_pointer;
638 :
639 : static size_t _S_buffer_size()
640 : { return __deque_buf_size(sizeof(_Tp)); }
641 :
642 : // Functions controlling memory layout, and nothing else.
643 : using _Base::_M_initialize_map;
644 : using _Base::_M_create_nodes;
645 : using _Base::_M_destroy_nodes;
646 : using _Base::_M_allocate_node;
647 : using _Base::_M_deallocate_node;
648 : using _Base::_M_allocate_map;
649 : using _Base::_M_deallocate_map;
650 : using _Base::_M_get_Tp_allocator;
651 :
652 : /** @if maint
653 : * A total of four data members accumulated down the heirarchy.
654 : * May be accessed via _M_impl.*
655 : * @endif
656 : */
657 : using _Base::_M_impl;
658 :
659 : public:
660 : // [23.2.1.1] construct/copy/destroy
661 : // (assign() and get_allocator() are also listed in this section)
662 : /**
663 : * @brief Default constructor creates no elements.
664 : */
665 : explicit
666 1678719 : deque(const allocator_type& __a = allocator_type())
667 1678719 : : _Base(__a, 0) {}
668 :
669 : /**
670 : * @brief Create a %deque with copies of an exemplar element.
671 : * @param n The number of elements to initially create.
672 : * @param value An element to copy.
673 : *
674 : * This constructor fills the %deque with @a n copies of @a value.
675 : */
676 : explicit
677 : deque(size_type __n, const value_type& __value = value_type(),
678 : const allocator_type& __a = allocator_type())
679 : : _Base(__a, __n)
680 : { _M_fill_initialize(__value); }
681 :
682 : /**
683 : * @brief %Deque copy constructor.
684 : * @param x A %deque of identical element and allocator types.
685 : *
686 : * The newly-created %deque uses a copy of the allocation object used
687 : * by @a x.
688 : */
689 1678719 : deque(const deque& __x)
690 1678719 : : _Base(__x.get_allocator(), __x.size())
691 3357438 : { std::__uninitialized_copy_a(__x.begin(), __x.end(),
692 : this->_M_impl._M_start,
693 : _M_get_Tp_allocator()); }
694 :
695 : /**
696 : * @brief Builds a %deque from a range.
697 : * @param first An input iterator.
698 : * @param last An input iterator.
699 : *
700 : * Create a %deque consisting of copies of the elements from [first,
701 : * last).
702 : *
703 : * If the iterators are forward, bidirectional, or random-access, then
704 : * this will call the elements' copy constructor N times (where N is
705 : * distance(first,last)) and do no memory reallocation. But if only
706 : * input iterators are used, then this will do at most 2N calls to the
707 : * copy constructor, and logN memory reallocations.
708 : */
709 : template<typename _InputIterator>
710 : deque(_InputIterator __first, _InputIterator __last,
711 : const allocator_type& __a = allocator_type())
712 : : _Base(__a)
713 : {
714 : // Check whether it's an integral type. If so, it's not an iterator.
715 : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
716 : _M_initialize_dispatch(__first, __last, _Integral());
717 : }
718 :
719 : /**
720 : * The dtor only erases the elements, and note that if the elements
721 : * themselves are pointers, the pointed-to memory is not touched in any
722 : * way. Managing the pointer is the user's responsibilty.
723 : */
724 3357438 : ~deque()
725 3357438 : { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
726 : _M_get_Tp_allocator()); }
727 :
728 : /**
729 : * @brief %Deque assignment operator.
730 : * @param x A %deque of identical element and allocator types.
731 : *
732 : * All the elements of @a x are copied, but unlike the copy constructor,
733 : * the allocator object is not copied.
734 : */
735 : deque&
736 : operator=(const deque& __x);
737 :
738 : /**
739 : * @brief Assigns a given value to a %deque.
740 : * @param n Number of elements to be assigned.
741 : * @param val Value to be assigned.
742 : *
743 : * This function fills a %deque with @a n copies of the given
744 : * value. Note that the assignment completely changes the
745 : * %deque and that the resulting %deque's size is the same as
746 : * the number of elements assigned. Old data may be lost.
747 : */
748 : void
749 : assign(size_type __n, const value_type& __val)
750 : { _M_fill_assign(__n, __val); }
751 :
752 : /**
753 : * @brief Assigns a range to a %deque.
754 : * @param first An input iterator.
755 : * @param last An input iterator.
756 : *
757 : * This function fills a %deque with copies of the elements in the
758 : * range [first,last).
759 : *
760 : * Note that the assignment completely changes the %deque and that the
761 : * resulting %deque's size is the same as the number of elements
762 : * assigned. Old data may be lost.
763 : */
764 : template<typename _InputIterator>
765 : void
766 : assign(_InputIterator __first, _InputIterator __last)
767 : {
768 : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
769 : _M_assign_dispatch(__first, __last, _Integral());
770 : }
771 :
772 : /// Get a copy of the memory allocation object.
773 : allocator_type
774 1678719 : get_allocator() const
775 1678719 : { return _Base::get_allocator(); }
776 :
777 : // iterators
778 : /**
779 : * Returns a read/write iterator that points to the first element in the
780 : * %deque. Iteration is done in ordinary element order.
781 : */
782 : iterator
783 : begin()
784 : { return this->_M_impl._M_start; }
785 :
786 : /**
787 : * Returns a read-only (constant) iterator that points to the first
788 : * element in the %deque. Iteration is done in ordinary element order.
789 : */
790 : const_iterator
791 1678719 : begin() const
792 1678719 : { return this->_M_impl._M_start; }
793 :
794 : /**
795 : * Returns a read/write iterator that points one past the last
796 : * element in the %deque. Iteration is done in ordinary
797 : * element order.
798 : */
799 : iterator
800 7373155 : end()
801 7373155 : { return this->_M_impl._M_finish; }
802 :
803 : /**
804 : * Returns a read-only (constant) iterator that points one past
805 : * the last element in the %deque. Iteration is done in
806 : * ordinary element order.
807 : */
808 : const_iterator
809 1678719 : end() const
810 1678719 : { return this->_M_impl._M_finish; }
811 :
812 : /**
813 : * Returns a read/write reverse iterator that points to the
814 : * last element in the %deque. Iteration is done in reverse
815 : * element order.
816 : */
817 : reverse_iterator
818 : rbegin()
819 : { return reverse_iterator(this->_M_impl._M_finish); }
820 :
821 : /**
822 : * Returns a read-only (constant) reverse iterator that points
823 : * to the last element in the %deque. Iteration is done in
824 : * reverse element order.
825 : */
826 : const_reverse_iterator
827 : rbegin() const
828 : { return const_reverse_iterator(this->_M_impl._M_finish); }
829 :
830 : /**
831 : * Returns a read/write reverse iterator that points to one
832 : * before the first element in the %deque. Iteration is done
833 : * in reverse element order.
834 : */
835 : reverse_iterator
836 : rend() { return reverse_iterator(this->_M_impl._M_start); }
837 :
838 : /**
839 : * Returns a read-only (constant) reverse iterator that points
840 : * to one before the first element in the %deque. Iteration is
841 : * done in reverse element order.
842 : */
843 : const_reverse_iterator
844 : rend() const
845 : { return const_reverse_iterator(this->_M_impl._M_start); }
846 :
847 : // [23.2.1.2] capacity
848 : /** Returns the number of elements in the %deque. */
849 : size_type
850 1678719 : size() const
851 1678719 : { return this->_M_impl._M_finish - this->_M_impl._M_start; }
852 :
853 : /** Returns the size() of the largest possible %deque. */
854 : size_type
855 : max_size() const
856 : { return size_type(-1); }
857 :
858 : /**
859 : * @brief Resizes the %deque to the specified number of elements.
860 : * @param new_size Number of elements the %deque should contain.
861 : * @param x Data with which new elements should be populated.
862 : *
863 : * This function will %resize the %deque to the specified
864 : * number of elements. If the number is smaller than the
865 : * %deque's current size the %deque is truncated, otherwise the
866 : * %deque is extended and new elements are populated with given
867 : * data.
868 : */
869 : void
870 : resize(size_type __new_size, value_type __x = value_type())
871 : {
872 : const size_type __len = size();
873 : if (__new_size < __len)
874 : erase(this->_M_impl._M_start + __new_size, this->_M_impl._M_finish);
875 : else
876 : insert(this->_M_impl._M_finish, __new_size - __len, __x);
877 : }
878 :
879 : /**
880 : * Returns true if the %deque is empty. (Thus begin() would
881 : * equal end().)
882 : */
883 : bool
884 7373155 : empty() const
885 7373155 : { return this->_M_impl._M_finish == this->_M_impl._M_start; }
886 :
887 : // element access
888 : /**
889 : * @brief Subscript access to the data contained in the %deque.
890 : * @param n The index of the element for which data should be
891 : * accessed.
892 : * @return Read/write reference to data.
893 : *
894 : * This operator allows for easy, array-style, data access.
895 : * Note that data access with this operator is unchecked and
896 : * out_of_range lookups are not defined. (For checked lookups
897 : * see at().)
898 : */
899 : reference
900 : operator[](size_type __n)
901 : { return this->_M_impl._M_start[difference_type(__n)]; }
902 :
903 : /**
904 : * @brief Subscript access to the data contained in the %deque.
905 : * @param n The index of the element for which data should be
906 : * accessed.
907 : * @return Read-only (constant) reference to data.
908 : *
909 : * This operator allows for easy, array-style, data access.
910 : * Note that data access with this operator is unchecked and
911 : * out_of_range lookups are not defined. (For checked lookups
912 : * see at().)
913 : */
914 : const_reference
915 : operator[](size_type __n) const
916 : { return this->_M_impl._M_start[difference_type(__n)]; }
917 :
918 : protected:
919 : /// @if maint Safety check used only from at(). @endif
920 : void
921 : _M_range_check(size_type __n) const
922 : {
923 : if (__n >= this->size())
924 : __throw_out_of_range(__N("deque::_M_range_check"));
925 : }
926 :
927 : public:
928 : /**
929 : * @brief Provides access to the data contained in the %deque.
930 : * @param n The index of the element for which data should be
931 : * accessed.
932 : * @return Read/write reference to data.
933 : * @throw std::out_of_range If @a n is an invalid index.
934 : *
935 : * This function provides for safer data access. The parameter
936 : * is first checked that it is in the range of the deque. The
937 : * function throws out_of_range if the check fails.
938 : */
939 : reference
940 : at(size_type __n)
941 : {
942 : _M_range_check(__n);
943 : return (*this)[__n];
944 : }
945 :
946 : /**
947 : * @brief Provides access to the data contained in the %deque.
948 : * @param n The index of the element for which data should be
949 : * accessed.
950 : * @return Read-only (constant) reference to data.
951 : * @throw std::out_of_range If @a n is an invalid index.
952 : *
953 : * This function provides for safer data access. The parameter is first
954 : * checked that it is in the range of the deque. The function throws
955 : * out_of_range if the check fails.
956 : */
957 : const_reference
958 : at(size_type __n) const
959 : {
960 : _M_range_check(__n);
961 : return (*this)[__n];
962 : }
963 :
964 : /**
965 : * Returns a read/write reference to the data at the first
966 : * element of the %deque.
967 : */
968 : reference
969 : front()
970 : { return *begin(); }
971 :
972 : /**
973 : * Returns a read-only (constant) reference to the data at the first
974 : * element of the %deque.
975 : */
976 : const_reference
977 : front() const
978 : { return *begin(); }
979 :
980 : /**
981 : * Returns a read/write reference to the data at the last element of the
982 : * %deque.
983 : */
984 : reference
985 7373155 : back()
986 : {
987 7373155 : iterator __tmp = end();
988 7373155 : --__tmp;
989 7373155 : return *__tmp;
990 : }
991 :
992 : /**
993 : * Returns a read-only (constant) reference to the data at the last
994 : * element of the %deque.
995 : */
996 : const_reference
997 : back() const
998 : {
999 : const_iterator __tmp = end();
1000 : --__tmp;
1001 : return *__tmp;
1002 : }
1003 :
1004 : // [23.2.1.2] modifiers
1005 : /**
1006 : * @brief Add data to the front of the %deque.
1007 : * @param x Data to be added.
1008 : *
1009 : * This is a typical stack operation. The function creates an
1010 : * element at the front of the %deque and assigns the given
1011 : * data to it. Due to the nature of a %deque this operation
1012 : * can be done in constant time.
1013 : */
1014 : void
1015 : push_front(const value_type& __x)
1016 : {
1017 : if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1018 : {
1019 : this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
1020 : --this->_M_impl._M_start._M_cur;
1021 : }
1022 : else
1023 : _M_push_front_aux(__x);
1024 : }
1025 :
1026 : /**
1027 : * @brief Add data to the end of the %deque.
1028 : * @param x Data to be added.
1029 : *
1030 : * This is a typical stack operation. The function creates an
1031 : * element at the end of the %deque and assigns the given data
1032 : * to it. Due to the nature of a %deque this operation can be
1033 : * done in constant time.
1034 : */
1035 : void
1036 7579481 : push_back(const value_type& __x)
1037 : {
1038 7579481 : if (this->_M_impl._M_finish._M_cur
1039 : != this->_M_impl._M_finish._M_last - 1)
1040 : {
1041 7579481 : this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
1042 7579481 : ++this->_M_impl._M_finish._M_cur;
1043 : }
1044 : else
1045 0 : _M_push_back_aux(__x);
1046 : }
1047 :
1048 : /**
1049 : * @brief Removes first element.
1050 : *
1051 : * This is a typical stack operation. It shrinks the %deque by one.
1052 : *
1053 : * Note that no data is returned, and if the first element's data is
1054 : * needed, it should be retrieved before pop_front() is called.
1055 : */
1056 : void
1057 : pop_front()
1058 : {
1059 : if (this->_M_impl._M_start._M_cur
1060 : != this->_M_impl._M_start._M_last - 1)
1061 : {
1062 : this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
1063 : ++this->_M_impl._M_start._M_cur;
1064 : }
1065 : else
1066 : _M_pop_front_aux();
1067 : }
1068 :
1069 : /**
1070 : * @brief Removes last element.
1071 : *
1072 : * This is a typical stack operation. It shrinks the %deque by one.
1073 : *
1074 : * Note that no data is returned, and if the last element's data is
1075 : * needed, it should be retrieved before pop_back() is called.
1076 : */
1077 : void
1078 7579459 : pop_back()
1079 : {
1080 7579459 : if (this->_M_impl._M_finish._M_cur
1081 : != this->_M_impl._M_finish._M_first)
1082 : {
1083 7579459 : --this->_M_impl._M_finish._M_cur;
1084 7579459 : this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
1085 : }
1086 : else
1087 0 : _M_pop_back_aux();
1088 : }
1089 :
1090 : /**
1091 : * @brief Inserts given value into %deque before specified iterator.
1092 : * @param position An iterator into the %deque.
1093 : * @param x Data to be inserted.
1094 : * @return An iterator that points to the inserted data.
1095 : *
1096 : * This function will insert a copy of the given value before the
1097 : * specified location.
1098 : */
1099 : iterator
1100 : insert(iterator position, const value_type& __x);
1101 :
1102 : /**
1103 : * @brief Inserts a number of copies of given data into the %deque.
1104 : * @param position An iterator into the %deque.
1105 : * @param n Number of elements to be inserted.
1106 : * @param x Data to be inserted.
1107 : *
1108 : * This function will insert a specified number of copies of the given
1109 : * data before the location specified by @a position.
1110 : */
1111 : void
1112 : insert(iterator __position, size_type __n, const value_type& __x)
1113 : { _M_fill_insert(__position, __n, __x); }
1114 :
1115 : /**
1116 : * @brief Inserts a range into the %deque.
1117 : * @param position An iterator into the %deque.
1118 : * @param first An input iterator.
1119 : * @param last An input iterator.
1120 : *
1121 : * This function will insert copies of the data in the range
1122 : * [first,last) into the %deque before the location specified
1123 : * by @a pos. This is known as "range insert."
1124 : */
1125 : template<typename _InputIterator>
1126 : void
1127 : insert(iterator __position, _InputIterator __first,
1128 : _InputIterator __last)
1129 : {
1130 : // Check whether it's an integral type. If so, it's not an iterator.
1131 : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1132 : _M_insert_dispatch(__position, __first, __last, _Integral());
1133 : }
1134 :
1135 : /**
1136 : * @brief Remove element at given position.
1137 : * @param position Iterator pointing to element to be erased.
1138 : * @return An iterator pointing to the next element (or end()).
1139 : *
1140 : * This function will erase the element at the given position and thus
1141 : * shorten the %deque by one.
1142 : *
1143 : * The user is cautioned that
1144 : * this function only erases the element, and that if the element is
1145 : * itself a pointer, the pointed-to memory is not touched in any way.
1146 : * Managing the pointer is the user's responsibilty.
1147 : */
1148 : iterator
1149 : erase(iterator __position);
1150 :
1151 : /**
1152 : * @brief Remove a range of elements.
1153 : * @param first Iterator pointing to the first element to be erased.
1154 : * @param last Iterator pointing to one past the last element to be
1155 : * erased.
1156 : * @return An iterator pointing to the element pointed to by @a last
1157 : * prior to erasing (or end()).
1158 : *
1159 : * This function will erase the elements in the range [first,last) and
1160 : * shorten the %deque accordingly.
1161 : *
1162 : * The user is cautioned that
1163 : * this function only erases the elements, and that if the elements
1164 : * themselves are pointers, the pointed-to memory is not touched in any
1165 : * way. Managing the pointer is the user's responsibilty.
1166 : */
1167 : iterator
1168 : erase(iterator __first, iterator __last);
1169 :
1170 : /**
1171 : * @brief Swaps data with another %deque.
1172 : * @param x A %deque of the same element and allocator types.
1173 : *
1174 : * This exchanges the elements between two deques in constant time.
1175 : * (Four pointers, so it should be quite fast.)
1176 : * Note that the global std::swap() function is specialized such that
1177 : * std::swap(d1,d2) will feed to this function.
1178 : */
1179 : void
1180 : swap(deque& __x)
1181 : {
1182 : std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
1183 : std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
1184 : std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
1185 : std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
1186 : }
1187 :
1188 : /**
1189 : * Erases all the elements. Note that this function only erases the
1190 : * elements, and that if the elements themselves are pointers, the
1191 : * pointed-to memory is not touched in any way. Managing the pointer is
1192 : * the user's responsibilty.
1193 : */
1194 : void clear();
1195 :
1196 : protected:
1197 : // Internal constructor functions follow.
1198 :
1199 : // called by the range constructor to implement [23.1.1]/9
1200 : template<typename _Integer>
1201 : void
1202 : _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1203 : {
1204 : _M_initialize_map(__n);
1205 : _M_fill_initialize(__x);
1206 : }
1207 :
1208 : // called by the range constructor to implement [23.1.1]/9
1209 : template<typename _InputIterator>
1210 : void
1211 : _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1212 : __false_type)
1213 : {
1214 : typedef typename std::iterator_traits<_InputIterator>::
1215 : iterator_category _IterCategory;
1216 : _M_range_initialize(__first, __last, _IterCategory());
1217 : }
1218 :
1219 : // called by the second initialize_dispatch above
1220 : //@{
1221 : /**
1222 : * @if maint
1223 : * @brief Fills the deque with whatever is in [first,last).
1224 : * @param first An input iterator.
1225 : * @param last An input iterator.
1226 : * @return Nothing.
1227 : *
1228 : * If the iterators are actually forward iterators (or better), then the
1229 : * memory layout can be done all at once. Else we move forward using
1230 : * push_back on each value from the iterator.
1231 : * @endif
1232 : */
1233 : template<typename _InputIterator>
1234 : void
1235 : _M_range_initialize(_InputIterator __first, _InputIterator __last,
1236 : std::input_iterator_tag);
1237 :
1238 : // called by the second initialize_dispatch above
1239 : template<typename _ForwardIterator>
1240 : void
1241 : _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1242 : std::forward_iterator_tag);
1243 : //@}
1244 :
1245 : /**
1246 : * @if maint
1247 : * @brief Fills the %deque with copies of value.
1248 : * @param value Initial value.
1249 : * @return Nothing.
1250 : * @pre _M_start and _M_finish have already been initialized,
1251 : * but none of the %deque's elements have yet been constructed.
1252 : *
1253 : * This function is called only when the user provides an explicit size
1254 : * (with or without an explicit exemplar value).
1255 : * @endif
1256 : */
1257 : void
1258 : _M_fill_initialize(const value_type& __value);
1259 :
1260 : // Internal assign functions follow. The *_aux functions do the actual
1261 : // assignment work for the range versions.
1262 :
1263 : // called by the range assign to implement [23.1.1]/9
1264 : template<typename _Integer>
1265 : void
1266 : _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1267 : {
1268 : _M_fill_assign(static_cast<size_type>(__n),
1269 : static_cast<value_type>(__val));
1270 : }
1271 :
1272 : // called by the range assign to implement [23.1.1]/9
1273 : template<typename _InputIterator>
1274 : void
1275 : _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1276 : __false_type)
1277 : {
1278 : typedef typename std::iterator_traits<_InputIterator>::
1279 : iterator_category _IterCategory;
1280 : _M_assign_aux(__first, __last, _IterCategory());
1281 : }
1282 :
1283 : // called by the second assign_dispatch above
1284 : template<typename _InputIterator>
1285 : void
1286 : _M_assign_aux(_InputIterator __first, _InputIterator __last,
1287 : std::input_iterator_tag);
1288 :
1289 : // called by the second assign_dispatch above
1290 : template<typename _ForwardIterator>
1291 : void
1292 : _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1293 : std::forward_iterator_tag)
1294 : {
1295 : const size_type __len = std::distance(__first, __last);
1296 : if (__len > size())
1297 : {
1298 : _ForwardIterator __mid = __first;
1299 : std::advance(__mid, size());
1300 : std::copy(__first, __mid, begin());
1301 : insert(end(), __mid, __last);
1302 : }
1303 : else
1304 : erase(std::copy(__first, __last, begin()), end());
1305 : }
1306 :
1307 : // Called by assign(n,t), and the range assign when it turns out
1308 : // to be the same thing.
1309 : void
1310 : _M_fill_assign(size_type __n, const value_type& __val)
1311 : {
1312 : if (__n > size())
1313 : {
1314 : std::fill(begin(), end(), __val);
1315 : insert(end(), __n - size(), __val);
1316 : }
1317 : else
1318 : {
1319 : erase(begin() + __n, end());
1320 : std::fill(begin(), end(), __val);
1321 : }
1322 : }
1323 :
1324 : //@{
1325 : /**
1326 : * @if maint
1327 : * @brief Helper functions for push_* and pop_*.
1328 : * @endif
1329 : */
1330 : void _M_push_back_aux(const value_type&);
1331 : void _M_push_front_aux(const value_type&);
1332 : void _M_pop_back_aux();
1333 : void _M_pop_front_aux();
1334 : //@}
1335 :
1336 : // Internal insert functions follow. The *_aux functions do the actual
1337 : // insertion work when all shortcuts fail.
1338 :
1339 : // called by the range insert to implement [23.1.1]/9
1340 : template<typename _Integer>
1341 : void
1342 : _M_insert_dispatch(iterator __pos,
1343 : _Integer __n, _Integer __x, __true_type)
1344 : {
1345 : _M_fill_insert(__pos, static_cast<size_type>(__n),
1346 : static_cast<value_type>(__x));
1347 : }
1348 :
1349 : // called by the range insert to implement [23.1.1]/9
1350 : template<typename _InputIterator>
1351 : void
1352 : _M_insert_dispatch(iterator __pos,
1353 : _InputIterator __first, _InputIterator __last,
1354 : __false_type)
1355 : {
1356 : typedef typename std::iterator_traits<_InputIterator>::
1357 : iterator_category _IterCategory;
1358 : _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1359 : }
1360 :
1361 : // called by the second insert_dispatch above
1362 : template<typename _InputIterator>
1363 : void
1364 : _M_range_insert_aux(iterator __pos, _InputIterator __first,
1365 : _InputIterator __last, std::input_iterator_tag);
1366 :
1367 : // called by the second insert_dispatch above
1368 : template<typename _ForwardIterator>
1369 : void
1370 : _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1371 : _ForwardIterator __last, std::forward_iterator_tag);
1372 :
1373 : // Called by insert(p,n,x), and the range insert when it turns out to be
1374 : // the same thing. Can use fill functions in optimal situations,
1375 : // otherwise passes off to insert_aux(p,n,x).
1376 : void
1377 : _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1378 :
1379 : // called by insert(p,x)
1380 : iterator
1381 : _M_insert_aux(iterator __pos, const value_type& __x);
1382 :
1383 : // called by insert(p,n,x) via fill_insert
1384 : void
1385 : _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1386 :
1387 : // called by range_insert_aux for forward iterators
1388 : template<typename _ForwardIterator>
1389 : void
1390 : _M_insert_aux(iterator __pos,
1391 : _ForwardIterator __first, _ForwardIterator __last,
1392 : size_type __n);
1393 :
1394 : //@{
1395 : /**
1396 : * @if maint
1397 : * @brief Memory-handling helpers for the previous internal insert
1398 : * functions.
1399 : * @endif
1400 : */
1401 : iterator
1402 : _M_reserve_elements_at_front(size_type __n)
1403 : {
1404 : const size_type __vacancies = this->_M_impl._M_start._M_cur
1405 : - this->_M_impl._M_start._M_first;
1406 : if (__n > __vacancies)
1407 : _M_new_elements_at_front(__n - __vacancies);
1408 : return this->_M_impl._M_start - difference_type(__n);
1409 : }
1410 :
1411 : iterator
1412 : _M_reserve_elements_at_back(size_type __n)
1413 : {
1414 : const size_type __vacancies = (this->_M_impl._M_finish._M_last
1415 : - this->_M_impl._M_finish._M_cur) - 1;
1416 : if (__n > __vacancies)
1417 : _M_new_elements_at_back(__n - __vacancies);
1418 : return this->_M_impl._M_finish + difference_type(__n);
1419 : }
1420 :
1421 : void
1422 : _M_new_elements_at_front(size_type __new_elements);
1423 :
1424 : void
1425 : _M_new_elements_at_back(size_type __new_elements);
1426 : //@}
1427 :
1428 :
1429 : //@{
1430 : /**
1431 : * @if maint
1432 : * @brief Memory-handling helpers for the major %map.
1433 : *
1434 : * Makes sure the _M_map has space for new nodes. Does not
1435 : * actually add the nodes. Can invalidate _M_map pointers.
1436 : * (And consequently, %deque iterators.)
1437 : * @endif
1438 : */
1439 : void
1440 0 : _M_reserve_map_at_back (size_type __nodes_to_add = 1)
1441 : {
1442 0 : if (__nodes_to_add + 1 > this->_M_impl._M_map_size
1443 : - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
1444 0 : _M_reallocate_map(__nodes_to_add, false);
1445 : }
1446 :
1447 : void
1448 : _M_reserve_map_at_front (size_type __nodes_to_add = 1)
1449 : {
1450 : if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
1451 : - this->_M_impl._M_map))
1452 : _M_reallocate_map(__nodes_to_add, true);
1453 : }
1454 :
1455 : void
1456 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1457 : //@}
1458 : };
1459 :
1460 :
1461 : /**
1462 : * @brief Deque equality comparison.
1463 : * @param x A %deque.
1464 : * @param y A %deque of the same type as @a x.
1465 : * @return True iff the size and elements of the deques are equal.
1466 : *
1467 : * This is an equivalence relation. It is linear in the size of the
1468 : * deques. Deques are considered equivalent if their sizes are equal,
1469 : * and if corresponding elements compare equal.
1470 : */
1471 : template<typename _Tp, typename _Alloc>
1472 : inline bool
1473 : operator==(const deque<_Tp, _Alloc>& __x,
1474 : const deque<_Tp, _Alloc>& __y)
1475 : { return __x.size() == __y.size()
1476 : && std::equal(__x.begin(), __x.end(), __y.begin()); }
1477 :
1478 : /**
1479 : * @brief Deque ordering relation.
1480 : * @param x A %deque.
1481 : * @param y A %deque of the same type as @a x.
1482 : * @return True iff @a x is lexicographically less than @a y.
1483 : *
1484 : * This is a total ordering relation. It is linear in the size of the
1485 : * deques. The elements must be comparable with @c <.
1486 : *
1487 : * See std::lexicographical_compare() for how the determination is made.
1488 : */
1489 : template<typename _Tp, typename _Alloc>
1490 : inline bool
1491 : operator<(const deque<_Tp, _Alloc>& __x,
1492 : const deque<_Tp, _Alloc>& __y)
1493 : { return lexicographical_compare(__x.begin(), __x.end(),
1494 : __y.begin(), __y.end()); }
1495 :
1496 : /// Based on operator==
1497 : template<typename _Tp, typename _Alloc>
1498 : inline bool
1499 : operator!=(const deque<_Tp, _Alloc>& __x,
1500 : const deque<_Tp, _Alloc>& __y)
1501 : { return !(__x == __y); }
1502 :
1503 : /// Based on operator<
1504 : template<typename _Tp, typename _Alloc>
1505 : inline bool
1506 : operator>(const deque<_Tp, _Alloc>& __x,
1507 : const deque<_Tp, _Alloc>& __y)
1508 : { return __y < __x; }
1509 :
1510 : /// Based on operator<
1511 : template<typename _Tp, typename _Alloc>
1512 : inline bool
1513 : operator<=(const deque<_Tp, _Alloc>& __x,
1514 : const deque<_Tp, _Alloc>& __y)
1515 : { return !(__y < __x); }
1516 :
1517 : /// Based on operator<
1518 : template<typename _Tp, typename _Alloc>
1519 : inline bool
1520 : operator>=(const deque<_Tp, _Alloc>& __x,
1521 : const deque<_Tp, _Alloc>& __y)
1522 : { return !(__x < __y); }
1523 :
1524 : /// See std::deque::swap().
1525 : template<typename _Tp, typename _Alloc>
1526 : inline void
1527 : swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
1528 : { __x.swap(__y); }
1529 : } // namespace std
1530 :
1531 : #endif /* _DEQUE_H */
|
