1// Deque implementation -*- C++ -*-
2
3// Copyright (C) 2001-2021 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 3, 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// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_deque.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{deque}
54 */
55
56#ifndef _STL_DEQUE_H
57#define _STL_DEQUE_H 1
58
59#include <bits/concept_check.h>
60#include <bits/stl_iterator_base_types.h>
61#include <bits/stl_iterator_base_funcs.h>
62#if __cplusplus >= 201103L
63#include <initializer_list>
64#include <bits/stl_uninitialized.h> // for __is_bitwise_relocatable
65#endif
66#if __cplusplus > 201703L
67# include <compare>
68#endif
69
70#include <debug/assertions.h>
71
72namespace std _GLIBCXX_VISIBILITY(default)
73{
74_GLIBCXX_BEGIN_NAMESPACE_VERSION
75_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
76
77 /**
78 * @brief This function controls the size of memory nodes.
79 * @param __size The size of an element.
80 * @return The number (not byte size) of elements per node.
81 *
82 * This function started off as a compiler kludge from SGI, but
83 * seems to be a useful wrapper around a repeated constant
84 * expression. The @b 512 is tunable (and no other code needs to
85 * change), but no investigation has been done since inheriting the
86 * SGI code. Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
87 * you are doing, however: changing it breaks the binary
88 * compatibility!!
89 */
90
91#ifndef _GLIBCXX_DEQUE_BUF_SIZE
92#define _GLIBCXX_DEQUE_BUF_SIZE 512
93#endif
94
95 _GLIBCXX_CONSTEXPR inline size_t
96 __deque_buf_size(size_t __size)
97 { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
98 ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
99
100
101 /**
102 * @brief A deque::iterator.
103 *
104 * Quite a bit of intelligence here. Much of the functionality of
105 * deque is actually passed off to this class. A deque holds two
106 * of these internally, marking its valid range. Access to
107 * elements is done as offsets of either of those two, relying on
108 * operator overloading in this class.
109 *
110 * All the functions are op overloads except for _M_set_node.
111 */
112 template<typename _Tp, typename _Ref, typename _Ptr>
113 struct _Deque_iterator
114 {
115#if __cplusplus < 201103L
116 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
117 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
118 typedef _Tp* _Elt_pointer;
119 typedef _Tp** _Map_pointer;
120#else
121 private:
122 template<typename _CvTp>
123 using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_rebind<_Ptr, _CvTp>>;
124 public:
125 typedef __iter<_Tp> iterator;
126 typedef __iter<const _Tp> const_iterator;
127 typedef __ptr_rebind<_Ptr, _Tp> _Elt_pointer;
128 typedef __ptr_rebind<_Ptr, _Elt_pointer> _Map_pointer;
129#endif
130
131 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
132 { return __deque_buf_size(size: sizeof(_Tp)); }
133
134 typedef std::random_access_iterator_tag iterator_category;
135 typedef _Tp value_type;
136 typedef _Ptr pointer;
137 typedef _Ref reference;
138 typedef size_t size_type;
139 typedef ptrdiff_t difference_type;
140 typedef _Deque_iterator _Self;
141
142 _Elt_pointer _M_cur;
143 _Elt_pointer _M_first;
144 _Elt_pointer _M_last;
145 _Map_pointer _M_node;
146
147 _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT
148 : _M_cur(__x), _M_first(*__y),
149 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
150
151 _Deque_iterator() _GLIBCXX_NOEXCEPT
152 : _M_cur(), _M_first(), _M_last(), _M_node() { }
153
154#if __cplusplus < 201103L
155 // Conversion from iterator to const_iterator.
156 _Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
157 : _M_cur(__x._M_cur), _M_first(__x._M_first),
158 _M_last(__x._M_last), _M_node(__x._M_node) { }
159#else
160 // Conversion from iterator to const_iterator.
161 template<typename _Iter,
162 typename = _Require<is_same<_Self, const_iterator>,
163 is_same<_Iter, iterator>>>
164 _Deque_iterator(const _Iter& __x) noexcept
165 : _M_cur(__x._M_cur), _M_first(__x._M_first),
166 _M_last(__x._M_last), _M_node(__x._M_node) { }
167
168 _Deque_iterator(const _Deque_iterator& __x) noexcept
169 : _M_cur(__x._M_cur), _M_first(__x._M_first),
170 _M_last(__x._M_last), _M_node(__x._M_node) { }
171
172 _Deque_iterator& operator=(const _Deque_iterator&) = default;
173#endif
174
175 iterator
176 _M_const_cast() const _GLIBCXX_NOEXCEPT
177 { return iterator(_M_cur, _M_node); }
178
179 reference
180 operator*() const _GLIBCXX_NOEXCEPT
181 { return *_M_cur; }
182
183 pointer
184 operator->() const _GLIBCXX_NOEXCEPT
185 { return _M_cur; }
186
187 _Self&
188 operator++() _GLIBCXX_NOEXCEPT
189 {
190 ++_M_cur;
191 if (_M_cur == _M_last)
192 {
193 _M_set_node(new_node: _M_node + 1);
194 _M_cur = _M_first;
195 }
196 return *this;
197 }
198
199 _Self
200 operator++(int) _GLIBCXX_NOEXCEPT
201 {
202 _Self __tmp = *this;
203 ++*this;
204 return __tmp;
205 }
206
207 _Self&
208 operator--() _GLIBCXX_NOEXCEPT
209 {
210 if (_M_cur == _M_first)
211 {
212 _M_set_node(new_node: _M_node - 1);
213 _M_cur = _M_last;
214 }
215 --_M_cur;
216 return *this;
217 }
218
219 _Self
220 operator--(int) _GLIBCXX_NOEXCEPT
221 {
222 _Self __tmp = *this;
223 --*this;
224 return __tmp;
225 }
226
227 _Self&
228 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
229 {
230 const difference_type __offset = __n + (_M_cur - _M_first);
231 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
232 _M_cur += __n;
233 else
234 {
235 const difference_type __node_offset =
236 __offset > 0 ? __offset / difference_type(_S_buffer_size())
237 : -difference_type((-__offset - 1)
238 / _S_buffer_size()) - 1;
239 _M_set_node(new_node: _M_node + __node_offset);
240 _M_cur = _M_first + (__offset - __node_offset
241 * difference_type(_S_buffer_size()));
242 }
243 return *this;
244 }
245
246 _Self&
247 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
248 { return *this += -__n; }
249
250 reference
251 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
252 { return *(*this + __n); }
253
254 /**
255 * Prepares to traverse new_node. Sets everything except
256 * _M_cur, which should therefore be set by the caller
257 * immediately afterwards, based on _M_first and _M_last.
258 */
259 void
260 _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
261 {
262 _M_node = __new_node;
263 _M_first = *__new_node;
264 _M_last = _M_first + difference_type(_S_buffer_size());
265 }
266
267 friend bool
268 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
269 { return __x._M_cur == __y._M_cur; }
270
271 // Note: we also provide overloads whose operands are of the same type in
272 // order to avoid ambiguous overload resolution when std::rel_ops
273 // operators are in scope (for additional details, see libstdc++/3628)
274 template<typename _RefR, typename _PtrR>
275 friend bool
276 operator==(const _Self& __x,
277 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
278 _GLIBCXX_NOEXCEPT
279 { return __x._M_cur == __y._M_cur; }
280
281#if __cpp_lib_three_way_comparison
282 friend strong_ordering
283 operator<=>(const _Self& __x, const _Self& __y) noexcept
284 {
285 if (const auto __cmp = __x._M_node <=> __y._M_node; __cmp != 0)
286 return __cmp;
287 return __x._M_cur <=> __y._M_cur;
288 }
289#else
290 friend bool
291 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
292 { return !(__x == __y); }
293
294 template<typename _RefR, typename _PtrR>
295 friend bool
296 operator!=(const _Self& __x,
297 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
298 _GLIBCXX_NOEXCEPT
299 { return !(__x == __y); }
300
301 friend bool
302 operator<(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
303 {
304 return (__x._M_node == __y._M_node)
305 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
306 }
307
308 template<typename _RefR, typename _PtrR>
309 friend bool
310 operator<(const _Self& __x,
311 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
312 _GLIBCXX_NOEXCEPT
313 {
314 return (__x._M_node == __y._M_node)
315 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
316 }
317
318 friend bool
319 operator>(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
320 { return __y < __x; }
321
322 template<typename _RefR, typename _PtrR>
323 friend bool
324 operator>(const _Self& __x,
325 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
326 _GLIBCXX_NOEXCEPT
327 { return __y < __x; }
328
329 friend bool
330 operator<=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
331 { return !(__y < __x); }
332
333 template<typename _RefR, typename _PtrR>
334 friend bool
335 operator<=(const _Self& __x,
336 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
337 _GLIBCXX_NOEXCEPT
338 { return !(__y < __x); }
339
340 friend bool
341 operator>=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
342 { return !(__x < __y); }
343
344 template<typename _RefR, typename _PtrR>
345 friend bool
346 operator>=(const _Self& __x,
347 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
348 _GLIBCXX_NOEXCEPT
349 { return !(__x < __y); }
350#endif // three-way comparison
351
352 friend difference_type
353 operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
354 {
355 return difference_type(_S_buffer_size())
356 * (__x._M_node - __y._M_node - bool(__x._M_node))
357 + (__x._M_cur - __x._M_first)
358 + (__y._M_last - __y._M_cur);
359 }
360
361 // _GLIBCXX_RESOLVE_LIB_DEFECTS
362 // According to the resolution of DR179 not only the various comparison
363 // operators but also operator- must accept mixed iterator/const_iterator
364 // parameters.
365 template<typename _RefR, typename _PtrR>
366 friend difference_type
367 operator-(const _Self& __x,
368 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
369 _GLIBCXX_NOEXCEPT
370 {
371 return difference_type(_S_buffer_size())
372 * (__x._M_node - __y._M_node - bool(__x._M_node))
373 + (__x._M_cur - __x._M_first)
374 + (__y._M_last - __y._M_cur);
375 }
376
377 friend _Self
378 operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
379 {
380 _Self __tmp = __x;
381 __tmp += __n;
382 return __tmp;
383 }
384
385 friend _Self
386 operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
387 {
388 _Self __tmp = __x;
389 __tmp -= __n;
390 return __tmp;
391 }
392
393 friend _Self
394 operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
395 { return __x + __n; }
396 };
397
398 /**
399 * Deque base class. This class provides the unified face for %deque's
400 * allocation. This class's constructor and destructor allocate and
401 * deallocate (but do not initialize) storage. This makes %exception
402 * safety easier.
403 *
404 * Nothing in this class ever constructs or destroys an actual Tp element.
405 * (Deque handles that itself.) Only/All memory management is performed
406 * here.
407 */
408 template<typename _Tp, typename _Alloc>
409 class _Deque_base
410 {
411 protected:
412 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
413 rebind<_Tp>::other _Tp_alloc_type;
414 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
415
416#if __cplusplus < 201103L
417 typedef _Tp* _Ptr;
418 typedef const _Tp* _Ptr_const;
419#else
420 typedef typename _Alloc_traits::pointer _Ptr;
421 typedef typename _Alloc_traits::const_pointer _Ptr_const;
422#endif
423
424 typedef typename _Alloc_traits::template rebind<_Ptr>::other
425 _Map_alloc_type;
426 typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
427
428 typedef _Alloc allocator_type;
429
430 allocator_type
431 get_allocator() const _GLIBCXX_NOEXCEPT
432 { return allocator_type(_M_get_Tp_allocator()); }
433
434 typedef _Deque_iterator<_Tp, _Tp&, _Ptr> iterator;
435 typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const> const_iterator;
436
437 _Deque_base()
438 : _M_impl()
439 { _M_initialize_map(0); }
440
441 _Deque_base(size_t __num_elements)
442 : _M_impl()
443 { _M_initialize_map(__num_elements); }
444
445 _Deque_base(const allocator_type& __a, size_t __num_elements)
446 : _M_impl(__a)
447 { _M_initialize_map(__num_elements); }
448
449 _Deque_base(const allocator_type& __a)
450 : _M_impl(__a)
451 { /* Caller must initialize map. */ }
452
453#if __cplusplus >= 201103L
454 _Deque_base(_Deque_base&& __x)
455 : _M_impl(std::move(__x._M_get_Tp_allocator()))
456 {
457 _M_initialize_map(0);
458 if (__x._M_impl._M_map)
459 this->_M_impl._M_swap_data(__x._M_impl);
460 }
461
462 _Deque_base(_Deque_base&& __x, const allocator_type& __a)
463 : _M_impl(std::move(__x._M_impl), _Tp_alloc_type(__a))
464 { __x._M_initialize_map(0); }
465
466 _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_t __n)
467 : _M_impl(__a)
468 {
469 if (__x.get_allocator() == __a)
470 {
471 if (__x._M_impl._M_map)
472 {
473 _M_initialize_map(0);
474 this->_M_impl._M_swap_data(__x._M_impl);
475 }
476 }
477 else
478 {
479 _M_initialize_map(__n);
480 }
481 }
482#endif
483
484 ~_Deque_base() _GLIBCXX_NOEXCEPT;
485
486 typedef typename iterator::_Map_pointer _Map_pointer;
487
488 struct _Deque_impl_data
489 {
490 _Map_pointer _M_map;
491 size_t _M_map_size;
492 iterator _M_start;
493 iterator _M_finish;
494
495 _Deque_impl_data() _GLIBCXX_NOEXCEPT
496 : _M_map(), _M_map_size(), _M_start(), _M_finish()
497 { }
498
499#if __cplusplus >= 201103L
500 _Deque_impl_data(const _Deque_impl_data&) = default;
501 _Deque_impl_data&
502 operator=(const _Deque_impl_data&) = default;
503
504 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
505 : _Deque_impl_data(__x)
506 { __x = _Deque_impl_data(); }
507#endif
508
509 void
510 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
511 {
512 // Do not use std::swap(_M_start, __x._M_start), etc as it loses
513 // information used by TBAA.
514 std::swap(*this, __x);
515 }
516 };
517
518 // This struct encapsulates the implementation of the std::deque
519 // standard container and at the same time makes use of the EBO
520 // for empty allocators.
521 struct _Deque_impl
522 : public _Tp_alloc_type, public _Deque_impl_data
523 {
524 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
525 is_nothrow_default_constructible<_Tp_alloc_type>::value)
526 : _Tp_alloc_type()
527 { }
528
529 _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
530 : _Tp_alloc_type(__a)
531 { }
532
533#if __cplusplus >= 201103L
534 _Deque_impl(_Deque_impl&&) = default;
535
536 _Deque_impl(_Tp_alloc_type&& __a) noexcept
537 : _Tp_alloc_type(std::move(__a))
538 { }
539
540 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
541 : _Tp_alloc_type(std::move(__a)), _Deque_impl_data(std::move(__d))
542 { }
543#endif
544 };
545
546 _Tp_alloc_type&
547 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
548 { return this->_M_impl; }
549
550 const _Tp_alloc_type&
551 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
552 { return this->_M_impl; }
553
554 _Map_alloc_type
555 _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
556 { return _Map_alloc_type(_M_get_Tp_allocator()); }
557
558 _Ptr
559 _M_allocate_node()
560 {
561 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
562 return _Traits::allocate(_M_impl, __deque_buf_size(size: sizeof(_Tp)));
563 }
564
565 void
566 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
567 {
568 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
569 _Traits::deallocate(_M_impl, __p, __deque_buf_size(size: sizeof(_Tp)));
570 }
571
572 _Map_pointer
573 _M_allocate_map(size_t __n)
574 {
575 _Map_alloc_type __map_alloc = _M_get_map_allocator();
576 return _Map_alloc_traits::allocate(__map_alloc, __n);
577 }
578
579 void
580 _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
581 {
582 _Map_alloc_type __map_alloc = _M_get_map_allocator();
583 _Map_alloc_traits::deallocate(__map_alloc, __p, __n);
584 }
585
586 void _M_initialize_map(size_t);
587 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
588 void _M_destroy_nodes(_Map_pointer __nstart,
589 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
590 enum { _S_initial_map_size = 8 };
591
592 _Deque_impl _M_impl;
593 };
594
595 template<typename _Tp, typename _Alloc>
596 _Deque_base<_Tp, _Alloc>::
597 ~_Deque_base() _GLIBCXX_NOEXCEPT
598 {
599 if (this->_M_impl._M_map)
600 {
601 _M_destroy_nodes(nstart: this->_M_impl._M_start._M_node,
602 nfinish: this->_M_impl._M_finish._M_node + 1);
603 _M_deallocate_map(p: this->_M_impl._M_map, n: this->_M_impl._M_map_size);
604 }
605 }
606
607 /**
608 * @brief Layout storage.
609 * @param __num_elements The count of T's for which to allocate space
610 * at first.
611 * @return Nothing.
612 *
613 * The initial underlying memory layout is a bit complicated...
614 */
615 template<typename _Tp, typename _Alloc>
616 void
617 _Deque_base<_Tp, _Alloc>::
618 _M_initialize_map(size_t __num_elements)
619 {
620 const size_t __num_nodes = (__num_elements / __deque_buf_size(size: sizeof(_Tp))
621 + 1);
622
623 this->_M_impl._M_map_size = std::max(a: (size_t) _S_initial_map_size,
624 b: size_t(__num_nodes + 2));
625 this->_M_impl._M_map = _M_allocate_map(n: this->_M_impl._M_map_size);
626
627 // For "small" maps (needing less than _M_map_size nodes), allocation
628 // starts in the middle elements and grows outwards. So nstart may be
629 // the beginning of _M_map, but for small maps it may be as far in as
630 // _M_map+3.
631
632 _Map_pointer __nstart = (this->_M_impl._M_map
633 + (this->_M_impl._M_map_size - __num_nodes) / 2);
634 _Map_pointer __nfinish = __nstart + __num_nodes;
635
636 __try
637 { _M_create_nodes(__nstart, __nfinish); }
638 __catch(...)
639 {
640 _M_deallocate_map(p: this->_M_impl._M_map, n: this->_M_impl._M_map_size);
641 this->_M_impl._M_map = _Map_pointer();
642 this->_M_impl._M_map_size = 0;
643 __throw_exception_again;
644 }
645
646 this->_M_impl._M_start._M_set_node(__nstart);
647 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
648 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
649 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
650 + __num_elements
651 % __deque_buf_size(size: sizeof(_Tp)));
652 }
653
654 template<typename _Tp, typename _Alloc>
655 void
656 _Deque_base<_Tp, _Alloc>::
657 _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish)
658 {
659 _Map_pointer __cur;
660 __try
661 {
662 for (__cur = __nstart; __cur < __nfinish; ++__cur)
663 *__cur = this->_M_allocate_node();
664 }
665 __catch(...)
666 {
667 _M_destroy_nodes(__nstart, nfinish: __cur);
668 __throw_exception_again;
669 }
670 }
671
672 template<typename _Tp, typename _Alloc>
673 void
674 _Deque_base<_Tp, _Alloc>::
675 _M_destroy_nodes(_Map_pointer __nstart,
676 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
677 {
678 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
679 _M_deallocate_node(p: *__n);
680 }
681
682 /**
683 * @brief A standard container using fixed-size memory allocation and
684 * constant-time manipulation of elements at either end.
685 *
686 * @ingroup sequences
687 *
688 * @tparam _Tp Type of element.
689 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
690 *
691 * Meets the requirements of a <a href="tables.html#65">container</a>, a
692 * <a href="tables.html#66">reversible container</a>, and a
693 * <a href="tables.html#67">sequence</a>, including the
694 * <a href="tables.html#68">optional sequence requirements</a>.
695 *
696 * In previous HP/SGI versions of deque, there was an extra template
697 * parameter so users could control the node size. This extension turned
698 * out to violate the C++ standard (it can be detected using template
699 * template parameters), and it was removed.
700 *
701 * Here's how a deque<Tp> manages memory. Each deque has 4 members:
702 *
703 * - Tp** _M_map
704 * - size_t _M_map_size
705 * - iterator _M_start, _M_finish
706 *
707 * map_size is at least 8. %map is an array of map_size
708 * pointers-to-@a nodes. (The name %map has nothing to do with the
709 * std::map class, and @b nodes should not be confused with
710 * std::list's usage of @a node.)
711 *
712 * A @a node has no specific type name as such, but it is referred
713 * to as @a node in this file. It is a simple array-of-Tp. If Tp
714 * is very large, there will be one Tp element per node (i.e., an
715 * @a array of one). For non-huge Tp's, node size is inversely
716 * related to Tp size: the larger the Tp, the fewer Tp's will fit
717 * in a node. The goal here is to keep the total size of a node
718 * relatively small and constant over different Tp's, to improve
719 * allocator efficiency.
720 *
721 * Not every pointer in the %map array will point to a node. If
722 * the initial number of elements in the deque is small, the
723 * /middle/ %map pointers will be valid, and the ones at the edges
724 * will be unused. This same situation will arise as the %map
725 * grows: available %map pointers, if any, will be on the ends. As
726 * new nodes are created, only a subset of the %map's pointers need
727 * to be copied @a outward.
728 *
729 * Class invariants:
730 * - For any nonsingular iterator i:
731 * - i.node points to a member of the %map array. (Yes, you read that
732 * correctly: i.node does not actually point to a node.) The member of
733 * the %map array is what actually points to the node.
734 * - i.first == *(i.node) (This points to the node (first Tp element).)
735 * - i.last == i.first + node_size
736 * - i.cur is a pointer in the range [i.first, i.last). NOTE:
737 * the implication of this is that i.cur is always a dereferenceable
738 * pointer, even if i is a past-the-end iterator.
739 * - Start and Finish are always nonsingular iterators. NOTE: this
740 * means that an empty deque must have one node, a deque with <N
741 * elements (where N is the node buffer size) must have one node, a
742 * deque with N through (2N-1) elements must have two nodes, etc.
743 * - For every node other than start.node and finish.node, every
744 * element in the node is an initialized object. If start.node ==
745 * finish.node, then [start.cur, finish.cur) are initialized
746 * objects, and the elements outside that range are uninitialized
747 * storage. Otherwise, [start.cur, start.last) and [finish.first,
748 * finish.cur) are initialized objects, and [start.first, start.cur)
749 * and [finish.cur, finish.last) are uninitialized storage.
750 * - [%map, %map + map_size) is a valid, non-empty range.
751 * - [start.node, finish.node] is a valid range contained within
752 * [%map, %map + map_size).
753 * - A pointer in the range [%map, %map + map_size) points to an allocated
754 * node if and only if the pointer is in the range
755 * [start.node, finish.node].
756 *
757 * Here's the magic: nothing in deque is @b aware of the discontiguous
758 * storage!
759 *
760 * The memory setup and layout occurs in the parent, _Base, and the iterator
761 * class is entirely responsible for @a leaping from one node to the next.
762 * All the implementation routines for deque itself work only through the
763 * start and finish iterators. This keeps the routines simple and sane,
764 * and we can use other standard algorithms as well.
765 */
766 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
767 class deque : protected _Deque_base<_Tp, _Alloc>
768 {
769#ifdef _GLIBCXX_CONCEPT_CHECKS
770 // concept requirements
771 typedef typename _Alloc::value_type _Alloc_value_type;
772# if __cplusplus < 201103L
773 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
774# endif
775 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
776#endif
777
778#if __cplusplus >= 201103L
779 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
780 "std::deque must have a non-const, non-volatile value_type");
781# if __cplusplus > 201703L || defined __STRICT_ANSI__
782 static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
783 "std::deque must have the same value_type as its allocator");
784# endif
785#endif
786
787 typedef _Deque_base<_Tp, _Alloc> _Base;
788 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
789 typedef typename _Base::_Alloc_traits _Alloc_traits;
790 typedef typename _Base::_Map_pointer _Map_pointer;
791
792 public:
793 typedef _Tp value_type;
794 typedef typename _Alloc_traits::pointer pointer;
795 typedef typename _Alloc_traits::const_pointer const_pointer;
796 typedef typename _Alloc_traits::reference reference;
797 typedef typename _Alloc_traits::const_reference const_reference;
798 typedef typename _Base::iterator iterator;
799 typedef typename _Base::const_iterator const_iterator;
800 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
801 typedef std::reverse_iterator<iterator> reverse_iterator;
802 typedef size_t size_type;
803 typedef ptrdiff_t difference_type;
804 typedef _Alloc allocator_type;
805
806 private:
807 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
808 { return __deque_buf_size(size: sizeof(_Tp)); }
809
810 // Functions controlling memory layout, and nothing else.
811 using _Base::_M_initialize_map;
812 using _Base::_M_create_nodes;
813 using _Base::_M_destroy_nodes;
814 using _Base::_M_allocate_node;
815 using _Base::_M_deallocate_node;
816 using _Base::_M_allocate_map;
817 using _Base::_M_deallocate_map;
818 using _Base::_M_get_Tp_allocator;
819
820 /**
821 * A total of four data members accumulated down the hierarchy.
822 * May be accessed via _M_impl.*
823 */
824 using _Base::_M_impl;
825
826 public:
827 // [23.2.1.1] construct/copy/destroy
828 // (assign() and get_allocator() are also listed in this section)
829
830 /**
831 * @brief Creates a %deque with no elements.
832 */
833#if __cplusplus >= 201103L
834 deque() = default;
835#else
836 deque() { }
837#endif
838
839 /**
840 * @brief Creates a %deque with no elements.
841 * @param __a An allocator object.
842 */
843 explicit
844 deque(const allocator_type& __a)
845 : _Base(__a, 0) { }
846
847#if __cplusplus >= 201103L
848 /**
849 * @brief Creates a %deque with default constructed elements.
850 * @param __n The number of elements to initially create.
851 * @param __a An allocator.
852 *
853 * This constructor fills the %deque with @a n default
854 * constructed elements.
855 */
856 explicit
857 deque(size_type __n, const allocator_type& __a = allocator_type())
858 : _Base(__a, _S_check_init_len(__n, __a))
859 { _M_default_initialize(); }
860
861 /**
862 * @brief Creates a %deque with copies of an exemplar element.
863 * @param __n The number of elements to initially create.
864 * @param __value An element to copy.
865 * @param __a An allocator.
866 *
867 * This constructor fills the %deque with @a __n copies of @a __value.
868 */
869 deque(size_type __n, const value_type& __value,
870 const allocator_type& __a = allocator_type())
871 : _Base(__a, _S_check_init_len(__n, __a))
872 { _M_fill_initialize(__value); }
873#else
874 /**
875 * @brief Creates a %deque with copies of an exemplar element.
876 * @param __n The number of elements to initially create.
877 * @param __value An element to copy.
878 * @param __a An allocator.
879 *
880 * This constructor fills the %deque with @a __n copies of @a __value.
881 */
882 explicit
883 deque(size_type __n, const value_type& __value = value_type(),
884 const allocator_type& __a = allocator_type())
885 : _Base(__a, _S_check_init_len(__n, __a))
886 { _M_fill_initialize(__value); }
887#endif
888
889 /**
890 * @brief %Deque copy constructor.
891 * @param __x A %deque of identical element and allocator types.
892 *
893 * The newly-created %deque uses a copy of the allocator object used
894 * by @a __x (unless the allocator traits dictate a different object).
895 */
896 deque(const deque& __x)
897 : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
898 __x.size())
899 { std::__uninitialized_copy_a(__x.begin(), __x.end(),
900 this->_M_impl._M_start,
901 _M_get_Tp_allocator()); }
902
903#if __cplusplus >= 201103L
904 /**
905 * @brief %Deque move constructor.
906 *
907 * The newly-created %deque contains the exact contents of the
908 * moved instance.
909 * The contents of the moved instance are a valid, but unspecified
910 * %deque.
911 */
912 deque(deque&&) = default;
913
914 /// Copy constructor with alternative allocator
915 deque(const deque& __x, const allocator_type& __a)
916 : _Base(__a, __x.size())
917 { std::__uninitialized_copy_a(__x.begin(), __x.end(),
918 this->_M_impl._M_start,
919 _M_get_Tp_allocator()); }
920
921 /// Move constructor with alternative allocator
922 deque(deque&& __x, const allocator_type& __a)
923 : deque(std::move(__x), __a, typename _Alloc_traits::is_always_equal{})
924 { }
925
926 private:
927 deque(deque&& __x, const allocator_type& __a, true_type)
928 : _Base(std::move(__x), __a)
929 { }
930
931 deque(deque&& __x, const allocator_type& __a, false_type)
932 : _Base(std::move(__x), __a, __x.size())
933 {
934 if (__x.get_allocator() != __a && !__x.empty())
935 {
936 std::__uninitialized_move_a(__x.begin(), __x.end(),
937 this->_M_impl._M_start,
938 _M_get_Tp_allocator());
939 __x.clear();
940 }
941 }
942
943 public:
944 /**
945 * @brief Builds a %deque from an initializer list.
946 * @param __l An initializer_list.
947 * @param __a An allocator object.
948 *
949 * Create a %deque consisting of copies of the elements in the
950 * initializer_list @a __l.
951 *
952 * This will call the element type's copy constructor N times
953 * (where N is __l.size()) and do no memory reallocation.
954 */
955 deque(initializer_list<value_type> __l,
956 const allocator_type& __a = allocator_type())
957 : _Base(__a)
958 {
959 _M_range_initialize(__l.begin(), __l.end(),
960 random_access_iterator_tag());
961 }
962#endif
963
964 /**
965 * @brief Builds a %deque from a range.
966 * @param __first An input iterator.
967 * @param __last An input iterator.
968 * @param __a An allocator object.
969 *
970 * Create a %deque consisting of copies of the elements from [__first,
971 * __last).
972 *
973 * If the iterators are forward, bidirectional, or random-access, then
974 * this will call the elements' copy constructor N times (where N is
975 * distance(__first,__last)) and do no memory reallocation. But if only
976 * input iterators are used, then this will do at most 2N calls to the
977 * copy constructor, and logN memory reallocations.
978 */
979#if __cplusplus >= 201103L
980 template<typename _InputIterator,
981 typename = std::_RequireInputIter<_InputIterator>>
982 deque(_InputIterator __first, _InputIterator __last,
983 const allocator_type& __a = allocator_type())
984 : _Base(__a)
985 {
986 _M_range_initialize(__first, __last,
987 std::__iterator_category(__first));
988 }
989#else
990 template<typename _InputIterator>
991 deque(_InputIterator __first, _InputIterator __last,
992 const allocator_type& __a = allocator_type())
993 : _Base(__a)
994 {
995 // Check whether it's an integral type. If so, it's not an iterator.
996 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
997 _M_initialize_dispatch(__first, __last, _Integral());
998 }
999#endif
1000
1001 /**
1002 * The dtor only erases the elements, and note that if the elements
1003 * themselves are pointers, the pointed-to memory is not touched in any
1004 * way. Managing the pointer is the user's responsibility.
1005 */
1006 ~deque()
1007 { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
1008
1009 /**
1010 * @brief %Deque assignment operator.
1011 * @param __x A %deque of identical element and allocator types.
1012 *
1013 * All the elements of @a x are copied.
1014 *
1015 * The newly-created %deque uses a copy of the allocator object used
1016 * by @a __x (unless the allocator traits dictate a different object).
1017 */
1018 deque&
1019 operator=(const deque& __x);
1020
1021#if __cplusplus >= 201103L
1022 /**
1023 * @brief %Deque move assignment operator.
1024 * @param __x A %deque of identical element and allocator types.
1025 *
1026 * The contents of @a __x are moved into this deque (without copying,
1027 * if the allocators permit it).
1028 * @a __x is a valid, but unspecified %deque.
1029 */
1030 deque&
1031 operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal())
1032 {
1033 using __always_equal = typename _Alloc_traits::is_always_equal;
1034 _M_move_assign1(std::move(__x), __always_equal{});
1035 return *this;
1036 }
1037
1038 /**
1039 * @brief Assigns an initializer list to a %deque.
1040 * @param __l An initializer_list.
1041 *
1042 * This function fills a %deque with copies of the elements in the
1043 * initializer_list @a __l.
1044 *
1045 * Note that the assignment completely changes the %deque and that the
1046 * resulting %deque's size is the same as the number of elements
1047 * assigned.
1048 */
1049 deque&
1050 operator=(initializer_list<value_type> __l)
1051 {
1052 _M_assign_aux(__l.begin(), __l.end(),
1053 random_access_iterator_tag());
1054 return *this;
1055 }
1056#endif
1057
1058 /**
1059 * @brief Assigns a given value to a %deque.
1060 * @param __n Number of elements to be assigned.
1061 * @param __val Value to be assigned.
1062 *
1063 * This function fills a %deque with @a n copies of the given
1064 * value. Note that the assignment completely changes the
1065 * %deque and that the resulting %deque's size is the same as
1066 * the number of elements assigned.
1067 */
1068 void
1069 assign(size_type __n, const value_type& __val)
1070 { _M_fill_assign(__n, __val); }
1071
1072 /**
1073 * @brief Assigns a range to a %deque.
1074 * @param __first An input iterator.
1075 * @param __last An input iterator.
1076 *
1077 * This function fills a %deque with copies of the elements in the
1078 * range [__first,__last).
1079 *
1080 * Note that the assignment completely changes the %deque and that the
1081 * resulting %deque's size is the same as the number of elements
1082 * assigned.
1083 */
1084#if __cplusplus >= 201103L
1085 template<typename _InputIterator,
1086 typename = std::_RequireInputIter<_InputIterator>>
1087 void
1088 assign(_InputIterator __first, _InputIterator __last)
1089 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1090#else
1091 template<typename _InputIterator>
1092 void
1093 assign(_InputIterator __first, _InputIterator __last)
1094 {
1095 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1096 _M_assign_dispatch(__first, __last, _Integral());
1097 }
1098#endif
1099
1100#if __cplusplus >= 201103L
1101 /**
1102 * @brief Assigns an initializer list to a %deque.
1103 * @param __l An initializer_list.
1104 *
1105 * This function fills a %deque with copies of the elements in the
1106 * initializer_list @a __l.
1107 *
1108 * Note that the assignment completely changes the %deque and that the
1109 * resulting %deque's size is the same as the number of elements
1110 * assigned.
1111 */
1112 void
1113 assign(initializer_list<value_type> __l)
1114 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
1115#endif
1116
1117 /// Get a copy of the memory allocation object.
1118 allocator_type
1119 get_allocator() const _GLIBCXX_NOEXCEPT
1120 { return _Base::get_allocator(); }
1121
1122 // iterators
1123 /**
1124 * Returns a read/write iterator that points to the first element in the
1125 * %deque. Iteration is done in ordinary element order.
1126 */
1127 iterator
1128 begin() _GLIBCXX_NOEXCEPT
1129 { return this->_M_impl._M_start; }
1130
1131 /**
1132 * Returns a read-only (constant) iterator that points to the first
1133 * element in the %deque. Iteration is done in ordinary element order.
1134 */
1135 const_iterator
1136 begin() const _GLIBCXX_NOEXCEPT
1137 { return this->_M_impl._M_start; }
1138
1139 /**
1140 * Returns a read/write iterator that points one past the last
1141 * element in the %deque. Iteration is done in ordinary
1142 * element order.
1143 */
1144 iterator
1145 end() _GLIBCXX_NOEXCEPT
1146 { return this->_M_impl._M_finish; }
1147
1148 /**
1149 * Returns a read-only (constant) iterator that points one past
1150 * the last element in the %deque. Iteration is done in
1151 * ordinary element order.
1152 */
1153 const_iterator
1154 end() const _GLIBCXX_NOEXCEPT
1155 { return this->_M_impl._M_finish; }
1156
1157 /**
1158 * Returns a read/write reverse iterator that points to the
1159 * last element in the %deque. Iteration is done in reverse
1160 * element order.
1161 */
1162 reverse_iterator
1163 rbegin() _GLIBCXX_NOEXCEPT
1164 { return reverse_iterator(this->_M_impl._M_finish); }
1165
1166 /**
1167 * Returns a read-only (constant) reverse iterator that points
1168 * to the last element in the %deque. Iteration is done in
1169 * reverse element order.
1170 */
1171 const_reverse_iterator
1172 rbegin() const _GLIBCXX_NOEXCEPT
1173 { return const_reverse_iterator(this->_M_impl._M_finish); }
1174
1175 /**
1176 * Returns a read/write reverse iterator that points to one
1177 * before the first element in the %deque. Iteration is done
1178 * in reverse element order.
1179 */
1180 reverse_iterator
1181 rend() _GLIBCXX_NOEXCEPT
1182 { return reverse_iterator(this->_M_impl._M_start); }
1183
1184 /**
1185 * Returns a read-only (constant) reverse iterator that points
1186 * to one before the first element in the %deque. Iteration is
1187 * done in reverse element order.
1188 */
1189 const_reverse_iterator
1190 rend() const _GLIBCXX_NOEXCEPT
1191 { return const_reverse_iterator(this->_M_impl._M_start); }
1192
1193#if __cplusplus >= 201103L
1194 /**
1195 * Returns a read-only (constant) iterator that points to the first
1196 * element in the %deque. Iteration is done in ordinary element order.
1197 */
1198 const_iterator
1199 cbegin() const noexcept
1200 { return this->_M_impl._M_start; }
1201
1202 /**
1203 * Returns a read-only (constant) iterator that points one past
1204 * the last element in the %deque. Iteration is done in
1205 * ordinary element order.
1206 */
1207 const_iterator
1208 cend() const noexcept
1209 { return this->_M_impl._M_finish; }
1210
1211 /**
1212 * Returns a read-only (constant) reverse iterator that points
1213 * to the last element in the %deque. Iteration is done in
1214 * reverse element order.
1215 */
1216 const_reverse_iterator
1217 crbegin() const noexcept
1218 { return const_reverse_iterator(this->_M_impl._M_finish); }
1219
1220 /**
1221 * Returns a read-only (constant) reverse iterator that points
1222 * to one before the first element in the %deque. Iteration is
1223 * done in reverse element order.
1224 */
1225 const_reverse_iterator
1226 crend() const noexcept
1227 { return const_reverse_iterator(this->_M_impl._M_start); }
1228#endif
1229
1230 // [23.2.1.2] capacity
1231 /** Returns the number of elements in the %deque. */
1232 size_type
1233 size() const _GLIBCXX_NOEXCEPT
1234 { return this->_M_impl._M_finish - this->_M_impl._M_start; }
1235
1236 /** Returns the size() of the largest possible %deque. */
1237 size_type
1238 max_size() const _GLIBCXX_NOEXCEPT
1239 { return _S_max_size(a: _M_get_Tp_allocator()); }
1240
1241#if __cplusplus >= 201103L
1242 /**
1243 * @brief Resizes the %deque to the specified number of elements.
1244 * @param __new_size Number of elements the %deque should contain.
1245 *
1246 * This function will %resize the %deque to the specified
1247 * number of elements. If the number is smaller than the
1248 * %deque's current size the %deque is truncated, otherwise
1249 * default constructed elements are appended.
1250 */
1251 void
1252 resize(size_type __new_size)
1253 {
1254 const size_type __len = size();
1255 if (__new_size > __len)
1256 _M_default_append(n: __new_size - __len);
1257 else if (__new_size < __len)
1258 _M_erase_at_end(pos: this->_M_impl._M_start
1259 + difference_type(__new_size));
1260 }
1261
1262 /**
1263 * @brief Resizes the %deque to the specified number of elements.
1264 * @param __new_size Number of elements the %deque should contain.
1265 * @param __x Data with which new elements should be populated.
1266 *
1267 * This function will %resize the %deque to the specified
1268 * number of elements. If the number is smaller than the
1269 * %deque's current size the %deque is truncated, otherwise the
1270 * %deque is extended and new elements are populated with given
1271 * data.
1272 */
1273 void
1274 resize(size_type __new_size, const value_type& __x)
1275#else
1276 /**
1277 * @brief Resizes the %deque to the specified number of elements.
1278 * @param __new_size Number of elements the %deque should contain.
1279 * @param __x Data with which new elements should be populated.
1280 *
1281 * This function will %resize the %deque to the specified
1282 * number of elements. If the number is smaller than the
1283 * %deque's current size the %deque is truncated, otherwise the
1284 * %deque is extended and new elements are populated with given
1285 * data.
1286 */
1287 void
1288 resize(size_type __new_size, value_type __x = value_type())
1289#endif
1290 {
1291 const size_type __len = size();
1292 if (__new_size > __len)
1293 _M_fill_insert(pos: this->_M_impl._M_finish, n: __new_size - __len, __x);
1294 else if (__new_size < __len)
1295 _M_erase_at_end(pos: this->_M_impl._M_start
1296 + difference_type(__new_size));
1297 }
1298
1299#if __cplusplus >= 201103L
1300 /** A non-binding request to reduce memory use. */
1301 void
1302 shrink_to_fit() noexcept
1303 { _M_shrink_to_fit(); }
1304#endif
1305
1306 /**
1307 * Returns true if the %deque is empty. (Thus begin() would
1308 * equal end().)
1309 */
1310 _GLIBCXX_NODISCARD bool
1311 empty() const _GLIBCXX_NOEXCEPT
1312 { return this->_M_impl._M_finish == this->_M_impl._M_start; }
1313
1314 // element access
1315 /**
1316 * @brief Subscript access to the data contained in the %deque.
1317 * @param __n The index of the element for which data should be
1318 * accessed.
1319 * @return Read/write reference to data.
1320 *
1321 * This operator allows for easy, array-style, data access.
1322 * Note that data access with this operator is unchecked and
1323 * out_of_range lookups are not defined. (For checked lookups
1324 * see at().)
1325 */
1326 reference
1327 operator[](size_type __n) _GLIBCXX_NOEXCEPT
1328 {
1329 __glibcxx_requires_subscript(__n);
1330 return this->_M_impl._M_start[difference_type(__n)];
1331 }
1332
1333 /**
1334 * @brief Subscript access to the data contained in the %deque.
1335 * @param __n The index of the element for which data should be
1336 * accessed.
1337 * @return Read-only (constant) reference to data.
1338 *
1339 * This operator allows for easy, array-style, data access.
1340 * Note that data access with this operator is unchecked and
1341 * out_of_range lookups are not defined. (For checked lookups
1342 * see at().)
1343 */
1344 const_reference
1345 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
1346 {
1347 __glibcxx_requires_subscript(__n);
1348 return this->_M_impl._M_start[difference_type(__n)];
1349 }
1350
1351 protected:
1352 /// Safety check used only from at().
1353 void
1354 _M_range_check(size_type __n) const
1355 {
1356 if (__n >= this->size())
1357 __throw_out_of_range_fmt(__N("deque::_M_range_check: __n "
1358 "(which is %zu)>= this->size() "
1359 "(which is %zu)"),
1360 __n, this->size());
1361 }
1362
1363 public:
1364 /**
1365 * @brief Provides access to the data contained in the %deque.
1366 * @param __n The index of the element for which data should be
1367 * accessed.
1368 * @return Read/write reference to data.
1369 * @throw std::out_of_range If @a __n is an invalid index.
1370 *
1371 * This function provides for safer data access. The parameter
1372 * is first checked that it is in the range of the deque. The
1373 * function throws out_of_range if the check fails.
1374 */
1375 reference
1376 at(size_type __n)
1377 {
1378 _M_range_check(__n);
1379 return (*this)[__n];
1380 }
1381
1382 /**
1383 * @brief Provides access to the data contained in the %deque.
1384 * @param __n The index of the element for which data should be
1385 * accessed.
1386 * @return Read-only (constant) reference to data.
1387 * @throw std::out_of_range If @a __n is an invalid index.
1388 *
1389 * This function provides for safer data access. The parameter is first
1390 * checked that it is in the range of the deque. The function throws
1391 * out_of_range if the check fails.
1392 */
1393 const_reference
1394 at(size_type __n) const
1395 {
1396 _M_range_check(__n);
1397 return (*this)[__n];
1398 }
1399
1400 /**
1401 * Returns a read/write reference to the data at the first
1402 * element of the %deque.
1403 */
1404 reference
1405 front() _GLIBCXX_NOEXCEPT
1406 {
1407 __glibcxx_requires_nonempty();
1408 return *begin();
1409 }
1410
1411 /**
1412 * Returns a read-only (constant) reference to the data at the first
1413 * element of the %deque.
1414 */
1415 const_reference
1416 front() const _GLIBCXX_NOEXCEPT
1417 {
1418 __glibcxx_requires_nonempty();
1419 return *begin();
1420 }
1421
1422 /**
1423 * Returns a read/write reference to the data at the last element of the
1424 * %deque.
1425 */
1426 reference
1427 back() _GLIBCXX_NOEXCEPT
1428 {
1429 __glibcxx_requires_nonempty();
1430 iterator __tmp = end();
1431 --__tmp;
1432 return *__tmp;
1433 }
1434
1435 /**
1436 * Returns a read-only (constant) reference to the data at the last
1437 * element of the %deque.
1438 */
1439 const_reference
1440 back() const _GLIBCXX_NOEXCEPT
1441 {
1442 __glibcxx_requires_nonempty();
1443 const_iterator __tmp = end();
1444 --__tmp;
1445 return *__tmp;
1446 }
1447
1448 // [23.2.1.2] modifiers
1449 /**
1450 * @brief Add data to the front of the %deque.
1451 * @param __x Data to be added.
1452 *
1453 * This is a typical stack operation. The function creates an
1454 * element at the front of the %deque and assigns the given
1455 * data to it. Due to the nature of a %deque this operation
1456 * can be done in constant time.
1457 */
1458 void
1459 push_front(const value_type& __x)
1460 {
1461 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1462 {
1463 _Alloc_traits::construct(this->_M_impl,
1464 this->_M_impl._M_start._M_cur - 1,
1465 __x);
1466 --this->_M_impl._M_start._M_cur;
1467 }
1468 else
1469 _M_push_front_aux(__x);
1470 }
1471
1472#if __cplusplus >= 201103L
1473 void
1474 push_front(value_type&& __x)
1475 { emplace_front(std::move(__x)); }
1476
1477 template<typename... _Args>
1478#if __cplusplus > 201402L
1479 reference
1480#else
1481 void
1482#endif
1483 emplace_front(_Args&&... __args);
1484#endif
1485
1486 /**
1487 * @brief Add data to the end of the %deque.
1488 * @param __x Data to be added.
1489 *
1490 * This is a typical stack operation. The function creates an
1491 * element at the end of the %deque and assigns the given data
1492 * to it. Due to the nature of a %deque this operation can be
1493 * done in constant time.
1494 */
1495 void
1496 push_back(const value_type& __x)
1497 {
1498 if (this->_M_impl._M_finish._M_cur
1499 != this->_M_impl._M_finish._M_last - 1)
1500 {
1501 _Alloc_traits::construct(this->_M_impl,
1502 this->_M_impl._M_finish._M_cur, __x);
1503 ++this->_M_impl._M_finish._M_cur;
1504 }
1505 else
1506 _M_push_back_aux(__x);
1507 }
1508
1509#if __cplusplus >= 201103L
1510 void
1511 push_back(value_type&& __x)
1512 { emplace_back(std::move(__x)); }
1513
1514 template<typename... _Args>
1515#if __cplusplus > 201402L
1516 reference
1517#else
1518 void
1519#endif
1520 emplace_back(_Args&&... __args);
1521#endif
1522
1523 /**
1524 * @brief Removes first element.
1525 *
1526 * This is a typical stack operation. It shrinks the %deque by one.
1527 *
1528 * Note that no data is returned, and if the first element's data is
1529 * needed, it should be retrieved before pop_front() is called.
1530 */
1531 void
1532 pop_front() _GLIBCXX_NOEXCEPT
1533 {
1534 __glibcxx_requires_nonempty();
1535 if (this->_M_impl._M_start._M_cur
1536 != this->_M_impl._M_start._M_last - 1)
1537 {
1538 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1539 this->_M_impl._M_start._M_cur);
1540 ++this->_M_impl._M_start._M_cur;
1541 }
1542 else
1543 _M_pop_front_aux();
1544 }
1545
1546 /**
1547 * @brief Removes last element.
1548 *
1549 * This is a typical stack operation. It shrinks the %deque by one.
1550 *
1551 * Note that no data is returned, and if the last element's data is
1552 * needed, it should be retrieved before pop_back() is called.
1553 */
1554 void
1555 pop_back() _GLIBCXX_NOEXCEPT
1556 {
1557 __glibcxx_requires_nonempty();
1558 if (this->_M_impl._M_finish._M_cur
1559 != this->_M_impl._M_finish._M_first)
1560 {
1561 --this->_M_impl._M_finish._M_cur;
1562 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1563 this->_M_impl._M_finish._M_cur);
1564 }
1565 else
1566 _M_pop_back_aux();
1567 }
1568
1569#if __cplusplus >= 201103L
1570 /**
1571 * @brief Inserts an object in %deque before specified iterator.
1572 * @param __position A const_iterator into the %deque.
1573 * @param __args Arguments.
1574 * @return An iterator that points to the inserted data.
1575 *
1576 * This function will insert an object of type T constructed
1577 * with T(std::forward<Args>(args)...) before the specified location.
1578 */
1579 template<typename... _Args>
1580 iterator
1581 emplace(const_iterator __position, _Args&&... __args);
1582
1583 /**
1584 * @brief Inserts given value into %deque before specified iterator.
1585 * @param __position A const_iterator into the %deque.
1586 * @param __x Data to be inserted.
1587 * @return An iterator that points to the inserted data.
1588 *
1589 * This function will insert a copy of the given value before the
1590 * specified location.
1591 */
1592 iterator
1593 insert(const_iterator __position, const value_type& __x);
1594#else
1595 /**
1596 * @brief Inserts given value into %deque before specified iterator.
1597 * @param __position An iterator into the %deque.
1598 * @param __x Data to be inserted.
1599 * @return An iterator that points to the inserted data.
1600 *
1601 * This function will insert a copy of the given value before the
1602 * specified location.
1603 */
1604 iterator
1605 insert(iterator __position, const value_type& __x);
1606#endif
1607
1608#if __cplusplus >= 201103L
1609 /**
1610 * @brief Inserts given rvalue into %deque before specified iterator.
1611 * @param __position A const_iterator into the %deque.
1612 * @param __x Data to be inserted.
1613 * @return An iterator that points to the inserted data.
1614 *
1615 * This function will insert a copy of the given rvalue before the
1616 * specified location.
1617 */
1618 iterator
1619 insert(const_iterator __position, value_type&& __x)
1620 { return emplace(__position, std::move(__x)); }
1621
1622 /**
1623 * @brief Inserts an initializer list into the %deque.
1624 * @param __p An iterator into the %deque.
1625 * @param __l An initializer_list.
1626 * @return An iterator that points to the inserted data.
1627 *
1628 * This function will insert copies of the data in the
1629 * initializer_list @a __l into the %deque before the location
1630 * specified by @a __p. This is known as <em>list insert</em>.
1631 */
1632 iterator
1633 insert(const_iterator __p, initializer_list<value_type> __l)
1634 {
1635 auto __offset = __p - cbegin();
1636 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1637 std::random_access_iterator_tag());
1638 return begin() + __offset;
1639 }
1640
1641 /**
1642 * @brief Inserts a number of copies of given data into the %deque.
1643 * @param __position A const_iterator into the %deque.
1644 * @param __n Number of elements to be inserted.
1645 * @param __x Data to be inserted.
1646 * @return An iterator that points to the inserted data.
1647 *
1648 * This function will insert a specified number of copies of the given
1649 * data before the location specified by @a __position.
1650 */
1651 iterator
1652 insert(const_iterator __position, size_type __n, const value_type& __x)
1653 {
1654 difference_type __offset = __position - cbegin();
1655 _M_fill_insert(pos: __position._M_const_cast(), __n, __x);
1656 return begin() + __offset;
1657 }
1658#else
1659 /**
1660 * @brief Inserts a number of copies of given data into the %deque.
1661 * @param __position An iterator into the %deque.
1662 * @param __n Number of elements to be inserted.
1663 * @param __x Data to be inserted.
1664 *
1665 * This function will insert a specified number of copies of the given
1666 * data before the location specified by @a __position.
1667 */
1668 void
1669 insert(iterator __position, size_type __n, const value_type& __x)
1670 { _M_fill_insert(__position, __n, __x); }
1671#endif
1672
1673#if __cplusplus >= 201103L
1674 /**
1675 * @brief Inserts a range into the %deque.
1676 * @param __position A const_iterator into the %deque.
1677 * @param __first An input iterator.
1678 * @param __last An input iterator.
1679 * @return An iterator that points to the inserted data.
1680 *
1681 * This function will insert copies of the data in the range
1682 * [__first,__last) into the %deque before the location specified
1683 * by @a __position. This is known as <em>range insert</em>.
1684 */
1685 template<typename _InputIterator,
1686 typename = std::_RequireInputIter<_InputIterator>>
1687 iterator
1688 insert(const_iterator __position, _InputIterator __first,
1689 _InputIterator __last)
1690 {
1691 difference_type __offset = __position - cbegin();
1692 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1693 std::__iterator_category(__first));
1694 return begin() + __offset;
1695 }
1696#else
1697 /**
1698 * @brief Inserts a range into the %deque.
1699 * @param __position An iterator into the %deque.
1700 * @param __first An input iterator.
1701 * @param __last An input iterator.
1702 *
1703 * This function will insert copies of the data in the range
1704 * [__first,__last) into the %deque before the location specified
1705 * by @a __position. This is known as <em>range insert</em>.
1706 */
1707 template<typename _InputIterator>
1708 void
1709 insert(iterator __position, _InputIterator __first,
1710 _InputIterator __last)
1711 {
1712 // Check whether it's an integral type. If so, it's not an iterator.
1713 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1714 _M_insert_dispatch(__position, __first, __last, _Integral());
1715 }
1716#endif
1717
1718 /**
1719 * @brief Remove element at given position.
1720 * @param __position Iterator pointing to element to be erased.
1721 * @return An iterator pointing to the next element (or end()).
1722 *
1723 * This function will erase the element at the given position and thus
1724 * shorten the %deque by one.
1725 *
1726 * The user is cautioned that
1727 * this function only erases the element, and that if the element is
1728 * itself a pointer, the pointed-to memory is not touched in any way.
1729 * Managing the pointer is the user's responsibility.
1730 */
1731 iterator
1732#if __cplusplus >= 201103L
1733 erase(const_iterator __position)
1734#else
1735 erase(iterator __position)
1736#endif
1737 { return _M_erase(__position._M_const_cast()); }
1738
1739 /**
1740 * @brief Remove a range of elements.
1741 * @param __first Iterator pointing to the first element to be erased.
1742 * @param __last Iterator pointing to one past the last element to be
1743 * erased.
1744 * @return An iterator pointing to the element pointed to by @a last
1745 * prior to erasing (or end()).
1746 *
1747 * This function will erase the elements in the range
1748 * [__first,__last) and shorten the %deque accordingly.
1749 *
1750 * The user is cautioned that
1751 * this function only erases the elements, and that if the elements
1752 * themselves are pointers, the pointed-to memory is not touched in any
1753 * way. Managing the pointer is the user's responsibility.
1754 */
1755 iterator
1756#if __cplusplus >= 201103L
1757 erase(const_iterator __first, const_iterator __last)
1758#else
1759 erase(iterator __first, iterator __last)
1760#endif
1761 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1762
1763 /**
1764 * @brief Swaps data with another %deque.
1765 * @param __x A %deque of the same element and allocator types.
1766 *
1767 * This exchanges the elements between two deques in constant time.
1768 * (Four pointers, so it should be quite fast.)
1769 * Note that the global std::swap() function is specialized such that
1770 * std::swap(d1,d2) will feed to this function.
1771 *
1772 * Whether the allocators are swapped depends on the allocator traits.
1773 */
1774 void
1775 swap(deque& __x) _GLIBCXX_NOEXCEPT
1776 {
1777#if __cplusplus >= 201103L
1778 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1779 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1780#endif
1781 _M_impl._M_swap_data(__x._M_impl);
1782 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1783 __x._M_get_Tp_allocator());
1784 }
1785
1786 /**
1787 * Erases all the elements. Note that this function only erases the
1788 * elements, and that if the elements themselves are pointers, the
1789 * pointed-to memory is not touched in any way. Managing the pointer is
1790 * the user's responsibility.
1791 */
1792 void
1793 clear() _GLIBCXX_NOEXCEPT
1794 { _M_erase_at_end(pos: begin()); }
1795
1796 protected:
1797 // Internal constructor functions follow.
1798
1799#if __cplusplus < 201103L
1800 // called by the range constructor to implement [23.1.1]/9
1801
1802 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1803 // 438. Ambiguity in the "do the right thing" clause
1804 template<typename _Integer>
1805 void
1806 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1807 {
1808 _M_initialize_map(_S_check_init_len(static_cast<size_type>(__n),
1809 _M_get_Tp_allocator()));
1810 _M_fill_initialize(__x);
1811 }
1812
1813 // called by the range constructor to implement [23.1.1]/9
1814 template<typename _InputIterator>
1815 void
1816 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1817 __false_type)
1818 {
1819 _M_range_initialize(__first, __last,
1820 std::__iterator_category(__first));
1821 }
1822#endif
1823
1824 static size_t
1825 _S_check_init_len(size_t __n, const allocator_type& __a)
1826 {
1827 if (__n > _S_max_size(__a))
1828 __throw_length_error(
1829 __N("cannot create std::deque larger than max_size()"));
1830 return __n;
1831 }
1832
1833 static size_type
1834 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1835 {
1836 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1837 const size_t __allocmax = _Alloc_traits::max_size(__a);
1838 return (std::min)(a: __diffmax, b: __allocmax);
1839 }
1840
1841 // called by the second initialize_dispatch above
1842 ///@{
1843 /**
1844 * @brief Fills the deque with whatever is in [first,last).
1845 * @param __first An input iterator.
1846 * @param __last An input iterator.
1847 * @return Nothing.
1848 *
1849 * If the iterators are actually forward iterators (or better), then the
1850 * memory layout can be done all at once. Else we move forward using
1851 * push_back on each value from the iterator.
1852 */
1853 template<typename _InputIterator>
1854 void
1855 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1856 std::input_iterator_tag);
1857
1858 // called by the second initialize_dispatch above
1859 template<typename _ForwardIterator>
1860 void
1861 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1862 std::forward_iterator_tag);
1863 ///@}
1864
1865 /**
1866 * @brief Fills the %deque with copies of value.
1867 * @param __value Initial value.
1868 * @return Nothing.
1869 * @pre _M_start and _M_finish have already been initialized,
1870 * but none of the %deque's elements have yet been constructed.
1871 *
1872 * This function is called only when the user provides an explicit size
1873 * (with or without an explicit exemplar value).
1874 */
1875 void
1876 _M_fill_initialize(const value_type& __value);
1877
1878#if __cplusplus >= 201103L
1879 // called by deque(n).
1880 void
1881 _M_default_initialize();
1882#endif
1883
1884 // Internal assign functions follow. The *_aux functions do the actual
1885 // assignment work for the range versions.
1886
1887#if __cplusplus < 201103L
1888 // called by the range assign to implement [23.1.1]/9
1889
1890 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1891 // 438. Ambiguity in the "do the right thing" clause
1892 template<typename _Integer>
1893 void
1894 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1895 { _M_fill_assign(__n, __val); }
1896
1897 // called by the range assign to implement [23.1.1]/9
1898 template<typename _InputIterator>
1899 void
1900 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1901 __false_type)
1902 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1903#endif
1904
1905 // called by the second assign_dispatch above
1906 template<typename _InputIterator>
1907 void
1908 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1909 std::input_iterator_tag);
1910
1911 // called by the second assign_dispatch above
1912 template<typename _ForwardIterator>
1913 void
1914 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1915 std::forward_iterator_tag)
1916 {
1917 const size_type __len = std::distance(__first, __last);
1918 if (__len > size())
1919 {
1920 _ForwardIterator __mid = __first;
1921 std::advance(__mid, size());
1922 std::copy(__first, __mid, begin());
1923 _M_range_insert_aux(end(), __mid, __last,
1924 std::__iterator_category(__first));
1925 }
1926 else
1927 _M_erase_at_end(pos: std::copy(__first, __last, begin()));
1928 }
1929
1930 // Called by assign(n,t), and the range assign when it turns out
1931 // to be the same thing.
1932 void
1933 _M_fill_assign(size_type __n, const value_type& __val)
1934 {
1935 if (__n > size())
1936 {
1937 std::fill(begin(), end(), __val);
1938 _M_fill_insert(pos: end(), n: __n - size(), x: __val);
1939 }
1940 else
1941 {
1942 _M_erase_at_end(pos: begin() + difference_type(__n));
1943 std::fill(begin(), end(), __val);
1944 }
1945 }
1946
1947 ///@{
1948 /// Helper functions for push_* and pop_*.
1949#if __cplusplus < 201103L
1950 void _M_push_back_aux(const value_type&);
1951
1952 void _M_push_front_aux(const value_type&);
1953#else
1954 template<typename... _Args>
1955 void _M_push_back_aux(_Args&&... __args);
1956
1957 template<typename... _Args>
1958 void _M_push_front_aux(_Args&&... __args);
1959#endif
1960
1961 void _M_pop_back_aux();
1962
1963 void _M_pop_front_aux();
1964 ///@}
1965
1966 // Internal insert functions follow. The *_aux functions do the actual
1967 // insertion work when all shortcuts fail.
1968
1969#if __cplusplus < 201103L
1970 // called by the range insert to implement [23.1.1]/9
1971
1972 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1973 // 438. Ambiguity in the "do the right thing" clause
1974 template<typename _Integer>
1975 void
1976 _M_insert_dispatch(iterator __pos,
1977 _Integer __n, _Integer __x, __true_type)
1978 { _M_fill_insert(__pos, __n, __x); }
1979
1980 // called by the range insert to implement [23.1.1]/9
1981 template<typename _InputIterator>
1982 void
1983 _M_insert_dispatch(iterator __pos,
1984 _InputIterator __first, _InputIterator __last,
1985 __false_type)
1986 {
1987 _M_range_insert_aux(__pos, __first, __last,
1988 std::__iterator_category(__first));
1989 }
1990#endif
1991
1992 // called by the second insert_dispatch above
1993 template<typename _InputIterator>
1994 void
1995 _M_range_insert_aux(iterator __pos, _InputIterator __first,
1996 _InputIterator __last, std::input_iterator_tag);
1997
1998 // called by the second insert_dispatch above
1999 template<typename _ForwardIterator>
2000 void
2001 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2002 _ForwardIterator __last, std::forward_iterator_tag);
2003
2004 // Called by insert(p,n,x), and the range insert when it turns out to be
2005 // the same thing. Can use fill functions in optimal situations,
2006 // otherwise passes off to insert_aux(p,n,x).
2007 void
2008 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
2009
2010 // called by insert(p,x)
2011#if __cplusplus < 201103L
2012 iterator
2013 _M_insert_aux(iterator __pos, const value_type& __x);
2014#else
2015 template<typename... _Args>
2016 iterator
2017 _M_insert_aux(iterator __pos, _Args&&... __args);
2018#endif
2019
2020 // called by insert(p,n,x) via fill_insert
2021 void
2022 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
2023
2024 // called by range_insert_aux for forward iterators
2025 template<typename _ForwardIterator>
2026 void
2027 _M_insert_aux(iterator __pos,
2028 _ForwardIterator __first, _ForwardIterator __last,
2029 size_type __n);
2030
2031
2032 // Internal erase functions follow.
2033
2034 void
2035 _M_destroy_data_aux(iterator __first, iterator __last);
2036
2037 // Called by ~deque().
2038 // NB: Doesn't deallocate the nodes.
2039 template<typename _Alloc1>
2040 void
2041 _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
2042 { _M_destroy_data_aux(__first, __last); }
2043
2044 void
2045 _M_destroy_data(iterator __first, iterator __last,
2046 const std::allocator<_Tp>&)
2047 {
2048 if (!__has_trivial_destructor(value_type))
2049 _M_destroy_data_aux(__first, __last);
2050 }
2051
2052 // Called by erase(q1, q2).
2053 void
2054 _M_erase_at_begin(iterator __pos)
2055 {
2056 _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
2057 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2058 this->_M_impl._M_start = __pos;
2059 }
2060
2061 // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
2062 // _M_fill_assign, operator=.
2063 void
2064 _M_erase_at_end(iterator __pos)
2065 {
2066 _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
2067 _M_destroy_nodes(__pos._M_node + 1,
2068 this->_M_impl._M_finish._M_node + 1);
2069 this->_M_impl._M_finish = __pos;
2070 }
2071
2072 iterator
2073 _M_erase(iterator __pos);
2074
2075 iterator
2076 _M_erase(iterator __first, iterator __last);
2077
2078#if __cplusplus >= 201103L
2079 // Called by resize(sz).
2080 void
2081 _M_default_append(size_type __n);
2082
2083 bool
2084 _M_shrink_to_fit();
2085#endif
2086
2087 ///@{
2088 /// Memory-handling helpers for the previous internal insert functions.
2089 iterator
2090 _M_reserve_elements_at_front(size_type __n)
2091 {
2092 const size_type __vacancies = this->_M_impl._M_start._M_cur
2093 - this->_M_impl._M_start._M_first;
2094 if (__n > __vacancies)
2095 _M_new_elements_at_front(new_elements: __n - __vacancies);
2096 return this->_M_impl._M_start - difference_type(__n);
2097 }
2098
2099 iterator
2100 _M_reserve_elements_at_back(size_type __n)
2101 {
2102 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2103 - this->_M_impl._M_finish._M_cur) - 1;
2104 if (__n > __vacancies)
2105 _M_new_elements_at_back(new_elements: __n - __vacancies);
2106 return this->_M_impl._M_finish + difference_type(__n);
2107 }
2108
2109 void
2110 _M_new_elements_at_front(size_type __new_elements);
2111
2112 void
2113 _M_new_elements_at_back(size_type __new_elements);
2114 ///@}
2115
2116
2117 ///@{
2118 /**
2119 * @brief Memory-handling helpers for the major %map.
2120 *
2121 * Makes sure the _M_map has space for new nodes. Does not
2122 * actually add the nodes. Can invalidate _M_map pointers.
2123 * (And consequently, %deque iterators.)
2124 */
2125 void
2126 _M_reserve_map_at_back(size_type __nodes_to_add = 1)
2127 {
2128 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2129 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2130 _M_reallocate_map(__nodes_to_add, add_at_front: false);
2131 }
2132
2133 void
2134 _M_reserve_map_at_front(size_type __nodes_to_add = 1)
2135 {
2136 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2137 - this->_M_impl._M_map))
2138 _M_reallocate_map(__nodes_to_add, add_at_front: true);
2139 }
2140
2141 void
2142 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
2143 ///@}
2144
2145#if __cplusplus >= 201103L
2146 // Constant-time, nothrow move assignment when source object's memory
2147 // can be moved because the allocators are equal.
2148 void
2149 _M_move_assign1(deque&& __x, /* always equal: */ true_type) noexcept
2150 {
2151 this->_M_impl._M_swap_data(__x._M_impl);
2152 __x.clear();
2153 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2154 }
2155
2156 // When the allocators are not equal the operation could throw, because
2157 // we might need to allocate a new map for __x after moving from it
2158 // or we might need to allocate new elements for *this.
2159 void
2160 _M_move_assign1(deque&& __x, /* always equal: */ false_type)
2161 {
2162 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2163 return _M_move_assign1(std::move(__x), true_type());
2164
2165 constexpr bool __move_storage =
2166 _Alloc_traits::_S_propagate_on_move_assign();
2167 _M_move_assign2(std::move(__x), __bool_constant<__move_storage>());
2168 }
2169
2170 // Destroy all elements and deallocate all memory, then replace
2171 // with elements created from __args.
2172 template<typename... _Args>
2173 void
2174 _M_replace_map(_Args&&... __args)
2175 {
2176 // Create new data first, so if allocation fails there are no effects.
2177 deque __newobj(std::forward<_Args>(__args)...);
2178 // Free existing storage using existing allocator.
2179 clear();
2180 _M_deallocate_node(*begin()._M_node); // one node left after clear()
2181 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2182 this->_M_impl._M_map = nullptr;
2183 this->_M_impl._M_map_size = 0;
2184 // Take ownership of replacement memory.
2185 this->_M_impl._M_swap_data(__newobj._M_impl);
2186 }
2187
2188 // Do move assignment when the allocator propagates.
2189 void
2190 _M_move_assign2(deque&& __x, /* propagate: */ true_type)
2191 {
2192 // Make a copy of the original allocator state.
2193 auto __alloc = __x._M_get_Tp_allocator();
2194 // The allocator propagates so storage can be moved from __x,
2195 // leaving __x in a valid empty state with a moved-from allocator.
2196 _M_replace_map(std::move(__x));
2197 // Move the corresponding allocator state too.
2198 _M_get_Tp_allocator() = std::move(__alloc);
2199 }
2200
2201 // Do move assignment when it may not be possible to move source
2202 // object's memory, resulting in a linear-time operation.
2203 void
2204 _M_move_assign2(deque&& __x, /* propagate: */ false_type)
2205 {
2206 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2207 {
2208 // The allocators are equal so storage can be moved from __x,
2209 // leaving __x in a valid empty state with its current allocator.
2210 _M_replace_map(std::move(__x), __x.get_allocator());
2211 }
2212 else
2213 {
2214 // The rvalue's allocator cannot be moved and is not equal,
2215 // so we need to individually move each element.
2216 _M_assign_aux(std::make_move_iterator(__x.begin()),
2217 std::make_move_iterator(__x.end()),
2218 std::random_access_iterator_tag());
2219 __x.clear();
2220 }
2221 }
2222#endif
2223 };
2224
2225#if __cpp_deduction_guides >= 201606
2226 template<typename _InputIterator, typename _ValT
2227 = typename iterator_traits<_InputIterator>::value_type,
2228 typename _Allocator = allocator<_ValT>,
2229 typename = _RequireInputIter<_InputIterator>,
2230 typename = _RequireAllocator<_Allocator>>
2231 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2232 -> deque<_ValT, _Allocator>;
2233#endif
2234
2235 /**
2236 * @brief Deque equality comparison.
2237 * @param __x A %deque.
2238 * @param __y A %deque of the same type as @a __x.
2239 * @return True iff the size and elements of the deques are equal.
2240 *
2241 * This is an equivalence relation. It is linear in the size of the
2242 * deques. Deques are considered equivalent if their sizes are equal,
2243 * and if corresponding elements compare equal.
2244 */
2245 template<typename _Tp, typename _Alloc>
2246 inline bool
2247 operator==(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2248 { return __x.size() == __y.size()
2249 && std::equal(__x.begin(), __x.end(), __y.begin()); }
2250
2251#if __cpp_lib_three_way_comparison
2252 /**
2253 * @brief Deque ordering relation.
2254 * @param __x A `deque`.
2255 * @param __y A `deque` of the same type as `__x`.
2256 * @return A value indicating whether `__x` is less than, equal to,
2257 * greater than, or incomparable with `__y`.
2258 *
2259 * See `std::lexicographical_compare_three_way()` for how the determination
2260 * is made. This operator is used to synthesize relational operators like
2261 * `<` and `>=` etc.
2262 */
2263 template<typename _Tp, typename _Alloc>
2264 inline __detail::__synth3way_t<_Tp>
2265 operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2266 {
2267 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2268 __y.begin(), __y.end(),
2269 __detail::__synth3way);
2270 }
2271#else
2272 /**
2273 * @brief Deque ordering relation.
2274 * @param __x A %deque.
2275 * @param __y A %deque of the same type as @a __x.
2276 * @return True iff @a x is lexicographically less than @a __y.
2277 *
2278 * This is a total ordering relation. It is linear in the size of the
2279 * deques. The elements must be comparable with @c <.
2280 *
2281 * See std::lexicographical_compare() for how the determination is made.
2282 */
2283 template<typename _Tp, typename _Alloc>
2284 inline bool
2285 operator<(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2286 { return std::lexicographical_compare(__x.begin(), __x.end(),
2287 __y.begin(), __y.end()); }
2288
2289 /// Based on operator==
2290 template<typename _Tp, typename _Alloc>
2291 inline bool
2292 operator!=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2293 { return !(__x == __y); }
2294
2295 /// Based on operator<
2296 template<typename _Tp, typename _Alloc>
2297 inline bool
2298 operator>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2299 { return __y < __x; }
2300
2301 /// Based on operator<
2302 template<typename _Tp, typename _Alloc>
2303 inline bool
2304 operator<=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2305 { return !(__y < __x); }
2306
2307 /// Based on operator<
2308 template<typename _Tp, typename _Alloc>
2309 inline bool
2310 operator>=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2311 { return !(__x < __y); }
2312#endif // three-way comparison
2313
2314 /// See std::deque::swap().
2315 template<typename _Tp, typename _Alloc>
2316 inline void
2317 swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
2318 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2319 { __x.swap(__y); }
2320
2321#undef _GLIBCXX_DEQUE_BUF_SIZE
2322
2323_GLIBCXX_END_NAMESPACE_CONTAINER
2324
2325#if __cplusplus >= 201103L
2326 // std::allocator is safe, but it is not the only allocator
2327 // for which this is valid.
2328 template<class _Tp>
2329 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2330 : true_type { };
2331#endif
2332
2333_GLIBCXX_END_NAMESPACE_VERSION
2334} // namespace std
2335
2336#endif /* _STL_DEQUE_H */
2337

source code of include/c++/11/bits/stl_deque.h