ReactOS  0.4.13-dev-79-gcd489d8
_deque.h
Go to the documentation of this file.
1 /*
2  *
3  * Copyright (c) 1994
4  * Hewlett-Packard Company
5  *
6  * Copyright (c) 1996,1997
7  * Silicon Graphics Computer Systems, Inc.
8  *
9  * Copyright (c) 1997
10  * Moscow Center for SPARC Technology
11  *
12  * Copyright (c) 1999
13  * Boris Fomitchev
14  *
15  * This material is provided "as is", with absolutely no warranty expressed
16  * or implied. Any use is at your own risk.
17  *
18  * Permission to use or copy this software for any purpose is hereby granted
19  * without fee, provided the above notices are retained on all copies.
20  * Permission to modify the code and to distribute modified code is granted,
21  * provided the above notices are retained, and a notice that the code was
22  * modified is included with the above copyright notice.
23  *
24  */
25 
26 /* NOTE: This is an internal header file, included by other STL headers.
27  * You should not attempt to use it directly.
28  */
29 
30 #ifndef _STLP_INTERNAL_DEQUE_H
31 #define _STLP_INTERNAL_DEQUE_H
32 
33 #ifndef _STLP_INTERNAL_ALGOBASE_H
34 # include <stl/_algobase.h>
35 #endif
36 
37 #ifndef _STLP_INTERNAL_ALLOC_H
38 # include <stl/_alloc.h>
39 #endif
40 
41 #ifndef _STLP_INTERNAL_ITERATOR_H
42 # include <stl/_iterator.h>
43 #endif
44 
45 #ifndef _STLP_INTERNAL_UNINITIALIZED_H
46 # include <stl/_uninitialized.h>
47 #endif
48 
49 #ifndef _STLP_RANGE_ERRORS_H
50 # include <stl/_range_errors.h>
51 #endif
52 
53 /* Class invariants:
54  * For any nonsingular iterator i:
55  * i.node is the address of an element in the map array. The
56  * contents of i.node is a pointer to the beginning of a node.
57  * i.first == *(i.node)
58  * i.last == i.first + node_size
59  * i.cur is a pointer in the range [i.first, i.last). NOTE:
60  * the implication of this is that i.cur is always a dereferenceable
61  * pointer, even if i is a past-the-end iterator.
62  * Start and Finish are always nonsingular iterators. NOTE: this means
63  * that an empty deque must have one node, and that a deque
64  * with N elements, where N is the buffer size, must have two nodes.
65  * For every node other than start.node and finish.node, every element
66  * in the node is an initialized object. If start.node == finish.node,
67  * then [start.cur, finish.cur) are initialized objects, and
68  * the elements outside that range are uninitialized storage. Otherwise,
69  * [start.cur, start.last) and [finish.first, finish.cur) are initialized
70  * objects, and [start.first, start.cur) and [finish.cur, finish.last)
71  * are uninitialized storage.
72  * [map, map + map_size) is a valid, non-empty range.
73  * [start.node, finish.node] is a valid range contained within
74  * [map, map + map_size).
75  * A pointer in the range [map, map + map_size) points to an allocated node
76  * if and only if the pointer is in the range [start.node, finish.node].
77  */
78 
80 
82 
83 template <class _Tp>
85 
86  static size_t _S_buffer_size() {
87  const size_t blocksize = _MAX_BYTES;
88  return (sizeof(_Tp) < blocksize ? (blocksize / sizeof(_Tp)) : 1);
89  }
90 
92 
93  typedef _Tp value_type;
94  typedef size_t size_type;
96 
98 
100 
105 
107  : _M_cur(__x), _M_first(*__y),
108  _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
109 
111 
112 // see comment in doc/README.evc4 and doc/README.evc8
113 #if defined (_STLP_MSVC) && (_STLP_MSVC <= 1401) && defined (MIPS) && defined (NDEBUG)
115  : _M_cur(__other._M_cur), _M_first(__other._M_first),
116  _M_last(__other._M_last), _M_node(__other._M_node) {}
117 #endif
118 
119  difference_type _M_subtract(const _Self& __x) const {
120  return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
121  (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
122  }
123 
124  void _M_increment() {
125  if (++_M_cur == _M_last) {
126  _M_set_node(_M_node + 1);
127  _M_cur = _M_first;
128  }
129  }
130 
131  void _M_decrement() {
132  if (_M_cur == _M_first) {
133  _M_set_node(_M_node - 1);
134  _M_cur = _M_last;
135  }
136  --_M_cur;
137  }
138 
140  const size_t buffersize = _S_buffer_size();
141  difference_type __offset = __n + (_M_cur - _M_first);
142  if (__offset >= 0 && __offset < difference_type(buffersize))
143  _M_cur += __n;
144  else {
145  difference_type __node_offset =
146  __offset > 0 ? __offset / buffersize
147  : -difference_type((-__offset - 1) / buffersize) - 1;
148  _M_set_node(_M_node + __node_offset);
149  _M_cur = _M_first +
150 
151  (__offset - __node_offset * difference_type(buffersize));
152  }
153  }
154 
155  void _M_set_node(_Map_pointer __new_node) {
156  _M_last = (_M_first = *(_M_node = __new_node)) + difference_type(_S_buffer_size());
157  }
158 };
159 
160 
161 template <class _Tp, class _Traits>
162 struct _Deque_iterator : public _Deque_iterator_base< _Tp> {
164  typedef _Tp value_type;
165  typedef typename _Traits::reference reference;
166  typedef typename _Traits::pointer pointer;
167  typedef size_t size_type;
170 
173  typedef typename _Traits::_NonConstTraits _NonConstTraits;
175  typedef typename _Traits::_ConstTraits _ConstTraits;
177 
179  _Deque_iterator_base<value_type>(__x,__y) {}
180 
182  //copy constructor for iterator and constructor from iterator for const_iterator
183  _Deque_iterator(const iterator& __x) :
185 
187  return *this->_M_cur;
188  }
189 
191 
192  difference_type operator-(const const_iterator& __x) const { return this->_M_subtract(__x); }
193 
194  _Self& operator++() { this->_M_increment(); return *this; }
195  _Self operator++(int) {
196  _Self __tmp = *this;
197  ++*this;
198  return __tmp;
199  }
200 
201  _Self& operator--() { this->_M_decrement(); return *this; }
202  _Self operator--(int) {
203  _Self __tmp = *this;
204  --*this;
205  return __tmp;
206  }
207 
208  _Self& operator+=(difference_type __n) { this->_M_advance(__n); return *this; }
210  _Self __tmp = *this;
211  return __tmp += __n;
212  }
213 
214  _Self& operator-=(difference_type __n) { return *this += -__n; }
216  _Self __tmp = *this;
217  return __tmp -= __n;
218  }
219 
220  reference operator[](difference_type __n) const { return *(*this + __n); }
221 };
222 
223 
224 template <class _Tp, class _Traits>
227 { return __x + __n; }
228 
229 
230 #if defined (_STLP_USE_SEPARATE_RELOPS_NAMESPACE)
231 template <class _Tp>
232 inline bool _STLP_CALL
234  const _Deque_iterator_base<_Tp >& __y)
235 { return __x._M_cur == __y._M_cur; }
236 
237 template <class _Tp>
238 inline bool _STLP_CALL
240  const _Deque_iterator_base<_Tp >& __y) {
241  return (__x._M_node == __y._M_node) ?
242  (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
243 }
244 
245 template <class _Tp>
246 inline bool _STLP_CALL
248  const _Deque_iterator_base<_Tp >& __y)
249 { return __x._M_cur != __y._M_cur; }
250 
251 template <class _Tp>
252 inline bool _STLP_CALL
254  const _Deque_iterator_base<_Tp >& __y)
255 { return __y < __x; }
256 
257 template <class _Tp>
258 inline bool _STLP_CALL operator>=(const _Deque_iterator_base<_Tp >& __x,
259  const _Deque_iterator_base<_Tp >& __y)
260 { return !(__x < __y); }
261 
262 template <class _Tp>
263 inline bool _STLP_CALL operator<=(const _Deque_iterator_base<_Tp >& __x,
264  const _Deque_iterator_base<_Tp >& __y)
265 { return !(__y < __x); }
266 
267 #else /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
268 
269 template <class _Tp, class _Traits1, class _Traits2>
270 inline bool _STLP_CALL
273 { return __x._M_cur == __y._M_cur; }
274 
275 template <class _Tp, class _Traits1, class _Traits2>
276 inline bool _STLP_CALL
278  const _Deque_iterator<_Tp, _Traits2 >& __y) {
279  return (__x._M_node == __y._M_node) ?
280  (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
281 }
282 
283 template <class _Tp>
284 inline bool _STLP_CALL
286  const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
287 { return __x._M_cur != __y._M_cur; }
288 
289 template <class _Tp>
290 inline bool _STLP_CALL
292  const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
293 { return __y < __x; }
294 
295 template <class _Tp>
296 inline bool _STLP_CALL
298  const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
299 { return !(__x < __y); }
300 
301 template <class _Tp>
302 inline bool _STLP_CALL
304  const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
305 { return !(__y < __x); }
306 #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
307 
308 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
310 template <class _Tp, class _Traits>
311 struct __type_traits<_STLP_PRIV _Deque_iterator<_Tp, _Traits> > {
316  typedef __false_type is_POD_type;
317 };
319 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
320 
321 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
323 template <class _Tp, class _Traits> inline _Tp* _STLP_CALL
324 value_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return (_Tp*)0; }
325 template <class _Tp, class _Traits> inline random_access_iterator_tag _STLP_CALL
326 iterator_category(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return random_access_iterator_tag(); }
327 template <class _Tp, class _Traits> inline ptrdiff_t* _STLP_CALL
328 distance_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return 0; }
330 #endif
331 
332 /* Deque base class. It has two purposes. First, its constructor
333  * and destructor allocate (but don't initialize) storage. This makes
334  * exception safety easier. Second, the base class encapsulates all of
335  * the differences between SGI-style allocators and standard-conforming
336  * allocators.
337  */
338 
339 template <class _Tp, class _Alloc>
340 class _Deque_base {
342 public:
343  typedef _Tp value_type;
347 
350 
353 
355 
356  _Deque_base(const allocator_type& __a, size_t __num_elements)
357  : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
358  _M_map_size(__a, (size_t)0)
359  { _M_initialize_map(__num_elements); }
360 
362  : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
363  _M_map_size(__a, (size_t)0) {}
364 
365 #if !defined (_STLP_NO_MOVE_SEMANTIC)
370  src.get()._M_map._M_data = 0;
371  src.get()._M_map_size._M_data = 0;
372  src.get()._M_finish = src.get()._M_start;
373  }
374 #endif
375 
376  ~_Deque_base();
377 
378 protected:
379  void _M_initialize_map(size_t);
380  void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
381  void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
382  enum { _S_initial_map_size = 8 };
383 
384 protected:
389 };
390 
391 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
392 # define deque _STLP_PTR_IMPL_NAME(deque)
393 #elif defined (_STLP_DEBUG)
394 # define deque _STLP_NON_DBG_NAME(deque)
395 #else
397 #endif
398 
399 template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) >
400 class deque : protected _STLP_PRIV _Deque_base<_Tp, _Alloc>
401 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (deque)
402  , public __stlport_class<deque<_Tp, _Alloc> >
403 #endif
404 {
407 public: // Basic types
408  typedef _Tp value_type;
409  typedef value_type* pointer;
410  typedef const value_type* const_pointer;
412  typedef const value_type& const_reference;
413  typedef size_t size_type;
418 
419 public: // Iterators
422 
424 
425 protected: // Internal typedefs
427 #if defined (_STLP_NO_MOVE_SEMANTIC)
428  typedef __false_type _Movable;
429 #endif
430 
431 public: // Basic accessors
432  iterator begin() { return this->_M_start; }
433  iterator end() { return this->_M_finish; }
434  const_iterator begin() const { return const_iterator(this->_M_start); }
435  const_iterator end() const { return const_iterator(this->_M_finish); }
436 
437  reverse_iterator rbegin() { return reverse_iterator(this->_M_finish); }
438  reverse_iterator rend() { return reverse_iterator(this->_M_start); }
439  const_reverse_iterator rbegin() const
440  { return const_reverse_iterator(this->_M_finish); }
441  const_reverse_iterator rend() const
442  { return const_reverse_iterator(this->_M_start); }
443 
445  { return this->_M_start[difference_type(__n)]; }
447  { return this->_M_start[difference_type(__n)]; }
448 
450  if (__n >= this->size())
451  __stl_throw_out_of_range("deque");
452  }
453  reference at(size_type __n)
454  { _M_range_check(__n); return (*this)[__n]; }
456  { _M_range_check(__n); return (*this)[__n]; }
457 
458  reference front() { return *this->_M_start; }
460  iterator __tmp = this->_M_finish;
461  --__tmp;
462  return *__tmp;
463  }
464  const_reference front() const { return *this->_M_start; }
466  const_iterator __tmp = this->_M_finish;
467  --__tmp;
468  return *__tmp;
469  }
470 
471  size_type size() const { return this->_M_finish - this->_M_start; }
472  size_type max_size() const { return size_type(-1); }
473  bool empty() const { return this->_M_finish == this->_M_start; }
474  allocator_type get_allocator() const { return this->_M_map_size; }
475 
476 public: // Constructor, destructor.
477 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
478  explicit deque(const allocator_type& __a = allocator_type())
479 #else
480  deque()
482  deque(const allocator_type& __a)
483 #endif
485 
486  deque(const _Self& __x)
487  : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__x.get_allocator(), __x.size())
488  { _STLP_PRIV __ucopy(__x.begin(), __x.end(), this->_M_start); }
489 
490 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
491 private:
493  typedef typename _TrivialInit<_Tp>::_Ret _TrivialInit;
495  }
496 public:
497  explicit deque(size_type __n)
499  { _M_initialize(__n); }
501 #else
502  explicit deque(size_type __n)
504  typedef typename _TrivialInit<_Tp>::_Ret _TrivialInit;
506  }
510  deque(size_type __n, const value_type& __val, const allocator_type& __a)
511 #endif
514 
515 #if defined (_STLP_MEMBER_TEMPLATES)
516 protected:
517  template <class _Integer>
518  void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
519  this->_M_initialize_map(__n);
521  }
522 
523  template <class _InputIter>
524  void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
525  const __false_type&) {
526  _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
527  }
528 
529 public:
530  // Check whether it's an integral type. If so, it's not an iterator.
531  template <class _InputIterator>
532  deque(_InputIterator __first, _InputIterator __last,
534  : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a) {
535  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
536  _M_initialize_dispatch(__first, __last, _Integral());
537  }
538 
539 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
540  template <class _InputIterator>
541  deque(_InputIterator __first, _InputIterator __last)
543  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
544  _M_initialize_dispatch(__first, __last, _Integral());
545  }
546 # endif
547 
548 #else
549  deque(const value_type* __first, const value_type* __last,
550  const allocator_type& __a = allocator_type() )
551  : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
552  { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
553 
555  const allocator_type& __a = allocator_type() )
556  : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
557  { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
558 #endif /* _STLP_MEMBER_TEMPLATES */
559 
560 #if !defined (_STLP_NO_MOVE_SEMANTIC)
563  {}
564 #endif
565 
567  { _STLP_STD::_Destroy_Range(this->_M_start, this->_M_finish); }
568 
569  _Self& operator= (const _Self& __x);
570 
571  void swap(_Self& __x) {
572  _STLP_STD::swap(this->_M_start, __x._M_start);
573  _STLP_STD::swap(this->_M_finish, __x._M_finish);
574  this->_M_map.swap(__x._M_map);
575  this->_M_map_size.swap(__x._M_map_size);
576  }
577 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
578  void _M_swap_workaround(_Self& __x) { swap(__x); }
579 #endif
580 
581 public:
582  // assign(), a generalized assignment member function. Two
583  // versions: one that takes a count, and one that takes a range.
584  // The range version is a member template, so we dispatch on whether
585  // or not the type is an integer.
586 
587  void _M_fill_assign(size_type __n, const _Tp& __val) {
588  if (__n > size()) {
590  insert(end(), __n - size(), __val);
591  }
592  else {
593  erase(begin() + __n, end());
595  }
596  }
597 
598  void assign(size_type __n, const _Tp& __val) {
600  }
601 
602 #if defined (_STLP_MEMBER_TEMPLATES)
603  template <class _InputIterator>
604  void assign(_InputIterator __first, _InputIterator __last) {
605  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
606  _M_assign_dispatch(__first, __last, _Integral());
607  }
608 
609 private: // helper functions for assign()
610 
611  template <class _Integer>
612  void _M_assign_dispatch(_Integer __n, _Integer __val,
613  const __true_type& /*_IsIntegral*/)
614  { _M_fill_assign((size_type) __n, (_Tp) __val); }
615 
616  template <class _InputIterator>
617  void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
618  const __false_type& /*_IsIntegral*/) {
619  _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
620  }
621 
622  template <class _InputIter>
623  void _M_assign_aux(_InputIter __first, _InputIter __last, const input_iterator_tag &) {
624  iterator __cur = begin();
625  for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
626  *__cur = *__first;
627  if (__first == __last)
628  erase(__cur, end());
629  else
630  insert(end(), __first, __last);
631  }
632 
633  template <class _ForwardIterator>
634  void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
635  const forward_iterator_tag &) {
636 #else
637  void assign(const value_type *__first, const value_type *__last) {
638  size_type __size = size();
639  size_type __len = __last - __first;
640  if (__len > __size) {
641  const value_type *__mid = __first + __size;
642  _STLP_STD::copy(__first, __mid, begin());
643  insert(end(), __mid, __last);
644  }
645  else {
646  erase(_STLP_STD::copy(__first, __last, begin()), end());
647  }
648  }
650  typedef const_iterator _ForwardIterator;
651 #endif /* _STLP_MEMBER_TEMPLATES */
652  size_type __len = _STLP_STD::distance(__first, __last);
653  if (__len > size()) {
654  _ForwardIterator __mid = __first;
655  _STLP_STD::advance(__mid, size());
656  _STLP_STD::copy(__first, __mid, begin());
657  insert(end(), __mid, __last);
658  }
659  else {
660  erase(_STLP_STD::copy(__first, __last, begin()), end());
661  }
662  }
663 
664 
665 public: // push_* and pop_*
666 
667 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
669 #else
670  void push_back(const value_type& __t) {
671 #endif
672  if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
673  _Copy_Construct(this->_M_finish._M_cur, __t);
674  ++this->_M_finish._M_cur;
675  }
676  else
677  _M_push_back_aux_v(__t);
678  }
679 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
681 #else
682  void push_front(const value_type& __t) {
683 #endif
684  if (this->_M_start._M_cur != this->_M_start._M_first) {
685  _Copy_Construct(this->_M_start._M_cur - 1, __t);
686  --this->_M_start._M_cur;
687  }
688  else
689  _M_push_front_aux_v(__t);
690  }
691 
692 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
693  void push_back() {
694  if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
695  _STLP_STD::_Construct(this->_M_finish._M_cur);
696  ++this->_M_finish._M_cur;
697  }
698  else
699  _M_push_back_aux();
700  }
701  void push_front() {
702  if (this->_M_start._M_cur != this->_M_start._M_first) {
703  _STLP_STD::_Construct(this->_M_start._M_cur - 1);
704  --this->_M_start._M_cur;
705  }
706  else
707  _M_push_front_aux();
708  }
709 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
710 
711  void pop_back() {
712  if (this->_M_finish._M_cur != this->_M_finish._M_first) {
713  --this->_M_finish._M_cur;
714  _STLP_STD::_Destroy(this->_M_finish._M_cur);
715  }
716  else {
717  _M_pop_back_aux();
718  _STLP_STD::_Destroy(this->_M_finish._M_cur);
719  }
720  }
721 
722  void pop_front() {
723  _STLP_STD::_Destroy(this->_M_start._M_cur);
725  }
726 
727 public: // Insert
728 
729 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
731 #else
732  iterator insert(iterator __pos, const value_type& __x) {
733 #endif
734 #if !defined (_STLP_NO_MOVE_SEMANTIC)
735  typedef typename __move_traits<_Tp>::implemented _Movable;
736 #endif
737  if (__pos._M_cur == this->_M_start._M_cur) {
738  push_front(__x);
739  return this->_M_start;
740  }
741  else if (__pos._M_cur == this->_M_finish._M_cur) {
742  push_back(__x);
743  iterator __tmp = this->_M_finish;
744  --__tmp;
745  return __tmp;
746  }
747  else {
748  return _M_fill_insert_aux(__pos, 1, __x, _Movable());
749  }
750  }
751 
752 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
753  iterator insert(iterator __pos)
754  { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
755 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
756 
757  void insert(iterator __pos, size_type __n, const value_type& __x)
758  { _M_fill_insert(__pos, __n, __x); }
759 
760 protected:
761  iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __true_type& /*_Movable*/);
762  iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __false_type& /*_Movable*/);
763 
764  void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
765 
766 #if defined (_STLP_MEMBER_TEMPLATES)
767  template <class _Integer>
768  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
769  const __true_type& /*_IsIntegral*/) {
770  _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
771  }
772 
773  template <class _InputIterator>
774  void _M_insert_dispatch(iterator __pos,
775  _InputIterator __first, _InputIterator __last,
776  const __false_type& /*_IsIntegral*/) {
777  _M_insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
778  }
779 
780 public:
781  // Check whether it's an integral type. If so, it's not an iterator.
782  template <class _InputIterator>
783  void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
784  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
785  _M_insert_dispatch(__pos, __first, __last, _Integral());
786  }
787 
788 #else /* _STLP_MEMBER_TEMPLATES */
789  void _M_insert_range_aux(iterator __pos,
790  const value_type* __first, const value_type* __last,
791  size_type __n, const __true_type& /*_Movable*/);
792  void _M_insert_range_aux(iterator __pos,
793  const value_type* __first, const value_type* __last,
794  size_type __n, const __false_type& /*_Movable*/);
795  void _M_insert_range_aux(iterator __pos,
797  size_type __n, const __true_type& /*_Movable*/);
798  void _M_insert_range_aux(iterator __pos,
800  size_type __n, const __false_type& /*_Movable*/);
801 public:
802  void insert(iterator __pos,
803  const value_type* __first, const value_type* __last);
804  void insert(iterator __pos,
806 
807 #endif /* _STLP_MEMBER_TEMPLATES */
808 
809 public:
810 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
811  void resize(size_type __new_size,
812  const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
813 #else
814  void resize(size_type __new_size, const value_type& __x) {
815 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
816  const size_type __len = size();
817  if (__new_size < __len)
818  erase(this->_M_start + __new_size, this->_M_finish);
819  else
820  insert(this->_M_finish, __new_size - __len, __x);
821  }
822 
823 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
824  void resize(size_type __new_size)
825  { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
826 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
827 
828 protected:
829  iterator _M_erase(iterator __pos, const __true_type& /*_Movable*/);
830  iterator _M_erase(iterator __pos, const __false_type& /*_Movable*/);
831 
832  iterator _M_erase(iterator __first, iterator __last, const __true_type& /*_Movable*/);
833  iterator _M_erase(iterator __first, iterator __last, const __false_type& /*_Movable*/);
834 public: // Erase
836 #if !defined (_STLP_NO_MOVE_SEMANTIC)
837  typedef typename __move_traits<_Tp>::implemented _Movable;
838 #endif
839  return _M_erase(__pos, _Movable());
840  }
842 #if !defined (_STLP_NO_MOVE_SEMANTIC)
843  typedef typename __move_traits<_Tp>::implemented _Movable;
844 #endif
845  if (__first == this->_M_start && __last == this->_M_finish) {
846  clear();
847  return this->_M_finish;
848  }
849  else {
850  if (__first == __last)
851  return __first;
852  return _M_erase(__first, __last, _Movable());
853  }
854  }
855  void clear();
856 
857 protected: // Internal construction/destruction
858 
859  void _M_fill_initialize(const value_type& __val, const __true_type& /*_TrivialInit*/)
860  {}
861  void _M_fill_initialize(const value_type& __val, const __false_type& /*_TrivialInit*/);
862 
863 #if defined (_STLP_MEMBER_TEMPLATES)
864  template <class _InputIterator>
865  void _M_range_initialize(_InputIterator __first, _InputIterator __last,
866  const input_iterator_tag &) {
867  this->_M_initialize_map(0);
868  _STLP_TRY {
869  for ( ; __first != __last; ++__first)
870  push_back(*__first);
871  }
873  }
874  template <class _ForwardIterator>
875  void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
876  const forward_iterator_tag &) {
878  this->_M_initialize_map(__n);
879  _Map_pointer __cur_node = this->_M_start._M_node;
880  _STLP_TRY {
881  for (; __cur_node < this->_M_finish._M_node; ++__cur_node) {
882  _ForwardIterator __mid = __first;
883  _STLP_STD::advance(__mid, this->buffer_size());
884  _STLP_STD::uninitialized_copy(__first, __mid, *__cur_node);
885  __first = __mid;
886  }
887  _STLP_STD::uninitialized_copy(__first, __last, this->_M_finish._M_first);
888  }
889  _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur_node, __cur_node)))
890  }
891 #endif /* _STLP_MEMBER_TEMPLATES */
892 
893 protected: // Internal push_* and pop_*
894 
895  void _M_push_back_aux_v(const value_type&);
896  void _M_push_front_aux_v(const value_type&);
897 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
898  void _M_push_back_aux();
899  void _M_push_front_aux();
900 #endif /*_STLP_DONT_SUP_DFLT_PARAM !_STLP_NO_ANACHRONISMS*/
901  void _M_pop_back_aux();
902  void _M_pop_front_aux();
903 
904 protected: // Internal insert functions
905 
906 #if defined (_STLP_MEMBER_TEMPLATES)
907 
908  template <class _InputIterator>
909  void _M_insert(iterator __pos,
910  _InputIterator __first,
911  _InputIterator __last,
912  const input_iterator_tag &) {
913  _STLP_STD::copy(__first, __last, inserter(*this, __pos));
914  }
915 
916  template <class _ForwardIterator>
917  void _M_insert(iterator __pos,
918  _ForwardIterator __first, _ForwardIterator __last,
919  const forward_iterator_tag &) {
920 #if !defined (_STLP_NO_MOVE_SEMANTIC)
921  typedef typename __move_traits<_Tp>::implemented _Movable;
922 #endif
924  if (__pos._M_cur == this->_M_start._M_cur) {
926  _STLP_TRY {
927  uninitialized_copy(__first, __last, __new_start);
928  this->_M_start = __new_start;
929  }
930  _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
931  }
932  else if (__pos._M_cur == this->_M_finish._M_cur) {
933  iterator __new_finish = _M_reserve_elements_at_back(__n);
934  _STLP_TRY {
935  uninitialized_copy(__first, __last, this->_M_finish);
936  this->_M_finish = __new_finish;
937  }
938  _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
939  }
940  else
941  _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
942  }
943 
944  template <class _ForwardIterator>
945  void _M_insert_range_aux(iterator __pos,
946  _ForwardIterator __first, _ForwardIterator __last,
947  size_type __n, const __true_type& /*_Movable*/) {
948  const difference_type __elemsbefore = __pos - this->_M_start;
949  size_type __length = size();
950  if (__elemsbefore <= difference_type(__length / 2)) {
952  __pos = this->_M_start + __elemsbefore;
953  _STLP_TRY {
954  iterator __dst = __new_start;
955  iterator __src = this->_M_start;
956  for (; __src != __pos; ++__dst, ++__src) {
957  _STLP_STD::_Move_Construct(&(*__dst), *__src);
958  _STLP_STD::_Destroy_Moved(&(*__src));
959  }
960  this->_M_start = __new_start;
961  uninitialized_copy(__first, __last, __dst);
962  }
963  _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
964  }
965  else {
966  iterator __new_finish = _M_reserve_elements_at_back(__n);
967  const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
968  __pos = this->_M_finish - __elemsafter;
969  _STLP_TRY {
970  iterator __dst = __new_finish;
971  iterator __src = this->_M_finish;
972  for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
973  _STLP_STD::_Move_Construct(&(*__dst), *__src);
974  _STLP_STD::_Destroy_Moved(&(*__src));
975  }
976  this->_M_finish = __new_finish;
977  uninitialized_copy(__first, __last, __pos);
978  }
979  _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
980  }
981  }
982 
983  template <class _ForwardIterator>
984  void _M_insert_range_aux(iterator __pos,
985  _ForwardIterator __first, _ForwardIterator __last,
986  size_type __n, const __false_type& /*_Movable*/) {
987  const difference_type __elemsbefore = __pos - this->_M_start;
988  size_type __length = size();
989  if (__elemsbefore <= difference_type(__length / 2)) {
991  iterator __old_start = this->_M_start;
992  __pos = this->_M_start + __elemsbefore;
993  _STLP_TRY {
994  if (__elemsbefore >= difference_type(__n)) {
995  iterator __start_n = this->_M_start + difference_type(__n);
996  _STLP_STD::uninitialized_copy(this->_M_start, __start_n, __new_start);
997  this->_M_start = __new_start;
998  _STLP_STD::copy(__start_n, __pos, __old_start);
999  _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
1000  }
1001  else {
1002  _ForwardIterator __mid = __first;
1003  _STLP_STD::advance(__mid, difference_type(__n) - __elemsbefore);
1004  _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
1005  this->_M_start = __new_start;
1006  _STLP_STD::copy(__mid, __last, __old_start);
1007  }
1008  }
1009  _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1010  }
1011  else {
1012  iterator __new_finish = _M_reserve_elements_at_back(__n);
1013  iterator __old_finish = this->_M_finish;
1014  const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
1015  __pos = this->_M_finish - __elemsafter;
1016  _STLP_TRY {
1017  if (__elemsafter > difference_type(__n)) {
1018  iterator __finish_n = this->_M_finish - difference_type(__n);
1019  _STLP_STD::uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
1020  this->_M_finish = __new_finish;
1021  _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
1022  _STLP_STD::copy(__first, __last, __pos);
1023  }
1024  else {
1025  _ForwardIterator __mid = __first;
1026  _STLP_STD::advance(__mid, __elemsafter);
1027  _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
1028  this->_M_finish = __new_finish;
1029  _STLP_STD::copy(__first, __mid, __pos);
1030  }
1031  }
1032  _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1033  }
1034  }
1035 #endif /* _STLP_MEMBER_TEMPLATES */
1036 
1038  size_type __vacancies = this->_M_start._M_cur - this->_M_start._M_first;
1039  if (__n > __vacancies)
1040  _M_new_elements_at_front(__n - __vacancies);
1041  return this->_M_start - difference_type(__n);
1042  }
1043 
1045  size_type __vacancies = (this->_M_finish._M_last - this->_M_finish._M_cur) - 1;
1046  if (__n > __vacancies)
1047  _M_new_elements_at_back(__n - __vacancies);
1048  return this->_M_finish + difference_type(__n);
1049  }
1050 
1051  void _M_new_elements_at_front(size_type __new_elements);
1052  void _M_new_elements_at_back(size_type __new_elements);
1053 
1054 protected: // Allocation of _M_map and nodes
1055 
1056  // Makes sure the _M_map has space for new nodes. Does not actually
1057  // add the nodes. Can invalidate _M_map pointers. (And consequently,
1058  // deque iterators.)
1059 
1060  void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
1061  if (__nodes_to_add + 1 > this->_M_map_size._M_data - (this->_M_finish._M_node - this->_M_map._M_data))
1062  _M_reallocate_map(__nodes_to_add, false);
1063  }
1064 
1065  void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
1066  if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map._M_data))
1067  _M_reallocate_map(__nodes_to_add, true);
1068  }
1069 
1070  void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1071 };
1072 
1073 #if defined (deque)
1074 # undef deque
1076 #endif
1077 
1079 
1080 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
1081 # include <stl/_deque.c>
1082 #endif
1083 
1084 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1085 # include <stl/pointers/_deque.h>
1086 #endif
1087 
1088 #if defined (_STLP_DEBUG)
1089 # include <stl/debug/_deque.h>
1090 #endif
1091 
1093 
1094 #define _STLP_TEMPLATE_CONTAINER deque<_Tp, _Alloc>
1095 #define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
1096 #include <stl/_relops_cont.h>
1097 #undef _STLP_TEMPLATE_CONTAINER
1098 #undef _STLP_TEMPLATE_HEADER
1099 
1100 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
1101 template <class _Tp, class _Alloc>
1102 struct __move_traits<deque<_Tp, _Alloc> > {
1103  typedef __true_type implemented;
1104  typedef typename __move_traits<_Alloc>::complete complete;
1105 };
1106 #endif
1107 
1109 
1110 #endif /* _STLP_INTERNAL_DEQUE_H */
1111 
1112 // Local Variables:
1113 // mode:C++
1114 // End:
1115 
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: _alloc.h:183
value_type * pointer
Definition: _deque.h:409
_Deque_base(const allocator_type &__a)
Definition: _deque.h:361
void assign(const value_type *__first, const value_type *__last)
Definition: _deque.h:637
void swap(_Self &__x)
Definition: _deque.h:571
void assign(const_iterator __first, const_iterator __last)
Definition: _deque.h:649
void _M_increment()
Definition: _deque.h:124
_Base::allocator_type allocator_type
Definition: _deque.h:417
void push_front(const value_type &__t=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:680
iterator _M_start
Definition: _deque.h:385
ptrdiff_t difference_type
Definition: _deque.h:414
void pop_front()
Definition: _deque.h:722
iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type &__x, const __true_type &)
Definition: _deque.c:464
ptrdiff_t difference_type
Definition: _deque.h:95
reference front()
Definition: _deque.h:458
bool _STLP_CALL operator<=(const _Deque_iterator< _Tp, _Nonconst_traits< _Tp > > &__x, const _Deque_iterator< _Tp, _Const_traits< _Tp > > &__y)
Definition: _deque.h:303
#define swap(a, b)
Definition: qsort.c:63
return __n
Definition: _algo.h:75
deque(const value_type *__first, const value_type *__last, const allocator_type &__a=allocator_type())
Definition: _deque.h:549
const value_type * const_pointer
Definition: _deque.h:410
void _M_range_check(size_type __n) const
Definition: _deque.h:449
_Deque_iterator< _Tp, _Traits > _Self
Definition: _deque.h:172
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Definition: _deque.c:773
char typename[32]
Definition: main.c:84
#define random_access_iterator_tag
Definition: _abbrevs.h:28
void push_back(const value_type &__t=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:668
value_type ** _Map_pointer
Definition: _deque.h:169
GLsizei const GLvoid * pointer
Definition: glext.h:5848
__bool2type< pod >::_Ret is_POD_type
deque(__move_source< _Self > src)
Definition: _deque.h:561
_Traits::pointer pointer
Definition: _deque.h:166
#define _Alloc
Definition: _bvector.h:330
void insert(iterator __pos, size_type __n, const value_type &__x)
Definition: _deque.h:757
iterator _M_reserve_elements_at_front(size_type __n)
Definition: _deque.h:1037
bool _STLP_CALL operator>=(const _Deque_iterator< _Tp, _Nonconst_traits< _Tp > > &__x, const _Deque_iterator< _Tp, _Const_traits< _Tp > > &__y)
Definition: _deque.h:297
iterator end()
Definition: _deque.h:433
#define reverse_iterator
Definition: _abbrevs.h:34
_STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS
Definition: _deque.h:423
static size_t _S_buffer_size()
Definition: _deque.h:86
deque(size_type __n)
Definition: _deque.h:497
_Deque_iterator< _Tp, _ConstTraits > const_iterator
Definition: _deque.h:176
const_reference front() const
Definition: _deque.h:464
static size_t _STLP_CALL buffer_size()
Definition: _deque.h:354
const value_type & const_reference
Definition: _deque.h:412
_Tp value_type
Definition: _deque.h:164
deque< _Tp, _Alloc > _Self
Definition: _deque.h:406
_Deque_base(__move_source< _Self > src)
Definition: _deque.h:366
_Deque_iterator_base< _Tp > _Base
Definition: _deque.h:171
_Self operator-(difference_type __n) const
Definition: _deque.h:215
_STLP_DEFINE_ARROW_OPERATOR difference_type operator-(const const_iterator &__x) const
Definition: _deque.h:192
_Self & operator-=(difference_type __n)
Definition: _deque.h:214
const_reverse_iterator rbegin() const
Definition: _deque.h:439
void _M_initialize_map(size_t)
Definition: _deque.c:48
value_type * _M_last
Definition: _deque.h:103
_Tp value_type
Definition: _deque.h:343
#define _STLP_ITERATOR_CATEGORY(_It, _Tp)
pointer * _Map_pointer
Definition: _deque.h:426
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
random_access_iterator_tag iterator_category
Definition: _deque.h:163
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
_Value _M_data
Definition: _alloc.h:478
value_type * _M_first
Definition: _deque.h:102
_Self operator++(int)
Definition: _deque.h:195
value_type ** _Map_pointer
Definition: _deque.h:97
~deque()
Definition: _deque.h:566
void _M_new_elements_at_back(size_type __new_elements)
Definition: _deque.c:759
void _M_decrement()
Definition: _deque.h:131
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Definition: _deque.h:1060
bool empty() const
Definition: _deque.h:473
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Definition: _deque.h:1065
_Alloc_traits< String *, _Alloc >::allocator_type _Map_alloc_type
Definition: _deque.h:348
~_Deque_base()
Definition: _deque.c:40
static void buffer_size(GLcontext *ctx, GLuint *width, GLuint *height)
Definition: swimpl.c:927
reference at(size_type __n)
Definition: _deque.h:453
random_access_iterator_tag iterator_category
Definition: _deque.h:91
#define _STLP_DEFAULT_CONSTRUCTED(_TTp)
Definition: _construct.h:265
iterator begin()
Definition: _deque.h:432
_Traits::_NonConstTraits _NonConstTraits
Definition: _deque.h:173
const_iterator begin() const
Definition: _deque.h:434
#define _STLP_UNWIND(action)
Definition: features.h:824
const_reference at(size_type __n) const
Definition: _deque.h:455
void _M_pop_front_aux()
Definition: _deque.c:453
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
void _M_set_node(_Map_pointer __new_node)
Definition: _deque.h:155
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result)
bool _STLP_CALL operator==(const _Deque_iterator< _Tp, _Traits1 > &__x, const _Deque_iterator< _Tp, _Traits2 > &__y)
Definition: _deque.h:271
reference operator[](size_type __n)
Definition: _deque.h:444
deque(const_iterator __first, const_iterator __last, const allocator_type &__a=allocator_type())
Definition: _deque.h:554
__kernel_size_t size_t
Definition: linux.h:237
const_reverse_iterator rend() const
Definition: _deque.h:441
reverse_iterator rbegin()
Definition: _deque.h:437
_Map_alloc_proxy _M_map
Definition: _deque.h:387
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
void get(int argc, const char *argv[])
Definition: cmds.c:480
iterator _M_erase(iterator __pos, const __true_type &)
Definition: _deque.c:208
void _Copy_Construct(_Tp *__p, const _Tp &__val)
Definition: _construct.h:130
void _M_new_elements_at_front(size_type __new_elements)
Definition: _deque.c:745
_Deque_iterator(const iterator &__x)
Definition: _deque.h:183
void _Destroy_Moved(_Tp *__pointer)
Definition: _construct.h:72
GLsizeiptr size
Definition: glext.h:5919
_Deque_iterator_base(value_type *__x, _Map_pointer __y)
Definition: _deque.h:106
value_type & reference
Definition: _deque.h:411
void _M_fill_insert(iterator __pos, size_type __n, const value_type &__x)
Definition: _deque.c:122
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:449
_Map_pointer _M_node
Definition: _deque.h:104
_Deque_base< _Tp, _Alloc > _Self
Definition: _deque.h:341
#define _STLP_ALLOCATOR_TYPE_DFL
Definition: features.h:691
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
insert_iterator< _Container > _STLP_CALL inserter(_Container &__x, _Iterator __i)
Definition: _iterator.h:250
_Deque_iterator< _Tp, _NonConstTraits > iterator
Definition: _deque.h:174
size_type max_size() const
Definition: _deque.h:472
ptrdiff_t difference_type
Definition: _deque.h:168
__bool2type< trivial_constructor >::_Ret has_trivial_default_constructor
Definition: _deque.h:400
deque(const allocator_type &__a=allocator_type())
Definition: _deque.h:478
static BOOL protected
Definition: protectdata.c:37
reference operator *() const
Definition: _deque.h:186
size_t size_type
Definition: _deque.h:167
_Deque_iterator< _Tp, _Traits > _STLP_CALL operator+(ptrdiff_t __n, const _Deque_iterator< _Tp, _Traits > &__x)
Definition: _deque.h:226
_STLP_PRIV _Deque_base< _Tp, _Alloc > _Base
Definition: _deque.h:405
_Tp value_type
Definition: _deque.h:408
iterator _M_reserve_elements_at_back(size_type __n)
Definition: _deque.h:1044
GLint reference
Definition: glext.h:11729
_STLP_BEGIN_NAMESPACE _STLP_MOVE_TO_PRIV_NAMESPACE _OutputIter __ucopy(_InputIter __first, _InputIter __last, _OutputIter __result, _Distance *)
#define _STLP_PRIV
Definition: _dm.h:70
void _Destroy(_Tp *__pointer)
Definition: _construct.h:63
_Base::const_iterator const_iterator
Definition: _deque.h:421
void _M_initialize(size_type __n, const value_type &__val=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:492
bool _STLP_CALL operator>(const _Deque_iterator< _Tp, _Nonconst_traits< _Tp > > &__x, const _Deque_iterator< _Tp, _Const_traits< _Tp > > &__y)
Definition: _deque.h:291
_STLP_MOVE_TO_STD_NAMESPACE void _STLP_CALL advance(_InputIterator &__i, _Distance __n)
void _M_push_back_aux_v(const value_type &)
Definition: _deque.c:382
GLenum src
Definition: glext.h:6340
void _M_insert_range_aux(iterator __pos, const value_type *__first, const value_type *__last, size_type __n, const __true_type &)
Definition: _deque.c:562
void _M_pop_back_aux()
Definition: _deque.c:443
size_t size_type
Definition: _deque.h:94
const_reference operator[](size_type __n) const
Definition: _deque.h:446
void _Construct(_T1 *__p)
Definition: _construct.h:106
_Self operator--(int)
Definition: _deque.h:202
void _Destroy_Range(_ForwardIterator __first, _ForwardIterator __last)
Definition: _construct.h:219
void _M_advance(difference_type __n)
Definition: _deque.h:139
void clear()
Definition: _deque.c:346
_Alloc_proxy _M_map_size
Definition: _deque.h:388
void assign(size_type __n, const _Tp &__val)
Definition: _deque.h:598
bool _STLP_CALL operator!=(const _Deque_iterator< _Tp, _Nonconst_traits< _Tp > > &__x, const _Deque_iterator< _Tp, _Const_traits< _Tp > > &__y)
Definition: _deque.h:285
_Traits::reference reference
Definition: _deque.h:165
difference_type _M_subtract(const _Self &__x) const
Definition: _deque.h:119
__bool2type< trivial_assign >::_Ret has_trivial_assignment_operator
_Self & operator--()
Definition: _deque.h:201
#define _STLP_END_NAMESPACE
Definition: features.h:503
allocator_type get_allocator() const
Definition: _deque.h:474
iterator erase(iterator __first, iterator __last)
Definition: _deque.h:841
#define _STLP_TRY
Definition: features.h:817
INT copy(TCHAR source[MAX_PATH], TCHAR dest[MAX_PATH], INT append, DWORD lpdwFlags, BOOL bTouch)
Definition: copy.c:51
__bool2type< trivial_copy >::_Ret has_trivial_copy_constructor
const_reference back() const
Definition: _deque.h:465
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
value_type * _M_cur
Definition: _deque.h:101
reference back()
Definition: _deque.h:459
void _M_fill_assign(size_type __n, const _Tp &__val)
Definition: _deque.h:587
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter __uninitialized_copy_copy(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _ForwardIter __result)
void _M_destroy_nodes(_Tp **__nstart, _Tp **__nfinish)
Definition: _deque.c:80
_Deque_base(const allocator_type &__a, size_t __num_elements)
Definition: _deque.h:356
void _M_push_front_aux_v(const value_type &)
Definition: _deque.c:412
reverse_iterator rend()
Definition: _deque.h:438
size_type size() const
Definition: _deque.h:471
deque(size_type __n, const value_type &__val, const allocator_type &__a=allocator_type())
Definition: _deque.h:500
#define _STLP_DEFINE_ARROW_OPERATOR
deque(const _Self &__x)
Definition: _deque.h:486
_Deque_iterator_base< _Tp > _Self
Definition: _deque.h:99
const_iterator end() const
Definition: _deque.h:435
bool _STLP_CALL operator<(const _Deque_iterator< _Tp, _Traits1 > &__x, const _Deque_iterator< _Tp, _Traits2 > &__y)
Definition: _deque.h:277
void _M_fill_initialize(const value_type &__val, const __true_type &)
Definition: _deque.h:859
_Self & operator=(const _Self &__x)
Definition: _deque.c:107
iterator _M_finish
Definition: _deque.h:386
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_out_of_range(const char *__msg)
Definition: _range_errors.c:69
void _M_create_nodes(_Tp **__nstart, _Tp **__nfinish)
Definition: _deque.c:69
static BOOL complete
Definition: htmldoc.c:198
void _Move_Construct(_T1 *__p, _T2 &__val)
Definition: _construct.h:174
_Self operator+(difference_type __n) const
Definition: _deque.h:209
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter copy_backward(_InputIter __first, _InputIter __last, _OutputIter __result)
Definition: _algobase.h:328
#define _STLP_CALL
Definition: _bc.h:131
void resize(size_type __new_size, const value_type &__x=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:811
iterator insert(iterator __pos, const value_type &__x=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:730
__bool2type< trivial_destructor >::_Ret has_trivial_destructor
size_t size_type
Definition: _deque.h:413
_Base::iterator iterator
Definition: _deque.h:420
_Traits::_ConstTraits _ConstTraits
Definition: _deque.h:175
iterator erase(iterator __pos)
Definition: _deque.h:835
_Self & operator+=(difference_type __n)
Definition: _deque.h:208
void pop_back()
Definition: _deque.h:711
reference operator[](difference_type __n) const
Definition: _deque.h:220
_Self & operator++()
Definition: _deque.h:194
random_access_iterator_tag _Iterator_category
Definition: _deque.h:415
#define _STLP_FORCE_ALLOCATORS(a, y)
Definition: _alloc.h:436
_Deque_iterator(value_type *__x, _Map_pointer __y)
Definition: _deque.h:178