ReactOS  0.4.14-dev-342-gdc047f9
_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_DBG_DEQUE_H
31 #define _STLP_INTERNAL_DBG_DEQUE_H
32 
33 #ifndef _STLP_DBG_ITERATOR_H
34 # include <stl/debug/_iterator.h>
35 #endif
36 
37 #define _STLP_NON_DBG_DEQUE _STLP_PRIV _STLP_NON_DBG_NAME(deque) <_Tp,_Alloc>
38 
40 
41 #if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
42 template <class _Tp, class _Alloc>
43 inline _Tp* value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_DEQUE >&)
44 { return (_Tp*)0; }
45 template <class _Tp, class _Alloc>
47 { return random_access_iterator_tag(); }
48 #endif
49 
50 template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) >
51 class deque :
52 #if !defined (__DMC__)
53  private
54 #endif
55  _STLP_PRIV __construct_checker<_STLP_NON_DBG_DEQUE >
56 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
57  , public __stlport_class<deque<_Tp, _Alloc> >
58 #endif
59 {
63 
64 public:
65  // Basic types
67 
68  // Iterators
71 
73 
74 protected:
76  _STLP_PRIV __owned_list _M_iter_list;
77 
79  { _M_iter_list._Invalidate_all(); }
81  { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); }
82  void _Invalidate_iterators(const iterator& __first, const iterator& __last)
83  { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); }
84 
85 public:
86  // Basic accessors
87  allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); }
88 
93 
96  const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
97  const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
98 
100  _STLP_VERBOSE_ASSERT(__n < size(), _StlMsg_OUT_OF_BOUNDS)
101  return _M_non_dbg_impl[__n];
102  }
104  _STLP_VERBOSE_ASSERT(__n < size(), _StlMsg_OUT_OF_BOUNDS)
105  return _M_non_dbg_impl[__n];
106  }
107 
110 
112  _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
113  return *begin();
114  }
116  _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
117  return *begin();
118  }
120  _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
121  return *(--end());
122  }
124  _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
125  return *(--end());
126  }
127 
128  // Constructor, destructor.
129  explicit deque(const allocator_type& __a = allocator_type()) :
131  deque(const _Self& __x) :
134 
135 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
136  explicit deque(size_type __n, const value_type& __x = _Tp(),
137 #else
138  deque(size_type __n, const value_type& __x,
139 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
140  const allocator_type& __a = allocator_type()) :
142 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
143  explicit deque(size_type __n) :
145 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
146 
147 #if !defined (_STLP_NO_MOVE_SEMANTIC)
151 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
152  src.get()._M_iter_list._Invalidate_all();
153 # else
154  src.get()._M_iter_list._Set_owner(_M_iter_list);
155 # endif
156  }
157 #endif
158 
159 #if defined (_STLP_MEMBER_TEMPLATES)
160  template <class _InputIterator>
161  deque(_InputIterator __first, _InputIterator __last,
163  : _ConstructCheck(__first, __last),
166  }
167 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
168  template <class _InputIterator>
169  deque(_InputIterator __first, _InputIterator __last)
170  : _ConstructCheck(__first, __last),
173  }
174 # endif
175 #else
176  deque(const value_type* __first, const value_type* __last,
177  const allocator_type& __a = allocator_type())
178  : _ConstructCheck(__first, __last),
179  _M_non_dbg_impl(__first, __last, __a),
181  }
182 
184  const allocator_type& __a = allocator_type())
185  : _ConstructCheck(__first, __last),
186  _M_non_dbg_impl(__first._M_iterator, __last._M_iterator, __a),
188  }
189 #endif
190 
191  _Self& operator=(const _Self& __x) {
192  if (this != &__x) {
193  _Invalidate_all();
195  }
196  return *this;
197  }
198 
199  bool empty() const { return _M_non_dbg_impl.empty(); }
200  size_type size() const { return _M_non_dbg_impl.size(); }
201  size_type max_size() const { return _M_non_dbg_impl.max_size(); }
202 
203  void swap(_Self& __x) {
204  _M_iter_list._Swap_owners(__x._M_iter_list);
206  }
207 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
208  void _M_swap_workaround(_Self& __x) { swap(__x); }
209 #endif
210 
211 public:
212  void assign(size_type __n, const _Tp& __val) {
213  _Invalidate_all();
214  _M_non_dbg_impl.assign(__n, __val);
215  }
216 
217 #if defined (_STLP_MEMBER_TEMPLATES)
218  template <class _InputIterator>
219  void assign(_InputIterator __first, _InputIterator __last) {
220  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
221  _Invalidate_all();
223  }
224 #else
226  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
227  _Invalidate_all();
228  _M_non_dbg_impl.assign(__first._M_iterator, __last._M_iterator);
229  }
230  void assign(const value_type *__first, const value_type *__last) {
231  _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last))
232  _Invalidate_all();
233  _M_non_dbg_impl.assign(__first, __last);
234  }
235 #endif
236 
237 public: // push_* and pop_*
238 
239 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
240  void push_back(const value_type& __t = _Tp()) {
241 #else
242  void push_back(const value_type& __t) {
243 #endif
244  _Invalidate_all();
245  _M_non_dbg_impl.push_back(__t);
246  }
247 
248 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
249  void push_back() {
250  _Invalidate_all();
251  _M_non_dbg_impl.push_back();
252  }
253 #endif
254 
255 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
256  void push_front(const value_type& __t = _Tp()) {
257 #else
258  void push_front(const value_type& __t) {
259 #endif
260  _Invalidate_all();
261  _M_non_dbg_impl.push_front(__t);
262  }
263 
264 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
265  void push_front() {
266  _Invalidate_all();
267  _M_non_dbg_impl.push_front();
268  }
269 #endif
270 
271  void pop_back() {
272  _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
274  _M_non_dbg_impl.pop_back();
275  }
276 
277  void pop_front() {
278  _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
280  _M_non_dbg_impl.pop_front();
281  }
282 
283 public: // Insert
284 
285 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
286  iterator insert(iterator __pos, const value_type& __x = _Tp()) {
287 #else
288  iterator insert(iterator __pos, const value_type& __x) {
289 #endif
290  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
291  _Invalidate_all();
292  return iterator(&_M_iter_list, _M_non_dbg_impl.insert(__pos._M_iterator, __x));
293  }
294 
295 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
296  iterator insert(iterator __pos) {
297  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
298  _Invalidate_all();
299  return iterator(&_M_iter_list, _M_non_dbg_impl.insert(__pos._M_iterator));
300  }
301 #endif
302 
303  void insert(iterator __pos, size_type __n, const value_type& __x) {
304  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
305  if (__n != 0) _Invalidate_all();
306  _M_non_dbg_impl.insert(__pos._M_iterator, __n, __x);
307  }
308 
309 #if defined (_STLP_MEMBER_TEMPLATES)
310  template <class _InputIterator>
311  void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
312  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
313  // We perform invalidate first to detect self referencing in __check_range as __first and __last
314  // will have been invalidated.
315  if (__first != __last) _Invalidate_all();
316  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
317  _M_non_dbg_impl.insert(__pos._M_iterator,
319  }
320 #endif
321 
322 #if !defined (_STLP_MEMBER_TEMPLATES)
323  void insert(iterator __pos,
324  const value_type* __first, const value_type* __last) {
325  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
326  _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last))
327  if (__first != __last) _Invalidate_all();
328  _M_non_dbg_impl.insert(__pos._M_iterator, __first, __last);
329  }
330 #endif
331 
332 #if !defined (_STLP_MEMBER_TEMPLATES) || !defined (_STLP_NO_METHOD_SPECIALIZATION)
333  void insert(iterator __pos,
335  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
336  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
337  //Sequence requirements 23.1.1 Table 67:
338  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_not_owner(&_M_iter_list, __first));
339  if (__first != __last) _Invalidate_all();
340  _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator);
341  }
342 
343  void insert(iterator __pos,
344  iterator __first, iterator __last) {
345  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
346  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
347  //Sequence requirements 23.1.1 Table 67:
348  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_not_owner(&_M_iter_list, __first));
349  if (__first != __last) _Invalidate_all();
350  _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator);
351  }
352 #endif
353 
354 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
355  void resize(size_type __new_size, const value_type& __x = _Tp()) {
356 #else
357  void resize(size_type __new_size, const value_type& __x) {
358 #endif
359  if (__new_size != size()) {
360  if ((__new_size > size()) || (__new_size < size() - 1))
361  _Invalidate_all();
362  else
364  }
365  _M_non_dbg_impl.resize(__new_size, __x);
366  }
367 
368 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
369  void resize(size_type new_size) { resize(new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
370 #endif
371 
372  // Erase
374  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
376  if (__pos._M_iterator == _M_non_dbg_impl.begin()) {
377  _Invalidate_iterator(__pos);
378  } else {
379  typename _Base::iterator tmp = --(_M_non_dbg_impl.end());
380  if (__pos._M_iterator == tmp)
381  _Invalidate_iterator(__pos);
382  else
383  _Invalidate_all();
384  }
385  return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__pos._M_iterator));
386  }
387 
389  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, begin(), end()))
390  if (!empty()) {
391  if (__first._M_iterator == _M_non_dbg_impl.begin() ||
392  __last._M_iterator == _M_non_dbg_impl.end())
393  _Invalidate_iterators(__first, __last);
394  else
395  _Invalidate_all();
396  }
397  return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator));
398  }
399 
400  void clear() {
401  _Invalidate_all();
402  _M_non_dbg_impl.clear();
403  }
404 };
405 
407 
408 #undef _STLP_NON_DBG_DEQUE
409 
410 #endif /* _STLP_INTERNAL_DEQUE_H */
411 
412 // Local Variables:
413 // mode:C++
414 // End:
_STLP_NON_DBG_DEQUE _Base
Definition: _deque.h:61
void assign(const value_type *__first, const value_type *__last)
Definition: _deque.h:230
void swap(_Self &__x)
Definition: _deque.h:203
void assign(const_iterator __first, const_iterator __last)
Definition: _deque.h:225
_Base::allocator_type allocator_type
Definition: _deque.h:417
void push_front(const value_type &__t=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:680
void pop_front()
Definition: _deque.h:277
reference front()
Definition: _deque.h:111
return __n
Definition: _algo.h:75
deque(const value_type *__first, const value_type *__last, const allocator_type &__a=allocator_type())
Definition: _deque.h:176
#define random_access_iterator_tag
Definition: _abbrevs.h:28
void push_back(const value_type &__t=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:668
deque(__move_source< _Self > src)
Definition: _deque.h:148
void insert(iterator __pos, size_type __n, const value_type &__x)
Definition: _deque.h:303
iterator end()
Definition: _deque.h:90
#define reverse_iterator
Definition: _abbrevs.h:34
_STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS
Definition: _deque.h:423
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _deque.h:82
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93
void push_front(const value_type &__t=_Tp())
Definition: _deque.h:256
_STLP_PRIV __construct_checker< _STLP_NON_DBG_DEQUE > _ConstructCheck
Definition: _deque.h:62
void _Invalidate_all()
Definition: _deque.h:78
const_reference front() const
Definition: _deque.h:115
#define _STLP_NON_DBG_DEQUE
Definition: _deque.h:37
deque< _Tp, _Alloc > _Self
Definition: _deque.h:406
void _Invalidate_iterator(const iterator &__it)
Definition: _deque.h:80
const_reverse_iterator rbegin() const
Definition: _deque.h:96
_Self & operator=(const _Self &__x)
Definition: _deque.h:191
void insert(iterator __pos, const value_type *__first, const value_type *__last)
Definition: _deque.h:323
deque(size_type __n, const value_type &__x=_Tp(), const allocator_type &__a=allocator_type())
Definition: _deque.h:136
bool empty() const
Definition: _deque.h:473
reference at(size_type __n)
Definition: _deque.h:108
#define _STLP_DEFAULT_CONSTRUCTED(_TTp)
Definition: _construct.h:265
iterator begin()
Definition: _deque.h:89
const_iterator begin() const
Definition: _deque.h:91
const_reference at(size_type __n) const
Definition: _deque.h:109
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#define __IMPORT_CONTAINER_TYPEDEFS(_Super)
Definition: features.h:750
_Iterator _Non_Dbg_iter(_Iterator __it)
Definition: _iterator.h:362
reference operator[](size_type __n)
Definition: _deque.h:99
deque(const_iterator __first, const_iterator __last, const allocator_type &__a=allocator_type())
Definition: _deque.h:183
const_reverse_iterator rend() const
Definition: _deque.h:97
reverse_iterator rbegin()
Definition: _deque.h:94
void get(int argc, const char *argv[])
Definition: cmds.c:480
#define _STLP_ALLOCATOR_TYPE_DFL
Definition: features.h:691
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
size_type max_size() const
Definition: _deque.h:201
Definition: _deque.h:400
deque(const allocator_type &__a=allocator_type())
Definition: _deque.h:129
static BOOL protected
Definition: protectdata.c:37
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void clear()
Definition: _deque.h:400
_STLP_PRIV _Deque_base< IncompleteClass, _Alloc > _Base
Definition: _deque.h:405
#define _STLP_PRIV
Definition: _dm.h:70
_Base::const_iterator const_iterator
Definition: _deque.h:421
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
GLenum src
Definition: glext.h:6340
const_reference operator[](size_type __n) const
Definition: _deque.h:103
void assign(size_type __n, const _Tp &__val)
Definition: _deque.h:212
_STLP_PRIV __owned_list _M_iter_list
Definition: _deque.h:76
void resize(size_type __new_size, const value_type &__x=_Tp())
Definition: _deque.h:355
_Base _M_non_dbg_impl
Definition: _deque.h:75
#define _STLP_END_NAMESPACE
Definition: features.h:503
allocator_type get_allocator() const
Definition: _deque.h:87
iterator erase(iterator __first, iterator __last)
Definition: _deque.h:388
const_reference back() const
Definition: _deque.h:123
void push_back(const value_type &__t=_Tp())
Definition: _deque.h:240
reference back()
Definition: _deque.h:119
reverse_iterator rend()
Definition: _deque.h:95
size_type size() const
Definition: _deque.h:471
deque(const _Self &__x)
Definition: _deque.h:131
const_iterator end() const
Definition: _deque.h:92
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
void insert(iterator __pos, const_iterator __first, const_iterator __last)
Definition: _deque.h:333
void insert(iterator __pos, iterator __first, iterator __last)
Definition: _deque.h:343
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
_Base::iterator iterator
Definition: _deque.h:420
iterator erase(iterator __pos)
Definition: _deque.h:373
deque< _Tp, _Alloc > _Self
Definition: _deque.h:60
void pop_back()
Definition: _deque.h:271
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439
iterator insert(iterator __pos, const value_type &__x=_Tp())
Definition: _deque.h:286