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