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;

Lines 1001 ... 1010 are skipped.

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