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