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