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