1		// xutility internal header
2		#pragma once
3		#ifndef _XUTILITY_
4		#define _XUTILITY_
5		#ifndef RC_INVOKED
6		#include <climits>
7		#include <utility>
8		#include <crtdbg.h>
9
10		#ifdef _MSC_VER
11		#pragma pack(push,_CRT_PACKING)
12		#pragma warning(push,3)
13		#endif  /* _MSC_VER */
14
15		_STD_BEGIN
16
17		// RANGE CHECKED ITERATOR TAGS
18		struct _Unchecked_iterator_tag
19		{
20		};
21		struct _Range_checked_iterator_tag
22		{
23		};
24
25		// CHECKED ITERATOR BASE TAGS
26		struct _Unchanged_checked_iterator_base_type_tag
27		{
28		};
29
30		struct _Different_checked_iterator_base_type_tag
31		{
32		};
33
34		// INNER TYPE TAG
35		struct _Undefined_inner_type_tag
36		{
37		};
38
39		// MOVE OPERATION TAG
40		struct _Undefined_move_tag
41		{
42		};
43
44		struct _Swap_move_tag
45		{
46		};
47
48
49		class _Iterator_base_universal
50		{    // base of all iterators
51		public:
52		typedef _Unchecked_iterator_tag _Checked_iterator_category;
53		typedef _Unchanged_checked_iterator_base_type_tag _Checked_iterator_base_type;
54		typedef _Undefined_inner_type_tag _Inner_type;
55		};
56
57
58		// Used to initialize _Mycont when _SECURE_SCL is off
59		#define _IGNORE_MYCONT ((const _Container_base_secure *)-4)
60
61		// Used to initialize _Myfirstiter and _Mynextiter when _HAS_ITERATOR_DEBUGGING is off
62		#define _IGNORE_MYITERLIST ((_Iterator_base *)-3)
63
64		#if _HAS_ITERATOR_DEBUGGING
65		/*
66		This internal implementation helper should not have been used externally, but is in our exports
67		and so cannot be removed right now. However, we deprecate it to avoid new uses
68		*/
69		__declspec(noreturn) __declspec(deprecated) _CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Debug_message(const char *, const char *);
70		/*
71		Use this one instead
72		*/
73
74		/* stl.net defined its own _Debug_message */
75		#if !defined(_CLI_MEMORY_)
76		_CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Debug_message(const wchar_t *, const wchar_t *, unsigned int line);
77		#else
78		void _Debug_message(const wchar_t *, const wchar_t *, unsigned int line);
79		#endif
80
81		// MACROS
82		#define _STRIZE(x)    _VAL(x)
83		#define _VAL(x)    #x
84		#define _DEBUG_ERROR(mesg)    _DEBUG_ERROR2(mesg, __FILEW__, __LINE__)
85		#ifndef _DEBUG_ERROR2
86		#define _DEBUG_ERROR2(mesg, filew, linew) _Debug_message(L ## mesg, filew, linew)
87		#endif /* _DEBUG_ERROR2 */
88
89		// CLASS _Container_base
90		class _Iterator_base;
91
92		class _CRTIMP2_PURE _Container_base_secure
93		{    // store head of iterator chain
94		public:
95		friend class _Iterator_base;
96
97		__CLR_OR_THIS_CALL _Container_base_secure()
98		: _Myfirstiter(0)
99		{    // construct childless container
100		}
101
102		__CLR_OR_THIS_CALL _Container_base_secure(const _Container_base_secure&)
103		: _Myfirstiter(0)
104		{    // copy a container
105		}
106
107		_Container_base_secure& __CLR_OR_THIS_CALL operator=(const _Container_base_secure&)
108		{    // assign a container
109		return (*this);
110		}
111
112		__CLR_OR_THIS_CALL ~_Container_base_secure()
113		{    // destroy the container
114		_Orphan_all();
115		}
116
117		void __CLR_OR_THIS_CALL _Orphan_all() const;    // orphan all iterators
118		void __CLR_OR_THIS_CALL _Swap_all(_Container_base_secure&) const;    // swaps all iterators
119
120		void __CLR_OR_THIS_CALL _Swap_aux(_Container_base_secure&)
121		{
122		// Do nothing: we don't have an aux object.
123		}
124
125		_Iterator_base *_Myfirstiter;
126		};
127
128		typedef _Container_base_secure _Container_base;
129
130		// CLASS _Iterator_base
131		class _Iterator_base : public _Iterator_base_universal
132		{    // store links to container, next iterator
133		public:
134		friend class _Container_base_secure;
135
136		__CLR_OR_THIS_CALL _Iterator_base()
137		: _Mycont(0), _Mynextiter(0)
138		{    // construct orphaned iterator
139		}
140
141		__CLR_OR_THIS_CALL _Iterator_base(const _Iterator_base& _Right)
142		: _Mycont(0), _Mynextiter(0)
143		{    // copy an iterator
144		*this = _Right;
145		}
146
147		_Iterator_base& __CLR_OR_THIS_CALL operator=(const _Iterator_base& _Right)
148		{    // assign an iterator
149		if (_Mycont != _Right._Mycont)
150		{    // change parentage
151		_Lockit _Lock(_LOCK_DEBUG);
152		_Orphan_me();
153		_Adopt(_Right._Mycont);
154		}
155		return (*this);
156		}
157
158		__CLR_OR_THIS_CALL ~_Iterator_base()
159		{    // destroy the iterator
160		_Lockit _Lock(_LOCK_DEBUG);
161		_Orphan_me();
162		}
163
164		void __CLR_OR_THIS_CALL _Adopt(const _Container_base_secure *_Parent)
165		{    // adopt this iterator by parent
166		if (_Mycont != _Parent)
167		{    // change parentage
168		_Lockit _Lock(_LOCK_DEBUG);
169		_Orphan_me();
170		if (_Parent != 0 && _Parent->_Myfirstiter != _IGNORE_MYITERLIST)
171		{    // switch to new parent
172		_Mynextiter = _Parent->_Myfirstiter;
173		((_Container_base_secure *)_Parent)->_Myfirstiter = this;
174		}
175		_Mycont = _Parent;
176		}
177		}
178
179		void __CLR_OR_THIS_CALL _Orphan_me()
180		{    // cut ties with parent
181		if (_Mycont != 0 && _Mycont->_Myfirstiter != _IGNORE_MYITERLIST)
182		{    // adopted, remove self from list
183		_Iterator_base **_Pnext =
184		(_Iterator_base **)&_Mycont->_Myfirstiter;
185		while (*_Pnext != 0 && *_Pnext != this)
186		_Pnext = &(*_Pnext)->_Mynextiter;
187
188		if (*_Pnext == 0)
189		_DEBUG_ERROR("ITERATOR LIST CORRUPTED!");
190		*_Pnext = _Mynextiter;
191		_Mycont = 0;
192		}
193		}
194
195		const _Container_base_secure * __CLR_OR_THIS_CALL _Getmycont() const
196		{    // This member function always exists when we can get a container pointer
197		return _Mycont;
198		}
199
200		bool __CLR_OR_THIS_CALL _Same_container(const _Iterator_base& _Other) const
201		{    // This member function always exists when we can get a container pointer
202		return _Mycont == _Other._Mycont;
203		}
204
205		bool __CLR_OR_THIS_CALL _Has_container() const
206		{    // This member function always exists when we can get a container pointer
207		return _Mycont != 0;
208		}
209
210		const _Container_base_secure *_Mycont;
211		_Iterator_base *_Mynextiter;
212		};
213
214		typedef _Iterator_base _Iterator_base_secure;
215
216		inline void __CLR_OR_THIS_CALL _Container_base_secure::_Orphan_all() const
217		{    // orphan all iterators
218		_Lockit _Lock(_LOCK_DEBUG);
219		if (_Myfirstiter != _IGNORE_MYITERLIST)
220		{
221		for (_Iterator_base **_Pnext = (_Iterator_base **)&_Myfirstiter;
222		*_Pnext != 0; *_Pnext = (*_Pnext)->_Mynextiter)
223		(*_Pnext)->_Mycont = 0;
224		*(_Iterator_base **)&_Myfirstiter = 0;
225		}
226		}
227
228		inline void __CLR_OR_THIS_CALL _Container_base_secure::_Swap_all(_Container_base_secure& _Right) const
229		{    // swap all iterators
230		_Lockit _Lock(_LOCK_DEBUG);
231		_Iterator_base *_Pnext;
232		_Iterator_base *_Temp = (_Iterator_base *)_Myfirstiter;
233		*(_Iterator_base **)&_Myfirstiter = (_Iterator_base *)_Right._Myfirstiter;
234		*(_Iterator_base **)&_Right._Myfirstiter = _Temp;
235
236		if (_Myfirstiter != _IGNORE_MYITERLIST)
237		{
238		for (_Pnext = (_Iterator_base *)_Myfirstiter;
239		_Pnext != 0; _Pnext = _Pnext->_Mynextiter)
240		_Pnext->_Mycont = this;
241		}
242		if (_Right._Myfirstiter != _IGNORE_MYITERLIST)
243		{
244		for (_Pnext = (_Iterator_base *)_Right._Myfirstiter;
245		_Pnext != 0; _Pnext = _Pnext->_Mynextiter)
246		_Pnext->_Mycont = &_Right;
247		}
248		}
249
250		// COMPARISON MACROS
251		#ifndef _DEBUG_LT_IMPL
252		#define _DEBUG_LT_IMPL    _Debug_lt
253		#endif /* _DEBUG_LT_IMPL */
254
255		#define _DEBUG_LT(x, y) _DEBUG_LT_IMPL(x, y, __FILEW__, __LINE__)
256
257		template<class _Ty1, class _Ty2> inline
258		bool __CLRCALL_OR_CDECL _Debug_lt(const _Ty1& _Left, const _Ty2& _Right,
259		const wchar_t *_Where, unsigned int _Line)
260		{    // test if _Left < _Right and operator< is strict weak ordering
261		if (!(_Left < _Right))
262		return (false);
263		else if (_Right < _Left)
264		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
265		return (true);
266		}
267
268		template<class _Ty1, class _Ty2> inline
269		bool __CLRCALL_OR_CDECL _Debug_lt(const _Ty1& _Left, _Ty2& _Right,
270		const wchar_t *_Where, unsigned int _Line)
271		{    // test if _Left < _Right and operator< is strict weak ordering
272		if (!(_Left < _Right))
273		return (false);
274		else if (_Right < _Left)
275		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
276		return (true);
277		}
278
279		template<class _Ty1, class _Ty2> inline
280		bool __CLRCALL_OR_CDECL _Debug_lt(_Ty1& _Left, const _Ty2& _Right,
281		const wchar_t *_Where, unsigned int _Line)
282		{    // test if _Left < _Right and operator< is strict weak ordering
283		if (!(_Left < _Right))
284		return (false);
285		else if (_Right < _Left)
286		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
287		return (true);
288		}
289
290		template<class _Ty1, class _Ty2> inline
291		bool __CLRCALL_OR_CDECL _Debug_lt(_Ty1& _Left, _Ty2& _Right,
292		const wchar_t *_Where, unsigned int _Line)
293		{    // test if _Left < _Right and operator< is strict weak ordering
294		if (!(_Left < _Right))
295		return (false);
296		else if (_Right < _Left)
297		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
298		return (true);
299		}
300
301
302		// COMPARISON MACRO WITH PRED
303		#ifndef _DEBUG_LT_PRED_IMPL
304		#define _DEBUG_LT_PRED_IMPL    _Debug_lt_pred
305		#endif /* _DEBUG_LT_PRED_IMPL */
306
307		#define _DEBUG_LT_PRED(pred, x, y)    _DEBUG_LT_PRED_IMPL(pred, x, y, __FILEW__, __LINE__)
308
309		template<class _Pr, class _Ty1, class _Ty2> inline
310		bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, const _Ty1& _Left, const _Ty2& _Right,
311		const wchar_t *_Where, unsigned int _Line)
312		{    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
313		if (!_Pred(_Left, _Right))
314		return (false);
315		else if (_Pred(_Right, _Left))
316		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
317		return (true);
318		}
319
320		template<class _Pr, class _Ty1, class _Ty2> inline
321		bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, const _Ty1& _Left, _Ty2& _Right,
322		const wchar_t *_Where, unsigned int _Line)
323		{    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
324		if (!_Pred(_Left, _Right))
325		return (false);
326		else if (_Pred(_Right, _Left))
327		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
328		return (true);
329		}
330
331		template<class _Pr, class _Ty1, class _Ty2> inline
332		bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, _Ty1& _Left, const _Ty2& _Right,
333		const wchar_t *_Where, unsigned int _Line)
334		{    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
335		if (!_Pred(_Left, _Right))
336		return (false);
337		else if (_Pred(_Right, _Left))
338		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
339		return (true);
340		}
341
342		template<class _Pr, class _Ty1, class _Ty2> inline
343		bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, _Ty1& _Left, _Ty2& _Right,
344		const wchar_t *_Where, unsigned int _Line)
345		{    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
346		if (!_Pred(_Left, _Right))
347		return (false);
348		else if (_Pred(_Right, _Left))
349		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
350		return (true);
351		}
352
353
354		#else /* _HAS_ITERATOR_DEBUGGING */
355
356		// SecureSCL needs to find the container that an iterator points into.
357		// The aux object allows container swapping to work when
358		// _HAS_ITERATOR_DEBUGGING is off and _SECURE_SCL is on.
359		class _Container_base_aux;
360
361		class _Aux_cont
362		{
363		public:
364		explicit _Aux_cont(const _Container_base_aux * const _Pcont)
365		: _Mycontainer(_Pcont) { }
366
367		const _Container_base_aux * _Getcont() const
368		{
369		return _Mycontainer;
370		}
371
372		private:
373		const _Container_base_aux * _Mycontainer;
374		};
375
376		class _Container_base_aux
377		{    // base of all containers
378		public:
379		_Container_base_aux()
380		{
381		// Do nothing: _Container_base_aux_alloc_real() will construct the aux object.
382		}
383
384		_Container_base_aux(const _Container_base_aux&)
385		{
386		// Do nothing: _Container_base_aux_alloc_real() will construct the aux object.
387		}
388
389		_Container_base_aux& operator=(const _Container_base_aux&)
390		{
391		// Do nothing: keep our aux object.
392		return *this;
393		}
394
395		void _Swap_aux(_Container_base_aux& _Right)
396		{
397		_STD swap(_Myownedaux, _Right._Myownedaux);
398		_STD swap(*_Myownedaux, *_Right._Myownedaux);
399		}
400
401		~_Container_base_aux()
402		{
403		// Do nothing: ~_Container_base_aux_alloc_real() previously destroyed the aux object.
404		}
405
406		protected:
407		friend class _Iterator_base_aux;
408
409		_Aux_cont * _Myownedaux;
410		};
411
412		template<class _Alloc>
413		class _Container_base_aux_alloc_real
414		: public _Container_base_aux
415		{ // base class for containers to hold allocator _Alaux
416		protected:
417		explicit _Container_base_aux_alloc_real(_Alloc _Al)
418		: _Alaux(_Al)
419		{
420		_Myownedaux = new (_Alaux.allocate(1)) _Aux_cont(this);
421		}
422
423		_Container_base_aux_alloc_real(const _Container_base_aux_alloc_real& _Right)
424		: _Alaux(_Right._Alaux)
425		{
426		_Myownedaux = new (_Alaux.allocate(1)) _Aux_cont(this);
427		}
428
429		_Container_base_aux_alloc_real& operator=(const _Container_base_aux_alloc_real&)
430		{
431		// Do nothing: keep our aux object.
432		return *this;
433		}
434
435		~_Container_base_aux_alloc_real()
436		{
437		_Myownedaux->~_Aux_cont();
438
439		_Alaux.deallocate(_Myownedaux, 1);
440		}
441
442		typename _Alloc::template rebind<_Aux_cont>::other _Alaux; // allocator object for aux objects
443		};
444
445		class _Iterator_base_aux : public _Iterator_base_universal
446		{    // base of all iterators
447		public:
448		_Iterator_base_aux()
449		: _Myaux(0) { }
450
451		void _Set_container(const _Container_base_aux * const _Pcont)
452		{
453		_Myaux = _Pcont->_Myownedaux;
454		}
455
456		const _Container_base_aux * _Getmycont() const
457		{    // Go through the aux object to get the container
458		return _Myaux ? _Myaux->_Getcont() : 0;
459		}
460
461		bool _Same_container(const _Iterator_base_aux& _Other) const
462		{    // Accelerate the comparison by not going through the aux object
463		return _Myaux == _Other._Myaux;
464		}
465
466		bool _Has_container() const
467		{    // Accelerate the comparison by not going through the aux object
468		return _Myaux != 0;
469		}
470
471		private:
472		const _Aux_cont * _Myaux;
473		};
474
475
476		// MACROS
477		#define _DEBUG_ERROR(mesg)
478		#define _DEBUG_LT(x, y)    ((x) < (y))
479		#define _DEBUG_LT_PRED(pred, x, y)    pred(x, y)
480
481		#ifdef _DEBUG
482		// Debug, _HAS_ITERATOR_DEBUGGING disabled.
483
484		typedef _Container_base_aux _Container_base;
485		typedef _Iterator_base_aux _Iterator_base;
486
487		class _Iterator_base_secure;
488		class _CRTIMP2_PURE _Container_base_secure
489		{    // base of all containers
490		public:
491		__CLR_OR_THIS_CALL _Container_base_secure()
492		: _Myfirstiter(0)
493		{    // construct childless container
494		}
495
496		__CLR_OR_THIS_CALL _Container_base_secure(const _Container_base_secure&)
497		: _Myfirstiter(0)
498		{    // copy a container
499		}
500
501		_Iterator_base *_Myfirstiter; // To match the type of _IGNORE_MYITERLIST
502		};
503
504		class _Iterator_base_secure : public _Iterator_base_universal
505		{    // base of all iterators
506		public:
507		__CLR_OR_THIS_CALL _Iterator_base_secure()
508		: _Mycont(0), _Mynextiter(0)
509		{    // construct orphaned iterator
510		}
511
512		__CLR_OR_THIS_CALL _Iterator_base_secure(const _Iterator_base_secure& _Right)
513		: _Mycont(0), _Mynextiter(0)
514		{    // copy an iterator
515		*this = _Right;
516		}
517
518		_Iterator_base_secure& __CLR_OR_THIS_CALL operator=(const _Iterator_base_secure& _Right)
519		{    // assign an iterator
520		this->_Mycont = _Right._Mycont;
521		this->_Mynextiter = _Right._Mynextiter;
522		return (*this);
523		}
524
525		const _Container_base_secure * __CLR_OR_THIS_CALL _Getmycont() const
526		{    // This member function always exists when we can get a container pointer
527		return _Mycont;
528		}
529
530		bool __CLR_OR_THIS_CALL _Same_container(const _Iterator_base_secure& _Other) const
531		{    // This member function always exists when we can get a container pointer
532		return _Mycont == _Other._Mycont;
533		}
534
535		bool __CLR_OR_THIS_CALL _Has_container() const
536		{    // This member function always exists when we can get a container pointer
537		return _Mycont != 0;
538		}
539
540		const _Container_base_secure *_Mycont;
541		_Iterator_base_secure *_Mynextiter;
542		};
543
544		#else
545		// Retail.
546
547		class _CRTIMP2_PURE _Container_base_secure
548		{    // base of all strings
549		};
550
551		// In retail, _Iterator_base_secure has always the same size
552		// regardless of the value of _SECURE_SCL.
553
554		// String iterators (see xstring) derives from _Iterator_base_secure
555		// to ensure that iterators instantiated from the msvcpXX.dll code
556		// are compatible with the one defined in the include files.
557
558		// When _SECURE_SCL is off, the _Mycont field of _Iterator_base_secure
559		// is always set to _IGNORE_MYCONT.
560
561		class _Iterator_base_secure : public _Iterator_base_universal
562		{    // base of all iterators
563		public:
564		// SecureSCL needs the base container
565		__CLR_OR_THIS_CALL _Iterator_base_secure()
566		: _Mycont(0)
567		{
568		}
569
570		const _Container_base_secure * __CLR_OR_THIS_CALL _Getmycont() const
571		{    // This member function always exists when we can get a container pointer
572		return _Mycont;
573		}
574
575		bool __CLR_OR_THIS_CALL _Same_container(const _Iterator_base_secure& _Other) const
576		{    // This member function always exists when we can get a container pointer
577		return _Mycont == _Other._Mycont;
578		}
579
580		bool __CLR_OR_THIS_CALL _Has_container() const
581		{    // This member function always exists when we can get a container pointer
582		return _Mycont != 0;
583		}
584
585		const _Container_base_secure *_Mycont;
586		};
587
588		#if _SECURE_SCL
589		// Retail, _SECURE_SCL enabled.
590
591		typedef _Container_base_aux _Container_base;
592		typedef _Iterator_base_aux _Iterator_base;
593
594		#else
595		// Retail, _SECURE_SCL disabled.
596
597		class _Container_base
598		{    // base of all containers
599		public:
600		void _Swap_aux(_Container_base&)
601		{
602		// Do nothing: we don't have an aux object.
603		}
604		};
605
606		typedef _Iterator_base_universal _Iterator_base;
607
608		#endif
609		#endif
610		#endif /* _HAS_ITERATOR_DEBUGGING */
611
612
613		template<class _Alloc>
614		class _Container_base_aux_alloc_empty
615		: public _Container_base
616		{ // base class for containers to avoid holding allocator _Alaux
617		protected:
618		explicit _Container_base_aux_alloc_empty(_Alloc) { }
619
620		_Container_base_aux_alloc_empty(const _Container_base_aux_alloc_empty&) { }
621
622		_Container_base_aux_alloc_empty& operator=(const _Container_base_aux_alloc_empty&)
623		{
624		return *this;
625		}
626
627		~_Container_base_aux_alloc_empty() { }
628		};
629
630		#if !_HAS_ITERATOR_DEBUGGING && (defined(_DEBUG) || _SECURE_SCL)
631		// We have an aux object.
632		#define _CONTAINER_BASE_AUX_ALLOC _Container_base_aux_alloc_real
633		#else
634		// We don't have an aux object.
635		#define _CONTAINER_BASE_AUX_ALLOC _Container_base_aux_alloc_empty
636		#endif
637
638
639		//    ITERATOR STUFF (from <iterator>)
640
641		// ITERATOR TAGS
642		struct input_iterator_tag
643		{    // identifying tag for input iterators
644		};
645
646		struct output_iterator_tag
647		{    // identifying tag for output iterators
648		};
649
650		struct forward_iterator_tag
651		: public input_iterator_tag
652		{    // identifying tag for forward iterators
653		};
654
655		struct bidirectional_iterator_tag
656		: public forward_iterator_tag
657		{    // identifying tag for bidirectional iterators
658		};
659
660		struct random_access_iterator_tag
661		: public bidirectional_iterator_tag
662		{    // identifying tag for random-access iterators
663		};
664
665		struct _Int_iterator_tag
666		{    // identifying tag for integer types, not an iterator
667		};
668
669		struct _Float_iterator_tag
670		{    // identifying tag for floating point types, not an iterator
671		};
672
673		// POINTER ITERATOR TAGS
674		struct _Nonscalar_ptr_iterator_tag
675		{    // pointer to unknown type
676		};
677		struct _Scalar_ptr_iterator_tag
678		{    // pointer to scalar type
679		};
680
681		// TEMPLATE CLASS iterator
682		template<class _Category,
683		class _Ty,
684		class _Diff = ptrdiff_t,
685		class _Pointer = _Ty *,
686		class _Reference = _Ty&>
687		struct iterator
688		: public _Iterator_base_universal
689
690		{    // base type for all iterator classes
691		typedef _Category iterator_category;
692		typedef _Ty value_type;
693		typedef _Diff difference_type;
694		typedef _Diff distance_type;    // retained
695		typedef _Pointer pointer;
696		typedef _Reference reference;
697		};
698
699		template<class _Category,
700		class _Ty,
701		class _Diff = ptrdiff_t,
702		class _Pointer = _Ty *,
703		class _Reference = _Ty&,
704		class _Base_class = _Iterator_base>
705		struct _Iterator_with_base
706		: public _Base_class
707
708		{    // base type for all iterator classes
709		typedef _Category iterator_category;
710		typedef _Ty value_type;
711		typedef _Diff difference_type;
712		typedef _Diff distance_type;    // retained
713		typedef _Pointer pointer;
714		typedef _Reference reference;
715		};
716
717		template<class _Ty,
718		class _Diff,
719		class _Pointer,
720		class _Reference>
721		struct _Bidit
722		: public _Iterator_with_base<bidirectional_iterator_tag,
723		_Ty, _Diff, _Pointer, _Reference>
724		{    // base type for container bidirectional iterator classes
725		};
726
727		template<class _Ty,
728		class _Diff,
729		class _Pointer,
730		class _Reference>
731		struct _Ranit
732		: public _Iterator_with_base<random_access_iterator_tag,
733		_Ty, _Diff, _Pointer, _Reference>
734		{    // base type for container random-access iterator classes
735		};
736
737		template<class _Ty,
738		class _Diff,
739		class _Pointer,
740		class _Reference,
741		class _Base_class>
742		struct _Ranit_base
743		: public _Base_class
744
745		{    // base type for container random-access iterator classes
746		typedef random_access_iterator_tag iterator_category;
747		typedef _Ty value_type;
748		typedef _Diff difference_type;
749		typedef _Diff distance_type;    // retained
750		typedef _Pointer pointer;
751		typedef _Reference reference;
752		};
753
754		struct _Outit
755		: public iterator<output_iterator_tag, void, void,
756		void, void>
757		{    // base for output iterators
758		};
759
760		// TEMPLATE CLASS iterator_traits
761		template<class _Iter>
762		struct iterator_traits
763		{    // get traits from iterator _Iter
764		typedef typename _Iter::iterator_category iterator_category;
765		typedef typename _Iter::value_type value_type;
766		typedef typename _Iter::difference_type difference_type;
767		typedef difference_type distance_type;    // retained
768		typedef typename _Iter::pointer pointer;
769		typedef typename _Iter::reference reference;
770		};
771
772		template<class _Ty>
773		struct iterator_traits<_Ty *>
774		{    // get traits from pointer
775		typedef random_access_iterator_tag iterator_category;
776		typedef _Ty value_type;
777		typedef ptrdiff_t difference_type;
778		typedef ptrdiff_t distance_type;    // retained
779		typedef _Ty *pointer;
780		typedef _Ty& reference;
781		};
782
783		template<class _Ty>
784		struct iterator_traits<const _Ty *>
785		{    // get traits from const pointer
786		typedef random_access_iterator_tag iterator_category;
787		typedef _Ty value_type;
788		typedef ptrdiff_t difference_type;
789		typedef ptrdiff_t distance_type;    // retained
790		typedef const _Ty *pointer;
791		typedef const _Ty& reference;
792		};
793
794		template<> struct iterator_traits<_Bool>
795		{    // get traits from integer type
796		typedef _Int_iterator_tag iterator_category;
797		typedef _Bool value_type;
798		typedef _Bool difference_type;
799		typedef _Bool distance_type;
800		typedef _Bool * pointer;
801		typedef _Bool& reference;
802		};
803
804		template<> struct iterator_traits<char>
805		{    // get traits from integer type
806		typedef _Int_iterator_tag iterator_category;
807		typedef char value_type;
808		typedef char difference_type;
809		typedef char distance_type;
810		typedef char * pointer;
811		typedef char& reference;
812		};
813
814		template<> struct iterator_traits<signed char>
815		{    // get traits from integer type
816		typedef _Int_iterator_tag iterator_category;
817		typedef signed char value_type;
818		typedef signed char difference_type;
819		typedef signed char distance_type;
820		typedef signed char * pointer;
821		typedef signed char& reference;
822		};
823
824		template<> struct iterator_traits<unsigned char>
825		{    // get traits from integer type
826		typedef _Int_iterator_tag iterator_category;
827		typedef unsigned char value_type;
828		typedef unsigned char difference_type;
829		typedef unsigned char distance_type;
830		typedef unsigned char * pointer;
831		typedef unsigned char& reference;
832		};
833
834		#ifdef _NATIVE_WCHAR_T_DEFINED
835		template<> struct iterator_traits<wchar_t>
836		{    // get traits from integer type
837		typedef _Int_iterator_tag iterator_category;
838		typedef wchar_t value_type;
839		typedef wchar_t difference_type;
840		typedef wchar_t distance_type;
841		typedef wchar_t * pointer;
842		typedef wchar_t& reference;
843		};
844		#endif /* _NATIVE_WCHAR_T_DEFINED */
845
846		template<> struct iterator_traits<short>
847		{    // get traits from integer type
848		typedef _Int_iterator_tag iterator_category;
849		typedef short value_type;
850		typedef short difference_type;
851		typedef short distance_type;
852		typedef short * pointer;
853		typedef short& reference;
854		};
855
856		template<> struct iterator_traits<unsigned short>
857		{    // get traits from integer type
858		typedef _Int_iterator_tag iterator_category;
859		typedef unsigned short value_type;
860		typedef unsigned short difference_type;
861		typedef unsigned short distance_type;
862		typedef unsigned short * pointer;
863		typedef unsigned short& reference;
864		};
865
866		template<> struct iterator_traits<int>
867		{    // get traits from integer type
868		typedef _Int_iterator_tag iterator_category;
869		typedef int value_type;
870		typedef int difference_type;
871		typedef int distance_type;
872		typedef int * pointer;
873		typedef int& reference;
874		};
875
876		template<> struct iterator_traits<unsigned int>
877		{    // get traits from integer type
878		typedef _Int_iterator_tag iterator_category;
879		typedef unsigned int value_type;
880		typedef unsigned int difference_type;
881		typedef unsigned int distance_type;
882		typedef unsigned int * pointer;
883		typedef unsigned int& reference;
884		};
885
886		template<> struct iterator_traits<long>
887		{    // get traits from integer type
888		typedef _Int_iterator_tag iterator_category;
889		typedef long value_type;
890		typedef long difference_type;
891		typedef long distance_type;
892		typedef long * pointer;
893		typedef long& reference;
894		};
895
896		template<> struct iterator_traits<unsigned long>
897		{    // get traits from integer type
898		typedef _Int_iterator_tag iterator_category;
899		typedef unsigned long value_type;
900		typedef unsigned long difference_type;
901		typedef unsigned long distance_type;
902		typedef unsigned long * pointer;
903		typedef unsigned long& reference;
904		};
905
906		template<> struct iterator_traits<double>
907		{
908		typedef _Float_iterator_tag iterator_category;
909		typedef double value_type;
910		typedef double difference_type;
911		typedef double distance_type;
912		typedef double * pointer;
913		typedef double& reference;
914		};
915
916		template<> struct iterator_traits<float>
917		{
918		typedef _Float_iterator_tag iterator_category;
919		typedef float value_type;
920		typedef float difference_type;
921		typedef float distance_type;
922		typedef float * pointer;
923		typedef float& reference;
924		};
925
926		#ifdef _LONGLONG
927		template<> struct iterator_traits<_LONGLONG>
928		{    // get traits from integer type
929		typedef _Int_iterator_tag iterator_category;
930		typedef _LONGLONG value_type;
931		typedef _LONGLONG difference_type;
932		typedef _LONGLONG distance_type;
933		typedef _LONGLONG * pointer;
934		typedef _LONGLONG& reference;
935		};
936
937		template<> struct iterator_traits<_ULONGLONG>
938		{    // get traits from integer type
939		typedef _Int_iterator_tag iterator_category;
940		typedef _ULONGLONG value_type;
941		typedef _ULONGLONG difference_type;
942		typedef _ULONGLONG distance_type;
943		typedef _ULONGLONG * pointer;
944		typedef _ULONGLONG& reference;
945		};
946		#endif /* _LONGLONG */
947
948		// TEMPLATE FUNCTION _Iter_cat
949		template<class _Iter> inline
950		typename iterator_traits<_Iter>::iterator_category
951		__CLRCALL_OR_CDECL _Iter_cat(const _Iter&)
952		{    // return category from iterator argument
953		typename iterator_traits<_Iter>::iterator_category _Cat;
954		return (_Cat);
955		}
956
957		// TEMPLATE FUNCTION _Iter_random
958		// Checks if both iterators belong to the random_access_iterator category;
959		// if not, then it returns the forward_iterator tag.
960		template<class _Cat1, class _Cat2>
961		class _Iter_random_helper
962		{
963		public:
964		typedef forward_iterator_tag _Iter_random_cat;
965		};
966
967		template<>
968		class _Iter_random_helper<random_access_iterator_tag, random_access_iterator_tag>
969		{
970		public:
971		typedef random_access_iterator_tag _Iter_random_cat;
972		};
973
974		template<class _Cat1, class _Cat2, class _Cat3>
975		class _Iter_random_helper3
976		{
977		public:
978		typedef forward_iterator_tag _Iter_random_cat;
979		};
980
981		template<>
982		class _Iter_random_helper3<random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag>
983		{
984		public:
985		typedef random_access_iterator_tag _Iter_random_cat;
986		};
987
988		template<class _Iter1, class _Iter2> inline
989		typename _Iter_random_helper<
990		typename iterator_traits<_Iter1>::iterator_category,
991		typename iterator_traits<_Iter2>::iterator_category>::_Iter_random_cat
992		__CLRCALL_OR_CDECL _Iter_random(const _Iter1&, const _Iter2&)
993		{    // return category from iterator argument
994		typename _Iter_random_helper<
995		iterator_traits<_Iter1>::iterator_category,
996		iterator_traits<_Iter2>::iterator_category>::_Iter_random_cat _Cat;
997		return (_Cat);
998		}
999
1000		template<class _Iter1, class _Iter2, class _Iter3> inline
1001		typename _Iter_random_helper3<
1002		typename iterator_traits<_Iter1>::iterator_category,
1003		typename iterator_traits<_Iter2>::iterator_category,
1004		typename iterator_traits<_Iter3>::iterator_category>::_Iter_random_cat
1005		__CLRCALL_OR_CDECL _Iter_random(const _Iter1&, const _Iter2&, const _Iter3&)
1006		{    // return category from iterator argument
1007		typename _Iter_random_helper3<
1008		iterator_traits<_Iter1>::iterator_category,
1009		iterator_traits<_Iter2>::iterator_category,
1010		iterator_traits<_Iter3>::iterator_category>::_Iter_random_cat _Cat;
1011		return (_Cat);
1012		}
1013
1014		// HELPER CLASS _If
1015		// Classic metaprogramming _If statement
1016		template <bool _Cond, class _Ty1, class _Ty2>
1017		class _If
1018		{
1019		public:
1020		typedef _Ty2 _Result;
1021		};
1022
1023		template <class _Ty1, class _Ty2>
1024		class _If<true, _Ty1, _Ty2>
1025		{
1026		public:
1027		typedef _Ty1 _Result;
1028		};
1029
1030		// HELPER CLASS _Secure_validation_helper
1031		template <bool _Secure_validation>
1032		class _Secure_validation_helper
1033		{
1034		public:
1035		typedef _Unchecked_iterator_tag _Checked_iterator_category;
1036		};
1037
1038		template <>
1039		class _Secure_validation_helper<true>
1040		{
1041		public:
1042		typedef _Range_checked_iterator_tag _Checked_iterator_category;
1043		};
1044
1045
1046		// TEMPLATE FUNCTION _Checked_cat
1047		template <class _Iter, bool _Inherits_from_iterator_base>
1048		class _Checked_iterator_category_helper
1049		{
1050		public:
1051		typedef _Unchecked_iterator_tag _Checked_cat;
1052		};
1053
1054		template <class _Iter>
1055		class _Checked_iterator_category_helper<_Iter, true>
1056		{
1057		public:
1058		typedef typename _Iter::_Checked_iterator_category _Checked_cat;
1059		};
1060
1061		template <class _Iter>
1062		class _Checked_iterator_category
1063		{
1064		public:
1065		typedef typename _Checked_iterator_category_helper<_Iter, __is_base_of(_Iterator_base_universal, _Iter)>::_Checked_cat _Checked_cat;
1066		};
1067
1068		template<class _Iter>
1069		inline
1070		typename _Checked_iterator_category<_Iter>::_Checked_cat _Checked_cat(const _Iter&)
1071		{
1072		typename _Checked_iterator_category<_Iter>::_Checked_cat _Cat;
1073		return (_Cat);
1074		}
1075
1076		// TEMPLATE FUNCTION _Checked_base
1077		template <class _Iter, bool _Inherits_from_iterator_base>
1078		class _Checked_iterator_base_helper2
1079		{
1080		public:
1081		typedef _Unchanged_checked_iterator_base_type_tag _Checked_iterator_base_type;
1082		};
1083
1084		template <class _Iter>
1085		class _Checked_iterator_base_helper2<_Iter, true>
1086		{
1087		public:
1088		typedef typename _Iter::_Checked_iterator_base_type _Checked_iterator_base_type;
1089		};
1090
1091		template <class _Iter, class _Base_type>
1092		class _Checked_iterator_base_helper1
1093		{
1094		public:
1095		typedef _Different_checked_iterator_base_type_tag _Base_type_tag;
1096		typedef _Base_type _Checked_iterator_base_type;
1097		};
1098
1099		template <class _Iter>
1100		class _Checked_iterator_base_helper1<_Iter, _Unchanged_checked_iterator_base_type_tag>
1101		{
1102		public:
1103		typedef _Unchanged_checked_iterator_base_type_tag _Base_type_tag;
1104		typedef _Iter _Checked_iterator_base_type;
1105		};
1106
1107		template <class _Iter>
1108		class _Checked_iterator_base_helper
1109		{
1110		public:
1111		typedef _Checked_iterator_base_helper2<_Iter, __is_base_of(_Iterator_base_universal, _Iter)> _Base_helper2;
1112		typedef _Checked_iterator_base_helper1<_Iter, typename  _Base_helper2::_Checked_iterator_base_type > _Base_helper1;
1113
1114		typedef typename _Base_helper1::_Base_type_tag _Checked_iterator_base_type_tag;
1115		typedef typename _Base_helper1::_Checked_iterator_base_type _Checked_iterator_base_type;
1116		};
1117
1118		template<class _Iter, class _Base_tag>
1119		inline
1120		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type
1121		__CLRCALL_OR_CDECL _Checked_base(const _Iter &_It, _Base_tag)
1122		{
1123		return _It._Checked_iterator_base();
1124		}
1125
1126		template<class _Iter>
1127		inline
1128		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type
1129		__CLRCALL_OR_CDECL _Checked_base(const _Iter &_It, _Unchanged_checked_iterator_base_type_tag)
1130		{
1131		return _It;
1132		}
1133
1134		template<class _Iter, class _Base_tag>
1135		inline
1136		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type
1137		__CLRCALL_OR_CDECL _Checked_base(_Iter &_It, _Base_tag)
1138		{
1139		return _It._Checked_iterator_base();
1140		}
1141
1142		template<class _Iter>
1143		inline
1144		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type
1145		__CLRCALL_OR_CDECL _Checked_base(_Iter &_It, _Unchanged_checked_iterator_base_type_tag)
1146		{
1147		return _It;
1148		}
1149
1150		template<class _Iter>
1151		inline
1152		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type
1153		__CLRCALL_OR_CDECL _Checked_base(const _Iter &_It)
1154		{
1155		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type_tag _Base_tag;
1156		return _Checked_base(_It, _Base_tag);
1157		}
1158
1159		template<class _Iter>
1160		inline
1161		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type
1162		__CLRCALL_OR_CDECL _Checked_base(_Iter &_It)
1163		{
1164		typename _Checked_iterator_base_helper<_Iter>::_Checked_iterator_base_type_tag _Base_tag;
1165		return _Checked_base(_It, _Base_tag);
1166		}
1167
1168		// TEMPLATE FUNCTION _Checked_assign_from_base
1169
1170		template<class _DstIter, class _BaseIter>
1171		inline
1172		void __CLRCALL_OR_CDECL _Checked_assign_from_base(_DstIter &_Dest, const _BaseIter &_Src)
1173		{
1174		_Dest._Checked_iterator_assign_from_base(_Src);
1175		}
1176
1177		template<class _Iter>
1178		inline
1179		void __CLRCALL_OR_CDECL _Checked_assign_from_base(_Iter &_Dest, const _Iter &_Src)
1180		{
1181		_Dest = _Src;
1182		}
1183
1184		// TEMPLATE FUNCTION _Move_cat
1185		#if !defined(_DEFAULT_MOVE_OPERATION_CATEGORY)
1186		#define _DEFAULT_MOVE_OPERATION_CATEGORY _Undefined_move_tag
1187		#endif
1188
1189		// default _Move_operation_category; std containers like vector, list overloads this trait class
1190		template <class _Value>
1191		class _Move_operation_category
1192		{
1193		public:
1194		typedef _DEFAULT_MOVE_OPERATION_CATEGORY _Move_cat;
1195		};
1196
1197		template<class _Iter>
1198		inline
1199		typename _Move_operation_category<typename iterator_traits<_Iter>::value_type>::_Move_cat _Move_cat(const _Iter&)
1200		{
1201		typename _Move_operation_category<typename iterator_traits<_Iter>::value_type>::_Move_cat _Cat;
1202		return (_Cat);
1203		}
1204
1205		template<class _Ty>
1206		struct _Is_swap_move
1207		{    // assumes _Ty is not _Swap_move_tag
1208		static const bool _Value = false;
1209		};
1210
1211		template<>
1212		struct _Is_swap_move<_Swap_move_tag>
1213		{    // reports true for _Swap_move_tag
1214		static const bool _Value = true;
1215		};
1216
1217		template<class _Ty1,
1218		class _Ty2>
1219		class _Move_operation_category<pair<_Ty1, _Ty2> >
1220		{    // pair implements a performant swap if both elements do
1221		public:
1222		typedef typename _If<
1223		_Is_swap_move<typename _Move_operation_category<
1224		_Ty1>::_Move_cat>::_Value &&
1225		_Is_swap_move<typename _Move_operation_category<
1226		_Ty2>::_Move_cat>::_Value,
1227		_Swap_move_tag,
1228		_Undefined_move_tag>::_Result _Move_cat;
1229		};
1230
1231		// TEMPLATE FUNCTION _Ptr_cat
1232		template<class _T1, class _T2, class _Checked_Cat1, class _Checked_Cat2>
1233		struct _Ptr_cat_with_checked_cat_helper
1234		{
1235		typedef _Nonscalar_ptr_iterator_tag _Ptr_cat;
1236		};
1237
1238		template<class _T1,    class _T2>
1239		struct _Ptr_cat_helper
1240		{
1241		typedef typename _Ptr_cat_with_checked_cat_helper<_T1, _T2,
1242		typename _Checked_iterator_category<_T1>::_Checked_cat,
1243		typename _Checked_iterator_category<_T2>::_Checked_cat>::_Ptr_cat _Ptr_cat;
1244		};
1245
1246		template<class _T1,    class _T2, class _Checked_Cat1>
1247		struct _Ptr_cat_with_checked_cat_helper<_T1, _T2, _Checked_Cat1, _Range_checked_iterator_tag>
1248		{
1249		typedef typename _Ptr_cat_helper<_T1, typename _T2::_Inner_type>::_Ptr_cat _Ptr_cat;
1250		};
1251
1252		template<class _T1,    class _T2, class _Checked_Cat2>
1253		struct _Ptr_cat_with_checked_cat_helper<_T1, _T2, _Range_checked_iterator_tag, _Checked_Cat2>
1254		{
1255		typedef typename _Ptr_cat_helper<typename _T1::_Inner_type, _T2>::_Ptr_cat _Ptr_cat;
1256		};
1257
1258		template<class _T1,    class _T2>
1259		struct _Ptr_cat_with_checked_cat_helper<_T1, _T2, _Range_checked_iterator_tag, _Range_checked_iterator_tag>
1260		{
1261		typedef typename _Ptr_cat_helper<typename _T1::_Inner_type, typename _T2::_Inner_type>::_Ptr_cat _Ptr_cat;
1262		};
1263
1264		template<class _T1>
1265		struct _Ptr_cat_helper<_T1, _Undefined_inner_type_tag>
1266		{
1267		typedef _Nonscalar_ptr_iterator_tag _Ptr_cat;
1268		};
1269
1270		template<class _T2>
1271		struct _Ptr_cat_helper<_Undefined_inner_type_tag, _T2>
1272		{
1273		typedef _Nonscalar_ptr_iterator_tag _Ptr_cat;
1274		};
1275
1276		template<>
1277		struct _Ptr_cat_helper<_Undefined_inner_type_tag, _Undefined_inner_type_tag>
1278		{
1279		typedef _Nonscalar_ptr_iterator_tag _Ptr_cat;
1280		};
1281
1282		// INTEGER FUNCTION _Ptr_cat
1283		template<>
1284		struct _Ptr_cat_helper<_Bool *, _Bool *>
1285		{    // return pointer category from pointer to pointer arguments
1286		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1287		};
1288
1289		template<>
1290		struct _Ptr_cat_helper<const _Bool *, _Bool *>
1291		{    // return pointer category from pointer to pointer arguments
1292		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1293		};
1294
1295		template<>
1296		struct _Ptr_cat_helper<char *, char *>
1297		{    // return pointer category from pointer to pointer arguments
1298		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1299		};
1300
1301		template<>
1302		struct _Ptr_cat_helper<const char *, char *>
1303		{    // return pointer category from pointer to pointer arguments
1304		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1305		};
1306
1307		template<>
1308		struct _Ptr_cat_helper<signed char *, signed char *>
1309		{    // return pointer category from pointer to pointer arguments
1310		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1311		};
1312
1313		template<>
1314		struct _Ptr_cat_helper<const signed char *, signed char *>
1315		{    // return pointer category from pointer to pointer arguments
1316		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1317		};
1318
1319		template<>
1320		struct _Ptr_cat_helper<unsigned char *, unsigned char *>
1321		{    // return pointer category from pointer to pointer arguments
1322		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1323		};
1324
1325		template<>
1326		struct _Ptr_cat_helper<const unsigned char *, unsigned char *>
1327		{    // return pointer category from pointer to pointer arguments
1328		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1329		};
1330
1331		#ifdef _NATIVE_WCHAR_T_DEFINED
1332
1333		template<>
1334		struct _Ptr_cat_helper<wchar_t *, wchar_t *>
1335		{    // return pointer category from pointer to pointer arguments
1336		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1337		};
1338
1339		template<>
1340		struct _Ptr_cat_helper<const wchar_t *, wchar_t *>
1341		{    // return pointer category from pointer to pointer arguments
1342		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1343		};
1344
1345		#endif /* _NATIVE_WCHAR_T_DEFINED */
1346		template<>
1347		struct _Ptr_cat_helper<short *, short *>
1348		{    // return pointer category from pointer to pointer arguments
1349		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1350		};
1351
1352		template<>
1353		struct _Ptr_cat_helper<const short *, short *>
1354		{    // return pointer category from pointer to pointer arguments
1355		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1356		};
1357
1358		template<>
1359		struct _Ptr_cat_helper<unsigned short *, unsigned short *>
1360		{    // return pointer category from pointer to pointer arguments
1361		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1362		};
1363
1364		template<>
1365		struct _Ptr_cat_helper<const unsigned short *, unsigned short *>
1366		{    // return pointer category from pointer to pointer arguments
1367		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1368		};
1369
1370		template<>
1371		struct _Ptr_cat_helper<int *, int *>
1372		{    // return pointer category from pointer to pointer arguments
1373		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1374		};
1375
1376		template<>
1377		struct _Ptr_cat_helper<const int *, int *>
1378		{    // return pointer category from pointer to pointer arguments
1379		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1380		};
1381
1382		template<>
1383		struct _Ptr_cat_helper<unsigned int *, unsigned int *>
1384		{    // return pointer category from pointer to pointer arguments
1385		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1386		};
1387
1388		template<>
1389		struct _Ptr_cat_helper<const unsigned int *, unsigned int *>
1390		{    // return pointer category from pointer to pointer arguments
1391		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1392		};
1393
1394		template<>
1395		struct _Ptr_cat_helper<long *, long *>
1396		{    // return pointer category from pointer to pointer arguments
1397		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1398		};
1399
1400		template<>
1401		struct _Ptr_cat_helper<const long *, long *>
1402		{    // return pointer category from pointer to pointer arguments
1403		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1404		};
1405
1406		template<>
1407		struct _Ptr_cat_helper<unsigned long *, unsigned long *>
1408		{    // return pointer category from pointer to pointer arguments
1409		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1410		};
1411
1412		template<>
1413		struct _Ptr_cat_helper<const unsigned long *, unsigned long *>
1414		{    // return pointer category from pointer to pointer arguments
1415		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1416		};
1417
1418		template<>
1419		struct _Ptr_cat_helper<float *, float *>
1420		{    // return pointer category from pointer to pointer arguments
1421		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1422		};
1423
1424		template<>
1425		struct _Ptr_cat_helper<const float *, float *>
1426		{    // return pointer category from pointer to pointer arguments
1427		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1428		};
1429
1430		template<>
1431		struct _Ptr_cat_helper<double *, double *>
1432		{    // return pointer category from pointer to pointer arguments
1433		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1434		};
1435
1436		template<>
1437		struct _Ptr_cat_helper<const double *, double *>
1438		{    // return pointer category from pointer to pointer arguments
1439		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1440		};
1441
1442		template<>
1443		struct _Ptr_cat_helper<long double *, long double *>
1444		{    // return pointer category from pointer to pointer arguments
1445		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1446		};
1447
1448		template<>
1449		struct _Ptr_cat_helper<const long double *, long double *>
1450		{    // return pointer category from pointer to pointer arguments
1451		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1452		};
1453
1454		#ifdef _LONGLONG
1455
1456		template<>
1457		struct _Ptr_cat_helper<_LONGLONG *, _LONGLONG *>
1458		{    // return pointer category from pointer to pointer arguments
1459		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1460		};
1461
1462		template<>
1463		struct _Ptr_cat_helper<const _LONGLONG *, _LONGLONG *>
1464		{    // return pointer category from pointer to pointer arguments
1465		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1466		};
1467
1468		template<>
1469		struct _Ptr_cat_helper<_ULONGLONG *, _ULONGLONG *>
1470		{    // return pointer category from pointer to pointer arguments
1471		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1472		};
1473
1474		template<>
1475		struct _Ptr_cat_helper<const _ULONGLONG *, _ULONGLONG *>
1476		{    // return pointer category from pointer to pointer arguments
1477		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1478		};
1479
1480		#endif /* _LONGLONG */
1481
1482		template<class _Ty>
1483		struct _Ptr_cat_helper<_Ty **, _Ty **>
1484		{    // return pointer category from pointer to pointer arguments
1485		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1486		};
1487
1488		template<class _Ty>
1489		struct _Ptr_cat_helper<_Ty **, const _Ty **>
1490		{    // return pointer category from pointer to pointer arguments
1491		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1492		};
1493
1494		template<class _Ty>
1495		struct _Ptr_cat_helper<_Ty *const *, _Ty **>
1496		{    // return pointer category from pointer to pointer arguments
1497		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1498		};
1499
1500		template<class _Ty>
1501		struct _Ptr_cat_helper<_Ty *const *, const _Ty **>
1502		{    // return pointer category from pointer to pointer arguments
1503		typedef _Scalar_ptr_iterator_tag _Ptr_cat;
1504		};
1505
1506		/* use _Ptr_cat_helper to determine the type of the pointer category */
1507		template<class _T1, class _T2> inline
1508		typename _Ptr_cat_helper<_T1, _T2>::_Ptr_cat __CLRCALL_OR_CDECL _Ptr_cat(_T1&, _T2&)
1509		{
1510		typename _Ptr_cat_helper<_T1, _T2>::_Ptr_cat _Cat;
1511		return (_Cat);
1512		}
1513
1514		#ifndef _DEBUG_ORDER_IMPL
1515		#define _DEBUG_ORDER_IMPL _Debug_order
1516		#endif
1517
1518		#ifndef _DEBUG_ORDER_SINGLE_IMPL
1519		#define _DEBUG_ORDER_SINGLE_IMPL _Debug_order_single
1520		#endif
1521
1522		#if _HAS_ITERATOR_DEBUGGING
1523		// ITERATOR DEBUGGING MACROS
1524		#ifndef _DEBUG_ORDER_IMPL
1525		#define _DEBUG_ORDER_IMPL    _Debug_order
1526		#endif /* _DEBUG_ORDER_IMPL */
1527
1528		#define _DEBUG_ORDER(first, last)    \
1529		_DEBUG_ORDER_IMPL(first, last, __FILEW__, __LINE__)
1530		#define _DEBUG_ORDER_PRED(first, last, pred)    \
1531		_DEBUG_ORDER_IMPL(first, last, pred, __FILEW__, __LINE__)
1532		#define _DEBUG_ORDER_SINGLE(first, last, is_first_iteration)    \
1533		_DEBUG_ORDER_SINGLE_IMPL(first, last, is_first_iteration, __FILEW__, __LINE__)
1534		#define _DEBUG_ORDER_SINGLE_PRED(first, last, pred, is_first_iteration)    \
1535		_DEBUG_ORDER_SINGLE_IMPL(first, last, pred, is_first_iteration, __FILEW__, __LINE__)
1536
1537		#ifndef _DEBUG_POINTER_IMPL
1538		#define _DEBUG_POINTER_IMPL    _Debug_pointer
1539		#endif /* _DEBUG_POINTER_IMPL */
1540
1541		#define _DEBUG_POINTER(first)    \
1542		_DEBUG_POINTER_IMPL(first, __FILEW__,__LINE__)
1543		#define _DEBUG_POINTER2(first, filew, line)    \
1544		_DEBUG_POINTER_IMPL(first, filew, line)
1545
1546		#ifndef _DEBUG_RANGE_IMPL
1547		#define _DEBUG_RANGE_IMPL    _Debug_range
1548		#endif /* _DEBUG_RANGE_IMPL */
1549
1550		#define _DEBUG_RANGE(first, last)    \
1551		_DEBUG_RANGE_IMPL(first, last, __FILEW__, __LINE__)
1552		#define _DEBUG_RANGE2(first, last, filew, line)    \
1553		_DEBUG_RANGE_IMPL(first, last, filew, line)
1554
1555		// TEMPLATE FUNCTION _Debug_pointer
1556		template<class _InIt> inline
1557		void __CLRCALL_OR_CDECL _Debug_pointer(_InIt&, const wchar_t *, unsigned int)
1558		{    // test pointer for non-singularity, arbitrary type
1559		}
1560
1561		template<class _Ty> inline
1562		void __CLRCALL_OR_CDECL _Debug_pointer(const _Ty *_First, const wchar_t *_File, unsigned int _Line)
1563		{    // test iterator for non-singularity, const pointers
1564		if (_First == 0)
1565		_DEBUG_ERROR2("invalid null pointer", _File, _Line);
1566		}
1567
1568		template<class _Ty> inline
1569		void __CLRCALL_OR_CDECL _Debug_pointer(_Ty *_First, const wchar_t *_File, unsigned int _Line)
1570		{    // test iterator for non-singularity, pointers
1571		if (_First == 0)
1572		_DEBUG_ERROR2("invalid null pointer", _File, _Line);
1573		}
1574
1575		// TEMPLATE FUNCTION _Debug_range
1576		template<class _InIt> inline
1577		void __CLRCALL_OR_CDECL _Debug_range2(_InIt, _InIt, const wchar_t *, unsigned int ,
1578		input_iterator_tag)
1579		{    // test iterator pair for valid range, arbitrary iterators
1580		}
1581
1582		template<class _RanIt> inline
1583		void __CLRCALL_OR_CDECL _Debug_range2(_RanIt _First, _RanIt _Last, const wchar_t *_File, unsigned int _Line,
1584		random_access_iterator_tag)
1585		{    // test iterator pair for valid range, random-access iterators
1586		if (_First != _Last)
1587		{    // check for non-null pointers, valid range
1588		_DEBUG_POINTER2(_First, _File, _Line);
1589		_DEBUG_POINTER2(_Last, _File, _Line);
1590		if (_Last < _First)
1591		_DEBUG_ERROR2("invalid iterator range", _File, _Line);
1592		}
1593		}
1594
1595		template<class _InIt> inline
1596		void __CLRCALL_OR_CDECL _Debug_range(_InIt _First, _InIt _Last, const wchar_t *_File, unsigned int _Line)
1597		{    // test iterator pair for valid range
1598		_Debug_range2(_First, _Last, _File, _Line, _Iter_cat(_First));
1599		}
1600
1601		// TEMPLATE FUNCTION _Debug_order
1602		template<class _InIt> inline
1603		void __CLRCALL_OR_CDECL _Debug_order2(_InIt _First, _InIt _Last,
1604		const wchar_t *_File, unsigned int _Line, input_iterator_tag)
1605		{    // test if range is ordered by operator<, input iterators
1606		}
1607
1608		template<class _FwdIt> inline
1609		void __CLRCALL_OR_CDECL _Debug_order2(_FwdIt _First, _FwdIt _Last,
1610		const wchar_t *_File, unsigned int _Line, forward_iterator_tag)
1611		{    // test if range is ordered by operator<, forward iterators
1612		if (_First != _Last)
1613		for (_FwdIt _Next = _First; ++_Next != _Last; ++_First)
1614		if (_DEBUG_LT(*_Next, *_First))
1615		_DEBUG_ERROR2("sequence not ordered", _File, _Line);
1616		}
1617
1618		template<class _InIt> inline
1619		void __CLRCALL_OR_CDECL _Debug_order(_InIt _First, _InIt _Last,
1620		const wchar_t *_File, unsigned int _Line)
1621		{    // test is range is ordered by operator<
1622		_DEBUG_RANGE2(_First, _Last, _File, _Line);
1623		_Debug_order2(_First, _Last, _File, _Line, _Iter_cat(_First));
1624		}
1625
1626		// TEMPLATE FUNCTION _Debug_order WITH PRED
1627		template<class _InIt,
1628		class _Pr> inline
1629		void __CLRCALL_OR_CDECL _Debug_order2(_InIt _First, _InIt _Last, _Pr _Pred,
1630		const wchar_t *_File, unsigned int _Line, input_iterator_tag)
1631		{    // test if range is ordered by predicate, input iterators
1632		}
1633
1634		template<class _FwdIt,
1635		class _Pr> inline
1636		void __CLRCALL_OR_CDECL _Debug_order2(_FwdIt _First, _FwdIt _Last, _Pr _Pred,
1637		const wchar_t *_File, unsigned int _Line, forward_iterator_tag)
1638		{    // test if range is ordered by predicate, forward iterators
1639		if (_First != _Last)
1640		for (_FwdIt _Next = _First; ++_Next != _Last; ++_First)
1641		if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
1642		_DEBUG_ERROR2("sequence not ordered", _File, _Line);
1643		}
1644
1645		template<class _InIt,
1646		class _Pr> inline
1647		void __CLRCALL_OR_CDECL _Debug_order(_InIt _First, _InIt _Last, _Pr _Pred,
1648		const wchar_t *_File, unsigned int _Line)
1649		{    // test if range is ordered by predicate
1650		_DEBUG_RANGE2(_First, _Last, _File, _Line);
1651		_DEBUG_POINTER2(_Pred, _File, _Line);
1652		_Debug_order2(_First, _Last, _Pred, _File, _Line, _Iter_cat(_First));
1653		}
1654
1655		// TEMPLATE FUNCTION _Debug_order_single
1656		template<class _InIt> inline
1657		void __CLRCALL_OR_CDECL _Debug_order_single2(_InIt _First, _InIt _Last, bool _IsFirstIteration,
1658		const wchar_t *_File, unsigned int _Line, input_iterator_tag)
1659		{    // test if _First and ++_First are ordered by operator<, input iterators
1660		}
1661
1662		template<class _FwdIt> inline
1663		void __CLRCALL_OR_CDECL _Debug_order_single2(_FwdIt _First, _FwdIt _Last, bool /* _IsFirstIteration */,
1664		const wchar_t *_File, unsigned int _Line, forward_iterator_tag)
1665		{    // test if _First and ++_First are ordered by operator<, forward iterators
1666		if (_First != _Last)
1667		{
1668		_FwdIt _Next = _First;
1669		if (++_Next != _Last)
1670		if (_DEBUG_LT(*_Next, *_First))
1671		_DEBUG_ERROR2("sequence not ordered", _File, _Line);
1672		}
1673		}
1674
1675		template<class _InIt> inline
1676		void __CLRCALL_OR_CDECL _Debug_order_single(_InIt _First, _InIt _Last, bool _IsFirstIteration,
1677		const wchar_t *_File, unsigned int _Line)
1678		{    // test if _First and ++_First are ordered by operator<
1679		_Debug_order_single2(_First, _Last, _IsFirstIteration, _File, _Line, _Iter_cat(_First));
1680		}
1681
1682		// TEMPLATE FUNCTION _Debug_order_single WITH PRED
1683		template<class _InIt,
1684		class _Pr> inline
1685		void __CLRCALL_OR_CDECL _Debug_order_single2(_InIt _First, _InIt _Last, _Pr _Pred, bool _IsFirstIteration,
1686		const wchar_t *_File, unsigned int _Line, input_iterator_tag)
1687		{    // test if _First and ++_First ordered by predicate, input iterators
1688		}
1689
1690		template<class _FwdIt,
1691		class _Pr> inline
1692		void __CLRCALL_OR_CDECL _Debug_order_single2(_FwdIt _First, _FwdIt _Last, _Pr _Pred, bool _IsFirstIteration,
1693		const wchar_t *_File, unsigned int _Line, forward_iterator_tag)
1694		{    // test if _First and ++_First ordered by predicate, forward iterators
1695		if (_First != _Last)
1696		{
1697		_FwdIt _Next = _First;
1698		if (++_Next != _Last)
1699		if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
1700		_DEBUG_ERROR2("sequence not ordered", _File, _Line);
1701		}
1702		}
1703
1704		template<class _InIt,
1705		class _Pr> inline
1706		void __CLRCALL_OR_CDECL _Debug_order_single(_InIt _First, _InIt _Last, _Pr _Pred, bool _IsFirstIteration,
1707		const wchar_t *_File, unsigned int _Line)
1708		{    // test if _First and ++_First is ordered by predicate
1709		_Debug_order_single2(_First, _Last, _Pred, _IsFirstIteration, _File, _Line, _Iter_cat(_First));
1710		}
1711
1712		#else /* _HAS_ITERATOR_DEBUGGING */
1713		#define _DEBUG_ORDER(first, last)
1714		#define _DEBUG_ORDER_PRED(first, last, pred)
1715		#define _DEBUG_ORDER_SINGLE(first, last, is_first_iteration)
1716		#define _DEBUG_ORDER_SINGLE_PRED(first, last, pred, is_first_iteration)
1717		#define _DEBUG_POINTER(first)
1718		#define _DEBUG_POINTER2(first, file, line)
1719		#define _DEBUG_RANGE(first, last)
1720		#define _DEBUG_RANGE2(first, last, file, line)
1721		#endif /* _HAS_ITERATOR_DEBUGGING */
1722
1723		#if _SECURE_SCL
1724
1725		// _CHECKED_CAT retrieves whether an iterator is checked.
1726		// It returns one of the range checked iterator tags:
1727		//      _Unchecked_iterator_tag: the iterator is unchecked;
1728		//      _Range_checked_iterator_tag: the iterator is checked.
1729		// To change the checked iterator category in your own iterators,
1730		// you will need to overload the _Checked_iterator_category typedef.
1731		#define _CHECKED_CAT(_Iter) _STD _Checked_cat(_Iter)
1732
1733		// _CHECKED_BASE retrieves the base of a checked iterator.
1734		// The base type of a checked iterator is supposed to be more
1735		// performant, but usually do not perform validation. See the standard
1736		// algorithm implementations for examples on how to use _CHECKED_BASE.
1737		// To change the checked iterator base type in your own iterators,
1738		// you will need to overload the _Checked_iterator_base_type typedef.
1739		#define _CHECKED_BASE(_Iter) _STD _Checked_base(_Iter)
1740		#define _CHECKED_BASE_TYPE(_Iter_type) \
1741		typename _STD _Checked_iterator_base_helper<_Iter_type>::_Checked_iterator_base_type
1742
1743		// _ASSIGN_FROM_BASE assign the value of _Src iterator to _Dest.
1744		// _Src is assumed to be the base of the checked iterator _Dest.
1745		// See the standard algorithm implementations for examples on how
1746		// to use _ASSIGN_FROM_BASE.
1747		// To change the checked iterator base type in your own iterators,
1748		// you will need to overload the _Checked_iterator_assign_from_base()
1749		// method.
1750		#define _ASSIGN_FROM_BASE(_Dest, _Src) _STD _Checked_assign_from_base(_Dest, _Src)
1751
1752		#else
1753
1754		#define _CHECKED_CAT(_Iter) _STD _Range_checked_iterator_tag()
1755		#define _CHECKED_BASE(_Iter) _Iter
1756		#define _CHECKED_BASE_TYPE(_Iter_type) _Iter_type
1757		#define _ASSIGN_FROM_BASE(_Dest, _Src) _Dest = (_Src)
1758
1759		#endif
1760
1761		// TEMPLATE FUNCTION _Val_type
1762
1763		template<class _Iter> inline
1764		typename iterator_traits<_Iter>::value_type *__CLRCALL_OR_CDECL _Val_type(_Iter)
1765		{    // return value type from arbitrary argument
1766		return (0);
1767		}
1768
1769		// TEMPLATE FUNCTION advance
1770		template<class _InIt,
1771		class _Diff> inline
1772		void __CLRCALL_OR_CDECL advance(_InIt& _Where, _Diff _Off)
1773		{    // increment iterator by offset, arbitrary iterators
1774		_Advance(_Where, _Off, _Iter_cat(_Where));
1775		}
1776
1777		template<class _InIt,
1778		class _Diff> inline
1779		void __CLRCALL_OR_CDECL _Advance(_InIt& _Where, _Diff _Off, input_iterator_tag)
1780		{    // increment iterator by offset, input iterators
1781
1782		#if _HAS_ITERATOR_DEBUGGING
1783		//    if (_Off < 0)
1784		//        _DEBUG_ERROR("negative offset in advance");
1785		#endif /* _HAS_ITERATOR_DEBUGGING */
1786
1787		for (; 0 < _Off; --_Off)
1788		++_Where;
1789		}
1790
1791		template<class _FI,
1792		class _Diff> inline
1793		void __CLRCALL_OR_CDECL _Advance(_FI& _Where, _Diff _Off, forward_iterator_tag)
1794		{    // increment iterator by offset, forward iterators
1795
1796		#if _HAS_ITERATOR_DEBUGGING
1797		//    if (_Off < 0)
1798		//        _DEBUG_ERROR("negative offset in advance");
1799		#endif /* _HAS_ITERATOR_DEBUGGING */
1800
1801		for (; 0 < _Off; --_Off)
1802		++_Where;
1803		}
1804
1805		#pragma warning(push)
1806		#pragma warning(disable: 6295)
1807		template<class _BI,
1808		class _Diff> inline
1809		void __CLRCALL_OR_CDECL _Advance(_BI& _Where, _Diff _Off, bidirectional_iterator_tag)
1810		{    // increment iterator by offset, bidirectional iterators
1811		for (; 0 < _Off; --_Off)
1812		++_Where;
1813		for (; _Off < 0; ++_Off)
1814		--_Where;
1815		}
1816		#pragma warning(pop)
1817
1818		template<class _RI,
1819		class _Diff> inline
1820		void __CLRCALL_OR_CDECL _Advance(_RI& _Where, _Diff _Off, random_access_iterator_tag)
1821		{    // increment iterator by offset, random-access iterators
1822		_Where += _Off;
1823		}
1824
1825		// TEMPLATE FUNCTION _Dist_type
1826
1827		template<class _Iter> inline
1828		typename iterator_traits<_Iter>::difference_type
1829		* __CLRCALL_OR_CDECL _Dist_type(_Iter)
1830		{    // return distance type from arbitrary argument
1831		return (0);
1832		}
1833
1834		// TEMPLATE FUNCTIONS distance and _Distance
1835		template<class _InIt,
1836		class _Diff> inline
1837		void __CLRCALL_OR_CDECL _Distance2(_InIt _First, _InIt _Last, _Diff& _Off,
1838		input_iterator_tag)
1839		{    // add to _Off distance between input iterators
1840		for (; _First != _Last; ++_First)
1841		++_Off;
1842		}
1843
1844		template<class _FwdIt,
1845		class _Diff> inline
1846		void __CLRCALL_OR_CDECL _Distance2(_FwdIt _First, _FwdIt _Last, _Diff& _Off,
1847		forward_iterator_tag)
1848		{    // add to _Off distance between forward iterators (redundant)
1849		for (; _First != _Last; ++_First)
1850		++_Off;
1851		}
1852
1853		template<class _BidIt,
1854		class _Diff> inline
1855		void __CLRCALL_OR_CDECL _Distance2(_BidIt _First, _BidIt _Last, _Diff& _Off,
1856		bidirectional_iterator_tag)
1857		{    // add to _Off distance between bidirectional iterators (redundant)
1858		for (; _First != _Last; ++_First)
1859		++_Off;
1860		}
1861
1862		template<class _RanIt,
1863		class _Diff> inline
1864		void __CLRCALL_OR_CDECL _Distance2(_RanIt _First, _RanIt _Last, _Diff& _Off,
1865		random_access_iterator_tag)
1866		{    // add to _Off distance between random-access iterators
1867
1868		#if _HAS_ITERATOR_DEBUGGING
1869		if (_First != _Last)
1870		{    // check for null pointers
1871		_DEBUG_POINTER(_First);
1872		_DEBUG_POINTER(_Last);
1873		}
1874		#endif /* _HAS_ITERATOR_DEBUGGING */
1875
1876		_Off += _Last - _First;
1877		}
1878
1879		template<class _InIt> inline
1880		typename iterator_traits<_InIt>::difference_type
1881		__CLRCALL_OR_CDECL distance(_InIt _First, _InIt _Last)
1882		{    // return distance between iterators
1883		typename iterator_traits<_InIt>::difference_type _Off = 0;
1884		_Distance2(_First, _Last, _Off, _Iter_cat(_First));
1885		return (_Off);
1886		}
1887
1888
1889		template<class _InIt,
1890		class _Diff> inline
1891		void __CLRCALL_OR_CDECL _Distance(_InIt _First, _InIt _Last, _Diff& _Off)
1892		{    // add to _Off distance between iterators
1893		_Distance2(_First, _Last, _Off, _Iter_cat(_First));
1894		}
1895
1896		// TEMPLATE CLASS _Revranit
1897		template<class _RanIt,
1898		class _Base>
1899		class _Revranit
1900		: public _Base
1901		{    // wrap iterator to run it backwards
1902		public:
1903		typedef _Revranit<_RanIt, _Base> _Myt;
1904		typedef typename iterator_traits<_RanIt>::iterator_category iterator_category;
1905		typedef typename iterator_traits<_RanIt>::value_type value_type;
1906		typedef typename iterator_traits<_RanIt>::difference_type difference_type;
1907		typedef typename iterator_traits<_RanIt>::difference_type distance_type;    // retained
1908		typedef typename iterator_traits<_RanIt>::pointer pointer;
1909		typedef typename iterator_traits<_RanIt>::reference reference;
1910		typedef _RanIt iterator_type;
1911
1912		__CLR_OR_THIS_CALL _Revranit()
1913		{    // construct with default wrapped iterator
1914		}
1915
1916		explicit __CLR_OR_THIS_CALL _Revranit(_RanIt _Right)
1917		: current(_Right)
1918		{    // construct wrapped iterator from _Right
1919		}
1920
1921		template<class _RanIt2,
1922		class _Base2>
1923		_Revranit(const _Revranit<_RanIt2, _Base2>& _Right)
1924		: current(_Right.base())
1925		{    // initialize with compatible base
1926		}
1927
1928		_RanIt __CLR_OR_THIS_CALL base() const
1929		{    // return wrapped iterator
1930		return (current);
1931		}
1932
1933		reference __CLR_OR_THIS_CALL operator*() const
1934		{    // return designated value
1935		_RanIt _Tmp = current;
1936		return (*--_Tmp);
1937		}
1938
1939		pointer __CLR_OR_THIS_CALL operator->() const
1940		{    // return pointer to class object
1941		return (&**this);
1942		}
1943
1944		_Myt& __CLR_OR_THIS_CALL operator++()
1945		{    // preincrement
1946		--current;
1947		return (*this);
1948		}
1949
1950		_Myt __CLR_OR_THIS_CALL operator++(int)
1951		{    // postincrement
1952		_Myt _Tmp = *this;
1953		--current;
1954		return (_Tmp);
1955		}
1956
1957		_Myt& __CLR_OR_THIS_CALL operator--()
1958		{    // predecrement
1959		++current;
1960		return (*this);
1961		}
1962
1963		_Myt __CLR_OR_THIS_CALL operator--(int)
1964		{    // postdecrement
1965		_Myt _Tmp = *this;
1966		++current;
1967		return (_Tmp);
1968		}
1969
1970		template<class _RanIt2,
1971		class _Base2>
1972		bool __CLR_OR_THIS_CALL _Equal(const _Revranit<_RanIt2, _Base2>& _Right) const
1973		{    // test for iterator equality
1974		return (current == _Right.base());
1975		}
1976
1977		// N.B. functions valid for random-access iterators only beyond this point
1978
1979		_Myt& __CLR_OR_THIS_CALL operator+=(difference_type _Off)
1980		{    // increment by integer
1981		current -= _Off;
1982		return (*this);
1983		}
1984
1985		_Myt __CLR_OR_THIS_CALL operator+(difference_type _Off) const
1986		{    // return this + integer
1987		return (_Myt(current - _Off));
1988		}
1989
1990		_Myt& __CLR_OR_THIS_CALL operator-=(difference_type _Off)
1991		{    // decrement by integer
1992		current += _Off;
1993		return (*this);
1994		}
1995
1996		_Myt __CLR_OR_THIS_CALL operator-(difference_type _Off) const
1997		{    // return this - integer
1998		return (_Myt(current + _Off));
1999		}
2000
2001		reference __CLR_OR_THIS_CALL operator[](difference_type _Off) const
2002		{    // subscript
2003		return (*(*this + _Off));
2004		}
2005
2006		template<class _RanIt2,
2007		class _Base2>
2008		bool __CLR_OR_THIS_CALL _Less(const _Revranit<_RanIt2, _Base2>& _Right) const
2009		{    // test if this < _Right
2010		return (_Right.base() < current);
2011		}
2012
2013		template<class _RanIt2,
2014		class _Base2>
2015		difference_type __CLR_OR_THIS_CALL _Minus(const _Revranit<_RanIt2, _Base2>& _Right) const
2016		{    // return difference of iterators
2017		return (_Right.base() - current);
2018		}
2019
2020		protected:
2021		_RanIt current;    // the wrapped iterator
2022		};
2023
2024		// _Revranit TEMPLATE OPERATORS
2025		template<class _RanIt,
2026		class _Base,
2027		class _Diff> inline
2028		_Revranit<_RanIt, _Base>
2029		operator+(_Diff _Off,
2030		const _Revranit<_RanIt, _Base>& _Right)
2031		{    // return reverse_iterator + integer
2032		return (_Right + _Off);
2033		}
2034
2035		template<class _RanIt1,
2036		class _Base1,
2037		class _RanIt2,
2038		class _Base2> inline
2039		typename _Base1::difference_type operator-(
2040		const _Revranit<_RanIt1, _Base1>& _Left,
2041		const _Revranit<_RanIt2, _Base2>& _Right)
2042		{    // return difference of reverse_iterators
2043		return (_Left._Minus(_Right));
2044		}
2045
2046		template<class _RanIt1,
2047		class _Base1,
2048		class _RanIt2,
2049		class _Base2> inline
2050		bool operator==(
2051		const _Revranit<_RanIt1, _Base1>& _Left,
2052		const _Revranit<_RanIt2, _Base2>& _Right)
2053		{    // test for reverse_iterator equality
2054		return (_Left._Equal(_Right));
2055		}
2056
2057		template<class _RanIt1,
2058		class _Base1,
2059		class _RanIt2,
2060		class _Base2> inline
2061		bool operator!=(
2062		const _Revranit<_RanIt1, _Base1>& _Left,
2063		const _Revranit<_RanIt2, _Base2>& _Right)
2064		{    // test for reverse_iterator inequality
2065		return (!(_Left == _Right));
2066		}
2067
2068		template<class _RanIt1,
2069		class _Base1,
2070		class _RanIt2,
2071		class _Base2> inline
2072		bool operator<(
2073		const _Revranit<_RanIt1, _Base1>& _Left,
2074		const _Revranit<_RanIt2, _Base2>& _Right)
2075		{    // test for reverse_iterator < reverse_iterator
2076		return (_Left._Less(_Right));
2077		}
2078
2079		template<class _RanIt1,
2080		class _Base1,
2081		class _RanIt2,
2082		class _Base2> inline
2083		bool operator>(
2084		const _Revranit<_RanIt1, _Base1>& _Left,
2085		const _Revranit<_RanIt2, _Base2>& _Right)
2086		{    // test for reverse_iterator > reverse_iterator
2087		return (_Right < _Left);
2088		}
2089
2090		template<class _RanIt1,
2091		class _Base1,
2092		class _RanIt2,
2093		class _Base2> inline
2094		bool operator<=(
2095		const _Revranit<_RanIt1, _Base1>& _Left,
2096		const _Revranit<_RanIt2, _Base2>& _Right)
2097		{    // test for reverse_iterator <= reverse_iterator
2098		return (!(_Right < _Left));
2099		}
2100
2101		template<class _RanIt1,
2102		class _Base1,
2103		class _RanIt2,
2104		class _Base2> inline
2105		bool operator>=(
2106		const _Revranit<_RanIt1, _Base1>& _Left,
2107		const _Revranit<_RanIt2, _Base2>& _Right)
2108		{    // test for reverse_iterator >= reverse_iterator
2109		return (!(_Left < _Right));
2110		}
2111
2112		// TEMPLATE CLASS reverse_iterator
2113		template<class _RanIt>
2114		class reverse_iterator
2115		: public _Revranit<_RanIt, iterator<
2116		typename iterator_traits<_RanIt>::iterator_category,
2117		typename iterator_traits<_RanIt>::value_type,
2118		typename iterator_traits<_RanIt>::difference_type,
2119		typename iterator_traits<_RanIt>::pointer,
2120		typename iterator_traits<_RanIt>::reference> >
2121		{    // wrap iterator to run it backwards
2122		typedef reverse_iterator<_RanIt> _Myt;
2123		typedef _Revranit<_RanIt, iterator<
2124		typename iterator_traits<_RanIt>::iterator_category,
2125		typename iterator_traits<_RanIt>::value_type,
2126		typename iterator_traits<_RanIt>::difference_type,
2127		typename iterator_traits<_RanIt>::pointer,
2128		typename iterator_traits<_RanIt>::reference> > _Mybase;
2129
2130		public:
2131		typedef typename iterator_traits<_RanIt>::iterator_category iterator_category;
2132		typedef typename iterator_traits<_RanIt>::value_type value_type;
2133		typedef typename iterator_traits<_RanIt>::difference_type difference_type;
2134		typedef typename iterator_traits<_RanIt>::difference_type distance_type;    // retained
2135		typedef typename iterator_traits<_RanIt>::pointer pointer;
2136		typedef typename iterator_traits<_RanIt>::reference reference;
2137		typedef _RanIt iterator_type;
2138
2139		__CLR_OR_THIS_CALL reverse_iterator()
2140		{    // construct with default wrapped iterator
2141		}
2142
2143		explicit __CLR_OR_THIS_CALL reverse_iterator(_RanIt _Right)
2144		: _Mybase(_Right)
2145		{    // construct wrapped iterator from _Right
2146		}
2147
2148		template<class _Other>
2149		__CLR_OR_THIS_CALL reverse_iterator(const reverse_iterator<_Other>& _Right)
2150		: _Mybase(_Right.base())
2151		{    // initialize with compatible base
2152		}
2153
2154		__CLR_OR_THIS_CALL reverse_iterator(_Mybase _Right)
2155		: _Mybase(_Right)
2156		{    // construct wrapped iterator from base object
2157		}
2158
2159		#if _SECURE_SCL
2160		typedef typename _STD _Checked_iterator_category<_RanIt>::_Checked_cat _Checked_iterator_category;
2161		typedef reverse_iterator<typename _Checked_iterator_base_helper<_RanIt>::_Checked_iterator_base_type> _Checked_iterator_base_type;
2162
2163		_Checked_iterator_base_type _Checked_iterator_base() const
2164		{
2165		typename _Checked_iterator_base_type _Base(_CHECKED_BASE(this->current));
2166		return _Base;
2167		}
2168
2169		void _Checked_iterator_assign_from_base(_Checked_iterator_base_type _Base)
2170		{
2171		_ASSIGN_FROM_BASE(this->current, _Base.base());
2172		}
2173		#endif
2174
2175		_Myt& operator++()
2176		{    // preincrement
2177		++*((_Mybase *)this);
2178		return (*this);
2179		}
2180
2181		_Myt operator++(int)
2182		{    // postincrement
2183		_Myt _Tmp = *this;
2184		++*this;
2185		return (_Tmp);
2186		}
2187
2188		_Myt& operator--()
2189		{    // predecrement
2190		--*((_Mybase *)this);
2191		return (*this);
2192		}
2193
2194		_Myt operator--(int)
2195		{    // postdecrement
2196		_Myt _Tmp = *this;
2197		--*this;
2198		return (_Tmp);
2199		}
2200
2201		_Myt& operator+=(difference_type _Off)
2202		{    // increment by integer
2203		*((_Mybase *)this) += _Off;
2204		return (*this);
2205		}
2206
2207		_Myt operator+(difference_type _Off) const
2208		{    // return this + integer
2209		_Myt _Tmp = *this;

Lines 2210 ... 2426 are skipped.

2427
2428		_Myt __CLR_OR_THIS_CALL operator++(int)
2429		{    // postincrement
2430		_Myt _Tmp = *this;
2431		--current;
2432		return (_Tmp);
2433		}
2434
2435		_Myt& __CLR_OR_THIS_CALL operator--()
2436		{    // predecrement
2437		++current;
2438		return (*this);
2439		}
2440
2441		_Myt __CLR_OR_THIS_CALL operator--(int)
2442		{    // postdecrement
2443		_Myt _Tmp = *this;
2444		++current;
2445		return (_Tmp);
2446		}
2447
2448		bool __CLR_OR_THIS_CALL operator==(const _Myt& _Right) const
2449		{    // test for iterator equality
2450		return (current == _Right.current);
2451		}
2452
2453		bool __CLR_OR_THIS_CALL operator!=(const _Myt& _Right) const
2454		{    // test for iterator inequality
2455		return (!(*this == _Right));
2456		}
2457
2458		protected:
2459		_BidIt current;
2460		};
2461
2462		//    ALGORITHM STUFF (from <algorithm>)
2463
2464		// TEMPLATE FUNCTION copy
2465		template<class _InIt, class _OutIt, class _InOutItCat>
2466		inline
2467		_OutIt __CLRCALL_OR_CDECL _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2468		_InOutItCat, _Nonscalar_ptr_iterator_tag, _Range_checked_iterator_tag)
2469		{    // copy [_First, _Last) to [_Dest, ...), arbitrary iterators
2470		_DEBUG_RANGE(_First, _Last);
2471		for (; _First != _Last; ++_Dest, ++_First)
2472		*_Dest = *_First;
2473		return (_Dest);
2474		}
2475
2476		#if _SECURE_SCL
2477		template<class _InIt, class _OutIt>
2478		inline
2479		_OutIt __CLRCALL_OR_CDECL _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2480		random_access_iterator_tag, _Nonscalar_ptr_iterator_tag, _Range_checked_iterator_tag)
2481		{    // copy [_First, _Last) to [_Dest, ...), random_access iterators
2482		// if _OutIt is range checked, this will make sure there is enough space for the copy
2483		_OutIt _Result = _Dest + (_Last - _First);
2484		_Copy_opt(_First, _Last, _CHECKED_BASE(_Dest),
2485		forward_iterator_tag(), _Nonscalar_ptr_iterator_tag(), _Range_checked_iterator_tag());
2486		return _Result;
2487		}
2488		#endif
2489
2490		template<class _InIt, class _OutIt, class _InOutItCat>
2491		inline
2492		_OutIt __CLRCALL_OR_CDECL _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2493		_InOutItCat, _Scalar_ptr_iterator_tag, _Range_checked_iterator_tag)
2494		{    // copy [_First, _Last) to [_Dest, ...), pointers to scalars
2495
2496		#if _HAS_ITERATOR_DEBUGGING
2497		_DEBUG_RANGE(_First, _Last);
2498		if (_First != _Last)
2499		_DEBUG_POINTER(_Dest);
2500		#endif /* _HAS_ITERATOR_DEBUGGING */
2501
2502		ptrdiff_t _Off = _Last - _First;    // NB: non-overlapping move
2503		// if _OutIt is range checked, this will make sure there is enough space for the memmove
2504		_OutIt _Result = _Dest + _Off;
2505		if (_Off > 0)
2506		_CRT_SECURE_MEMMOVE(&*_Dest, _Off * sizeof (*_First), &*_First, _Off * sizeof (*_First));
2507		return _Result;
2508		}
2509
2510		template <bool _Cond, class _Result_type>
2511		struct _Enable_if;
2512
2513		template <class _Result_type>
2514		struct _Enable_if<true, _Result_type>
2515		{
2516		typedef _Result_type _Result;
2517		};
2518
2519		template <class _Checked_iter_cat>
2520		struct _Is_checked_iterator_helper
2521		{
2522		enum { _Result = false };
2523		};
2524
2525		template <>
2526		struct _Is_checked_iterator_helper<_Range_checked_iterator_tag>
2527		{
2528		enum { _Result = true };
2529		};
2530
2531		template <class _Iter>
2532		struct _Is_checked_iterator
2533		{
2534		enum { _Result =
2535		_Is_checked_iterator_helper<typename _Checked_iterator_category<_Iter>::_Checked_cat>::_Result };
2536		};
2537
2538		#define _IF_CHK(_Iter_type) \
2539		typename _STD _Enable_if< _STD _Is_checked_iterator< _Iter_type >::_Result, _Iter_type >::_Result
2540		#define _IF_CHK_(_Iter_type, _Result_type) \
2541		typename _STD _Enable_if< _STD _Is_checked_iterator< _Iter_type >::_Result, _Result_type >::_Result
2542		#define _IF_CHK_RET_PAIR(_Iter_type, _Result_type1, _Result_type2) \
2543		typename _STD _Enable_if< _STD _Is_checked_iterator< _Iter_type >::_Result, _STD pair< _Result_type1, _Result_type2 > >::_Result
2544		#define _IF_CHK2_(_Iter1_type, _Iter2_type, _Result_type) \
2545		typename _STD _Enable_if< _STD _Is_checked_iterator< _Iter1_type >::_Result && _STD _Is_checked_iterator< _Iter2_type >::_Result, _Result_type >::_Result
2546
2547		#define _IF_NOT_CHK(_Iter_type) \
2548		typename _STD _Enable_if< ! _STD _Is_checked_iterator< _Iter_type >::_Result, _Iter_type >::_Result
2549		#define _IF_NOT_CHK_(_Iter_type, _Result_type) \
2550		typename _STD _Enable_if< ! _STD _Is_checked_iterator< _Iter_type >::_Result, _Result_type >::_Result
2551		#define _IF_NOT_CHK_RET_PAIR(_Iter_type, _Result_type1, _Result_type2) \
2552		typename _STD _Enable_if< ! _STD _Is_checked_iterator< _Iter_type >::_Result, _STD pair< _Result_type1, _Result_type2 > >::_Result
2553		#define _IF_NOT_CHK2_(_Iter1_type, _Iter2_type, _Result_type) \
2554		typename _STD _Enable_if< ! _STD _Is_checked_iterator< _Iter1_type >::_Result || !_STD _Is_checked_iterator< _Iter2_type >::_Result, _Result_type >::_Result
2555
2556		#if _SECURE_SCL
2557
2558		template<class _InIt, class _OutIt>
2559		inline
2560		_IF_CHK(_OutIt) __CLRCALL_OR_CDECL copy(_InIt _First, _InIt _Last, _OutIt _Dest)
2561		{    // copy [_First, _Last) to [_Dest, ...)
2562		return (_Copy_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2563		_Iter_random(_First, _Dest), _Ptr_cat(_First, _Dest), _Range_checked_iterator_tag()));
2564		}
2565
2566		template<class _InIt, class _OutElem, size_t _Size>
2567		inline
2568		_OutElem* __CLRCALL_OR_CDECL copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size])
2569		{    // copy [_First, _Last) to [_Dest, ...)
2570		return copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _STDEXT make_checked_array_iterator(_Dest, _Size)).base();
2571		}
2572
2573		template<class _InIt, class _OutIt>
2574		inline
2575		_SCL_INSECURE_DEPRECATE
2576		_IF_NOT_CHK(_OutIt) __CLRCALL_OR_CDECL copy(_InIt _First, _InIt _Last, _OutIt _Dest)
2577		{    // copy [_First, _Last) to [_Dest, ...)
2578		return (_Copy_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2579		_Iter_random(_First, _Dest), _Ptr_cat(_First, _Dest), _Range_checked_iterator_tag()));
2580		}
2581
2582		#else
2583
2584		template<class _InIt, class _OutIt>
2585		inline
2586		_OutIt __CLRCALL_OR_CDECL copy(_InIt _First, _InIt _Last, _OutIt _Dest)
2587		{    // copy [_First, _Last) to [_Dest, ...)
2588		return (_Copy_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2589		_Iter_random(_First, _Dest), _Ptr_cat(_First, _Dest), _Range_checked_iterator_tag()));
2590		}
2591
2592		#endif
2593
2594		// TEMPLATE FUNCTION _Move
2595		template<class _InIt, class _OutIt, class _InOutItCat, class _MoveCatTy>
2596		inline
2597		_OutIt __CLRCALL_OR_CDECL _Move_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2598		_InOutItCat _First_dest_cat, _MoveCatTy, _Range_checked_iterator_tag)
2599		{    // move defaults to copy if there is not a more effecient way
2600		return _Copy_opt(_First, _Last, _Dest,
2601		_First_dest_cat, _Ptr_cat(_First, _Dest), _Range_checked_iterator_tag());
2602		}
2603
2604		template<class _InIt, class _OutIt, class _InOutItCat>
2605		inline
2606		_OutIt __CLRCALL_OR_CDECL _Move_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2607		_InOutItCat, _Swap_move_tag, _Range_checked_iterator_tag)
2608		{    // use swap to instead of the copy constructor
2609		_DEBUG_RANGE(_First, _Last);
2610		for (; _First != _Last; ++_Dest, ++_First)
2611		_STD _Swap_adl(*_Dest, *_First);
2612		return (_Dest);
2613		}
2614
2615		#if _SECURE_SCL
2616		template<class _InIt, class _OutIt, class _InOutItCat>
2617		inline
2618		_OutIt __CLRCALL_OR_CDECL _Move_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2619		random_access_iterator_tag, _Swap_move_tag _Move_cat, _Range_checked_iterator_tag)
2620		{    // use swap to instead of the copy constructor
2621		// if _OutIt is range checked, this will make sure there is enough space for the copy
2622		_OutIt _Result = _Dest + (_Last - _First);
2623		_Move_opt(_First, _Last, _CHECKED_BASE(_Dest),
2624		forward_iterator_tag(), _Move_cat, _Range_checked_iterator_tag());
2625		return _Result;
2626		}
2627		#endif
2628
2629		#if _SECURE_SCL
2630
2631		template<class _InIt, class _OutIt>
2632		inline
2633		_IF_CHK(_OutIt) __CLRCALL_OR_CDECL _Move(_InIt _First, _InIt _Last, _OutIt _Dest)
2634		{    // move [_First, _Last) to [_Dest, ...)
2635		return _Move_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2636		_Iter_random(_First, _Dest), _Move_cat(_Dest), _STD _Range_checked_iterator_tag());
2637		}
2638
2639		template<class _InIt, class _OutElem, size_t _Size>
2640		inline
2641		_OutElem* __CLRCALL_OR_CDECL _Move(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size])
2642		{    // move [_First, _Last) to [_Dest, ...)
2643		return _Move(_CHECKED_BASE(_First), _CHECKED_BASE(_Last),
2644		_STDEXT make_checked_array_iterator(_Dest, _Size)).base();
2645		}
2646
2647		template<class _InIt, class _OutIt>
2648		inline
2649		_SCL_INSECURE_DEPRECATE
2650		_IF_NOT_CHK(_OutIt) __CLRCALL_OR_CDECL _Move(_InIt _First, _InIt _Last, _OutIt _Dest)
2651		{    // move [_First, _Last) to [_Dest, ...)
2652		return _Move_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2653		_Iter_random(_First, _Dest), _Move_cat(_Dest), _STD _Range_checked_iterator_tag());
2654		}
2655
2656		#else
2657
2658		template<class _InIt, class _OutIt>
2659		inline
2660		_OutIt __CLRCALL_OR_CDECL _Move(_InIt _First, _InIt _Last, _OutIt _Dest)
2661		{    // move [_First, _Last) to [_Dest, ...)
2662		return _Move_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2663		_Iter_random(_First, _Dest), _Move_cat(_Dest), _STD _Range_checked_iterator_tag());
2664		}
2665
2666		#endif
2667
2668		// TEMPLATE FUNCTION copy_backward
2669		template<class _BidIt1, class _BidIt2, class _InOutItCat>
2670		inline
2671		_BidIt2 __CLRCALL_OR_CDECL _Copy_backward_opt(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest,
2672		_InOutItCat, _Nonscalar_ptr_iterator_tag, _Range_checked_iterator_tag)
2673		{    // copy [_First, _Last) backwards to [..., _Dest), arbitrary iterators
2674		_DEBUG_RANGE(_First, _Last);
2675		while (_First != _Last)
2676		*--_Dest = *--_Last;
2677		return (_Dest);
2678		}
2679
2680		#if _SECURE_SCL
2681		template<class _InIt, class _OutIt>
2682		inline
2683		_OutIt __CLRCALL_OR_CDECL _Copy_backward_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2684		random_access_iterator_tag, _Nonscalar_ptr_iterator_tag, _Range_checked_iterator_tag)
2685		{    // copy [_First, _Last) backwards to [..., _Dest), arbitrary iterators
2686		// if _OutIt is range checked, this will make sure there is enough space for the copy
2687		_OutIt _Result = _Dest - (_Last - _First);
2688		_Copy_backward_opt(_First, _Last, _CHECKED_BASE(_Dest),
2689		forward_iterator_tag(), _Nonscalar_ptr_iterator_tag(), _Range_checked_iterator_tag());
2690		return _Result;
2691		}
2692		#endif
2693
2694		template<class _InIt, class _OutIt, class _InOutItCat>
2695		inline
2696		_OutIt __CLRCALL_OR_CDECL _Copy_backward_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
2697		_InOutItCat, _Scalar_ptr_iterator_tag, _Range_checked_iterator_tag)
2698		{    // copy [_First, _Last) backwards to [..., _Dest), pointers to scalars
2699
2700		#if _HAS_ITERATOR_DEBUGGING
2701		_DEBUG_RANGE(_First, _Last);
2702		if (_First != _Last)
2703		_DEBUG_POINTER(_Dest);
2704		#endif /* _HAS_ITERATOR_DEBUGGING */
2705
2706		ptrdiff_t _Off = _Last - _First;    // NB: non-overlapping move
2707		/* if _OutIt is range checked, this will make sure there is enough space for
2708		* the memmove
2709		*/
2710		_OutIt _Result = _Dest - _Off;
2711		if (_Off > 0)
2712		_CRT_SECURE_MEMMOVE(&*_Result, _Off * sizeof (*_First), &*_First, _Off * sizeof (*_First));
2713		return _Result;
2714		}
2715
2716		#if _SECURE_SCL
2717
2718		template<class _BidIt1,
2719		class _BidIt2> inline
2720		_IF_CHK(_BidIt2) __CLRCALL_OR_CDECL copy_backward(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
2721		{    // copy [_First, _Last) backwards to [..., _Dest)
2722		return _Copy_backward_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2723		_Iter_random(_First, _Dest), _Ptr_cat(_First, _Dest), _STD _Range_checked_iterator_tag());
2724		}
2725
2726		template<class _BidIt1,
2727		class _BidIt2> inline
2728		_SCL_INSECURE_DEPRECATE
2729		_IF_NOT_CHK(_BidIt2) __CLRCALL_OR_CDECL copy_backward(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
2730		{    // copy [_First, _Last) backwards to [..., _Dest)
2731		return _Copy_backward_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2732		_Iter_random(_First, _Dest), _Ptr_cat(_First, _Dest), _STD _Range_checked_iterator_tag());
2733		}
2734
2735		#else
2736
2737		template<class _BidIt1,
2738		class _BidIt2> inline
2739		_BidIt2 __CLRCALL_OR_CDECL copy_backward(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
2740		{    // copy [_First, _Last) backwards to [..., _Dest)
2741		return _Copy_backward_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2742		_Iter_random(_First, _Dest), _Ptr_cat(_First, _Dest), _STD _Range_checked_iterator_tag());
2743		}
2744
2745		#endif
2746
2747		// TEMPLATE FUNCTION _Move_backward
2748		template<class _BidIt1, class _BidIt2, class _InOutItCat, class _MoveCatTy>
2749		inline
2750		_BidIt2 __CLRCALL_OR_CDECL _Move_backward_opt(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest,
2751		_InOutItCat _First_dest_cat, _MoveCatTy, _Range_checked_iterator_tag)
2752		{    // move defaults to copy if there is not a more effecient way
2753		return _Copy_backward_opt(_First, _Last, _Dest,
2754		_First_dest_cat, _Ptr_cat(_First, _Dest), _Range_checked_iterator_tag());
2755		}
2756
2757		template<class _BidIt1, class _BidIt2, class _InOutItCat>
2758		inline
2759		_BidIt2 __CLRCALL_OR_CDECL _Move_backward_opt(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest,
2760		_InOutItCat, _Swap_move_tag, _Range_checked_iterator_tag)
2761		{    // use swap instead of the copy constructor
2762		_DEBUG_RANGE(_First, _Last);
2763		while (_First != _Last)
2764		_STD _Swap_adl(*--_Dest, *--_Last);
2765		return (_Dest);
2766		}
2767
2768		#if _SECURE_SCL
2769		template<class _BidIt1, class _BidIt2>
2770		inline
2771		_BidIt2 __CLRCALL_OR_CDECL _Move_backward_opt(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest,
2772		random_access_iterator_tag, _Swap_move_tag _Move_cat, _Range_checked_iterator_tag)
2773		{    // use swap to instead of the copy constructor
2774		// if _OutIt is range checked, this will make sure there is enough space for the copy
2775		_BidIt2 _Result = _Dest - (_Last - _First);
2776		_Move_backward_opt(_First, _Last, _CHECKED_BASE(_Dest),
2777		forward_iterator_tag(), _Move_cat, _Range_checked_iterator_tag());
2778		return _Result;
2779		}
2780		#endif
2781
2782		#if _SECURE_SCL
2783
2784		template<class _BidIt1, class _BidIt2>
2785		inline
2786		_IF_CHK(_BidIt2) __CLRCALL_OR_CDECL _Move_backward(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
2787		{    // move [_First, _Last) backwards to [..., _Dest)
2788		return _Move_backward_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2789		_Iter_random(_First, _Dest), _Move_cat(_Dest), _STD _Range_checked_iterator_tag());
2790		}
2791
2792		template<class _BidIt1, class _BidIt2>
2793		inline
2794		_SCL_INSECURE_DEPRECATE
2795		_IF_NOT_CHK(_BidIt2) __CLRCALL_OR_CDECL _Move_backward(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
2796		{    // move [_First, _Last) backwards to [..., _Dest)
2797		return _Move_backward_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2798		_Iter_random(_First, _Dest), _Move_cat(_Dest), _STD _Range_checked_iterator_tag());
2799		}
2800
2801		#else
2802
2803		template<class _BidIt1, class _BidIt2>
2804		inline
2805		_BidIt2 __CLRCALL_OR_CDECL _Move_backward(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
2806		{    // move [_First, _Last) backwards to [..., _Dest)
2807		return _Move_backward_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
2808		_Iter_random(_First, _Dest), _Move_cat(_Dest), _STD _Range_checked_iterator_tag());
2809		}
2810
2811		#endif
2812
2813		// TEMPLATE FUNCTION mismatch
2814		template<class _InIt1, class _InIt2, class _InItCats>
2815		inline
2816		pair<_InIt1, _InIt2>
2817		__CLRCALL_OR_CDECL _Mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
2818		_InItCats, _Range_checked_iterator_tag)
2819		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch
2820
2821		#if _HAS_ITERATOR_DEBUGGING
2822		_DEBUG_RANGE(_First1, _Last1);
2823		if (_First1 != _Last1)
2824		_DEBUG_POINTER(_First2);
2825		#endif /* _HAS_ITERATOR_DEBUGGING */
2826
2827		for (; _First1 != _Last1 && *_First1 == *_First2; )
2828		++_First1, ++_First2;
2829		return (pair<_InIt1, _InIt2>(_First1, _First2));
2830		}
2831
2832		#if _SECURE_SCL
2833		template<class _InIt1, class _InIt2>
2834		inline
2835		pair<_InIt1, _InIt2>
2836		__CLRCALL_OR_CDECL _Mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
2837		random_access_iterator_tag, _Range_checked_iterator_tag)
2838		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch
2839		// for range checked iterators, this will make sure there is enough space
2840		_InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
2841		pair<_InIt1, _CHECKED_BASE_TYPE(_InIt2)> _Result =
2842		_Mismatch(_First1, _Last1, _CHECKED_BASE(_First2),
2843		forward_iterator_tag(), _Range_checked_iterator_tag());
2844		_ASSIGN_FROM_BASE(_First2, _Result.second);
2845		return (pair<_InIt1, _InIt2>(_Result.first, _First2));
2846		}
2847		#endif
2848
2849		#if _SECURE_SCL
2850
2851		template<class _InIt1, class _InIt2>
2852		inline
2853		_IF_CHK_RET_PAIR(_InIt2, _InIt1, _InIt2)
2854		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
2855		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch
2856		pair<_CHECKED_BASE_TYPE(_InIt1), _InIt2> _Result =
2857		_Mismatch(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
2858		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
2859		_ASSIGN_FROM_BASE(_First1, _Result.first);
2860		return (pair<_InIt1, _InIt2>(_First1, _Result.second));
2861		}
2862
2863		template<class _InIt1, class _InElem2, size_t _Size>
2864		inline
2865		pair<_InIt1, _InElem2*>
2866		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_Size])
2867		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch
2868		pair<_InIt1, _STDEXT checked_array_iterator<_InElem2*> > _Result =
2869		mismatch(_First1, _Last1, _STDEXT make_checked_array_iterator(_First2, _Size));
2870		return (pair<_InIt1, _InElem2*>(_Result.first, _Result.second.base()));
2871		}
2872
2873		template<class _InIt1, class _InIt2>
2874		inline
2875		_SCL_INSECURE_DEPRECATE
2876		_IF_NOT_CHK_RET_PAIR(_InIt2, _InIt1, _InIt2)
2877		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
2878		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch
2879		pair<_CHECKED_BASE_TYPE(_InIt1), _InIt2> _Result =
2880		_Mismatch(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
2881		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
2882		_ASSIGN_FROM_BASE(_First1, _Result.first);
2883		return (pair<_InIt1, _InIt2>(_First1, _Result.second));
2884		}
2885
2886		#else
2887
2888		template<class _InIt1, class _InIt2>
2889		inline
2890		pair<_InIt1, _InIt2>
2891		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
2892		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch
2893		return _Mismatch(_First1, _Last1, _First2,
2894		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
2895		}
2896
2897		#endif
2898
2899		// TEMPLATE FUNCTION mismatch WITH PRED
2900		template<class _InIt1, class _InIt2, class _Pr, class _InItCats>
2901		inline
2902		pair<_InIt1, _InIt2>
2903		__CLRCALL_OR_CDECL _Mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred,
2904		_InItCats, _Range_checked_iterator_tag)
2905		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch using _Pred
2906
2907		#if _HAS_ITERATOR_DEBUGGING
2908		_DEBUG_RANGE(_First1, _Last1);
2909		if (_First1 != _Last1)
2910		_DEBUG_POINTER(_First2);
2911		_DEBUG_POINTER(_Pred);
2912		#endif /* _HAS_ITERATOR_DEBUGGING */
2913
2914		for (; _First1 != _Last1 && _Pred(*_First1, *_First2); )
2915		++_First1, ++_First2;
2916		return (pair<_InIt1, _InIt2>(_First1, _First2));
2917		}
2918
2919		#if _SECURE_SCL
2920		template<class _InIt1, class _InIt2, class _Pr>
2921		inline
2922		pair<_InIt1, _InIt2>
2923		__CLRCALL_OR_CDECL _Mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred,
2924		random_access_iterator_tag, _Range_checked_iterator_tag)
2925		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch using _Pred
2926		// for range checked iterators, this will make sure there is enough space
2927		_InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
2928		pair<_InIt1, _CHECKED_BASE_TYPE(_InIt2)> _Result =
2929		_Mismatch(_First1, _Last1, _CHECKED_BASE(_First2), _Pred,
2930		forward_iterator_tag(), _Range_checked_iterator_tag());
2931		_ASSIGN_FROM_BASE(_First2, _Result.second);
2932		return (pair<_InIt1, _InIt2>(_Result.first, _First2));
2933		}
2934		#endif
2935
2936		#if _SECURE_SCL
2937
2938		template<class _InIt1, class _InIt2, class _Pr>
2939		inline
2940		_IF_CHK_RET_PAIR(_InIt2, _InIt1, _InIt2)
2941		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
2942		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch using _Pred
2943		pair<_CHECKED_BASE_TYPE(_InIt1), _InIt2> _Result =
2944		_Mismatch(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Pred,
2945		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
2946		_ASSIGN_FROM_BASE(_First1, _Result.first);
2947		return (pair<_InIt1, _InIt2>(_First1, _Result.second));
2948		}
2949
2950		template<class _InIt1, class _InElem2, class _Pr, size_t _Size>
2951		inline
2952		pair<_InIt1, _InElem2*>
2953		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_Size], _Pr _Pred)
2954		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch using _Pred
2955		pair<_InIt1, _STDEXT checked_array_iterator<_InElem2*> > _Result =
2956		mismatch(_First1, _Last1, _STDEXT make_checked_array_iterator(_First2, _Size), _Pred);
2957		return (pair<_InIt1, _InElem2*>(_Result.first, _Result.second.base()));
2958		}
2959
2960		template<class _InIt1, class _InIt2, class _Pr>
2961		inline
2962		_SCL_INSECURE_DEPRECATE
2963		_IF_NOT_CHK_RET_PAIR(_InIt2, _InIt1, _InIt2)
2964		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
2965		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch using _Pred
2966		pair<_CHECKED_BASE_TYPE(_InIt1), _InIt2> _Result =
2967		_Mismatch(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Pred,
2968		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
2969		_ASSIGN_FROM_BASE(_First1, _Result.first);
2970		return (pair<_InIt1, _InIt2>(_First1, _Result.second));
2971		}
2972
2973		#else
2974
2975		template<class _InIt1, class _InIt2, class _Pr>
2976		inline
2977		pair<_InIt1, _InIt2>
2978		__CLRCALL_OR_CDECL mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
2979		{    // return [_First1, _Last1) and [_First2, _Last2) mismatch using _Pred
2980		return _Mismatch(_First1, _Last1, _First2, _Pred,
2981		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
2982		}
2983
2984		#endif
2985
2986		// TEMPLATE FUNCTION equal
2987		template<class _InIt1, class _InIt2, class _InItCats>
2988		inline
2989		bool __CLRCALL_OR_CDECL _Equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
2990		_InItCats, _Range_checked_iterator_tag)
2991		{    // compare [_First1, _Last1) to [First2, ...)
2992		for (; _First1 != _Last1; ++_First1, ++_First2)
2993		if (!(*_First1 == *_First2))
2994		return (false);
2995		return (true);
2996		}
2997
2998		inline bool __CLRCALL_OR_CDECL _Equal(const char *_First1,
2999		const char *_Last1, const char *_First2,
3000		random_access_iterator_tag, _Range_checked_iterator_tag)
3001		{    // compare [_First1, _Last1) to [First2, ...), for chars
3002		#if _HAS_ITERATOR_DEBUGGING
3003		_DEBUG_RANGE(_First1, _Last1);
3004		if (_First1 != _Last1)
3005		_DEBUG_POINTER(_First2);
3006		#endif /* _HAS_ITERATOR_DEBUGGING */
3007
3008		return (::memcmp(_First1, _First2, _Last1 - _First1) == 0);
3009		}
3010
3011		inline bool __CLRCALL_OR_CDECL _Equal(const signed char *_First1,
3012		const signed char *_Last1, const signed char *_First2,
3013		random_access_iterator_tag, _Range_checked_iterator_tag)
3014		{    // compare [_First1, _Last1) to [First2, ...), for signed chars
3015		#if _HAS_ITERATOR_DEBUGGING
3016		_DEBUG_RANGE(_First1, _Last1);
3017		if (_First1 != _Last1)
3018		_DEBUG_POINTER(_First2);
3019		#endif /* _HAS_ITERATOR_DEBUGGING */
3020
3021		return (::memcmp(_First1, _First2, _Last1 - _First1) == 0);
3022		}
3023
3024		inline bool __CLRCALL_OR_CDECL _Equal(const unsigned char *_First1,
3025		const unsigned char *_Last1, const unsigned char *_First2,
3026		random_access_iterator_tag, _Range_checked_iterator_tag)
3027		{    // compare [_First1, _Last1) to [First2, ...), for unsigned chars
3028		#if _HAS_ITERATOR_DEBUGGING
3029		_DEBUG_RANGE(_First1, _Last1);
3030		if (_First1 != _Last1)
3031		_DEBUG_POINTER(_First2);
3032		#endif /* _HAS_ITERATOR_DEBUGGING */
3033
3034		return (::memcmp(_First1, _First2, _Last1 - _First1) == 0);
3035		}
3036
3037		#if _SECURE_SCL
3038		template<class _InIt1, class _InIt2>
3039		inline
3040		bool __CLRCALL_OR_CDECL _Equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
3041		random_access_iterator_tag, _Range_checked_iterator_tag)
3042		{
3043		// for range checked iterators, this will make sure there is enough space
3044		_InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
3045		return _Equal(_First1, _Last1, _CHECKED_BASE(_First2),
3046		forward_iterator_tag(), _Range_checked_iterator_tag());
3047		}
3048		#endif
3049
3050		#if _SECURE_SCL
3051
3052		template<class _InIt1, class _InIt2>
3053		inline
3054		_IF_CHK_(_InIt2, bool) __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
3055		{    // compare [_First1, _Last1) to [First2, ...)
3056		return _Equal(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
3057		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
3058		}
3059
3060		template<class _InIt1, class _InElem2, size_t _Size>
3061		inline
3062		bool __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_Size])
3063		{    // compare [_First1, _Last1) to [First2, ...)
3064		return equal(_First1, _Last1,
3065		_STDEXT make_checked_array_iterator(_First2, _Size));
3066		}
3067
3068		template<class _InIt1, class _InIt2>
3069		inline
3070		_SCL_INSECURE_DEPRECATE
3071		_IF_NOT_CHK_(_InIt2, bool) __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
3072		{    // compare [_First1, _Last1) to [First2, ...)
3073		return _Equal(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
3074		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
3075		}
3076
3077		#else
3078
3079		template<class _InIt1, class _InIt2>
3080		inline
3081		bool __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
3082		{    // compare [_First1, _Last1) to [First2, ...)
3083		return _Equal(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
3084		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
3085		}
3086
3087		#endif
3088
3089		// TEMPLATE FUNCTION equal WITH PRED
3090		template<class _InIt1, class _InIt2, class _Pr, class _InItCats>
3091		inline
3092		bool __CLRCALL_OR_CDECL _Equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred,
3093		_InItCats, _Range_checked_iterator_tag)
3094		{    // compare [_First1, _Last1) to [First2, ...) using _Pred
3095		for (; _First1 != _Last1; ++_First1, ++_First2)
3096		if (!_Pred(*_First1, *_First2))
3097		return (false);
3098		return (true);
3099		}
3100
3101		#if _SECURE_SCL
3102		template<class _InIt1, class _InIt2, class _Pr>
3103		inline
3104		bool __CLRCALL_OR_CDECL _Equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred,
3105		random_access_iterator_tag, _Range_checked_iterator_tag)
3106		{
3107		// for range checked iterators, this will make sure there is enough space
3108		_InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
3109		return _Equal(_First1, _Last1, _CHECKED_BASE(_First2), _Pred,
3110		forward_iterator_tag(), _Range_checked_iterator_tag());
3111		}
3112		#endif
3113
3114		#if _SECURE_SCL
3115
3116		template<class _InIt1, class _InIt2, class _Pr>
3117		inline
3118		_IF_CHK_(_InIt2, bool) __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
3119		{    // compare [_First1, _Last1) to [First2, ...) using _Pred
3120		return _Equal(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Pred,
3121		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
3122		}
3123
3124		template<class _InIt1, class _InElem2, class _Pr, size_t _Size>
3125		inline
3126		bool __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_Size], _Pr _Pred)
3127		{    // compare [_First1, _Last1) to [First2, ...) using _Pred
3128		return equal(_First1, _Last1,
3129		_STDEXT make_checked_array_iterator(_First2, _Size), _Pred);
3130		}
3131
3132		template<class _InIt1, class _InIt2, class _Pr>
3133		inline
3134		_SCL_INSECURE_DEPRECATE
3135		_IF_NOT_CHK_(_InIt2, bool) __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
3136		{    // compare [_First1, _Last1) to [First2, ...) using _Pred
3137		return _Equal(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Pred,
3138		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
3139		}
3140
3141		#else
3142
3143		template<class _InIt1, class _InIt2, class _Pr>
3144		inline
3145		bool __CLRCALL_OR_CDECL equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
3146		{    // compare [_First1, _Last1) to [First2, ...) using _Pred
3147		return _Equal(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Pred,
3148		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
3149		}
3150
3151		#endif
3152
3153		// TEMPLATE FUNCTION fill
3154		template<class _FwdIt, class _Ty> inline
3155		void __CLRCALL_OR_CDECL _Fill(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
3156		{    // copy _Val through [_First, _Last)
3157		_DEBUG_RANGE(_First, _Last);
3158		for (; _First != _Last; ++_First)
3159		*_First = _Val;
3160		}
3161
3162		inline void __CLRCALL_OR_CDECL _Fill(_Out_capcount_x_(_Last-_First) char *_First,
3163