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