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