|
|
|
1 |
|
// list standard header |
2 |
|
#pragma once |
3 |
|
#ifndef _LIST_ |
4 |
|
#define _LIST_ |
5 |
|
#ifndef RC_INVOKED |
6 |
|
#include <functional> |
7 |
|
#include <memory> |
8 |
|
#include <stdexcept> |
9 |
|
|
10 |
|
#ifdef _MSC_VER |
11 |
|
#pragma pack(push,_CRT_PACKING) |
12 |
|
#endif /* _MSC_VER */ |
13 |
|
|
14 |
|
_STD_BEGIN |
15 |
|
|
16 |
|
// TEMPLATE CLASS _List_nod |
17 |
|
template<class _Ty, |
18 |
|
class _Alloc> |
19 |
|
class _List_nod |
20 |
|
: public _CONTAINER_BASE_AUX_ALLOC<_Alloc> |
21 |
|
{ // base class for _List_ptr to hold allocator _Alnod |
22 |
|
protected: |
23 |
|
struct _Node; |
24 |
|
friend struct _Node; |
25 |
|
typedef _Node *_Nodeptr; // _Node allocator must have ordinary pointers |
26 |
|
|
27 |
|
// disable warning 4512: assignment operator could not be generated |
28 |
|
// if _Ty is const, then this warning is generated; if we try to |
29 |
|
// use the unavailable assignement operator, then the compiler will |
30 |
|
// generate error C2582: 'operator =' function is unavailable |
31 |
|
#pragma warning(push) |
32 |
|
#pragma warning(disable:4512) |
33 |
|
struct _Node |
34 |
|
{ // list node |
35 |
|
_Node() |
36 |
|
{ // default constructor, do nothing |
37 |
|
} |
38 |
|
|
39 |
|
_Nodeptr _Next; // successor node, or first element if head |
40 |
|
_Nodeptr _Prev; // predecessor node, or last element if head |
41 |
|
_Ty _Myval; // the stored value, unused if head |
42 |
|
}; |
43 |
|
#pragma warning(pop) |
44 |
|
|
45 |
|
_List_nod(_Alloc _Al) |
46 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alnod(_Al) |
47 |
|
{ // construct allocator from _Al |
48 |
|
} |
49 |
|
|
50 |
|
typename _Alloc::template rebind<_Node>::other |
51 |
|
_Alnod; // allocator object for nodes |
52 |
|
}; |
53 |
|
|
54 |
|
// TEMPLATE CLASS _List_ptr |
55 |
|
template<class _Ty, |
56 |
|
class _Alloc> |
57 |
|
class _List_ptr |
58 |
|
: public _List_nod<_Ty, _Alloc> |
59 |
|
{ // base class for _List_val to hold allocator _Alptr |
60 |
|
protected: |
61 |
|
typedef _List_nod<_Ty, _Alloc> _Mybase; |
62 |
|
typedef typename _Mybase::_Node _Node; |
63 |
|
typedef typename _Mybase::_Nodeptr _Nodeptr; |
64 |
|
|
65 |
|
_List_ptr(_Alloc _Al) |
66 |
|
: _List_nod<_Ty, _Alloc>(_Al), _Alptr(_Al) |
67 |
|
{ // construct base, and allocator from _Al |
68 |
|
} |
69 |
|
|
70 |
|
typename _Alloc::template rebind<_Nodeptr>::other |
71 |
|
_Alptr; // allocator object for pointers to nodes |
72 |
|
}; |
73 |
|
|
74 |
|
// TEMPLATE CLASS _List_val |
75 |
|
template<class _Ty, |
76 |
|
class _Alloc> |
77 |
|
class _List_val |
78 |
|
: public _List_ptr<_Ty, _Alloc> |
79 |
|
{ // base class for list to hold allocator _Alval |
80 |
|
public: |
81 |
|
typedef typename _Alloc::template rebind<_Ty>::other _Alty; |
82 |
|
|
83 |
|
_List_val(_Alloc _Al = _Alloc()) |
84 |
|
: _List_ptr<_Ty, _Alloc>(_Al), _Alval(_Al) |
85 |
|
{ // construct base, and allocator from _Al |
86 |
|
} |
87 |
|
|
88 |
|
_Alty _Alval; // allocator object for values stored in nodes |
89 |
|
}; |
90 |
|
|
91 |
|
// TEMPLATE CLASS list |
92 |
|
template<class _Ty, |
93 |
|
class _Ax = allocator<_Ty> > |
94 |
|
class list |
95 |
|
: public _List_val<_Ty, _Ax> |
96 |
|
{ // bidirectional linked list |
97 |
|
public: |
98 |
|
typedef list<_Ty, _Ax> _Myt; |
99 |
|
typedef _List_val<_Ty, _Ax> _Mybase; |
100 |
|
typedef typename _Mybase::_Alty _Alloc; |
101 |
|
|
102 |
|
protected: |
103 |
|
typedef typename _Mybase::_Node _Node; |
104 |
|
typedef typename _Mybase::_Nodeptr _Nodeptr; |
105 |
|
|
106 |
|
typedef typename _Alloc::template rebind<_Nodeptr>::other |
107 |
|
_Nodeptr_alloc; |
108 |
|
typedef typename _Nodeptr_alloc::reference _Nodepref; |
109 |
|
|
110 |
|
|
111 |
|
typedef typename _Alloc::reference _Vref; |
112 |
|
|
113 |
|
static _Nodepref _Nextnode(_Nodeptr _Pnode) |
114 |
|
{ // return reference to successor pointer in node |
115 |
|
return ((_Nodepref)(*_Pnode)._Next); |
116 |
|
} |
117 |
|
|
118 |
|
static _Nodepref _Prevnode(_Nodeptr _Pnode) |
119 |
|
{ // return reference to predecessor pointer in node |
120 |
|
return ((_Nodepref)(*_Pnode)._Prev); |
121 |
|
} |
122 |
|
|
123 |
|
static _Vref _Myval(_Nodeptr _Pnode) |
124 |
|
{ // return reference to value in node |
125 |
|
return ((_Vref)(*_Pnode)._Myval); |
126 |
|
} |
127 |
|
|
128 |
|
public: |
129 |
|
typedef _Alloc allocator_type; |
130 |
|
typedef typename _Alloc::size_type size_type; |
131 |
|
typedef typename _Alloc::difference_type _Dift; |
132 |
|
typedef _Dift difference_type; |
133 |
|
typedef typename _Alloc::pointer _Tptr; |
134 |
|
typedef typename _Alloc::const_pointer _Ctptr; |
135 |
|
typedef _Tptr pointer; |
136 |
|
typedef _Ctptr const_pointer; |
137 |
|
typedef typename _Alloc::reference _Reft; |
138 |
|
typedef _Reft reference; |
139 |
|
typedef typename _Alloc::const_reference const_reference; |
140 |
|
typedef typename _Alloc::value_type value_type; |
141 |
|
|
142 |
|
// CLASS const_iterator |
143 |
|
template <bool _SECURE_VALIDATION> class _Const_iterator; |
144 |
|
friend class _Const_iterator<_SECURE_VALIDATION_DEFAULT>; |
145 |
|
#if _SECURE_SCL |
146 |
|
friend class _Const_iterator<false>; |
147 |
|
#endif |
148 |
|
|
149 |
|
template <bool _SECURE_VALIDATION> |
150 |
|
class _Const_iterator |
151 |
|
: public _Bidit<_Ty, _Dift, _Ctptr, const_reference> |
152 |
|
{ // iterator for nonmutable list |
153 |
|
public: |
154 |
|
typedef _Const_iterator<_SECURE_VALIDATION> _Myt_iter; |
155 |
|
typedef bidirectional_iterator_tag iterator_category; |
156 |
|
typedef _Ty value_type; |
157 |
|
typedef _Dift difference_type; |
158 |
|
typedef _Ctptr pointer; |
159 |
|
typedef const_reference reference; |
160 |
|
|
161 |
|
_Const_iterator() |
162 |
|
: _Ptr(0) |
163 |
|
{ // construct with null node pointer |
164 |
|
} |
165 |
|
|
166 |
|
#if _HAS_ITERATOR_DEBUGGING |
167 |
|
_Const_iterator(_Nodeptr _Pnode, const _Myt *_Plist) |
168 |
|
: _Ptr(_Pnode) |
169 |
|
{ // construct with node pointer _Pnode |
170 |
|
this->_Adopt(_Plist); |
171 |
|
} |
172 |
|
|
173 |
|
#elif _SECURE_SCL |
174 |
|
_Const_iterator(_Nodeptr _Pnode, const _Myt *_Plist) |
175 |
|
: _Ptr(_Pnode) |
176 |
|
{ // construct with node pointer _Pnode |
177 |
|
_SCL_SECURE_TRAITS_VALIDATE(_Plist != NULL); |
178 |
|
this->_Set_container(_Plist); |
179 |
|
} |
180 |
|
|
181 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
182 |
|
explicit _Const_iterator(_Nodeptr _Pnode) |
183 |
|
: _Ptr(_Pnode) |
184 |
|
{ // construct with node pointer _Pnode |
185 |
|
} |
186 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
187 |
|
|
188 |
|
#if _SECURE_SCL |
189 |
|
typedef typename _Secure_validation_helper<_SECURE_VALIDATION>::_Checked_iterator_category _Checked_iterator_category; |
190 |
|
typedef typename _If<_SECURE_VALIDATION, |
191 |
|
_Const_iterator<false>, |
192 |
|
_Unchanged_checked_iterator_base_type_tag>::_Result _Checked_iterator_base_type; |
193 |
|
|
194 |
|
friend _Const_iterator<false>; |
195 |
|
friend _Const_iterator<true>; |
196 |
|
|
197 |
|
_Const_iterator<false> _Checked_iterator_base() const |
198 |
|
{ |
199 |
|
_Const_iterator<false> _Base(this->_Ptr, ((_Myt *)this->_Getmycont())); |
200 |
|
return _Base; |
201 |
|
} |
202 |
|
|
203 |
|
void _Checked_iterator_assign_from_base(_Const_iterator<false> _Base) |
204 |
|
{ |
205 |
|
_SCL_SECURE_VALIDATE(this->_Same_container(_Base)); |
206 |
|
this->_Ptr = _Base._Ptr; |
207 |
|
} |
208 |
|
#endif |
209 |
|
|
210 |
|
const_reference operator*() const |
211 |
|
{ // return designated value |
212 |
|
|
213 |
|
#if _HAS_ITERATOR_DEBUGGING |
214 |
|
if (this->_Mycont == 0 |
215 |
|
|| _Ptr == 0 |
216 |
|
|| _Ptr == ((_Myt *)this->_Mycont)->_Myhead) |
217 |
|
{ |
218 |
|
_DEBUG_ERROR("list iterator not dereferencable"); |
219 |
|
_SCL_SECURE_TRAITS_OUT_OF_RANGE; |
220 |
|
} |
221 |
|
#else |
222 |
|
_SCL_SECURE_TRAITS_VALIDATE(this->_Has_container()); |
223 |
|
_SCL_SECURE_TRAITS_VALIDATE_RANGE(_Ptr != ((_Myt *)(this->_Getmycont()))->_Myhead); |
224 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
225 |
|
|
226 |
|
return (_Myval(_Ptr)); |
227 |
|
} |
228 |
|
|
229 |
|
_Ctptr operator->() const |
230 |
|
{ // return pointer to class object |
231 |
|
return (&**this); |
232 |
|
} |
233 |
|
|
234 |
|
_Myt_iter& operator++() |
235 |
|
{ // preincrement |
236 |
|
|
237 |
|
#if _HAS_ITERATOR_DEBUGGING |
238 |
|
if (this->_Mycont == 0 |
239 |
|
|| _Ptr == 0 |
240 |
|
|| _Ptr == ((_Myt *)this->_Mycont)->_Myhead) |
241 |
|
{ |
242 |
|
_DEBUG_ERROR("list iterator not incrementable"); |
243 |
|
_SCL_SECURE_TRAITS_OUT_OF_RANGE; |
244 |
|
} |
245 |
|
#else |
246 |
|
_SCL_SECURE_TRAITS_VALIDATE(this->_Has_container()); |
247 |
|
_SCL_SECURE_TRAITS_VALIDATE_RANGE(_Ptr != ((_Myt *)(this->_Getmycont()))->_Myhead); |
248 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
249 |
|
|
250 |
|
_Ptr = _Nextnode(_Ptr); |
251 |
|
return (*this); |
252 |
|
} |
253 |
|
|
254 |
|
_Myt_iter operator++(int) |
255 |
|
{ // postincrement |
256 |
|
_Myt_iter _Tmp = *this; |
257 |
|
++*this; |
258 |
|
return (_Tmp); |
259 |
|
} |
260 |
|
|
261 |
|
_Myt_iter& operator--() |
262 |
|
{ // predecrement |
263 |
|
|
264 |
|
#if _HAS_ITERATOR_DEBUGGING |
265 |
|
if (this->_Mycont == 0 |
266 |
|
|| _Ptr == 0 |
267 |
|
|| (_Ptr = _Prevnode(_Ptr)) |
268 |
|
== ((_Myt *)this->_Mycont)->_Myhead) |
269 |
|
{ |
270 |
|
_DEBUG_ERROR("list iterator not decrementable"); |
271 |
|
_SCL_SECURE_TRAITS_OUT_OF_RANGE; |
272 |
|
} |
273 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
274 |
|
_SCL_SECURE_TRAITS_VALIDATE(this->_Has_container()); |
275 |
|
_Ptr = _Prevnode(_Ptr); |
276 |
|
_SCL_SECURE_TRAITS_VALIDATE_RANGE(_Ptr != ((_Myt *)(this->_Getmycont()))->_Myhead); |
277 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
278 |
|
|
279 |
|
return (*this); |
280 |
|
} |
281 |
|
|
282 |
|
_Myt_iter operator--(int) |
283 |
|
{ // postdecrement |
284 |
|
_Myt_iter _Tmp = *this; |
285 |
|
--*this; |
286 |
|
return (_Tmp); |
287 |
|
} |
288 |
|
|
289 |
|
bool operator==(const _Myt_iter& _Right) const |
290 |
|
{ // test for iterator equality |
291 |
|
|
292 |
|
#if _HAS_ITERATOR_DEBUGGING |
293 |
|
_Compat(_Right); |
294 |
|
#else |
295 |
|
_SCL_SECURE_TRAITS_VALIDATE(this->_Has_container() && this->_Same_container(_Right)); |
296 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
297 |
|
|
298 |
|
return (_Ptr == _Right._Ptr); |
299 |
|
} |
300 |
|
|
301 |
|
bool operator!=(const _Myt_iter& _Right) const |
302 |
|
{ // test for iterator inequality |
303 |
|
return (!(*this == _Right)); |
304 |
|
} |
305 |
|
|
306 |
|
_Nodeptr _Mynode() const |
307 |
|
{ // return node pointer |
308 |
|
return (_Ptr); |
309 |
|
} |
310 |
|
|
311 |
|
#if _HAS_ITERATOR_DEBUGGING |
312 |
|
void _Compat(const _Myt_iter& _Right) const |
313 |
|
{ // test for compatible iterator pair |
314 |
|
if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont) |
315 |
|
{ |
316 |
|
_DEBUG_ERROR("list iterators incompatible"); |
317 |
|
_SCL_SECURE_TRAITS_INVALID_ARGUMENT; |
318 |
|
} |
319 |
|
} |
320 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
321 |
|
|
322 |
|
_Nodeptr _Ptr; // pointer to node |
323 |
|
}; |
324 |
|
|
325 |
|
typedef _Const_iterator<_SECURE_VALIDATION_DEFAULT> const_iterator; |
326 |
|
|
327 |
|
// CLASS iterator |
328 |
|
template <bool _SECURE_VALIDATION> class _Iterator; |
329 |
|
friend class _Iterator<_SECURE_VALIDATION_DEFAULT>; |
330 |
|
#if _SECURE_SCL |
331 |
|
friend class _Iterator<false>; |
332 |
|
#endif |
333 |
|
|
334 |
|
template <bool _SECURE_VALIDATION> |
335 |
|
class _Iterator |
336 |
|
: public _Const_iterator<_SECURE_VALIDATION> |
337 |
|
{ // iterator for mutable list |
338 |
|
public: |
339 |
|
friend class list<_Ty, _Ax>; |
340 |
|
typedef _Iterator<_SECURE_VALIDATION> _Myt_iter; |
341 |
|
typedef _Const_iterator<_SECURE_VALIDATION> _Mybase_iter; |
342 |
|
typedef bidirectional_iterator_tag iterator_category; |
343 |
|
typedef _Ty value_type; |
344 |
|
typedef _Dift difference_type; |
345 |
|
typedef _Tptr pointer; |
346 |
|
typedef _Reft reference; |
347 |
|
|
348 |
|
_Iterator() |
349 |
|
{ // construct with null node |
350 |
|
} |
351 |
|
|
352 |
|
#if _HAS_ITERATOR_DEBUGGING |
353 |
|
_Iterator(_Nodeptr _Pnode, const _Myt *_Plist) |
354 |
|
: _Mybase_iter(_Pnode, _Plist) |
355 |
|
{ // construct with node pointer _Pnode |
356 |
|
} |
357 |
|
|
358 |
|
#elif _SECURE_SCL |
359 |
|
_Iterator(_Nodeptr _Pnode, const _Myt *_Plist) |
360 |
|
: _Mybase_iter(_Pnode, _Plist) |
361 |
|
{ // construct with node pointer _Pnode |
362 |
|
} |
363 |
|
|
364 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
365 |
|
explicit _Iterator(_Nodeptr _Pnode) |
366 |
|
: _Mybase_iter(_Pnode) |
367 |
|
{ // construct with node pointer _Pnode |
368 |
|
} |
369 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
370 |
|
|
371 |
|
#if _SECURE_SCL |
372 |
|
typedef typename _If<_SECURE_VALIDATION, |
373 |
|
_Iterator<false>, |
374 |
|
_Unchanged_checked_iterator_base_type_tag>::_Result _Checked_iterator_base_type; |
375 |
|
|
376 |
|
friend _Iterator<false>; |
377 |
|
friend _Iterator<true>; |
378 |
|
|
379 |
|
_Iterator<false> _Checked_iterator_base() const |
380 |
|
{ |
381 |
|
_Iterator<false> _Base(this->_Ptr, ((_Myt *)this->_Getmycont())); |
382 |
|
return _Base; |
383 |
|
} |
384 |
|
|
385 |
|
void _Checked_iterator_assign_from_base(_Iterator<false> _Base) |
386 |
|
{ |
387 |
|
_SCL_SECURE_VALIDATE(this->_Same_container(_Base)); |
388 |
|
this->_Ptr = _Base._Ptr; |
389 |
|
} |
390 |
|
#endif |
391 |
|
|
392 |
|
reference operator*() const |
393 |
|
{ // return designated value |
394 |
|
return ((reference)**(_Mybase_iter *)this); |
395 |
|
} |
396 |
|
|
397 |
|
_Tptr operator->() const |
398 |
|
{ // return pointer to class object |
399 |
|
return (&**this); |
400 |
|
} |
401 |
|
|
402 |
|
_Myt_iter& operator++() |
403 |
|
{ // preincrement |
404 |
|
++(*(_Mybase_iter *)this); |
405 |
|
return (*this); |
406 |
|
} |
407 |
|
|
408 |
|
_Myt_iter operator++(int) |
409 |
|
{ // postincrement |
410 |
|
_Myt_iter _Tmp = *this; |
411 |
|
++*this; |
412 |
|
return (_Tmp); |
413 |
|
} |
414 |
|
|
415 |
|
_Myt_iter& operator--() |
416 |
|
{ // predecrement |
417 |
|
--(*(_Mybase_iter *)this); |
418 |
|
return (*this); |
419 |
|
} |
420 |
|
|
421 |
|
_Myt_iter operator--(int) |
422 |
|
{ // postdecrement |
423 |
|
_Myt_iter _Tmp = *this; |
424 |
|
--*this; |
425 |
|
return (_Tmp); |
426 |
|
} |
427 |
|
}; |
428 |
|
|
429 |
|
typedef _Iterator<_SECURE_VALIDATION_DEFAULT> iterator; |
430 |
|
|
431 |
|
typedef std::reverse_iterator<iterator> reverse_iterator; |
432 |
|
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
433 |
|
|
434 |
|
list() |
435 |
|
: _Mybase(), _Myhead(_Buynode()), _Mysize(0) |
436 |
|
{ // construct empty list |
437 |
|
} |
438 |
|
|
439 |
|
explicit list(const _Alloc& _Al) |
440 |
|
: _Mybase(_Al), _Myhead(_Buynode()), _Mysize(0) |
441 |
|
{ // construct empty list, allocator |
442 |
|
} |
443 |
|
|
444 |
|
explicit list(size_type _Count) |
445 |
|
: _Mybase(), _Mysize(0) |
446 |
|
{ // construct list from _Count * _Ty() |
447 |
|
_Ty _Val = _Ty(); |
448 |
|
_Myhead = _Buynode(); |
449 |
|
_Construct_n(_Count, _Val); |
450 |
|
} |
451 |
|
|
452 |
|
list(size_type _Count, const _Ty& _Val) |
453 |
|
: _Mybase(), _Myhead(_Buynode()), _Mysize(0) |
454 |
|
{ // construct list from _Count * _Val |
455 |
|
_Construct_n(_Count, _Val); |
456 |
|
} |
457 |
|
|
458 |
|
list(size_type _Count, const _Ty& _Val, const _Alloc& _Al) |
459 |
|
: _Mybase(_Al), _Myhead(_Buynode()), _Mysize(0) |
460 |
|
{ // construct list, allocator from _Count * _Val |
461 |
|
_Construct_n(_Count, _Val); |
462 |
|
} |
463 |
|
|
464 |
|
list(const _Myt& _Right) |
465 |
|
: _Mybase(_Right._Alval), |
466 |
|
_Myhead(_Buynode()), _Mysize(0) |
467 |
|
{ // construct list by copying _Right |
468 |
|
_TRY_BEGIN |
469 |
|
insert(begin(), _Right.begin(), _Right.end()); |
470 |
|
_CATCH_ALL |
471 |
|
_Tidy(); |
472 |
|
_RERAISE; |
473 |
|
_CATCH_END |
474 |
|
} |
475 |
|
|
476 |
|
template<class _Iter> |
477 |
|
list(_Iter _First, _Iter _Last) |
478 |
|
: _Mybase(), _Myhead(_Buynode()), _Mysize(0) |
479 |
|
{ // construct list from [_First, _Last) |
480 |
|
_Construct(_First, _Last, _Iter_cat(_First)); |
481 |
|
} |
482 |
|
|
483 |
|
template<class _Iter> |
484 |
|
list(_Iter _First, _Iter _Last, const _Alloc& _Al) |
485 |
|
: _Mybase(_Al), _Myhead(_Buynode()), _Mysize(0) |
486 |
|
{ // construct list, allocator from [_First, _Last) |
487 |
|
_Construct(_First, _Last, _Iter_cat(_First)); |
488 |
|
} |
489 |
|
|
490 |
|
template<class _Iter> |
491 |
|
void _Construct(_Iter _Count, _Iter _Val, _Int_iterator_tag) |
492 |
|
{ // construct list from _Count * _Val |
493 |
|
_Construct_n((size_type)_Count, (_Ty)_Val); |
494 |
|
} |
495 |
|
|
496 |
|
template<class _Iter> |
497 |
|
void _Construct(_Iter _First, |
498 |
|
_Iter _Last, input_iterator_tag) |
499 |
|
{ // construct list from [_First, _Last), input iterators |
500 |
|
_TRY_BEGIN |
501 |
|
insert(begin(), _First, _Last); |
502 |
|
_CATCH_ALL |
503 |
|
_Tidy(); |
504 |
|
_RERAISE; |
505 |
|
_CATCH_END |
506 |
|
} |
507 |
|
|
508 |
|
void _Construct_n(size_type _Count, |
509 |
|
const _Ty& _Val) |
510 |
|
{ // construct from _Count * _Val |
511 |
|
_TRY_BEGIN |
512 |
|
_Insert_n(begin(), _Count, _Val); |
513 |
|
_CATCH_ALL |
514 |
|
_Tidy(); |
515 |
|
_RERAISE; |
516 |
|
_CATCH_END |
517 |
|
} |
518 |
|
|
519 |
|
~list() |
520 |
|
{ // destroy the object |
521 |
|
_Tidy(); |
522 |
|
} |
523 |
|
|
524 |
|
_Myt& operator=(const _Myt& _Right) |
525 |
|
{ // assign _Right |
526 |
|
if (this != &_Right) |
527 |
|
assign(_Right.begin(), _Right.end()); |
528 |
|
return (*this); |
529 |
|
} |
530 |
|
|
531 |
|
#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL |
532 |
|
iterator begin() |
533 |
|
{ // return iterator for beginning of mutable sequence |
534 |
|
return (iterator(_Nextnode(_Myhead), this)); |
535 |
|
} |
536 |
|
|
537 |
|
const_iterator begin() const |
538 |
|
{ // return iterator for beginning of nonmutable sequence |
539 |
|
return (const_iterator(_Nextnode(_Myhead), this)); |
540 |
|
} |
541 |
|
|
542 |
|
iterator end() |
543 |
|
{ // return iterator for end of mutable sequence |
544 |
|
return (iterator(_Myhead, this)); |
545 |
|
} |
546 |
|
|
547 |
|
const_iterator end() const |
548 |
|
{ // return iterator for end of nonmutable sequence |
549 |
|
return (const_iterator(_Myhead, this)); |
550 |
|
} |
551 |
|
|
552 |
|
iterator _Make_iter(const_iterator _Where) const |
553 |
|
{ // make iterator from const_iterator |
554 |
|
return (iterator(_Where._Ptr, this)); |
555 |
|
} |
556 |
|
|
557 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
558 |
|
iterator begin() |
559 |
|
{ // return iterator for beginning of mutable sequence |
560 |
|
return (iterator(_Nextnode(_Myhead))); |
561 |
|
} |
562 |
|
|
563 |
|
const_iterator begin() const |
564 |
|
{ // return iterator for beginning of nonmutable sequence |
565 |
|
return (const_iterator(_Nextnode(_Myhead))); |
566 |
|
} |
567 |
|
|
568 |
|
iterator end() |
569 |
|
{ // return iterator for end of mutable sequence |
570 |
|
return (iterator(_Myhead)); |
571 |
|
} |
572 |
|
|
573 |
|
const_iterator end() const |
574 |
|
{ // return iterator for end of nonmutable sequence |
575 |
|
return (const_iterator(_Myhead)); |
576 |
|
} |
577 |
|
|
578 |
|
iterator _Make_iter(const_iterator _Where) const |
579 |
|
{ // make iterator from const_iterator |
580 |
|
return (iterator(_Where._Ptr)); |
581 |
|
} |
582 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
583 |
|
|
584 |
|
reverse_iterator rbegin() |
585 |
|
{ // return iterator for beginning of reversed mutable sequence |
586 |
|
return (reverse_iterator(end())); |
587 |
|
} |
588 |
|
|
589 |
|
const_reverse_iterator rbegin() const |
590 |
|
{ // return iterator for beginning of reversed nonmutable sequence |
591 |
|
return (const_reverse_iterator(end())); |
592 |
|
} |
593 |
|
|
594 |
|
reverse_iterator rend() |
595 |
|
{ // return iterator for end of reversed mutable sequence |
596 |
|
return (reverse_iterator(begin())); |
597 |
|
} |
598 |
|
|
599 |
|
const_reverse_iterator rend() const |
600 |
|
{ // return iterator for end of reversed nonmutable sequence |
601 |
|
return (const_reverse_iterator(begin())); |
602 |
|
} |
603 |
|
|
604 |
|
void resize(size_type _Newsize) |
605 |
|
{ // determine new length, padding with _Ty() elements as needed |
606 |
|
resize(_Newsize, _Ty()); |
607 |
|
} |
608 |
|
|
609 |
|
void resize(size_type _Newsize, _Ty _Val) |
610 |
|
{ // determine new length, padding with _Val elements as needed |
611 |
|
if (_Mysize < _Newsize) |
612 |
|
_Insert_n(end(), _Newsize - _Mysize, _Val); |
613 |
|
else |
614 |
|
while (_Newsize < _Mysize) |
615 |
|
pop_back(); |
616 |
|
} |
617 |
|
|
618 |
|
size_type size() const |
619 |
|
{ // return length of sequence |
620 |
|
return (_Mysize); |
621 |
|
} |
622 |
|
|
623 |
|
size_type max_size() const |
624 |
|
{ // return maximum possible length of sequence |
625 |
|
return (this->_Alval.max_size()); |
626 |
|
} |
627 |
|
|
628 |
|
bool empty() const |
629 |
|
{ // test if sequence is empty |
630 |
|
return (_Mysize == 0); |
631 |
|
} |
632 |
|
|
633 |
|
allocator_type get_allocator() const |
634 |
|
{ // return allocator object for values |
635 |
|
return (this->_Alval); |
636 |
|
} |
637 |
|
|
638 |
|
reference front() |
639 |
|
{ // return first element of mutable sequence |
640 |
|
return (*begin()); |
641 |
|
} |
642 |
|
|
643 |
|
const_reference front() const |
644 |
|
{ // return first element of nonmutable sequence |
645 |
|
return (*begin()); |
646 |
|
} |
647 |
|
|
648 |
|
reference back() |
649 |
|
{ // return last element of mutable sequence |
650 |
|
return (*(--end())); |
651 |
|
} |
652 |
|
|
653 |
|
const_reference back() const |
654 |
|
{ // return last element of nonmutable sequence |
655 |
|
return (*(--end())); |
656 |
|
} |
657 |
|
|
658 |
|
void push_front(const _Ty& _Val) |
659 |
|
{ // insert element at beginning |
660 |
|
_Insert(begin(), _Val); |
661 |
|
} |
662 |
|
|
663 |
|
void pop_front() |
664 |
|
{ // erase element at beginning |
665 |
|
erase(begin()); |
666 |
|
} |
667 |
|
|
668 |
|
void push_back(const _Ty& _Val) |
669 |
|
{ // insert element at end |
670 |
|
_Insert(end(), _Val); |
671 |
|
} |
672 |
|
|
673 |
|
void pop_back() |
674 |
|
{ // erase element at end |
675 |
|
erase(--end()); |
676 |
|
} |
677 |
|
|
678 |
|
template<class _Iter> |
679 |
|
void assign(_Iter _First, _Iter _Last) |
680 |
|
{ // assign [_First, _Last) |
681 |
|
_Assign(_First, _Last, _Iter_cat(_First)); |
682 |
|
} |
683 |
|
|
684 |
|
template<class _Iter> |
685 |
|
void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag) |
686 |
|
{ // assign _Count * _Val |
687 |
|
_Assign_n((size_type)_Count, (_Ty)_Val); |
688 |
|
} |
689 |
|
|
690 |
|
template<class _Iter> |
691 |
|
void _Assign(_Iter _First, _Iter _Last, input_iterator_tag) |
692 |
|
{ // assign [_First, _Last), input iterators |
693 |
|
clear(); |
694 |
|
insert(begin(), _First, _Last); |
695 |
|
} |
696 |
|
|
697 |
|
void assign(size_type _Count, const _Ty& _Val) |
698 |
|
{ // assign _Count * _Val |
699 |
|
_Assign_n(_Count, _Val); |
700 |
|
} |
701 |
|
|
702 |
|
iterator insert(const_iterator _Where, const _Ty& _Val) |
703 |
|
{ // insert _Val at _Where |
704 |
|
_Insert(_Where, _Val); |
705 |
|
return (_Make_iter(--_Where)); |
706 |
|
} |
707 |
|
|
708 |
|
void _Insert(const_iterator _Where, |
709 |
|
const _Ty& _Val) |
710 |
|
{ // insert _Val at _Where |
711 |
|
|
712 |
|
#if _HAS_ITERATOR_DEBUGGING |
713 |
|
if (_Where._Mycont != this) |
714 |
|
_DEBUG_ERROR("list insert iterator outside range"); |
715 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
716 |
|
|
717 |
|
_Nodeptr _Pnode = _Where._Mynode(); |
718 |
|
_Nodeptr _Newnode = _Buynode(_Pnode, _Prevnode(_Pnode), _Val); |
719 |
|
_Incsize(1); |
720 |
|
_Prevnode(_Pnode) = _Newnode; |
721 |
|
_Nextnode(_Prevnode(_Newnode)) = _Newnode; |
722 |
|
} |
723 |
|
|
724 |
|
void insert(const_iterator _Where, size_type _Count, const _Ty& _Val) |
725 |
|
{ // insert _Count * _Val at _Where |
726 |
|
_Insert_n(_Where, _Count, _Val); |
727 |
|
} |
728 |
|
|
729 |
|
template<class _Iter> |
730 |
|
void insert(const_iterator _Where, _Iter _First, _Iter _Last) |
731 |
|
{ // insert [_First, _Last) at _Where |
732 |
|
_Insert(_Where, _First, _Last, _Iter_cat(_First)); |
733 |
|
} |
734 |
|
|
735 |
|
template<class _Iter> |
736 |
|
void _Insert(const_iterator _Where, _Iter _Count, _Iter _Val, |
737 |
|
_Int_iterator_tag) |
738 |
|
{ // insert _Count * _Val at _Where |
739 |
|
_Insert_n(_Where, (size_type)_Count, (_Ty)_Val); |
740 |
|
} |
741 |
|
|
742 |
|
template<class _Iter> |
743 |
|
void _Insert(const_iterator _Where, |
744 |
|
_Iter _First, _Iter _Last, input_iterator_tag) |
745 |
|
{ // insert [_First, _Last) at _Where, input iterators |
746 |
|
size_type _Num = 0; |
747 |
|
|
748 |
|
_TRY_BEGIN |
749 |
|
for (; _First != _Last; ++_First, ++_Num) |
750 |
|
_Insert(_Where, *_First); |
751 |
|
_CATCH_ALL |
752 |
|
for (; 0 < _Num; --_Num) |
753 |
|
{ // undo inserts |
754 |
|
const_iterator _Before = _Where; |
755 |
|
erase(--_Before); |
756 |
|
} |
757 |
|
_RERAISE; |
758 |
|
_CATCH_END |
759 |
|
} |
760 |
|
|
761 |
|
template<class _Iter> |
762 |
|
void _Insert(const_iterator _Where, |
763 |
|
_Iter _First, _Iter _Last, forward_iterator_tag) |
764 |
|
{ // insert [_First, _Last) at _Where, forward iterators |
765 |
|
|
766 |
|
#if _HAS_ITERATOR_DEBUGGING |
767 |
|
_DEBUG_RANGE(_First, _Last); |
768 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
769 |
|
|
770 |
|
_Iter _Next = _First; |
771 |
|
|
772 |
|
_TRY_BEGIN |
773 |
|
for (; _First != _Last; ++_First) |
774 |
|
_Insert(_Where, *_First); |
775 |
|
_CATCH_ALL |
776 |
|
for (; _Next != _First; ++_Next) |
777 |
|
{ // undo inserts |
778 |
|
const_iterator _Before = _Where; |
779 |
|
erase(--_Before); |
780 |
|
} |
781 |
|
_RERAISE; |
782 |
|
_CATCH_END |
783 |
|
} |
784 |
|
|
785 |
|
iterator erase(const_iterator _Where) |
786 |
|
{ // erase element at _Where |
787 |
|
|
788 |
|
#if _HAS_ITERATOR_DEBUGGING |
789 |
|
if (_Where._Mycont != this || _Where._Ptr == _Myhead) |
790 |
|
_DEBUG_ERROR("list erase iterator outside range"); |
791 |
|
_Nodeptr _Pnode = (_Where++)._Mynode(); |
792 |
|
_Orphan_ptr(*this, _Pnode); |
793 |
|
|
794 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
795 |
|
_Nodeptr _Pnode = (_Where++)._Mynode(); |
796 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
797 |
|
|
798 |
|
if (_Pnode != _Myhead) |
799 |
|
{ // not list head, safe to erase |
800 |
|
_Nextnode(_Prevnode(_Pnode)) = _Nextnode(_Pnode); |
801 |
|
_Prevnode(_Nextnode(_Pnode)) = _Prevnode(_Pnode); |
802 |
|
this->_Alnod.destroy(_Pnode); |
803 |
|
this->_Alnod.deallocate(_Pnode, 1); |
804 |
|
--_Mysize; |
805 |
|
} |
806 |
|
return (_Make_iter(_Where)); |
807 |
|
} |
808 |
|
|
809 |
|
iterator erase(const_iterator _First, const_iterator _Last) |
810 |
|
{ // erase [_First, _Last) |
811 |
|
if (_First == begin() && _Last == end()) |
812 |
|
{ // erase all and return fresh iterator |
813 |
|
clear(); |
814 |
|
return (end()); |
815 |
|
} |
816 |
|
else |
817 |
|
{ // erase subrange |
818 |
|
while (_First != _Last) |
819 |
|
_First = erase(_First); |
820 |
|
return (_Make_iter(_Last)); |
821 |
|
} |
822 |
|
} |
823 |
|
|
824 |
|
void clear() |
825 |
|
{ // erase all |
826 |
|
|
827 |
|
#if _HAS_ITERATOR_DEBUGGING |
828 |
|
this->_Orphan_ptr(*this, 0); |
829 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
830 |
|
|
831 |
|
_Nodeptr _Pnext; |
832 |
|
_Nodeptr _Pnode = _Nextnode(_Myhead); |
833 |
|
_Nextnode(_Myhead) = _Myhead; |
834 |
|
_Prevnode(_Myhead) = _Myhead; |
835 |
|
_Mysize = 0; |
836 |
|
|
837 |
|
for (; _Pnode != _Myhead; _Pnode = _Pnext) |
838 |
|
{ // delete an element |
839 |
|
_Pnext = _Nextnode(_Pnode); |
840 |
|
this->_Alnod.destroy(_Pnode); |
841 |
|
this->_Alnod.deallocate(_Pnode, 1); |
842 |
|
} |
843 |
|
} |
844 |
|
|
845 |
|
void swap(_Myt& _Right) |
846 |
|
{ // exchange contents with _Right |
847 |
|
if (this == &_Right) |
848 |
|
; // same object, do nothing |
849 |
|
else if (this->_Alval == _Right._Alval) |
850 |
|
{ // same allocator, swap control information |
851 |
|
|
852 |
|
#if _HAS_ITERATOR_DEBUGGING |
853 |
|
this->_Swap_all(_Right); |
854 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
855 |
|
|
856 |
|
this->_Swap_aux(_Right); |
857 |
|
|
858 |
|
std::swap(_Myhead, _Right._Myhead); |
859 |
|
std::swap(_Mysize, _Right._Mysize); |
860 |
|
} |
861 |
|
else |
862 |
|
{ // different allocator, do splices |
863 |
|
this->_Swap_aux(_Right); |
864 |
|
|
865 |
|
iterator _Where = begin(); |
866 |
|
splice(_Where, _Right); |
867 |
|
_Right.splice(_Right.begin(), *this, _Where, end()); |
868 |
|
} |
869 |
|
} |
870 |
|
|
871 |
|
|
872 |
|
|
873 |
|
void splice(const_iterator _Where, _Myt& _Right) |
874 |
|
{ // splice all of _Right at _Where |
875 |
|
if (this != &_Right && !_Right.empty()) |
876 |
|
{ // worth splicing, do it |
877 |
|
_Splice(_Where, _Right, _Right.begin(), _Right.end(), |
878 |
|
_Right._Mysize); |
879 |
|
} |
880 |
|
} |
881 |
|
|
882 |
|
void splice(const_iterator _Where, _Myt& _Right, const_iterator _First) |
883 |
|
{ // splice _Right [_First, _First + 1) at _Where |
884 |
|
|
885 |
|
#if _HAS_ITERATOR_DEBUGGING |
886 |
|
if (_First == _Right.end()) |
887 |
|
_DEBUG_ERROR("list splice iterator outside range"); |
888 |
|
else |
889 |
|
|
890 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
891 |
|
if (_First != _Right.end()) |
892 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
893 |
|
|
894 |
|
{ // element exists, try splice |
895 |
|
const_iterator _Last = _First; |
896 |
|
++_Last; |
897 |
|
if (this != &_Right |
898 |
|
|| (_Where != _First && _Where != _Last)) |
899 |
|
_Splice(_Where, _Right, _First, _Last, 1); |
900 |
|
} |
901 |
|
} |
902 |
|
|
903 |
|
void splice(const_iterator _Where, |
904 |
|
_Myt& _Right, const_iterator _First, const_iterator _Last) |
905 |
|
{ // splice _Right [_First, _Last) at _Where |
906 |
|
if (_First != _Last && (this != &_Right || _Where != _Last)) |
907 |
|
{ // worth splicing, do it |
908 |
|
size_type _Count = 0; |
909 |
|
if (this == &_Right) |
910 |
|
; // just rearrange this list |
911 |
|
else if (_First == _Right.begin() && _Last == _Right.end()) |
912 |
|
_Count = _Right._Mysize; // splice in whole list |
913 |
|
else |
914 |
|
{ // count nodes and check for knot |
915 |
|
const_iterator _Next = _First; |
916 |
|
|
917 |
|
for (; _Next != _Last; ++_Next, ++_Count) |
918 |
|
if (_Next == _Right.end()) |
919 |
|
if (_First == _Right.end()) |
920 |
|
_THROW(length_error, "list<T> bad splice"); |
921 |
|
} |
922 |
|
_Splice(_Where, _Right, _First, _Last, _Count); |
923 |
|
} |
924 |
|
} |
925 |
|
|
926 |
|
void remove(const _Ty& _Val_arg) |
927 |
|
{ // erase each element matching _Val |
928 |
|
/* Dinkumware makes a copy of _Val_arg in case it's removed along the way, i.e. |
929 |
|
* when the user pass an element of the list as _Val_arg. |
930 |
|
* |
931 |
|
* We believe that the signature of std::list::remove should be changed |
932 |
|
* from remove(const _Ty&) to remove(_Ty) to explicitly indicate that a copy is involved. |
933 |
|
*/ |
934 |
|
const _Ty _Val = _Val_arg; // in case it's removed along the way |
935 |
|
iterator _Last = end(); |
936 |
|
for (iterator _First = begin(); _First != _Last; ) |
937 |
|
if (*_First == _Val) |
938 |
|
_First = erase(_First); |
939 |
|
else |
940 |
|
++_First; |
941 |
|
} |
942 |
|
|
943 |
|
template<class _Pr1> |
944 |
|
void remove_if(_Pr1 _Pred) |
945 |
|
{ // erase each element satisfying _Pr1 |
946 |
|
iterator _Last = end(); |
947 |
|
for (iterator _First = begin(); _First != _Last; ) |
948 |
|
if (_Pred(*_First)) |
949 |
|
_First = erase(_First); |
950 |
|
else |
951 |
|
++_First; |
952 |
|
} |
953 |
|
|
954 |
|
void unique() |
955 |
|
{ // erase each element matching previous |
956 |
|
if (2 <= _Mysize) |
957 |
|
{ // worth doing |
958 |
|
iterator _First = begin(); |
959 |
|
iterator _After = _First; |
960 |
|
for (++_After; _After != end(); ) |
961 |
|
if (*_First == *_After) |
962 |
|
_After = erase(_After); |
963 |
|
else |
964 |
|
_First = _After++; |
965 |
|
} |
966 |
|
} |
967 |
|
|
968 |
|
template<class _Pr2> |
969 |
|
void unique(_Pr2 _Pred) |
970 |
|
{ // erase each element satisfying _Pred with previous |
971 |
|
if (2 <= _Mysize) |
972 |
|
{ // worth doing |
973 |
|
iterator _First = begin(); |
974 |
|
iterator _After = _First; |
975 |
|
for (++_After; _After != end(); ) |
976 |
|
if (_Pred(*_First, *_After)) |
977 |
|
_After = erase(_After); |
978 |
|
else |
979 |
|
_First = _After++; |
980 |
|
} |
981 |
|
} |
982 |
|
|
983 |
|
void merge(_Myt& _Right) |
984 |
|
{ // merge in elements from _Right, both ordered by operator< |
985 |
|
if (&_Right != this) |
986 |
|
{ // safe to merge, do it |
987 |
|
iterator _First1 = begin(), _Last1 = end(); |
988 |
|
iterator _First2 = _Right.begin(), _Last2 = _Right.end(); |
989 |
|
_DEBUG_ORDER(_First1, _Last1); |
990 |
|
_DEBUG_ORDER(_First2, _Last2); |
991 |
|
|
992 |
|
while (_First1 != _Last1 && _First2 != _Last2) |
993 |
|
if (_DEBUG_LT(*_First2, *_First1)) |
994 |
|
{ // splice in an element from _Right |
995 |
|
iterator _Mid2 = _First2; |
996 |
|
_Splice(_First1, _Right, _First2, ++_Mid2, 1); |
997 |
|
_First2 = _Mid2; |
998 |
|
} |
999 |
|
else |
1000 |
|
++_First1; |
1011 |
|
if (&_Right != this) |
1012 |
|
{ // safe to merge, do it |
1013 |
|
iterator _First1 = begin(), _Last1 = end(); |
1014 |
|
iterator _First2 = _Right.begin(), _Last2 = _Right.end(); |
1015 |
|
_DEBUG_ORDER_PRED(_First1, _Last1, _Pred); |
1016 |
|
_DEBUG_ORDER_PRED(_First2, _Last2, _Pred); |
1017 |
|
|
1018 |
|
while (_First1 != _Last1 && _First2 != _Last2) |
1019 |
|
if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1)) |
1020 |
|
{ // splice in an element from _Right |
1021 |
|
iterator _Mid2 = _First2; |
1022 |
|
_Splice(_First1, _Right, _First2, ++_Mid2, 1); |
1023 |
|
_First2 = _Mid2; |
1024 |
|
} |
1025 |
|
else |
1026 |
|
++_First1; |
1027 |
|
|
1028 |
|
if (_First2 != _Last2) |
1029 |
|
_Splice(_Last1, _Right, _First2, _Last2, |
1030 |
|
_Right._Mysize); // splice remainder of _Right |
1031 |
|
} |
1032 |
|
} |
1033 |
|
|
1034 |
|
void sort() |
1035 |
|
{ // order sequence, using operator< |
1036 |
|
if (2 <= _Mysize) |
1037 |
|
{ // worth sorting, do it |
1038 |
|
const size_t _MAXBINS = 25; |
1039 |
|
_Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1]; |
1040 |
|
size_t _Maxbin = 0; |
1041 |
|
|
1042 |
|
while (!empty()) |
1043 |
|
{ // sort another element, using bins |
1044 |
|
_Templist._Splice(_Templist.begin(), *this, begin(), |
1045 |
|
++begin(), 1, true); // don't invalidate iterators |
1046 |
|
|
1047 |
|
size_t _Bin; |
1048 |
|
for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty(); |
1049 |
|
++_Bin) |
1050 |
|
{ // merge into ever larger bins |
1051 |
|
_Binlist[_Bin].merge(_Templist); |
1052 |
|
_Binlist[_Bin].swap(_Templist); |
1053 |
|
} |
1054 |
|
|
1055 |
|
if (_Bin == _MAXBINS) |
1056 |
|
_Binlist[_Bin - 1].merge(_Templist); |
1057 |
|
else |
1058 |
|
{ // spill to new bin, while they last |
1059 |
|
_Binlist[_Bin].swap(_Templist); |
1060 |
|
if (_Bin == _Maxbin) |
1061 |
|
++_Maxbin; |
1062 |
|
} |
1063 |
|
} |
1064 |
|
|
1065 |
|
for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin) |
1066 |
|
_Binlist[_Bin].merge(_Binlist[_Bin - 1]); // merge up |
1067 |
|
splice(begin(), _Binlist[_Maxbin - 1]); // result in last bin |
1068 |
|
} |
1069 |
|
} |
1070 |
|
|
1071 |
|
template<class _Pr3> |
1072 |
|
void sort(_Pr3 _Pred) |
1073 |
|
{ // order sequence, using _Pred |
1074 |
|
if (2 <= _Mysize) |
1075 |
|
{ // worth sorting, do it |
1076 |
|
const size_t _MAXBINS = 25; |
1077 |
|
_Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1]; |
1078 |
|
size_t _Maxbin = 0; |
1079 |
|
|
1080 |
|
while (!empty()) |
1081 |
|
{ // sort another element, using bins |
1082 |
|
_Templist._Splice(_Templist.begin(), *this, begin(), |
1083 |
|
++begin(), 1, true); // don't invalidate iterators |
1084 |
|
|
1085 |
|
size_t _Bin; |
1086 |
|
for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty(); |
1087 |
|
++_Bin) |
1088 |
|
{ // merge into ever larger bins |
1089 |
|
_Binlist[_Bin].merge(_Templist, _Pred); |
1090 |
|
_Binlist[_Bin].swap(_Templist); |
1091 |
|
} |
1092 |
|
|
1093 |
|
if (_Bin == _MAXBINS) |
1094 |
|
_Binlist[_Bin - 1].merge(_Templist, _Pred); |
1095 |
|
else |
1096 |
|
{ // spill to new bin, while they last |
1097 |
|
_Binlist[_Bin].swap(_Templist); |
1098 |
|
if (_Bin == _Maxbin) |
1099 |
|
++_Maxbin; |
1100 |
|
} |
1101 |
|
} |
1102 |
|
|
1103 |
|
for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin) |
1104 |
|
_Binlist[_Bin].merge(_Binlist[_Bin - 1], |
1105 |
|
_Pred); // merge up |
1106 |
|
splice(begin(), _Binlist[_Maxbin - 1]); // result in last bin |
1107 |
|
} |
1108 |
|
} |
1109 |
|
|
1110 |
|
void reverse() |
1111 |
|
{ // reverse sequence |
1112 |
|
if (2 <= _Mysize) |
1113 |
|
{ // worth doing |
1114 |
|
iterator _Last = end(); |
1115 |
|
for (iterator _Next = ++begin(); _Next != _Last; ) |
1116 |
|
{ // move next element to beginning |
1117 |
|
iterator _Before = _Next; |
1118 |
|
_Splice(begin(), *this, _Before, ++_Next, 1); |
1119 |
|
} |
1120 |
|
} |
1121 |
|
} |
1122 |
|
|
1123 |
|
void _Splice(const_iterator _Where, |
1124 |
|
_Myt& _Right, const_iterator _First, const_iterator _Last, |
1125 |
|
size_type _Count, bool _Keep = false) |
1126 |
|
{ // splice _Right [_First, _Last) before _Where |
1127 |
|
#if _HAS_ITERATOR_DEBUGGING |
1128 |
|
if (_Where._Mycont != this) |
1129 |
|
_DEBUG_ERROR("list splice iterator outside range"); |
1130 |
|
if (this->_Alval == _Right._Alval) |
1131 |
|
{ // same allocator, just relink |
1132 |
|
if (!_Keep && this != &_Right) |
1133 |
|
for (const_iterator _Next = _First; _Next != _Last; ) |
1134 |
|
_Orphan_ptr(_Right, (_Next++)._Ptr); |
1135 |
|
|
1136 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
1137 |
|
_Keep; // unused in this branch |
1138 |
|
if (this->_Alval == _Right._Alval) |
1139 |
|
{ // same allocator, just relink |
1140 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1141 |
|
|
1142 |
|
if (this != &_Right) |
1143 |
|
{ // splicing from another list, adjust counts |
1144 |
|
_Incsize(_Count); |
1145 |
|
_Right._Mysize -= _Count; |
1146 |
|
} |
1147 |
|
_Nextnode(_Prevnode(_First._Mynode())) = _Last._Mynode(); |
1148 |
|
_Nextnode(_Prevnode(_Last._Mynode())) = _Where._Mynode(); |
1149 |
|
_Nextnode(_Prevnode(_Where._Mynode())) = _First._Mynode(); |
1150 |
|
_Nodeptr _Pnode = _Prevnode(_Where._Mynode()); |
1151 |
|
_Prevnode(_Where._Mynode()) = _Prevnode(_Last._Mynode()); |
1152 |
|
_Prevnode(_Last._Mynode()) = _Prevnode(_First._Mynode()); |
1153 |
|
_Prevnode(_First._Mynode()) = _Pnode; |
1154 |
|
} |
1155 |
|
else |
1156 |
|
{ // different allocator, copy nodes then erase source |
1157 |
|
insert(_Where, _First, _Last); |
1158 |
|
_Right.erase(_First, _Last); |
1159 |
|
} |
1160 |
|
} |
1161 |
|
|
1162 |
|
protected: |
1163 |
|
void _Assign_n(size_type _Count, const _Ty& _Val) |
1164 |
|
{ // assign _Count * _Val |
1165 |
|
_Ty _Tmp = _Val; // in case _Val is in sequence |
1166 |
|
clear(); |
1167 |
|
_Insert_n(begin(), _Count, _Tmp); |
1168 |
|
} |
1169 |
|
|
1170 |
|
_Nodeptr _Buynode() |
1171 |
|
{ // allocate a head node and set links |
1172 |
|
_Nodeptr _Pnode = this->_Alnod.allocate(1); |
1173 |
|
int _Linkcnt = 0; |
1174 |
|
|
1175 |
|
_TRY_BEGIN |
1176 |
|
this->_Alptr.construct(&_Nextnode(_Pnode), _Pnode); |
1177 |
|
++_Linkcnt; |
1178 |
|
this->_Alptr.construct(&_Prevnode(_Pnode), _Pnode); |
1179 |
|
_CATCH_ALL |
1180 |
|
if (0 < _Linkcnt) |
1181 |
|
this->_Alptr.destroy(&_Nextnode(_Pnode)); |
1182 |
|
this->_Alnod.deallocate(_Pnode, 1); |
1183 |
|
_RERAISE; |
1184 |
|
_CATCH_END |
1185 |
|
return (_Pnode); |
1186 |
|
} |
1187 |
|
|
1188 |
|
_Nodeptr _Buynode(_Nodeptr _Next, |
1189 |
|
_Nodeptr _Prev, const _Ty& _Val) |
1190 |
|
{ // allocate a node and set links and value |
1191 |
|
_Nodeptr _Pnode = this->_Alnod.allocate(1); |
1192 |
|
int _Linkcnt = 0; |
1193 |
|
|
1194 |
|
_TRY_BEGIN |
1195 |
|
this->_Alptr.construct(&_Nextnode(_Pnode), _Next); |
1196 |
|
++_Linkcnt; |
1197 |
|
this->_Alptr.construct(&_Prevnode(_Pnode), _Prev); |
1198 |
|
++_Linkcnt; |
1199 |
|
this->_Alval.construct(&_Myval(_Pnode), _Val); |
1200 |
|
_CATCH_ALL |
1201 |
|
if (1 < _Linkcnt) |
1202 |
|
this->_Alptr.destroy(&_Prevnode(_Pnode)); |
1203 |
|
if (0 < _Linkcnt) |
1204 |
|
this->_Alptr.destroy(&_Nextnode(_Pnode)); |
1205 |
|
this->_Alnod.deallocate(_Pnode, 1); |
1206 |
|
_RERAISE; |
1207 |
|
_CATCH_END |
1208 |
|
return (_Pnode); |
1209 |
|
} |
1210 |
|
|
1211 |
|
void _Tidy() |
1212 |
|
{ // free all storage |
1213 |
|
clear(); |
1214 |
|
this->_Alptr.destroy(&_Nextnode(_Myhead)); |
1215 |
|
this->_Alptr.destroy(&_Prevnode(_Myhead)); |
1216 |
|
this->_Alnod.deallocate(_Myhead, 1); |
1217 |
|
_Myhead = 0; |
1218 |
|
} |
1219 |
|
|
1220 |
|
void _Insert_n(const_iterator _Where, |
1221 |
|
size_type _Count, const _Ty& _Val) |
1222 |
|
{ // insert _Count * _Val at _Where |
1223 |
|
size_type _Countsave = _Count; |
1224 |
|
|
1225 |
|
_TRY_BEGIN |
1226 |
|
for (; 0 < _Count; --_Count) |
1227 |
|
_Insert(_Where, _Val); |
1228 |
|
_CATCH_ALL |
1229 |
|
for (; _Count < _Countsave; ++_Count) |
1230 |
|
{ // undo inserts |
1231 |
|
const_iterator _Before = _Where; |
1232 |
|
erase(--_Before); |
1233 |
|
} |
1234 |
|
_RERAISE; |
1235 |
|
_CATCH_END |
1236 |
|
} |
1237 |
|
|
1238 |
|
void _Incsize(size_type _Count) |
1239 |
|
{ // alter element count, with checking |
1240 |
|
if (max_size() - _Mysize < _Count) |
1241 |
|
_THROW(length_error, "list<T> too long"); |
1242 |
|
_Mysize += _Count; |
1243 |
|
} |
1244 |
|
|
1245 |
|
static void _Xran() |
1246 |
|
{ // report an out_of_range error |
1247 |
|
_THROW(out_of_range, "invalid list<T> subscript"); |
1248 |
|
} |
1249 |
|
|
1250 |
|
static void _Xinvarg() |
1251 |
|
{ // report an invalid_argument error |
1252 |
|
_THROW(invalid_argument, "invalid list<T> argument"); |
1253 |
|
} |
1254 |
|
|
1255 |
|
#if _HAS_ITERATOR_DEBUGGING |
1256 |
|
void _Orphan_ptr(_Myt& _Cont, _Nodeptr _Ptr) const |
1257 |
|
{ // orphan iterators with specified node pointers |
1258 |
|
_Lockit _Lock(_LOCK_DEBUG); |
1259 |
|
const_iterator **_Pnext = (const_iterator **)&_Cont._Myfirstiter; |
1260 |
|
while (*_Pnext != 0) |
1261 |
|
if ((*_Pnext)->_Ptr == _Myhead |
1262 |
|
|| _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr) |
1263 |
|
_Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter; |
1264 |
|
else |
1265 |
|
{ // orphan the iterator |
1266 |
|
(*_Pnext)->_Mycont = 0; |
1267 |
|
*_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter; |
1268 |
|
} |
1269 |
|
} |
1270 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1271 |
|
|
1272 |
|
_Nodeptr _Myhead; // pointer to head node |
1273 |
|
size_type _Mysize; // number of elements |
1274 |
|
}; |
1275 |
|
|
1276 |
|
// list implements a performant swap |
1277 |
|
template <class _Ty, class _Ax> |
1278 |
|
class _Move_operation_category<list<_Ty, _Ax> > |
1279 |
|
{ |
1280 |
|
public: |
1281 |
|
typedef _Swap_move_tag _Move_cat; |
1282 |
|
}; |
1283 |
|
|
1284 |
|
template<class _Ty, |
1285 |
|
class _Alloc> inline |
1286 |
|
void swap(list<_Ty, _Alloc>& _Left, list<_Ty, _Alloc>& _Right) |
1287 |
|
{ // swap _Left and _Right lists |
1288 |
|
_Left.swap(_Right); |
1289 |
|
} |
1290 |
|
|
1291 |
|
template<class _Ty, |
1292 |
|
class _Alloc> inline |
1293 |
|
bool operator==(const list<_Ty, _Alloc>& _Left, |
1294 |
|
const list<_Ty, _Alloc>& _Right) |
1295 |
|
{ // test for list equality |
1296 |
|
return (_Left.size() == _Right.size() |
1297 |
|
&& equal(_Left.begin(), _Left.end(), _Right.begin())); |
1298 |
|
} |
1299 |
|
|
1300 |
|
template<class _Ty, |
1301 |
|
class _Alloc> inline |
1302 |
|
bool operator!=(const list<_Ty, _Alloc>& _Left, |
1303 |
|
const list<_Ty, _Alloc>& _Right) |
1304 |
|
{ // test for list inequality |
1305 |
|
return (!(_Left == _Right)); |
1306 |
|
} |
1307 |
|
|
1308 |
|
template<class _Ty, |
1309 |
|
class _Alloc> inline |
1310 |
|
bool operator<(const list<_Ty, _Alloc>& _Left, |
1311 |
|
const list<_Ty, _Alloc>& _Right) |
1312 |
|
{ // test if _Left < _Right for lists |
1313 |
|
return (lexicographical_compare(_Left.begin(), _Left.end(), |
1314 |
|
_Right.begin(), _Right.end())); |
1315 |
|
} |
1316 |
|
|
1317 |
|
template<class _Ty, |
1318 |
|
class _Alloc> inline |
1319 |
|
bool operator>(const list<_Ty, _Alloc>& _Left, |
1320 |
|
const list<_Ty, _Alloc>& _Right) |
1321 |
|
{ // test if _Left > _Right for lists |
1322 |
|
return (_Right < _Left); |
1323 |
|
} |
1324 |
|
|
1325 |
|
template<class _Ty, |
1326 |
|
class _Alloc> inline |
1327 |
|
bool operator<=(const list<_Ty, _Alloc>& _Left, |
1328 |
|
const list<_Ty, _Alloc>& _Right) |
1329 |
|
{ // test if _Left <= _Right for lists |
1330 |
|
return (!(_Right < _Left)); |
1331 |
|
} |
1332 |
|
|
1333 |
|
template<class _Ty, |
1334 |
|
class _Alloc> inline |
1335 |
|
bool operator>=(const list<_Ty, _Alloc>& _Left, |
1336 |
|
const list<_Ty, _Alloc>& _Right) |
1337 |
|
{ // test if _Left >= _Right for lists |
1338 |
|
return (!(_Left < _Right)); |
1339 |
|
} |
1340 |
|
|
1341 |
|
#pragma warning(default:4284) |
1342 |
|
|
1343 |
|
#if _HAS_TRADITIONAL_STL |
1344 |
|
#define __list__ list |
1345 |
|
#endif /* _HAS_TRADITIONAL_STL */ |
1346 |
|
|
1347 |
|
_STD_END |
1348 |
|
|
1349 |
|
#ifdef _MSC_VER |
1350 |
|
#pragma pack(pop) |
1351 |
|
#endif /* _MSC_VER */ |
1352 |
|
|
1353 |
|
#endif /* RC_INVOKED */ |
1354 |
|
#endif /* _LIST_ */ |
1355 |
|
|
1356 |
|
/* |
1357 |
|
* This file is derived from software bearing the following |
1358 |
|
* restrictions: |
1359 |
|
* |
1360 |
|
* Copyright (c) 1994 |
1361 |
|
* Hewlett-Packard Company |
1362 |
|
* |
1363 |
|
* Permission to use, copy, modify, distribute and sell this |
1364 |
|
* software and its documentation for any purpose is hereby |
1365 |
|
* granted without fee, provided that the above copyright notice |
1366 |
|
* appear in all copies and that both that copyright notice and |
1367 |
|
* this permission notice appear in supporting documentation. |
1368 |
|
* Hewlett-Packard Company makes no representations about the |
1369 |
|
* suitability of this software for any purpose. It is provided |
1370 |
|
* "as is" without express or implied warranty. |
1371 |
|
*/ |
1372 |
|
|
1373 |
|
/* |
1374 |
|
* Copyright (c) 1992-2007 by P.J. Plauger. ALL RIGHTS RESERVED. |
1375 |
|
* Consult your license regarding permissions and restrictions. |
1376 |
|
V5.03:0009 */ |
1377 |
|
|
|
|
|