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