ReactOS 0.4.15-dev-7704-gc07eb9f
_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)
42template <class _Tp, class _Alloc>
43inline _Tp* value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_DEQUE >&)
44{ return (_Tp*)0; }
45template <class _Tp, class _Alloc>
48#endif
49
50template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) >
51class 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
64public:
65 // Basic types
67
68 // Iterators
71
73
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
85public:
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) {
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
211public:
212 void assign(size_type __n, const _Tp& __val) {
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))
223 }
224#else
226 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
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))
233 _M_non_dbg_impl.assign(__first, __last);
234 }
235#endif
236
237public: // 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
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() {
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
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() {
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
283public: // 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))
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))
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))
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()) {
378 } else {
379 typename _Base::iterator tmp = --(_M_non_dbg_impl.end());
380 if (__pos._M_iterator == tmp)
382 else
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())
394 else
396 }
397 return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator));
398 }
399
400 void clear() {
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:
#define reverse_iterator
Definition: _abbrevs.h:34
#define random_access_iterator_tag
Definition: _abbrevs.h:28
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
return __n
Definition: _algo.h:75
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
#define _STLP_DEFAULT_CONSTRUCTED(_TTp)
Definition: _construct.h:265
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439
#define _STLP_PRIV
Definition: _dm.h:70
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void get(int argc, const char *argv[])
Definition: cmds.c:480
Definition: _deque.h:404
const_iterator end() const
Definition: _deque.h:92
const_reference back() const
Definition: _deque.h:123
iterator erase(iterator __pos)
Definition: _deque.h:373
iterator end()
Definition: _deque.h:90
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _deque.h:82
size_type max_size() const
Definition: _deque.h:201
_Base _M_non_dbg_impl
Definition: _deque.h:75
reverse_iterator rbegin()
Definition: _deque.h:94
void _Invalidate_iterator(const iterator &__it)
Definition: _deque.h:80
void pop_front()
Definition: _deque.h:277
void swap(_Self &__x)
Definition: _deque.h:203
void push_back(const value_type &__t=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:668
_Base::iterator iterator
Definition: _deque.h:420
deque(const_iterator __first, const_iterator __last, const allocator_type &__a=allocator_type())
Definition: _deque.h:183
_STLP_PRIV __construct_checker< _STLP_NON_DBG_DEQUE > _ConstructCheck
Definition: _deque.h:62
iterator begin()
Definition: _deque.h:89
_Self & operator=(const _Self &__x)
Definition: _deque.h:191
const_reverse_iterator rend() const
Definition: _deque.h:97
bool empty() const
Definition: _deque.h:473
void resize(size_type __new_size, const value_type &__x=_Tp())
Definition: _deque.h:355
_Tp value_type
Definition: _deque.h:408
value_type & reference
Definition: _deque.h:411
void push_front(const value_type &__t=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:680
deque(const allocator_type &__a=allocator_type())
Definition: _deque.h:129
reverse_iterator rend()
Definition: _deque.h:95
_STLP_NON_DBG_DEQUE _Base
Definition: _deque.h:61
_Base::const_iterator const_iterator
Definition: _deque.h:421
const_reverse_iterator rbegin() const
Definition: _deque.h:96
const_reference front() const
Definition: _deque.h:115
size_type size() const
Definition: _deque.h:471
deque< _Tp, _Alloc > _Self
Definition: _deque.h:406
reference back()
Definition: _deque.h:119
iterator erase(iterator __first, iterator __last)
Definition: _deque.h:388
void _Invalidate_all()
Definition: _deque.h:78
size_t size_type
Definition: _deque.h:413
reference operator[](size_type __n)
Definition: _deque.h:99
const_reference operator[](size_type __n) const
Definition: _deque.h:103
void push_back(const value_type &__t=_Tp())
Definition: _deque.h:240
deque(__move_source< _Self > src)
Definition: _deque.h:148
_STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS
Definition: _deque.h:423
_STLP_PRIV __owned_list _M_iter_list
Definition: _deque.h:76
_Base::allocator_type allocator_type
Definition: _deque.h:417
const value_type & const_reference
Definition: _deque.h:412
_STLP_PRIV _Deque_base< _Tp, _Alloc > _Base
Definition: _deque.h:405
const_reference at(size_type __n) const
Definition: _deque.h:109
allocator_type get_allocator() const
Definition: _deque.h:87
void assign(size_type __n, const _Tp &__val)
Definition: _deque.h:212
void insert(iterator __pos, const value_type *__first, const value_type *__last)
Definition: _deque.h:323
void assign(const value_type *__first, const value_type *__last)
Definition: _deque.h:230
void insert(iterator __pos, iterator __first, iterator __last)
Definition: _deque.h:343
const_iterator begin() const
Definition: _deque.h:91
void push_front(const value_type &__t=_Tp())
Definition: _deque.h:256
void insert(iterator __pos, size_type __n, const value_type &__x)
Definition: _deque.h:303
deque< _Tp, _Alloc > _Self
Definition: _deque.h:60
void clear()
Definition: _deque.h:400
deque(const value_type *__first, const value_type *__last, const allocator_type &__a=allocator_type())
Definition: _deque.h:176
void assign(const_iterator __first, const_iterator __last)
Definition: _deque.h:225
deque(size_type __n, const value_type &__x=_Tp(), const allocator_type &__a=allocator_type())
Definition: _deque.h:136
deque(const _Self &__x)
Definition: _deque.h:131
iterator insert(iterator __pos, const value_type &__x=_Tp())
Definition: _deque.h:286
reference front()
Definition: _deque.h:111
reference at(size_type __n)
Definition: _deque.h:108
void pop_back()
Definition: _deque.h:271
void resize(size_type __new_size, const value_type &__x=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _deque.h:811
void insert(iterator __pos, const_iterator __first, const_iterator __last)
Definition: _deque.h:333
#define _STLP_NON_DBG_DEQUE
Definition: _deque.h:37
_Iterator _Non_Dbg_iter(_Iterator __it)
Definition: _iterator.h:362
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93
#define __IMPORT_CONTAINER_TYPEDEFS(_Super)
Definition: features.h:750
#define _STLP_ALLOCATOR_TYPE_DFL
Definition: features.h:691
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_END_NAMESPACE
Definition: features.h:503
GLenum src
Definition: glext.h:6340
static BOOL protected
Definition: protectdata.c:37
#define swap(a, b)
Definition: qsort.c:63
static int insert
Definition: xmllint.c:138