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  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>
410  {
411  protected:
413  rebind<_Tp>::other _Tp_alloc_type;
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;
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 
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  {
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  {
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(
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  {
562  return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
563  }
564 
565  void
566  _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
567  {
569  _Traits::deallocate(_M_impl, __p, __deque_buf_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(this->_M_impl._M_start._M_node,
602  this->_M_impl._M_finish._M_node + 1);
603  _M_deallocate_map(this->_M_impl._M_map, 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
618  _M_initialize_map(size_t __num_elements)
619  {
620  const size_t __num_nodes = (__num_elements / __deque_buf_size(sizeof(_Tp))
621  + 1);
622 
623  this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
624  size_t(__num_nodes + 2));
625  this->_M_impl._M_map = _M_allocate_map(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(this->_M_impl._M_map, 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(sizeof(_Tp)));
652  }
653 
654  template<typename _Tp, typename _Alloc>
655  void
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, __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(*__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__
783  "std::deque must have the same value_type as its allocator");
784 # endif
785 #endif
786 
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;
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(sizeof(_Tp)); }
809 
810  // Functions controlling memory layout, and nothing else.
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  */
956  const allocator_type& __a = allocator_type())
957  : _Base(__a)
958  {
959  _M_range_initialize(__l.begin(), __l.end(),
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  */
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&
1051  {
1052  _M_assign_aux(__l.begin(), __l.end(),
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
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  */
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  */
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(_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(__new_size - __len);
1257  else if (__new_size < __len)
1258  _M_erase_at_end(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(this->_M_impl._M_finish, __new_size - __len, __x);
1294  else if (__new_size < __len)
1295  _M_erase_at_end(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
1634  {
1635  auto __offset = __p - cbegin();
1636  _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
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(__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
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(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)(__diffmax, __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,
1857 
1858  // called by the second initialize_dispatch above
1859  template<typename _ForwardIterator>
1860  void
1861  _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
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,
1910 
1911  // called by the second assign_dispatch above
1912  template<typename _ForwardIterator>
1913  void
1914  _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
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(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(end(), __n - size(), __val);
1939  }
1940  else
1941  {
1942  _M_erase_at_end(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
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(__n - __vacancies);
2096  return this->_M_impl._M_start - difference_type(__n);
2097  }
2098 
2099  iterator
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(__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, 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, 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()),
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
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 */
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
Definition: stl_deque.h:92
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:83
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:86
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
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
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
Definition: ptr_traits.h:155
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
initializer_list
integral_constant
Definition: type_traits:66
is_same
Definition: type_traits:1410
is_nothrow_default_constructible
Definition: type_traits:1033
__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 C++03 [20.4.1].
Definition: allocator.h:125
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:618
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
Definition: stl_deque.h:768
reverse_iterator rbegin() noexcept
Definition: stl_deque.h:1163
deque(const deque &__x)
Deque copy constructor.
Definition: stl_deque.h:896
const_reference at(size_type __n) const
Provides access to the data contained in the deque.
Definition: stl_deque.h:1394
deque(const deque &__x, const allocator_type &__a)
Copy constructor with alternative allocator.
Definition: stl_deque.h:915
deque(deque &&__x, const allocator_type &__a)
Move constructor with alternative allocator.
Definition: stl_deque.h:922
reverse_iterator rend() noexcept
Definition: stl_deque.h:1181
iterator erase(const_iterator __position)
Remove element at given position.
Definition: stl_deque.h:1733
const_reference back() const noexcept
Definition: stl_deque.h:1440
const_reverse_iterator crend() const noexcept
Definition: stl_deque.h:1226
void clear() noexcept
Definition: stl_deque.h:1793
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
Definition: deque.tcc:577
void pop_back() noexcept
Removes last element.
Definition: stl_deque.h:1555
size_type size() const noexcept
Definition: stl_deque.h:1233
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Memory-handling helpers for the major map.
Definition: deque.tcc:932
const_iterator cbegin() const noexcept
Definition: stl_deque.h:1199
void resize(size_type __new_size)
Resizes the deque to the specified number of elements.
Definition: stl_deque.h:1252
const_reverse_iterator rend() const noexcept
Definition: stl_deque.h:1190
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
Definition: stl_deque.h:2090
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:1532
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_deque.h:1119
void swap(deque &__x) noexcept
Swaps data with another deque.
Definition: stl_deque.h:1775
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the deque.
Definition: stl_deque.h:1327
reference at(size_type __n)
Provides access to the data contained in the deque.
Definition: stl_deque.h:1376
deque(size_type __n, const allocator_type &__a=allocator_type())
Creates a deque with default constructed elements.
Definition: stl_deque.h:857
bool empty() const noexcept
Definition: stl_deque.h:1311
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the deque.
Definition: stl_deque.h:1345
size_type max_size() const noexcept
Definition: stl_deque.h:1238
void push_front(const value_type &__x)
Add data to the front of the deque.
Definition: stl_deque.h:1459
void resize(size_type __new_size, const value_type &__x)
Resizes the deque to the specified number of elements.
Definition: stl_deque.h:1274
const_reference front() const noexcept
Definition: stl_deque.h:1416
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
Definition: stl_deque.h:1069
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
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
Definition: deque.tcc:907
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
Definition: stl_deque.h:1050
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
Definition: stl_deque.h:1633
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
Definition: stl_deque.h:1031
iterator end() noexcept
Definition: stl_deque.h:1145
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:869
const_reverse_iterator crbegin() const noexcept
Definition: stl_deque.h:1217
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
Definition: stl_deque.h:2126
reference back() noexcept
Definition: stl_deque.h:1427
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
Definition: deque.tcc:882
deque()=default
Creates a deque with no elements.
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition: deque.tcc:485
void push_back(const value_type &__x)
Add data to the end of the deque.
Definition: stl_deque.h:1496
deque(const allocator_type &__a)
Creates a deque with no elements.
Definition: stl_deque.h:844
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
Definition: stl_deque.h:2134
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition: deque.tcc:524
void _M_range_check(size_type __n) const
Safety check used only from at().
Definition: stl_deque.h:1354
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
Definition: stl_deque.h:1113
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
Definition: stl_deque.h:955
void shrink_to_fit() noexcept
Definition: stl_deque.h:1302
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
Definition: stl_deque.h:1088
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
Definition: stl_deque.h:982
const_iterator begin() const noexcept
Definition: stl_deque.h:1136
deque & operator=(const deque &__x)
Deque assignment operator.
Definition: deque.tcc:96
const_iterator end() const noexcept
Definition: stl_deque.h:1154
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:1652
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
Definition: stl_deque.h:1619
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
Definition: deque.tcc:561
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:1405
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
Definition: stl_deque.h:2100
const_iterator cend() const noexcept
Definition: stl_deque.h:1208
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
Definition: stl_deque.h:1688
const_reverse_iterator rbegin() const noexcept
Definition: stl_deque.h:1172
iterator begin() noexcept
Definition: stl_deque.h:1128
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
Definition: stl_deque.h:1757
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.