1		// algorithm standard header
2		#pragma once
3		#ifndef _ALGORITHM_
4		#define _ALGORITHM_
5		#ifndef RC_INVOKED
6		#include <memory>
7
8		#ifdef  _MSC_VER
9		#pragma pack(push,_CRT_PACKING)
10		#pragma warning(push,3)
11		#pragma warning(disable: 4244)
12		#endif  /* _MSC_VER */
13
14		_STD_BEGIN
15
16		// COMMON SORT PARAMETERS
17		const int _ISORT_MAX = 32;    // maximum size for insertion sort
18
19		// TEMPLATE FUNCTION for_each
20		template<class _InIt,
21		class _Fn1> inline
22		_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
23		{    // perform function for each element
24		_DEBUG_RANGE(_First, _Last);
25		_DEBUG_POINTER(_Func);
26		_CHECKED_BASE_TYPE(_InIt) _ChkFirst(_CHECKED_BASE(_First));
27		_CHECKED_BASE_TYPE(_InIt) _ChkLast(_CHECKED_BASE(_Last));
28		for (; _ChkFirst != _ChkLast; ++_ChkFirst)
29		_Func(*_ChkFirst);
30		return (_Func);
31		}
32
33		// TEMPLATE FUNCTION find
34		template<class _InIt, class _Ty>
35		inline
36		_InIt _Find(_InIt _First, _InIt _Last, const _Ty& _Val)
37		{    // find first matching _Val
38		_DEBUG_RANGE(_First, _Last);
39		for (; _First != _Last; ++_First)
40		if (*_First == _Val)
41		break;
42		return (_First);
43		}
44
45		inline const char *_Find(const char *_First, const char *_Last, int _Val)
46		{    // find first char that matches _Val
47		_DEBUG_RANGE(_First, _Last);
48		_First = (const char *)::memchr(_First, _Val, _Last - _First);
49		return (_First == 0 ? _Last : _First);
50		}
51
52		inline const signed char *_Find(const signed char *_First,
53		const signed char *_Last, int _Val)
54		{    // find first signed char that matches _Val
55		_DEBUG_RANGE(_First, _Last);
56		_First = (const signed char *)::memchr(_First, _Val,
57		_Last - _First);
58		return (_First == 0 ? _Last : _First);

Lines 59 ... 559 are skipped.

560		}
561
562		// TEMPLATE FUNCTION find_first_of WITH PRED
563		template<class _FwdIt1,
564		class _FwdIt2,
565		class _Pr> inline
566		_FwdIt1 _Find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
567		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
568		{    // look for one of [_First2, _Last2) satisfying _Pred with element
569		_DEBUG_POINTER(_Pred);
570		for (; _First1 != _Last1; ++_First1)
571		for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
572		if (_Pred(*_First1, *_Mid2))
573		return (_First1);
574		return (_First1);
575		}
576
577		template<class _FwdIt1,
578		class _FwdIt2,
579		class _Pr> inline
580		_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
581		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
582		{    // look for one of [_First2, _Last2) satisfying _Pred with element
583		_ASSIGN_FROM_BASE(_First1,
584		_Find_first_of(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
585		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred));
586		return (_First1);
587		}
588
589		// TEMPLATE FUNCTION iter_swap
590		template<class _FwdIt1,
591		class _FwdIt2> inline
592		void iter_swap(_FwdIt1 _Left, _FwdIt2 _Right)
593		{    // swap *_Left and *_Right
594		swap(*_Left, *_Right);
595		}
596
597		// TEMPLATE FUNCTION swap_ranges
598		template<class _FwdIt1, class _FwdIt2, class _FwdItCats>
599		inline
600		_FwdIt2 _Swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2,
601		_FwdItCats, _Range_checked_iterator_tag)
602		{    // swap [_First1, _Last1) with [_First2, ...)
603		_DEBUG_RANGE(_First1, _Last1);
604		for (; _First1 != _Last1; ++_First1, ++_First2)
605		std::iter_swap(_First1, _First2);
606		return (_First2);
607		}
608
609		#if _SECURE_SCL
610		template<class _FwdIt1, class _FwdIt2>
611		inline
612		_FwdIt2 _Swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2,
613		random_access_iterator_tag, _Range_checked_iterator_tag)
614		{    // swap [_First1, _Last1) with [_First2, ...)
615		// if _FwdIt2 is range checked, this will make sure there is enough space
616		_FwdIt2 _Result = _First2 + (_Last1 - _First1);
617		_Swap_ranges(_First1, _Last1, _CHECKED_BASE(_First2),
618		forward_iterator_tag(), _Range_checked_iterator_tag());
619		return (_Result);
620		}
621		#endif
622
623		#if _SECURE_SCL
624
625		template<class _FwdIt1, class _FwdIt2>
626		inline
627		_IF_CHK(_FwdIt2) swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
628		{
629		return _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
630		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
631		}
632
633		template<class _FwdIt1, class _FwdElem2, size_t _Size>
634		inline
635		_FwdElem2* swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdElem2 (&_First2)[_Size])
636		{
637		return (swap_ranges(_First1, _Last1, _STDEXT make_checked_array_iterator(_First2, _Size)).base());
638		}
639
640		template<class _FwdIt1, class _FwdIt2>
641		inline
642		_SCL_INSECURE_DEPRECATE
643		_IF_NOT_CHK(_FwdIt2) swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
644		{
645		return _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
646		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
647		}
648
649		#else
650
651		template<class _FwdIt1, class _FwdIt2>
652		inline
653		_FwdIt2 swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
654		{
655		return _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
656		_Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
657		}
658
659		#endif
660
661		// TEMPLATE FUNCTION transform WITH UNARY OP
662		template<class _InIt, class _OutIt, class _Fn1, class _InOutItCat>
663		inline
664		_OutIt _Transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func,
665		_InOutItCat, _Range_checked_iterator_tag)
666		{    // transform [_First, _Last) with _Func
667		_DEBUG_RANGE(_First, _Last);
668		_DEBUG_POINTER(_Dest);
669		_DEBUG_POINTER(_Func);
670		for (; _First != _Last; ++_First, ++_Dest)
671		*_Dest = _Func(*_First);
672		return (_Dest);
673		}
674
675		#if _SECURE_SCL
676		template<class _InIt, class _OutIt, class _Fn1>
677		inline
678		_OutIt _Transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func,
679		random_access_iterator_tag, _Range_checked_iterator_tag)
680		{    // transform [_First, _Last) with _Func
681		// for range checked iterators, this will make sure there is enough space
682		_OutIt _Result = _Dest + (_Last - _First);
683		_Transform(_First, _Last, _CHECKED_BASE(_Dest), _Func,
684		forward_iterator_tag(), _Range_checked_iterator_tag());
685		return (_Result);
686		}
687		#endif
688
689		#if _SECURE_SCL
690
691		template<class _InIt, class _OutIt, class _Fn1>
692		inline
693		_IF_CHK(_OutIt) transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
694		{
695		return _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
696		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
697		}
698
699		template<class _InIt, class _OutElem, class _Fn1, size_t _Size>
700		inline
701		_OutElem* transform(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Fn1 _Func)
702		{
703		return (transform(_First, _Last,
704		_STDEXT make_checked_array_iterator(_Dest, _Size), _Func).base());
705		}
706
707		template<class _InIt, class _OutIt, class _Fn1>
708		inline
709		_SCL_INSECURE_DEPRECATE
710		_IF_NOT_CHK(_OutIt) transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
711		{
712		return _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
713		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
714		}
715
716		#else
717
718		template<class _InIt, class _OutIt, class _Fn1>
719		inline
720		_OutIt transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
721		{
722		return _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
723		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
724		}
725
726		#endif
727
728		// TEMPLATE FUNCTION transform WITH BINARY OP
729		template<class _InIt1, class _InIt2, class _OutIt, class _Fn2, class _InItCats, class _InOutItCat>
730		inline
731		_OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
732		_OutIt _Dest, _Fn2 _Func,
733		_InItCats, _InOutItCat,
734		_Range_checked_iterator_tag, _Range_checked_iterator_tag)
735		{    // transform [_First1, _Last1) and [_First2, _Last2) with _Func
736		_DEBUG_RANGE(_First1, _Last1);
737		_DEBUG_POINTER(_Dest);
738		_DEBUG_POINTER(_Func);
739		for (; _First1 != _Last1; ++_First1, ++_First2, ++_Dest)
740		*_Dest = _Func(*_First1, *_First2);
741		return (_Dest);
742		}
743
744		#if _SECURE_SCL
745		template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
746		inline
747		_OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
748		_OutIt _Dest, _Fn2 _Func,
749		random_access_iterator_tag, random_access_iterator_tag,
750		_Range_checked_iterator_tag, _Range_checked_iterator_tag)
751		{    // transform [_First1, _Last1) and [_First2, _Last2) with _Func
752		// for range checked iterators, this will make sure there is enough space
753		_InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
754		_OutIt _Result = _Dest + (_Last1 - _First1);
755		_Transform(_First1, _Last1, _CHECKED_BASE(_First2),
756		_CHECKED_BASE(_Dest), _Func,
757		forward_iterator_tag(), forward_iterator_tag(),
758		_Range_checked_iterator_tag(), _Range_checked_iterator_tag());
759		return _Result;
760		}
761
762		template<class _InIt1, class _InIt2, class _OutIt, class _Fn2, class _InOutItCat>
763		inline
764		_OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
765		_OutIt _Dest, _Fn2 _Func,
766		random_access_iterator_tag, _InOutItCat,
767		_Range_checked_iterator_tag, _Range_checked_iterator_tag)
768		{    // transform [_First1, _Last1) and [_First2, _Last2) with _Func
769		// for range checked iterators, this will make sure there is enough space
770		_InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
771		return _Transform(_First1, _Last1, _CHECKED_BASE(_First2),
772		_Dest, _Func,
773		forward_iterator_tag(), forward_iterator_tag(),
774		_Range_checked_iterator_tag(), _Range_checked_iterator_tag());
775		}
776
777		template<class _InIt1, class _InIt2, class _OutIt, class _Fn2, class _InItCats>
778		inline
779		_OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
780		_OutIt _Dest, _Fn2 _Func,
781		_InItCats, random_access_iterator_tag,
782		_Range_checked_iterator_tag, _Range_checked_iterator_tag)
783		{    // transform [_First1, _Last1) and [_First2, _Last2) with _Func
784		// for range checked iterators, this will make sure there is enough space
785		_OutIt _Result = _Dest + (_Last1 - _First1);
786		_Transform(_First1, _Last1, _First2,
787		_CHECKED_BASE(_Dest), _Func,
788		forward_iterator_tag(), forward_iterator_tag(),
789		_Range_checked_iterator_tag(), _Range_checked_iterator_tag());
790		return _Result;
791		}
792		#endif
793
794		#if _SECURE_SCL
795
796		template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
797		inline
798		_IF_CHK2_(_InIt2, _OutIt, _OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
799		_OutIt _Dest, _Fn2 _Func)
800		{
801		return _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
802		_Iter_random(_First1, _First2), _Iter_random(_First1, _Dest),
803		_STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
804		}
805
806		template<class _InIt1, class _InElem2, class _OutElem, class _Fn2, size_t _SizeFirst2, size_t _SizeDest>
807		inline
808		_OutElem* transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
809		_OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
810		{
811		return (transform(_First1, _Last1,
812		_STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
813		_STDEXT make_checked_array_iterator(_Dest, _SizeDest),
814		_Func).base());
815		}
816
817		template<class _InIt1, class _InIt2, class _OutElem, class _Fn2, size_t _SizeDest>
818		inline
819		_IF_CHK_(_InIt2, _OutElem*) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
820		_OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
821		{
822		return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
823		_STDEXT make_checked_array_iterator(_Dest, _SizeDest), _Func,
824		_Iter_random(_First1, _First2), _Iter_cat(_First1),
825		_STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()).base());
826		}
827
828		template<class _InIt1, class _InIt2, class _OutElem, class _Fn2, size_t _SizeDest>
829		inline
830		_SCL_INSECURE_DEPRECATE
831		_IF_NOT_CHK_(_InIt2, _OutElem*) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
832		_OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
833		{
834		return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
835		_STDEXT make_checked_array_iterator(_Dest, _SizeDest), _Func,
836		_Iter_random(_First1, _First2), _Iter_cat(_First1),
837		_STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()).base());
838		}
839
840		template<class _InIt1, class _InElem2, class _OutIt, class _Fn2, size_t _SizeFirst2>
841		inline
842		_IF_CHK(_OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
843		_OutIt _Dest, _Fn2 _Func)
844		{
845		return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
846		_STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
847		_Dest, _Func,
848		_Iter_cat(_First1), _Iter_random(_First1, _Dest),
849		_STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()));
850		}
851
852		template<class _InIt1, class _InElem2, class _OutIt, class _Fn2, size_t _SizeFirst2>
853		inline
854		_SCL_INSECURE_DEPRECATE
855		_IF_NOT_CHK(_OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
856		_OutIt _Dest, _Fn2 _Func)
857		{
858		return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
859		_STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
860		_Dest, _Func,
861		_Iter_cat(_First1), _Iter_random(_First1, _Dest),
862		_STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()));
863		}
864
865		template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
866		inline
867		_SCL_INSECURE_DEPRECATE
868		_IF_NOT_CHK2_(_InIt2, _OutIt, _OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
869		_OutIt _Dest, _Fn2 _Func)
870		{
871		return _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
872		_Iter_random(_First1, _First2), _Iter_random(_First1, _Dest),
873		_STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
874		}
875
876		#else
877
878		template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
879		inline
880		_OutIt transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
881		_OutIt _Dest, _Fn2 _Func)
882		{
883		return _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
884		_Iter_random(_First1, _First2), _Iter_random(_First1, _Dest),
885		_STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
886		}
887
888		#endif
889
890		// TEMPLATE FUNCTION replace
891		template<class _FwdIt,
892		class _Ty> inline
893		void _Replace(_FwdIt _First, _FwdIt _Last,
894		const _Ty& _Oldval, const _Ty& _Newval)
895		{    // replace each matching _Oldval with _Newval
896		_DEBUG_RANGE(_First, _Last);
897		for (; _First != _Last; ++_First)
898		if (*_First == _Oldval)
899		*_First = _Newval;
900		}
901
902		template<class _FwdIt,
903		class _Ty> inline
904		void replace(_FwdIt _First, _FwdIt _Last,
905		const _Ty& _Oldval, const _Ty& _Newval)
906		{    // replace each matching _Oldval with _Newval
907		_Replace(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Oldval, _Newval);
908		}
909
910		// TEMPLATE FUNCTION replace_if
911		template<class _FwdIt,
912		class _Pr,
913		class _Ty> inline
914		void _Replace_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred, const _Ty& _Val)
915		{    // replace each satisfying _Pred with _Val
916		_DEBUG_RANGE(_First, _Last);
917		_DEBUG_POINTER(_Pred);
918		for (; _First != _Last; ++_First)
919		if (_Pred(*_First))
920		*_First = _Val;
921		}
922
923		template<class _FwdIt,
924		class _Pr,
925		class _Ty> inline
926		void replace_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred, const _Ty& _Val)
927		{    // replace each satisfying _Pred with _Val
928		_Replace_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred, _Val);
929		}
930
931		// TEMPLATE FUNCTION replace_copy
932		template<class _InIt, class _OutIt, class _Ty, class _InOutItCat>
933		inline
934		_OutIt _Replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
935		const _Ty& _Oldval, const _Ty& _Newval,
936		_InOutItCat, _Range_checked_iterator_tag)
937		{    // copy replacing each matching _Oldval with _Newval
938		_DEBUG_RANGE(_First, _Last);
939		_DEBUG_POINTER(_Dest);
940		for (; _First != _Last; ++_First, ++_Dest)
941		*_Dest = *_First == _Oldval ? _Newval : *_First;
942		return (_Dest);
943		}
944
945		#if _SECURE_SCL
946		template<class _InIt, class _OutIt, class _Ty>
947		inline
948		_OutIt _Replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
949		const _Ty& _Oldval, const _Ty& _Newval,
950		random_access_iterator_tag, _Range_checked_iterator_tag)
951		{    // copy replacing each matching _Oldval with _Newval
952		// for range checked iterators, this will make sure there is enough space
953		_OutIt _Result = _Dest + (_Last - _First);
954		_Replace_copy(_First, _Last, _CHECKED_BASE(_Dest),
955		_Oldval, _Newval,
956		forward_iterator_tag(), _Range_checked_iterator_tag());
957		return (_Result);
958		}
959		#endif
960
961		#if _SECURE_SCL
962
963		template<class _InIt,
964		class _OutIt,
965		class _Ty> inline
966		_IF_CHK(_OutIt) replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
967		const _Ty& _Oldval, const _Ty& _Newval)
968		{    // copy replacing each matching _Oldval with _Newval
969		return _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
970		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
971		}
972
973		template<class _InIt, class _OutElem, class _Ty, size_t _Size>
974		inline
975		_OutElem* replace_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size],
976		const _Ty& _Oldval, const _Ty& _Newval)
977		{    // copy replacing each matching _Oldval with _Newval
978		return (replace_copy(_First, _Last,
979		_STDEXT make_checked_array_iterator(_Dest, _Size),
980		_Oldval, _Newval).base());
981		}
982
983		template<class _InIt,
984		class _OutIt,
985		class _Ty> inline
986		_SCL_INSECURE_DEPRECATE
987		_IF_NOT_CHK(_OutIt) replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
988		const _Ty& _Oldval, const _Ty& _Newval)
989		{    // copy replacing each matching _Oldval with _Newval
990		return _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
991		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
992		}
993
994		#else
995
996		template<class _InIt,
997		class _OutIt,
998		class _Ty> inline
999		_OutIt replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
1000		const _Ty& _Oldval, const _Ty& _Newval)
1001		{    // copy replacing each matching _Oldval with _Newval
1002		return _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
1003		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1004		}
1005
1006		#endif
1007
1008		// TEMPLATE FUNCTION replace_copy_if
1009		template<class _InIt, class _OutIt, class _Pr, class _Ty, class _InOutItCat>
1010		inline
1011		_OutIt _Replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1012		_Pr _Pred, const _Ty& _Val, _InOutItCat, _Range_checked_iterator_tag)
1013		{    // copy replacing each satisfying _Pred with _Val
1014		_DEBUG_RANGE(_First, _Last);
1015		_DEBUG_POINTER(_Dest);
1016		_DEBUG_POINTER(_Pred);
1017		for (; _First != _Last; ++_First, ++_Dest)
1018		*_Dest = _Pred(*_First) ? _Val : *_First;
1019		return (_Dest);
1020		}
1021
1022		#if _SECURE_SCL
1023		template<class _InIt, class _OutIt, class _Pr, class _Ty>
1024		inline
1025		_OutIt _Replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1026		_Pr _Pred, const _Ty& _Val,
1027		random_access_iterator_tag, _Range_checked_iterator_tag)
1028		{    // copy replacing each satisfying _Pred with _Val
1029		// for range checked iterators, this will make sure there is enough space
1030		_OutIt _Result = _Dest + (_Last - _First);
1031		_Replace_copy_if(_First, _Last, _CHECKED_BASE(_Dest),
1032		_Pred, _Val,
1033		forward_iterator_tag(), _Range_checked_iterator_tag());
1034		return (_Result);
1035		}
1036		#endif
1037
1038		#if _SECURE_SCL
1039
1040		template<class _InIt,
1041		class _OutIt,
1042		class _Pr,
1043		class _Ty> inline
1044		_IF_CHK(_OutIt) replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1045		_Pr _Pred, const _Ty& _Val)
1046		{    // copy replacing each satisfying _Pred with _Val
1047		return _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
1048		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1049		}
1050
1051		template<class _InIt, class _OutElem, class _Pr, class _Ty, size_t _Size>
1052		inline
1053		_OutElem* replace_copy_if(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size],
1054		_Pr _Pred, const _Ty& _Val)
1055		{    // copy replacing each satisfying _Pred with _Val
1056		return (replace_copy_if(_First, _Last,
1057		_STDEXT make_checked_array_iterator(_Dest, _Size),
1058		_Pred, _Val).base());
1059		}
1060
1061		template<class _InIt,
1062		class _OutIt,
1063		class _Pr,
1064		class _Ty> inline
1065		_SCL_INSECURE_DEPRECATE
1066		_IF_NOT_CHK(_OutIt) replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1067		_Pr _Pred, const _Ty& _Val)
1068		{    // copy replacing each satisfying _Pred with _Val
1069		return _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
1070		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1071		}
1072
1073		#else
1074
1075		template<class _InIt,
1076		class _OutIt,
1077		class _Pr,
1078		class _Ty> inline
1079		_OutIt replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1080		_Pr _Pred, const _Ty& _Val)
1081		{    // copy replacing each satisfying _Pred with _Val
1082		return _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
1083		_Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1084		}
1085
1086		#endif
1087
1088		// TEMPLATE FUNCTION generate
1089		template<class _FwdIt,
1090		class _Fn0> inline
1091		void _Generate(_FwdIt _First, _FwdIt _Last, _Fn0 _Func)
1092		{    // replace [_First, _Last) with _Func()
1093		_DEBUG_RANGE(_First, _Last);
1094		_DEBUG_POINTER(_Func);
1095		for (; _First != _Last; ++_First)
1096		*_First = _Func();
1097		}
1098
1099		template<class _FwdIt,
1100		class _Fn0> inline
1101		void generate(_FwdIt _First, _FwdIt _Last, _Fn0 _Func)
1102		{    // replace [_First, _Last) with _Func()
1103		_Generate(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Func);
1104		}
1105
1106		// TEMPLATE FUNCTION generate_n
1107		template<class _OutIt, class _Diff, class _Fn0, class _OutItCat>
1108		inline
1109		void _Generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func,
1110		_OutItCat, _Range_checked_iterator_tag)
1111		{    // replace [_Dest, _Dest + _Count) with _Func()
1112		_DEBUG_POINTER(_Dest);
1113		_DEBUG_POINTER(_Func);
1114		for (; 0 < _Count; --_Count, ++_Dest)
1115		*_Dest = _Func();
1116		}
1117
1118		#if _SECURE_SCL
1119		template<class _OutIt, class _Diff, class _Fn0>
1120		inline
1121		void _Generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func,
1122		random_access_iterator_tag, _Range_checked_iterator_tag)
1123		{    // replace [_Dest, _Dest + _Count) with _Func()
1124		// for range checked iterators, this will make sure there is enough space
1125		_OutIt _Result = _Dest + _Count;
1126		_Generate_n(_CHECKED_BASE(_Dest), _Count, _Func,
1127		forward_iterator_tag(), _Range_checked_iterator_tag());
1128		}
1129		#endif
1130
1131		#if _SECURE_SCL
1132
1133		template<class _OutIt,
1134		class _Diff,
1135		class _Fn0> inline
1136		_IF_CHK_(_OutIt, void) generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
1137		{    // replace [_Dest, _Dest + _Count) with _Func()
1138		_Generate_n(_Dest, _Count, _Func,
1139		_Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
1140		}
1141
1142		template<class _OutElem, class _Diff, class _Fn0, size_t _Size>
1143		inline
1144		void generate_n(_OutElem (&_Dest)[_Size], _Diff _Count, _Fn0 _Func)
1145		{    // replace [_Dest, _Dest + _Count) with _Func()
1146		generate_n(_STDEXT make_checked_array_iterator(_Dest, _Size), _Count, _Func);
1147		}
1148
1149		template<class _OutIt,
1150		class _Diff,
1151		class _Fn0> inline
1152		_SCL_INSECURE_DEPRECATE
1153		_IF_NOT_CHK_(_OutIt, void) generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
1154		{    // replace [_Dest, _Dest + _Count) with _Func()
1155		_Generate_n(_Dest, _Count, _Func,
1156		_Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
1157		}
1158
1159		#else
1160
1161		template<class _OutIt,
1162		class _Diff,
1163		class _Fn0> inline
1164		void generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
1165		{    // replace [_Dest, _Dest + _Count) with _Func()
1166		_Generate_n(_Dest, _Count, _Func,
1167		_Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
1168		}
1169
1170		#endif
1171
1172		// TEMPLATE FUNCTION remove_copy
1173		template<class _InIt,
1174		class _OutIt,
1175		class _Ty> inline
1176		_OutIt _Remove_copy(_InIt _First, _InIt _Last,
1177		_OutIt _Dest, const _Ty& _Val, _Range_checked_iterator_tag)
1178		{    // copy omitting each matching _Val
1179		_DEBUG_RANGE(_First, _Last);
1180		_DEBUG_POINTER(_Dest);
1181		for (; _First != _Last; ++_First)
1182		if (!(*_First == _Val))
1183		*_Dest++ = *_First;
1184		return (_Dest);
1185		}
1186
1187		#if _SECURE_SCL
1188
1189		template<class _InIt,
1190		class _OutIt,
1191		class _Ty> inline
1192		_IF_CHK(_OutIt) remove_copy(_InIt _First, _InIt _Last,
1193		_OutIt _Dest, const _Ty& _Val)
1194		{    // copy omitting each matching _Val
1195		return _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
1196		}
1197
1198		template<class _InIt, class _OutElem, class _Ty, size_t _Size>
1199		inline
1200		_OutElem* remove_copy(_InIt _First, _InIt _Last,
1201		_OutElem (&_Dest)[_Size], const _Ty& _Val)
1202		{    // copy omitting each matching _Val
1203		return (remove_copy(_First, _Last,
1204		_STDEXT make_checked_array_iterator(_Dest, _Size),
1205		_Val).base());
1206		}
1207
1208		template<class _InIt,
1209		class _OutIt,
1210		class _Ty> inline
1211		_SCL_INSECURE_DEPRECATE
1212		_IF_NOT_CHK(_OutIt) remove_copy(_InIt _First, _InIt _Last,
1213		_OutIt _Dest, const _Ty& _Val)
1214		{    // copy omitting each matching _Val
1215		return _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
1216		}
1217
1218		#else
1219
1220		template<class _InIt,
1221		class _OutIt,
1222		class _Ty> inline
1223		_OutIt remove_copy(_InIt _First, _InIt _Last,
1224		_OutIt _Dest, const _Ty& _Val)
1225		{    // copy omitting each matching _Val
1226		return _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
1227		}
1228
1229		#endif
1230
1231		// TEMPLATE FUNCTION remove_copy_if
1232		template<class _InIt,
1233		class _OutIt,
1234		class _Pr> inline
1235		_OutIt _Remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
1236		{    // copy omitting each element satisfying _Pred
1237		_DEBUG_RANGE(_First, _Last);
1238		_DEBUG_POINTER(_Dest);
1239		_DEBUG_POINTER(_Pred);
1240		for (; _First != _Last; ++_First)
1241		if (!_Pred(*_First))
1242		*_Dest++ = *_First;
1243		return (_Dest);
1244		}
1245
1246		#if _SECURE_SCL
1247
1248		template<class _InIt,
1249		class _OutIt,
1250		class _Pr> inline
1251		_IF_CHK(_OutIt) remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1252		{    // copy omitting each element satisfying _Pred
1253		return _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
1254		}
1255
1256		template<class _InIt, class _OutElem, class _Pr, size_t _Size>
1257		inline
1258		_OutElem* remove_copy_if(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Pr _Pred)
1259		{    // copy omitting each element satisfying _Pred
1260		return (remove_copy_if(_First, _Last,
1261		_STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
1262		}
1263
1264		template<class _InIt,
1265		class _OutIt,
1266		class _Pr> inline
1267		_SCL_CHECKED_ALGORITHM_WARN
1268		_IF_NOT_CHK(_OutIt) remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1269		{    // copy omitting each element satisfying _Pred
1270		return _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
1271		}
1272
1273		#else
1274
1275		template<class _InIt,
1276		class _OutIt,
1277		class _Pr> inline
1278		_OutIt remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1279		{    // copy omitting each element satisfying _Pred
1280		return _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
1281		}
1282
1283		#endif
1284
1285		// TEMPLATE FUNCTION remove
1286		template<class _FwdIt,
1287		class _Ty> inline
1288		_FwdIt remove(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
1289		{    // remove each matching _Val
1290		_First = find(_First, _Last, _Val);
1291		if (_First == _Last)
1292		return (_First);    // empty sequence, all done
1293		else
1294		{    // nonempty sequence, worth doing
1295		_FwdIt _First1 = _First;
1296		return (_STDEXT unchecked_remove_copy(++_First1, _Last, _First, _Val));
1297		}
1298		}
1299
1300		// TEMPLATE FUNCTION remove_if
1301		template<class _FwdIt,
1302		class _Pr> inline
1303		_FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
1304		{    // remove each satisfying _Pred
1305		_First = std::find_if(_First, _Last, _Pred);
1306		if (_First == _Last)
1307		return (_First);    // empty sequence, all done
1308		else
1309		{    // nonempty sequence, worth doing
1310		_FwdIt _First1 = _First;
1311		return (_STDEXT unchecked_remove_copy_if(++_First1, _Last, _First, _Pred));
1312		}
1313		}
1314
1315		// TEMPLATE FUNCTION unique
1316		template<class _FwdIt> inline
1317		_FwdIt _Unique(_FwdIt _First, _FwdIt _Last)
1318		{    // remove each matching previous
1319		_DEBUG_RANGE(_First, _Last);
1320		for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
1321		if (*_Firstb == *_First)
1322		{    // copy down
1323		for (; ++_First != _Last; )
1324		if (!(*_Firstb == *_First))
1325		*++_Firstb = *_First;
1326		return (++_Firstb);
1327		}
1328		return (_Last);
1329		}
1330
1331		template<class _FwdIt> inline
1332		_FwdIt unique(_FwdIt _First, _FwdIt _Last)
1333		{    // remove each matching previous
1334		_ASSIGN_FROM_BASE(_Last,
1335		_Unique(_CHECKED_BASE(_First), _CHECKED_BASE(_Last)));
1336		return (_Last);
1337		}
1338
1339		// TEMPLATE FUNCTION unique WITH PRED
1340		template<class _FwdIt,
1341		class _Pr> inline
1342		_FwdIt _Unique(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
1343		{    // remove each satisfying _Pred with previous
1344		_DEBUG_RANGE(_First, _Last);
1345		_DEBUG_POINTER(_Pred);
1346		for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
1347		if (_Pred(*_Firstb, *_First))
1348		{    // copy down
1349		for (; ++_First != _Last; )
1350		if (!_Pred(*_Firstb, *_First))
1351		*++_Firstb = *_First;
1352		return (++_Firstb);
1353		}
1354		return (_Last);
1355		}
1356
1357		template<class _FwdIt,
1358		class _Pr> inline
1359		_FwdIt unique(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
1360		{    // remove each satisfying _Pred with previous
1361		_ASSIGN_FROM_BASE(_Last,
1362		_Unique(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
1363		return (_Last);
1364		}
1365
1366		// TEMPLATE FUNCTION unique_copy
1367		template<class _InIt,
1368		class _OutIt,
1369		class _Ty> inline
1370		_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Ty *, _Range_checked_iterator_tag)
1371		{    // copy compressing pairs that match, input iterators
1372		_DEBUG_POINTER(_Dest);
1373		_Ty _Val = *_First;
1374
1375		for (*_Dest++ = _Val; ++_First != _Last; )
1376		if (!(_Val == *_First))
1377		_Val = *_First, *_Dest++ = _Val;
1378		return (_Dest);
1379		}
1380
1381		template<class _InIt,
1382		class _OutIt> inline
1383		_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
1384		input_iterator_tag, _Range_checked_iterator_tag)
1385		{    // copy compressing pairs that match, input iterators
1386		return (_Unique_copy(_First, _Last, _Dest, _Val_type(_First), _Range_checked_iterator_tag()));
1387		}
1388
1389		template<class _FwdIt,
1390		class _OutIt> inline
1391		_OutIt _Unique_copy(_FwdIt _First, _FwdIt _Last, _OutIt _Dest,
1392		forward_iterator_tag, _Range_checked_iterator_tag)
1393		{    // copy compressing pairs that match, forward iterators
1394		_DEBUG_RANGE(_First, _Last);
1395		_DEBUG_POINTER(_Dest);
1396		_FwdIt _Firstb = _First;
1397		for (*_Dest++ = *_Firstb; ++_First != _Last; )
1398		if (!(*_Firstb == *_First))
1399		_Firstb = _First, *_Dest++ = *_Firstb;
1400		return (_Dest);
1401		}
1402
1403		template<class _BidIt,
1404		class _OutIt> inline
1405		_OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
1406		bidirectional_iterator_tag, _Range_checked_iterator_tag)
1407		{    // copy compressing pairs that match, bidirectional iterators
1408		return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag(), _Range_checked_iterator_tag()));
1409		}
1410
1411		template<class _RanIt,
1412		class _OutIt> inline
1413		_OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest,
1414		random_access_iterator_tag, _Range_checked_iterator_tag)
1415		{    // copy compressing pairs that match, random-access iterators
1416		return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag(), _Range_checked_iterator_tag()));
1417		}
1418
1419		#if _SECURE_SCL
1420
1421		template<class _InIt,
1422		class _OutIt> inline
1423		_IF_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
1424		{    // copy compressing pairs that match
1425		return (_First == _Last ? _Dest :
1426		_Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1427		}
1428
1429		template<class _InIt, class _OutElem, size_t _Size>
1430		inline
1431		_OutElem* unique_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size])
1432		{    // copy compressing pairs that match
1433		return (_First == _Last ? _Dest :
1434		(unique_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base()));
1435		}
1436
1437		template<class _InIt,
1438		class _OutIt> inline
1439		_SCL_INSECURE_DEPRECATE
1440		_IF_NOT_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
1441		{    // copy compressing pairs that match
1442		return (_First == _Last ? _Dest :
1443		_Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1444		}
1445
1446		#else
1447
1448		template<class _InIt,
1449		class _OutIt> inline
1450		_OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
1451		{    // copy compressing pairs that match
1452		return (_First == _Last ? _Dest :
1453		_Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1454		}
1455
1456		#endif
1457
1458		// TEMPLATE FUNCTION unique_copy WITH PRED
1459		template<class _InIt,
1460		class _OutIt,
1461		class _Ty,
1462		class _Pr> inline
1463		_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred,
1464		_Ty *, _Range_checked_iterator_tag)
1465		{    // copy compressing pairs satisfying _Pred, input iterators
1466		_DEBUG_POINTER(_Dest);
1467		_DEBUG_POINTER(_Pred);
1468		_Ty _Val = *_First;
1469
1470		for (*_Dest++ = _Val; ++_First != _Last; )
1471		if (!_Pred(_Val, *_First))
1472		_Val = *_First, *_Dest++ = _Val;
1473		return (_Dest);
1474		}
1475
1476		template<class _InIt,
1477		class _OutIt,
1478		class _Pr> inline
1479		_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred,
1480		input_iterator_tag, _Range_checked_iterator_tag)
1481		{    // copy compressing pairs satisfying _Pred, input iterators
1482		return (_Unique_copy(_First, _Last, _Dest, _Pred, _Val_type(_First), _Range_checked_iterator_tag()));
1483		}
1484
1485		template<class _FwdIt,
1486		class _OutIt,
1487		class _Pr> inline
1488		_OutIt _Unique_copy(_FwdIt _First, _FwdIt _Last, _OutIt _Dest, _Pr _Pred,
1489		forward_iterator_tag, _Range_checked_iterator_tag)
1490		{    // copy compressing pairs satisfying _Pred, forward iterators
1491		_DEBUG_RANGE(_First, _Last);
1492		_DEBUG_POINTER(_Dest);
1493		_DEBUG_POINTER(_Pred);
1494		_FwdIt _Firstb = _First;
1495
1496		for (*_Dest++ = *_Firstb; ++_First != _Last; )
1497		if (!_Pred(*_Firstb, *_First))
1498		_Firstb = _First, *_Dest++ = *_Firstb;
1499		return (_Dest);
1500		}
1501
1502		template<class _BidIt,
1503		class _OutIt,
1504		class _Pr> inline
1505		_OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest, _Pr _Pred,
1506		bidirectional_iterator_tag, _Range_checked_iterator_tag)
1507		{    // copy compressing pairs satisfying _Pred, bidirectional iterators
1508		return (_Unique_copy(_First, _Last, _Dest, _Pred,
1509		forward_iterator_tag(), _Range_checked_iterator_tag()));
1510		}
1511
1512		template<class _RanIt,
1513		class _OutIt,
1514		class _Pr> inline
1515		_OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest, _Pr _Pred,
1516		random_access_iterator_tag, _Range_checked_iterator_tag)
1517		{    // copy compressing pairs satisfying _Pred, random-access iterators
1518		return (_Unique_copy(_First, _Last, _Dest, _Pred,
1519		forward_iterator_tag(), _Range_checked_iterator_tag()));
1520		}
1521
1522		#if _SECURE_SCL
1523
1524		template<class _InIt,
1525		class _OutIt,
1526		class _Pr> inline
1527		_IF_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1528		{    // copy compressing pairs satisfying _Pred
1529		return (_First == _Last ? _Dest
1530		: _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1531		}
1532
1533		template<class _InIt, class _OutElem, class _Pr, size_t _Size>
1534		inline
1535		_OutElem* unique_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Pr _Pred)
1536		{    // copy compressing pairs satisfying _Pred
1537		return (_First == _Last ? _Dest
1538		: (unique_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base()));
1539		}
1540
1541		template<class _InIt,
1542		class _OutIt,
1543		class _Pr> inline
1544		_SCL_INSECURE_DEPRECATE
1545		_IF_NOT_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1546		{    // copy compressing pairs satisfying _Pred
1547		return (_First == _Last ? _Dest
1548		: _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1549		}
1550
1551		#else
1552
1553		template<class _InIt,
1554		class _OutIt,
1555		class _Pr> inline
1556		_OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1557		{    // copy compressing pairs satisfying _Pred
1558		return (_First == _Last ? _Dest
1559		: _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1560		}
1561
1562		#endif
1563
1564		// TEMPLATE FUNCTION reverse
1565		template<class _BidIt> inline
1566		void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
1567		{    // reverse elements in [_First, _Last), bidirectional iterators
1568		for (; _First != _Last && _First != --_Last; ++_First)
1569		std::iter_swap(_First, _Last);
1570		}
1571
1572		template<class _RanIt> inline
1573		void _Reverse(_RanIt _First, _RanIt _Last, random_access_iterator_tag)
1574		{    // reverse elements in [_First, _Last), random-access iterators
1575		_DEBUG_RANGE(_First, _Last);
1576		for (; _First < _Last; ++_First)
1577		std::iter_swap(_First, --_Last);
1578		}
1579
1580		template<class _BidIt> inline
1581		void reverse(_BidIt _First, _BidIt _Last)
1582		{    // reverse elements in [_First, _Last)
1583		_Reverse(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Iter_cat(_First));
1584		}
1585
1586		// TEMPLATE FUNCTION reverse_copy
1587		template<class _BidIt, class _OutIt, class _InOutItCat>
1588		inline
1589		_OutIt _Reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
1590		_InOutItCat, _Range_checked_iterator_tag)
1591		{    // copy reversing elements in [_First, _Last)
1592		_DEBUG_RANGE(_First, _Last);
1593		_DEBUG_POINTER(_Dest);
1594		for (; _First != _Last; ++_Dest)
1595		*_Dest = *--_Last;
1596		return (_Dest);
1597		}
1598
1599		#if _SECURE_SCL
1600		template<class _BidIt, class _OutIt>
1601		inline
1602		_OutIt _Reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
1603		random_access_iterator_tag, _Range_checked_iterator_tag)
1604		{    // copy reversing elements in [_First, _Last)
1605		// for range checked iterators, this will make sure there is enough space
1606		_OutIt _Result = _Dest + (_Last - _First);
1607		_Reverse_copy(_First, _Last, _CHECKED_BASE(_Dest),
1608		forward_iterator_tag(), _Range_checked_iterator_tag());
1609		return (_Result);
1610		}
1611		#endif
1612
1613		#if _SECURE_SCL
1614
1615		template<class _BidIt,
1616		class _OutIt> inline
1617		_IF_CHK(_OutIt) reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
1618		{    // copy reversing elements in [_First, _Last)
1619		return _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1620		}
1621
1622		template<class _BidIt, class _OutElem, size_t _Size>
1623		inline
1624		_OutElem* reverse_copy(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size])
1625		{    // copy reversing elements in [_First, _Last)
1626		return (reverse_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
1627		}
1628
1629		template<class _BidIt,
1630		class _OutIt> inline
1631		_SCL_INSECURE_DEPRECATE
1632		_IF_NOT_CHK(_OutIt) reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
1633		{    // copy reversing elements in [_First, _Last)
1634		return _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1635		}
1636
1637		#else
1638
1639		template<class _BidIt,
1640		class _OutIt> inline
1641		_OutIt reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
1642		{    // copy reversing elements in [_First, _Last)
1643		return _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1644		}
1645
1646		#endif
1647
1648		// TEMPLATE FUNCTION rotate
1649		template<class _FwdIt> inline
1650		void _Rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
1651		forward_iterator_tag)
1652		{    // rotate [_First, _Last), forward iterators
1653		for (_FwdIt _Next = _Mid; ; )
1654		{    // swap [_First, ...) into place
1655		std::iter_swap(_First, _Next);
1656		if (++_First == _Mid)
1657		if (++_Next == _Last)
1658		break;    // done, quit
1659		else
1660		_Mid = _Next;    // mark end of next interval
1661		else if (++_Next == _Last)
1662		_Next = _Mid;    // wrap to last end
1663		}
1664		}
1665
1666		template<class _BidIt> inline
1667		void _Rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
1668		bidirectional_iterator_tag)
1669		{    // rotate [_First, _Last), bidirectional iterators
1670		std::reverse(_First, _Mid);
1671		std::reverse(_Mid, _Last);
1672		std::reverse(_First, _Last);
1673		}
1674
1675		template<class _RanIt,
1676		class _Diff,
1677		class _Ty> inline
1678		void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Diff *, _Ty *)
1679		{    // rotate [_First, _Last), random-access iterators
1680		_DEBUG_RANGE(_First, _Mid);
1681		_DEBUG_RANGE(_Mid, _Last);
1682		_Diff _Shift = _Mid - _First;
1683		_Diff _Count = _Last - _First;
1684
1685		for (_Diff _Factor = _Shift; _Factor != 0; )
1686		{    // find subcycle count as GCD of shift count and length
1687		_Diff _Tmp = _Count % _Factor;
1688		_Count = _Factor, _Factor = _Tmp;
1689		}
1690
1691		if (_Count < _Last - _First)
1692		for (; 0 < _Count; --_Count)
1693		{    // rotate each subcycle
1694		_RanIt _Hole = _First + _Count;
1695		_RanIt _Next = _Hole;
1696		_Ty _Holeval = *_Hole;
1697		_RanIt _Next1 = _Next + _Shift == _Last ? _First : _Next + _Shift;
1698		while (_Next1 != _Hole)
1699		{    // percolate elements back around subcycle
1700		*_Next = *_Next1;
1701		_Next = _Next1;
1702		_Next1 = _Shift < _Last - _Next1 ? _Next1 + _Shift
1703		: _First + (_Shift - (_Last - _Next1));
1704		}
1705		*_Next = _Holeval;
1706		}
1707		}
1708
1709		template<class _RanIt> inline
1710		void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
1711		random_access_iterator_tag)
1712		{    // rotate [_First, _Last), random-access iterators
1713		_Rotate(_First, _Mid, _Last, _Dist_type(_First), _Val_type(_First));
1714		}
1715
1716		template<class _FwdIt> inline
1717		void rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last)
1718		{    // rotate [_First, _Last)
1719		if (_First != _Mid && _Mid != _Last)
1720		_Rotate(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last), _Iter_cat(_First));
1721		}
1722
1723		// TEMPLATE FUNCTION rotate_copy
1724		template<class _FwdIt,
1725		class _OutIt> inline
1726		_OutIt _Rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest, _Range_checked_iterator_tag)
1727		{    // copy rotating [_First, _Last)
1728		_Dest = _STDEXT unchecked_copy(_Mid, _Last, _Dest);
1729		return (_STDEXT unchecked_copy(_First, _Mid, _Dest));
1730		}
1731
1732		#if _SECURE_SCL
1733
1734		template<class _FwdIt, class _OutIt>
1735		inline
1736		_IF_CHK(_OutIt) rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
1737		{
1738		return _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
1739		}
1740
1741		template<class _FwdIt, class _OutElem, size_t _Size>
1742		inline
1743		_OutElem* rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutElem (&_Dest)[_Size])
1744		{
1745		return (rotate_copy(_First, _Mid, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
1746		}
1747
1748		template<class _FwdIt, class _OutIt>
1749		inline
1750		_SCL_INSECURE_DEPRECATE
1751		_IF_NOT_CHK(_OutIt) rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
1752		{
1753		return _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
1754		}
1755
1756		#else
1757
1758		template<class _FwdIt, class _OutIt>
1759		inline
1760		_OutIt rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
1761		{
1762		return _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
1763		}
1764
1765		#endif
1766
1767		// TEMPLATE FUNCTION random_shuffle
1768		template<class _RanIt,
1769		class _Diff> inline
1770		void _Random_shuffle(_RanIt _First, _RanIt _Last, _Diff *)
1771		{    // shuffle [_First, _Last)
1772		_DEBUG_RANGE(_First, _Last);
1773		const int _RANDOM_BITS = 15;    // minimum random bits from rand()
1774		const int _RANDOM_MAX = (1U << _RANDOM_BITS) - 1;
1775
1776		_RanIt _Next = _First;
1777		for (unsigned long _Index = 2; ++_Next != _Last; ++_Index)
1778		{    // assume unsigned long big enough for _Diff count
1779		unsigned long _Rm = _RANDOM_MAX;
1780		unsigned long _Rn = ::rand() & _RANDOM_MAX;
1781		for (; _Rm < _Index && _Rm != ~0UL;
1782		_Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX)
1783		_Rn = _Rn << _RANDOM_BITS
1784		| (::rand() & _RANDOM_MAX);    // build random value
1785
1786		std::iter_swap(_Next, _First + _Diff(_Rn % _Index));    // swap a pair
1787		}
1788		}
1789
1790		template<class _RanIt> inline
1791		void random_shuffle(_RanIt _First, _RanIt _Last)
1792		{    // shuffle [_First, _Last)
1793		if (_First != _Last)
1794		_Random_shuffle(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dist_type(_First));
1795		}
1796
1797		// TEMPLATE FUNCTION random_shuffle WITH RANDOM FN
1798		template<class _RanIt,
1799		class _Fn1,
1800		class _Diff> inline
1801		void _Random_shuffle(_RanIt _First, _RanIt _Last, _Fn1& _Func, _Diff *)
1802		{    // shuffle nonempty [_First, _Last) using random function _Func
1803		_DEBUG_RANGE(_First, _Last);
1804		_DEBUG_POINTER(_Func);
1805		_RanIt _Next = _First;
1806
1807		for (_Diff _Index = 2; ++_Next != _Last; ++_Index)
1808		std::iter_swap(_Next, _First + _Diff(_Func(_Index) % _Index));
1809		}
1810
1811		template<class _RanIt,
1812		class _Fn1> inline
1813		void random_shuffle(_RanIt _First, _RanIt _Last, _Fn1& _Func)
1814		{    // shuffle [_First, _Last) using random function _Func
1815		if (_First != _Last)
1816		_Random_shuffle(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Func, _Dist_type(_First));
1817		}
1818
1819		// TEMPLATE FUNCTION partition
1820		template<class _BidIt,
1821		class _Pr> inline
1822		_BidIt _Partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
1823		{    // move elements satisfying _Pred to beginning of sequence
1824		_DEBUG_RANGE(_First, _Last);
1825		_DEBUG_POINTER(_Pred);
1826		for (; ; ++_First)
1827		{    // find any out-of-order pair
1828		for (; _First != _Last && _Pred(*_First); ++_First)
1829		;    // skip in-place elements at beginning
1830		if (_First == _Last)
1831		break;    // done
1832
1833		for (; _First != --_Last && !_Pred(*_Last); )
1834		;    // skip in-place elements at end
1835		if (_First == _Last)
1836		break;    // done
1837
1838		std::iter_swap(_First, _Last);    // swap out-of-place pair and loop
1839		}
1840		return (_First);
1841		}
1842
1843		template<class _BidIt,
1844		class _Pr> inline
1845		_BidIt partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
1846		{    // move elements satisfying _Pred to beginning of sequence
1847		_ASSIGN_FROM_BASE(_First,
1848		_Partition(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
1849		return (_First);
1850		}
1851
1852		// TEMPLATE FUNCTION stable_partition
1853		template<class _BidIt,
1854		class _Pr,
1855		class _Diff,
1856		class _Ty> inline
1857		_BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
1858		_Diff _Count, _Temp_iterator<_Ty>& _Tempbuf)
1859		{    // partition preserving order of equivalents, using _Pred
1860		if (_Count == 0)
1861		return (_First);
1862		else if (_Count == 1)
1863		return (_Pred(*_First) ? _Last : _First);
1864		else if (_Count <= _Tempbuf._Maxlen())
1865		{    // temp buffer big enough, copy right partition out and back
1866		_BidIt _Next = _First;
1867		for (_Tempbuf._Init(); _First != _Last; ++_First)
1868		if (_Pred(*_First))
1869		*_Next++ = *_First;
1870		else
1871		*_Tempbuf++ = *_First;
1872
1873		_STDEXT unchecked_copy(_Tempbuf._First(), _Tempbuf._Last(), _Next);    // copy back
1874		return (_Next);
1875		}
1876		else
1877		{    // temp buffer not big enough, divide and conquer
1878		_BidIt _Mid = _First;
1879		std::advance(_Mid, _Count / 2);
1880
1881		_BidIt _Left = _Stable_partition(_First, _Mid, _Pred,
1882		_Count / 2, _Tempbuf);    // form L1R1 in left half
1883		_BidIt _Right = _Stable_partition(_Mid, _Last, _Pred,
1884		_Count - _Count / 2, _Tempbuf);    // form L2R2 in right half
1885
1886		_Diff _Count1 = 0;
1887		_Distance(_Left, _Mid, _Count1);
1888		_Diff _Count2 = 0;
1889		_Distance(_Mid, _Right, _Count2);
1890
1891		return (_Buffered_rotate(_Left, _Mid, _Right,
1892		_Count1, _Count2, _Tempbuf));    // rotate L1R1L2R2 to L1L2R1R2
1893		}
1894		}
1895
1896		template<class _BidIt,
1897		class _Pr,
1898		class _Diff,
1899		class _Ty> inline
1900		_BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
1901		_Diff *, _Ty *)
1902		{    // partition preserving order of equivalents, using _Pred
1903		_Diff _Count = 0;
1904		_Distance(_First, _Last, _Count);
1905		_Temp_iterator<_Ty> _Tempbuf(_Count);
1906		return (_Stable_partition(_First, _Last, _Pred, _Count, _Tempbuf));
1907		}
1908
1909		template<class _BidIt,
1910		class _Pr> inline
1911		_BidIt stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
1912		{    // partition preserving order of equivalents, using _Pred
1913		if (_First != _Last)
1914		{
1915		_ASSIGN_FROM_BASE(_First,
1916		_Stable_partition(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred,
1917		_Dist_type(_First), _Val_type(_First)));
1918		}
1919		return _First;
1920		}
1921
1922		#ifndef _DEBUG_HEAP_IMPL
1923		#define _DEBUG_HEAP_IMPL _Debug_heap
1924		#endif
1925
1926		#if _HAS_ITERATOR_DEBUGGING
1927		// TEMPLATE FUNCTION _Debug_heap
1928		template<class _RanIt> inline
1929		void _Debug_heap(_RanIt _First, _RanIt _Last)
1930		{    // test if range is a heap ordered by operator<
1931		if (_First != _Last)
1932		for (_RanIt _Root = _First; ++_First != _Last; ++_Root)
1933		if (_DEBUG_LT(*_Root, *_First))
1934		_DEBUG_ERROR("invalid heap");
1935		else if (++_First == _Last)
1936		break;
1937		else if (_DEBUG_LT(*_Root, *_First))
1938		_DEBUG_ERROR("invalid heap");
1939		}
1940
1941		// TEMPLATE FUNCTION _Debug_heap WITH PRED
1942		template<class _RanIt,
1943		class _Pr> inline
1944		void _Debug_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
1945		{    // test if range is a heap ordered by _Pred
1946		if (_First != _Last)
1947		for (_RanIt _Root = _First; ++_First != _Last; ++_Root)
1948		if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
1949		_DEBUG_ERROR("invalid heap");
1950		else if (++_First == _Last)
1951		break;
1952		else if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
1953		_DEBUG_ERROR("invalid heap");
1954		}
1955
1956		#define _DEBUG_HEAP(first, last)    \
1957		_DEBUG_HEAP_IMPL(first, last)
1958		#define _DEBUG_HEAP_PRED(first, last, pred)    \
1959		_DEBUG_HEAP_IMPL(first, last, pred)
1960
1961		#else /* _HAS_ITERATOR_DEBUGGING */
1962		#define _DEBUG_HEAP(first, last)
1963		#define _DEBUG_HEAP_PRED(first, last, pred)
1964		#endif /* _HAS_ITERATOR_DEBUGGING */
1965
1966		// TEMPLATE FUNCTION push_heap
1967		template<class _RanIt,
1968		class _Diff,
1969		class _Ty> inline
1970		void _Push_heap(_RanIt _First, _Diff _Hole,
1971		_Diff _Top, _Ty _Val)
1972		{    // percolate _Hole to _Top or where _Val belongs, using operator<
1973		for (_Diff _Idx = (_Hole - 1) / 2;
1974		_Top < _Hole && _DEBUG_LT(*(_First + _Idx), _Val);
1975		_Idx = (_Hole - 1) / 2)
1976		{    // move _Hole up to parent

Lines 1977 ... 2473 are skipped.

2474		template<class _FwdIt,
2475		class _Ty,
2476		class _Pr> inline
2477		pair<_FwdIt, _FwdIt> equal_range(_FwdIt _First, _FwdIt _Last,
2478		const _Ty& _Val, _Pr _Pred)
2479		{    // find range equivalent to _Val, using _Pred
2480		return (_Equal_range(_First, _Last, _Val, _Pred, _Dist_type(_First)));
2481		}
2482
2483		// TEMPLATE FUNCTION binary_search
2484		template<class _FwdIt,
2485		class _Ty> inline
2486		bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
2487		{    // test if _Val equivalent to some element, using operator<
2488		_First = std::lower_bound(_First, _Last, _Val);
2489		return (_First != _Last && !(_Val < *_First));
2490		}
2491
2492		// TEMPLATE FUNCTION binary_search WITH PRED
2493		template<class _FwdIt,
2494		class _Ty,
2495		class _Pr> inline
2496		bool binary_search(_FwdIt _First, _FwdIt _Last,
2497		const _Ty& _Val, _Pr _Pred)
2498		{    // test if _Val equivalent to some element, using _Pred
2499		_First = std::lower_bound(_First, _Last, _Val, _Pred);
2500		return (_First != _Last && !_Pred(_Val, *_First));
2501		}
2502
2503		// TEMPLATE FUNCTION merge
2504		template<class _InIt1, class _InIt2, class _OutIt, class _InOutItCat>
2505		inline
2506		_OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2507		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest,
2508		_InOutItCat, _Range_checked_iterator_tag)
2509		{    // copy merging ranges, both using operator<
2510		_DEBUG_ORDER(_First1, _Last1);
2511		_DEBUG_ORDER(_First2, _Last2);
2512		_DEBUG_POINTER(_Dest);
2513		for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
2514		if (_DEBUG_LT(*_First2, *_First1))
2515		*_Dest = *_First2, ++_First2;
2516		else
2517		*_Dest = *_First1, ++_First1;
2518
2519		_Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);    // copy any tail
2520		return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
2521		}
2522
2523		#if _SECURE_SCL
2524		template<class _InIt1, class _InIt2, class _OutIt>
2525		inline
2526		_OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2527		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest,
2528		random_access_iterator_tag, _Range_checked_iterator_tag)
2529		{    // copy merging ranges, both using operator<
2530		// for range checked iterators, this will make sure there is enough space
2531		_OutIt _Result = _Dest + (_Last1 - _First1) + (_Last2 - _First2);
2532		_Merge(_First1, _Last1, _First2, _Last2, _CHECKED_BASE(_Dest),
2533		forward_iterator_tag(), _Range_checked_iterator_tag());
2534		return _Result;
2535		}
2536		#endif
2537
2538		#if _SECURE_SCL
2539
2540		template<class _InIt1,
2541		class _InIt2,
2542		class _OutIt> inline
2543		_IF_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2544		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
2545		{    // copy merging ranges, both using operator<
2546		return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2547		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
2548		_Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2549		}
2550
2551		template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
2552		inline
2553		_OutElem* merge(_InIt1 _First1, _InIt1 _Last1,
2554		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
2555		{    // copy merging ranges, both using operator<
2556		return (merge(_First1, _Last1, _First2, _Last2,
2557		_STDEXT make_checked_array_iterator(_Dest, _Size)).base());
2558		}
2559
2560		template<class _InIt1,
2561		class _InIt2,
2562		class _OutIt> inline
2563		_SCL_INSECURE_DEPRECATE
2564		_IF_NOT_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2565		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
2566		{    // copy merging ranges, both using operator<
2567		return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2568		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
2569		_Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2570		}
2571
2572		#else
2573
2574		template<class _InIt1,
2575		class _InIt2,
2576		class _OutIt> inline
2577		_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
2578		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
2579		{    // copy merging ranges, both using operator<
2580		return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2581		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
2582		_Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2583		}
2584
2585		#endif
2586
2587		// TEMPLATE FUNCTION merge WITH PRED
2588		template<class _InIt1, class _InIt2, class _OutIt, class _Pr, class _InOutItCat>
2589		inline
2590		_OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2591		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred,
2592		_InOutItCat, _Range_checked_iterator_tag)
2593		{    //  copy merging ranges, both using _Pred
2594		_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
2595		_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
2596		_DEBUG_POINTER(_Dest);
2597		for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
2598		if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
2599		*_Dest = *_First2, ++_First2;
2600		else
2601		*_Dest = *_First1, ++_First1;
2602
2603		_Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);    // copy any tail
2604		return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
2605		}
2606
2607		#if _SECURE_SCL
2608		template<class _InIt1, class _InIt2, class _OutIt, class _Pr>
2609		inline
2610		_OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2611		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred,
2612		random_access_iterator_tag, _Range_checked_iterator_tag)
2613		{    //  copy merging ranges, both using _Pred
2614		// for range checked iterators, this will make sure there is enough space
2615		_OutIt _Result = _Dest + (_Last1 - _First1) + (_Last2 - _First2);
2616		_Merge(_First1, _Last1, _First2, _Last2, _CHECKED_BASE(_Dest), _Pred,
2617		forward_iterator_tag(), _Range_checked_iterator_tag());
2618		return _Result;
2619		}
2620		#endif
2621
2622		#if _SECURE_SCL
2623
2624		template<class _InIt1,
2625		class _InIt2,
2626		class _OutIt,
2627		class _Pr> inline
2628		_IF_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2629		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
2630		{    //  copy merging ranges, both using _Pred
2631		return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2632		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
2633		_Dest, _Pred,
2634		_Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2635		}
2636
2637		template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
2638		inline
2639		_OutElem* merge(_InIt1 _First1, _InIt1 _Last1,
2640		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
2641		{    //  copy merging ranges, both using _Pred
2642		return (merge(_First1, _Last1, _First2, _Last2,
2643		_STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
2644		}
2645
2646		template<class _InIt1,
2647		class _InIt2,
2648		class _OutIt,
2649		class _Pr> inline
2650		_SCL_INSECURE_DEPRECATE
2651		_IF_NOT_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2652		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
2653		{    //  copy merging ranges, both using _Pred
2654		return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2655		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
2656		_Dest, _Pred,
2657		_Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2658		}
2659
2660		#else
2661
2662		template<class _InIt1,
2663		class _InIt2,
2664		class _OutIt,
2665		class _Pr> inline
2666		_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
2667		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
2668		{    //  copy merging ranges, both using _Pred
2669		return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2670		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
2671		_Dest, _Pred,
2672		_Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2673		}
2674
2675		#endif
2676
2677		// TEMPLATE FUNCTION inplace_merge
2678		template<class _BidIt,
2679		class _Diff,
2680		class _Ty> inline
2681		_BidIt _Buffered_rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2682		_Diff _Count1, _Diff _Count2, _Temp_iterator<_Ty>& _Tempbuf)
2683		{    // rotate [_First, _Last) using temp buffer
2684		if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2685		{    // buffer left partition, then copy parts
2686		_STDEXT unchecked_copy(_First, _Mid, _Tempbuf._Init());
2687		_STDEXT unchecked_copy(_Mid, _Last, _First);
2688		return (_STDEXT unchecked_copy_backward(_Tempbuf._First(), _Tempbuf._Last(),
2689		_Last));
2690		}
2691		else if (_Count2 <= _Tempbuf._Maxlen())
2692		{    // buffer right partition, then copy parts
2693		_STDEXT unchecked_copy(_Mid, _Last, _Tempbuf._Init());
2694		_STDEXT unchecked_copy_backward(_First, _Mid, _Last);
2695		return (_STDEXT unchecked_copy(_Tempbuf._First(), _Tempbuf._Last(), _First));
2696		}
2697		else
2698		{    // buffer too small, rotate in place
2699		std::rotate(_First, _Mid, _Last);
2700		std::advance(_First, _Count2);
2701		return (_First);
2702		}
2703		}
2704
2705		template<class _BidIt1,
2706		class _BidIt2,
2707		class _BidIt3> inline
2708		_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2709		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Range_checked_iterator_tag)
2710		{    // merge backwards to _Dest, using operator<
2711		for (; ; )
2712		if (_First1 == _Last1)
2713		return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
2714		else if (_First2 == _Last2)
2715		return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
2716		else if (_DEBUG_LT(*--_Last2, *--_Last1))
2717		*--_Dest = *_Last1, ++_Last2;
2718		else
2719		*--_Dest = *_Last2, ++_Last1;
2720		}
2721
2722		#if _SECURE_SCL
2723
2724		template<class _BidIt1, class _BidIt2, class _BidIt3>
2725		inline
2726		_IF_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2727		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
2728		{
2729		return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
2730		}
2731
2732		template<class _BidIt1, class _BidIt2, class _BidIt3>
2733		inline
2734		_SCL_INSECURE_DEPRECATE
2735		_IF_NOT_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2736		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
2737		{
2738		return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
2739		}
2740
2741		#else
2742
2743		template<class _BidIt1, class _BidIt2, class _BidIt3>
2744		inline
2745		_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2746		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
2747		{
2748		return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
2749		}
2750
2751		#endif
2752
2753		template<class _BidIt,
2754		class _Diff,
2755		class _Ty> inline
2756		void _Buffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2757		_Diff _Count1, _Diff _Count2,
2758		_Temp_iterator<_Ty>& _Tempbuf)
2759		{    // merge [_First, _Mid) with [_Mid, _Last), using operator<
2760		if (_Count1 + _Count2 == 2)
2761		{    // order two one-element partitions
2762		if (_DEBUG_LT(*_Mid, *_First))
2763		std::iter_swap(_First, _Mid);
2764		}
2765		else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2766		{    // buffer left partition, then merge
2767		_STDEXT unchecked_copy(_First, _Mid, _Tempbuf._Init());
2768		_STDEXT unchecked_merge(_Tempbuf._First(), _Tempbuf._Last(), _Mid, _Last, _First);
2769		}
2770		else if (_Count2 <= _Tempbuf._Maxlen())
2771		{    // buffer right partition, then merge
2772		_STDEXT unchecked_copy(_Mid, _Last, _Tempbuf._Init());
2773		_STDEXT _Unchecked_merge_backward(_First, _Mid,
2774		_Tempbuf._First(), _Tempbuf._Last(), _Last);
2775		}
2776		else
2777		{    // buffer too small, divide and conquer
2778		_BidIt _Firstn, _Lastn;
2779		_Diff _Count1n, _Count2n;
2780
2781		if (_Count2 < _Count1)
2782		{    // left larger, cut it in half and partition right to match
2783		_Count1n = _Count1 / 2, _Count2n = 0;
2784		_Firstn = _First;
2785		std::advance(_Firstn, _Count1n);
2786		_Lastn = std::lower_bound(_Mid, _Last, *_Firstn);
2787		_Distance(_Mid, _Lastn, _Count2n);
2788		}
2789		else
2790		{    // right larger, cut it in half and partition left to match
2791		_Count1n = 0, _Count2n = _Count2 / 2;
2792		_Lastn = _Mid;
2793		std::advance(_Lastn, _Count2n);
2794		_Firstn = std::upper_bound(_First, _Mid, *_Lastn);
2795		_Distance(_First, _Firstn, _Count1n);
2796		}
2797
2798		_BidIt _Midn = _Buffered_rotate(_Firstn, _Mid, _Lastn,
2799		_Count1 - _Count1n, _Count2n, _Tempbuf);    // rearrange middle
2800		_Buffered_merge(_First, _Firstn, _Midn,
2801		_Count1n, _Count2n, _Tempbuf);    // merge each new part
2802		_Buffered_merge(_Midn, _Lastn, _Last,
2803		_Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf);
2804		}
2805		}
2806
2807		template<class _BidIt,
2808		class _Diff,
2809		class _Ty> inline
2810		void _Inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2811		_Diff *, _Ty *)
2812		{    // merge [_First, _Mid) with [_Mid, _Last), using operator<
2813		_DEBUG_ORDER(_First, _Mid);
2814		_DEBUG_ORDER(_Mid, _Last);
2815		_Diff _Count1 = 0;
2816		_Distance(_First, _Mid, _Count1);
2817		_Diff _Count2 = 0;
2818		_Distance(_Mid, _Last, _Count2);
2819		_Temp_iterator<_Ty> _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
2820		_Buffered_merge(_First, _Mid, _Last,
2821		_Count1, _Count2, _Tempbuf);
2822		}
2823
2824		template<class _BidIt> inline
2825		void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last)
2826		{    // merge [_First, _Mid) with [_Mid, _Last), using operator<
2827		if (_First != _Mid && _Mid != _Last)
2828		_Inplace_merge(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last),
2829		_Dist_type(_First), _Val_type(_First));
2830		}
2831
2832		// TEMPLATE FUNCTION inplace_merge WITH PRED
2833		template<class _BidIt1,
2834		class _BidIt2,
2835		class _BidIt3,
2836		class _Pr> inline
2837		_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2838		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred, _Range_checked_iterator_tag)
2839		{    // merge backwards to _Dest, using _Pred
2840		for (; ; )
2841		if (_First1 == _Last1)
2842		return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
2843		else if (_First2 == _Last2)
2844		return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
2845		else if (_DEBUG_LT_PRED(_Pred, *--_Last2, *--_Last1))
2846		*--_Dest = *_Last1, ++_Last2;
2847		else
2848		*--_Dest = *_Last2, ++_Last1;
2849		}
2850
2851		#if _SECURE_SCL
2852
2853		template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
2854		inline
2855		_IF_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2856		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
2857		{
2858		return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
2859		}
2860
2861		template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
2862		inline
2863		_SCL_INSECURE_DEPRECATE
2864		_IF_NOT_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2865		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
2866		{
2867		return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
2868		}
2869
2870		#else
2871
2872		template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
2873		inline
2874		_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2875		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
2876		{
2877		return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
2878		}
2879
2880		#endif
2881
2882		template<class _BidIt,
2883		class _Diff,
2884		class _Ty,
2885		class _Pr> inline
2886		void _Buffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2887		_Diff _Count1, _Diff _Count2,
2888		_Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
2889		{    // merge [_First, _Mid) with [_Mid, _Last), using _Pred
2890		if (_Count1 + _Count2 == 2)
2891		{    // order two one-element partitions
2892		if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
2893		std::iter_swap(_First, _Mid);
2894		}
2895		else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2896		{    // buffer left partition, then merge
2897		_STDEXT unchecked_copy(_First, _Mid, _Tempbuf._Init());
2898		_STDEXT unchecked_merge(_Tempbuf._First(), _Tempbuf._Last(),
2899		_Mid, _Last, _First, _Pred);
2900		}
2901		else if (_Count2 <= _Tempbuf._Maxlen())

Lines 2902 ... 3261 are skipped.

3262		}
3263
3264		if (_ISORT_MAX < _Count)
3265		{    // heap sort if too many divisions
3266		std::make_heap(_First, _Last, _Pred);
3267		std::sort_heap(_First, _Last, _Pred);
3268		}
3269		else if (1 < _Count)
3270		std::_Insertion_sort(_First, _Last, _Pred);    // small
3271		}
3272
3273		template<class _RanIt,
3274		class _Pr> inline
3275		void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
3276		{    // order [_First, _Last), using _Pred
3277		_DEBUG_RANGE(_First, _Last);
3278		_DEBUG_POINTER(_Pred);
3279		std::_Sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Last - _First, _Pred);
3280		}
3281
3282		// TEMPLATE FUNCTION stable_sort
3283		template<class _BidIt,
3284		class _OutIt,
3285		class _Diff> inline
3286		void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3287		_Diff _Chunk, _Diff _Count, _Range_checked_iterator_tag)
3288		{    // copy merging chunks, using operator<
3289		for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
3290		{    // copy merging pairs of adjacent chunks
3291		_BidIt _Mid1 = _First;
3292		std::advance(_Mid1, _Chunk);
3293		_BidIt _Mid2 = _Mid1;
3294		std::advance(_Mid2, _Chunk);
3295
3296		_Dest = _STDEXT unchecked_merge(_First, _Mid1, _Mid1, _Mid2, _Dest);
3297		_First = _Mid2;
3298		}
3299
3300		if (_Count <= _Chunk)
3301		_STDEXT unchecked_copy(_First, _Last, _Dest);    // copy partial last chunk
3302		else
3303		{    // copy merging whole and partial last chunk
3304		_BidIt _Mid = _First;
3305		std::advance(_Mid, _Chunk);
3306
3307		_STDEXT unchecked_merge(_First, _Mid, _Mid, _Last, _Dest);
3308		}
3309		}
3310
3311		#if _SECURE_SCL
3312
3313		template<class _BidIt, class _OutIt, class _Diff>
3314		inline
3315		_IF_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3316		_Diff _Chunk, _Diff _Count)
3317		{
3318		_Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
3319		}
3320
3321		template<class _BidIt, class _OutElem, class _Diff, size_t _Size>
3322		inline
3323		void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size],
3324		_Diff _Chunk, _Diff _Count)
3325		{
3326		_Chunked_merge(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Chunk, _Count, _STD _Range_checked_iterator_tag());
3327		}
3328
3329		template<class _BidIt, class _OutIt, class _Diff>
3330		inline
3331		_SCL_INSECURE_DEPRECATE
3332		_IF_NOT_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3333		_Diff _Chunk, _Diff _Count)
3334		{
3335		_Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
3336		}
3337
3338		#else
3339
3340		template<class _BidIt, class _OutIt, class _Diff>
3341		inline
3342		void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3343		_Diff _Chunk, _Diff _Count)
3344		{
3345		_Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
3346		}
3347
3348		#endif
3349
3350		template<class _BidIt,
3351		class _Diff,
3352		class _Ty> inline
3353		void _Buffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3354		_Temp_iterator<_Ty>& _Tempbuf)
3355		{    // sort using temp buffer for merges, using operator<
3356		_BidIt _Mid = _First;
3357		for (_Diff _Nleft = _Count; _ISORT_MAX <= _Nleft; _Nleft -= _ISORT_MAX)
3358		{    // sort chunks
3359		_BidIt _Midend = _Mid;
3360		std::advance(_Midend, (int)_ISORT_MAX);
3361
3362		std::_Insertion_sort(_Mid, _Midend);
3363		_Mid = _Midend;
3364		}
3365		std::_Insertion_sort(_Mid, _Last);    // sort partial last chunk
3366
3367		for (_Diff _Chunk = _ISORT_MAX; _Chunk < _Count; _Chunk *= 2)
3368		{    // merge adjacent pairs of chunks to and from temp buffer
3369		_STDEXT _Unchecked_chunked_merge(_First, _Last, _Tempbuf._Init(),
3370		_Chunk, _Count);
3371		_STDEXT _Unchecked_chunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
3372		_Chunk *= 2, _Count);
3373		}
3374		}
3375
3376		template<class _BidIt,
3377		class _Diff,
3378		class _Ty> inline
3379		void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3380		_Temp_iterator<_Ty>& _Tempbuf)
3381		{    //  sort preserving order of equivalents, using operator<
3382		if (_Count <= _ISORT_MAX)
3383		std::_Insertion_sort(_First, _Last);    // small
3384		else
3385		{    // sort halves and merge
3386		_Diff _Count2 = (_Count + 1) / 2;
3387		_BidIt _Mid = _First;
3388		std::advance(_Mid, _Count2);
3389
3390		if (_Count2 <= _Tempbuf._Maxlen())
3391		{    // temp buffer big enough, sort each half using buffer
3392		_Buffered_merge_sort(_First, _Mid, _Count2, _Tempbuf);
3393		_Buffered_merge_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
3394		}
3395		else
3396		{    // temp buffer not big enough, divide and conquer
3397		_Stable_sort(_First, _Mid, _Count2, _Tempbuf);
3398		_Stable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
3399		}
3400
3401		_Buffered_merge(_First, _Mid, _Last,
3402		_Count2, _Count - _Count2, _Tempbuf);    // merge sorted halves
3403		}
3404		}
3405
3406		template<class _BidIt,
3407		class _Diff,
3408		class _Ty> inline
3409		void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff *, _Ty *)
3410		{    // sort preserving order of equivalents, using operator<
3411		_Diff _Count = 0;
3412		_Distance(_First, _Last, _Count);
3413		_Temp_iterator<_Ty> _Tempbuf((_Count + 1) / 2);
3414		_Stable_sort(_First, _Last, _Count, _Tempbuf);
3415		}
3416
3417		template<class _BidIt> inline
3418		void stable_sort(_BidIt _First, _BidIt _Last)
3419		{    // sort preserving order of equivalents, using operator<
3420		_DEBUG_RANGE(_First, _Last);
3421		if (_First != _Last)
3422		{
3423		_Stable_sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dist_type(_First), _Val_type(_First));
3424		}
3425		}
3426
3427		// TEMPLATE FUNCTION stable_sort WITH PRED
3428		template<class _BidIt,
3429		class _OutIt,
3430		class _Diff,
3431		class _Pr> inline
3432		void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3433		_Diff _Chunk, _Diff _Count, _Pr _Pred, _Range_checked_iterator_tag)
3434		{    // copy merging chunks, using _Pred
3435		for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
3436		{    // copy merging pairs of adjacent chunks
3437		_BidIt _Mid1 = _First;
3438		std::advance(_Mid1, _Chunk);
3439		_BidIt _Mid2 = _Mid1;
3440		std::advance(_Mid2, _Chunk);
3441
3442		_Dest = _STDEXT unchecked_merge(_First, _Mid1, _Mid1, _Mid2, _Dest, _Pred);
3443		_First = _Mid2;
3444		}
3445
3446		if (_Count <= _Chunk)
3447		_STDEXT unchecked_copy(_First, _Last, _Dest);    // copy partial last chunk
3448		else
3449		{    // copy merging whole and partial last chunk
3450		_BidIt _Mid1 = _First;
3451		std::advance(_Mid1, _Chunk);
3452
3453		_STDEXT unchecked_merge(_First, _Mid1, _Mid1, _Last, _Dest, _Pred);
3454		}
3455		}
3456
3457		#if _SECURE_SCL
3458
3459		template<class _BidIt, class _OutIt, class _Diff, class _Pr>
3460		inline
3461		_IF_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3462		_Diff _Chunk, _Diff _Count, _Pr _Pred)
3463		{
3464		_Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3465		}
3466
3467		template<class _BidIt, class _OutElem, class _Diff, class _Pr, size_t _Size>
3468		inline
3469		void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size],
3470		_Diff _Chunk, _Diff _Count, _Pr _Pred)
3471		{
3472		_Chunked_merge(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3473		}
3474
3475		template<class _BidIt, class _OutIt, class _Diff, class _Pr>
3476		inline
3477		_SCL_INSECURE_DEPRECATE
3478		_IF_NOT_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3479		_Diff _Chunk, _Diff _Count, _Pr _Pred)
3480		{
3481		_Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3482		}
3483
3484		#else
3485
3486		template<class _BidIt, class _OutIt, class _Diff, class _Pr>
3487		inline
3488		void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3489		_Diff _Chunk, _Diff _Count, _Pr _Pred)
3490		{
3491		_Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3492		}
3493
3494		#endif
3495
3496		template<class _BidIt,
3497		class _Diff,
3498		class _Ty,
3499		class _Pr> inline
3500		void _Buffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3501		_Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
3502		{    // sort using temp buffer for merges, using _Pred
3503		_BidIt _Mid = _First;
3504		for (_Diff _Nleft = _Count; _ISORT_MAX <= _Nleft; _Nleft -= _ISORT_MAX)
3505		{    // sort chunks
3506		_BidIt _Midn = _Mid;
3507		std::advance(_Midn, (int)_ISORT_MAX);

Lines 3508 ... 3787 are skipped.

3788		template<class _InIt1,
3789		class _InIt2,
3790		class _Pr> inline
3791		bool _Includes(_InIt1 _First1, _InIt1 _Last1,
3792		_InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
3793		{    // test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
3794		_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
3795		_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
3796		for (; _First1 != _Last1 && _First2 != _Last2; )
3797		if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
3798		return (false);
3799		else if (_Pred(*_First1, *_First2))
3800		++_First1;
3801		else
3802		++_First1, ++_First2;
3803		return (_First2 == _Last2);
3804		}
3805
3806		template<class _InIt1,
3807		class _InIt2,
3808		class _Pr> inline
3809		bool includes(_InIt1 _First1, _InIt1 _Last1,
3810		_InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
3811		{    // test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
3812		return _Includes(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3813		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred);
3814		}
3815
3816		// TEMPLATE FUNCTION set_union
3817		template<class _InIt1,
3818		class _InIt2,
3819		class _OutIt> inline
3820		_OutIt _Set_union(_InIt1 _First1, _InIt1 _Last1,
3821		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
3822		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3823		_DEBUG_ORDER(_First1, _Last1);
3824		_DEBUG_ORDER(_First2, _Last2);
3825		_DEBUG_POINTER(_Dest);
3826		for (; _First1 != _Last1 && _First2 != _Last2; )
3827		if (_DEBUG_LT(*_First1, *_First2))
3828		*_Dest++ = *_First1, ++_First1;
3829		else if (*_First2 < *_First1)
3830		*_Dest++ = *_First2, ++_First2;
3831		else
3832		*_Dest++ = *_First1, ++_First1, ++_First2;
3833		_Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
3834		return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
3835		}
3836
3837		#if _SECURE_SCL
3838
3839		template<class _InIt1,
3840		class _InIt2,
3841		class _OutIt> inline
3842		_IF_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3843		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3844		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3845		return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3846		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3847		_Dest, _STD _Range_checked_iterator_tag());
3848		}
3849
3850		template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
3851		inline
3852		_OutElem* set_union(_InIt1 _First1, _InIt1 _Last1,
3853		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
3854		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3855		return (set_union(_First1, _Last1, _First2, _Last2,
3856		_STDEXT make_checked_array_iterator(_Dest, _Size)).base());
3857		}
3858
3859		template<class _InIt1,
3860		class _InIt2,
3861		class _OutIt> inline
3862		_SCL_INSECURE_DEPRECATE
3863		_IF_NOT_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3864		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3865		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3866		return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3867		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3868		_Dest, _STD _Range_checked_iterator_tag());
3869		}
3870
3871		#else
3872
3873		template<class _InIt1,
3874		class _InIt2,
3875		class _OutIt> inline
3876		_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
3877		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3878		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3879		return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3880		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3881		_Dest, _STD _Range_checked_iterator_tag());
3882		}
3883
3884		#endif
3885
3886		// TEMPLATE FUNCTION set_union WITH PRED
3887		template<class _InIt1,
3888		class _InIt2,
3889		class _OutIt,
3890		class _Pr> inline
3891		_OutIt _Set_union(_InIt1 _First1, _InIt1 _Last1,
3892		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
3893		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3894		_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
3895		_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
3896		_DEBUG_POINTER(_Dest);
3897		for (; _First1 != _Last1 && _First2 != _Last2; )
3898		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
3899		*_Dest++ = *_First1, ++_First1;
3900		else if (_Pred(*_First2, *_First1))
3901		*_Dest++ = *_First2, ++_First2;
3902		else
3903		*_Dest++ = *_First1, ++_First1, ++_First2;
3904		_Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
3905		return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
3906		}
3907
3908		#if _SECURE_SCL
3909
3910		template<class _InIt1,
3911		class _InIt2,
3912		class _OutIt,
3913		class _Pr> inline
3914		_IF_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3915		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
3916		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3917		return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3918		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3919		_Dest, _Pred, _STD _Range_checked_iterator_tag());
3920		}
3921
3922		template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
3923		inline
3924		_OutElem* set_union(_InIt1 _First1, _InIt1 _Last1,
3925		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
3926		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3927		return (set_union(_First1, _Last1, _First2, _Last2,
3928		_STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
3929		}
3930
3931		template<class _InIt1,
3932		class _InIt2,
3933		class _OutIt,
3934		class _Pr> inline
3935		_SCL_INSECURE_DEPRECATE
3936		_IF_NOT_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3937		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
3938		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3939		return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3940		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3941		_Dest, _Pred, _STD _Range_checked_iterator_tag());
3942		}
3943
3944		#else
3945
3946		template<class _InIt1,
3947		class _InIt2,
3948		class _OutIt,
3949		class _Pr> inline
3950		_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
3951		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
3952		{    // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3953		return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3954		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3955		_Dest, _Pred, _STD _Range_checked_iterator_tag());
3956		}
3957
3958		#endif
3959
3960		// TEMPLATE FUNCTION set_intersection
3961		template<class _InIt1,
3962		class _InIt2,
3963		class _OutIt> inline
3964		_OutIt _Set_intersection(_InIt1 _First1, _InIt1 _Last1,
3965		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
3966		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
3967		_DEBUG_ORDER(_First1, _Last1);
3968		_DEBUG_ORDER(_First2, _Last2);
3969		_DEBUG_POINTER(_Dest);
3970		for (; _First1 != _Last1 && _First2 != _Last2; )
3971		if (_DEBUG_LT(*_First1, *_First2))
3972		++_First1;
3973		else if (*_First2 < *_First1)
3974		++_First2;
3975		else
3976		*_Dest++ = *_First1++, ++_First2;
3977		return (_Dest);
3978		}
3979
3980		#if _SECURE_SCL
3981
3982		template<class _InIt1,
3983		class _InIt2,
3984		class _OutIt> inline
3985		_IF_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
3986		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3987		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
3988		return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3989		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3990		_Dest, _STD _Range_checked_iterator_tag());
3991		}
3992
3993		template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
3994		inline
3995		_OutElem* set_intersection(_InIt1 _First1, _InIt1 _Last1,
3996		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
3997		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
3998		return (set_intersection(_First1, _Last1, _First2, _Last2,
3999		_STDEXT make_checked_array_iterator(_Dest, _Size)).base());
4000		}
4001
4002		template<class _InIt1,
4003		class _InIt2,
4004		class _OutIt> inline
4005		_SCL_INSECURE_DEPRECATE
4006		_IF_NOT_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
4007		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4008		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
4009		return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4010		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4011		_Dest, _STD _Range_checked_iterator_tag());
4012		}
4013
4014		#else
4015
4016		template<class _InIt1,
4017		class _InIt2,
4018		class _OutIt> inline
4019		_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
4020		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4021		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
4022		return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4023		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4024		_Dest, _STD _Range_checked_iterator_tag());
4025		}
4026
4027		#endif
4028
4029		// TEMPLATE FUNCTION set_intersection WITH PRED
4030		template<class _InIt1,
4031		class _InIt2,
4032		class _OutIt,
4033		class _Pr> inline
4034		_OutIt _Set_intersection(_InIt1 _First1, _InIt1 _Last1,
4035		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
4036		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4037		_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
4038		_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
4039		_DEBUG_POINTER(_Dest);
4040		for (; _First1 != _Last1 && _First2 != _Last2; )
4041		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
4042		++_First1;
4043		else if (_Pred(*_First2, *_First1))
4044		++_First2;
4045		else
4046		*_Dest++ = *_First1++, ++_First2;
4047		return (_Dest);
4048		}
4049
4050		#if _SECURE_SCL
4051
4052		template<class _InIt1,
4053		class _InIt2,
4054		class _OutIt,
4055		class _Pr> inline
4056		_IF_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
4057		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4058		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4059		return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4060		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4061		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4062		}
4063
4064		template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
4065		inline
4066		_OutElem* set_intersection(_InIt1 _First1, _InIt1 _Last1,
4067		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
4068		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4069		return (set_intersection(_First1, _Last1, _First2, _Last2,
4070		_STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
4071		}
4072
4073		template<class _InIt1,
4074		class _InIt2,
4075		class _OutIt,
4076		class _Pr> inline
4077		_SCL_INSECURE_DEPRECATE
4078		_IF_NOT_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
4079		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4080		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4081		return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4082		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4083		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4084		}
4085
4086		#else
4087
4088		template<class _InIt1,
4089		class _InIt2,
4090		class _OutIt,
4091		class _Pr> inline
4092		_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
4093		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4094		{    // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4095		return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4096		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4097		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4098		}
4099
4100		#endif
4101
4102		// TEMPLATE FUNCTION set_difference
4103		template<class _InIt1,
4104		class _InIt2,
4105		class _OutIt> inline
4106		_OutIt _Set_difference(_InIt1 _First1, _InIt1 _Last1,
4107		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
4108		{    // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4109		_DEBUG_ORDER(_First1, _Last1);
4110		_DEBUG_ORDER(_First2, _Last2);
4111		_DEBUG_POINTER(_Dest);
4112		for (; _First1 != _Last1 && _First2 != _Last2; )
4113		if (_DEBUG_LT(*_First1, *_First2))
4114		*_Dest++ = *_First1, ++_First1;
4115		else if (*_First2 < *_First1)
4116		++_First2;
4117		else
4118		++_First1, ++_First2;
4119		return (_STDEXT unchecked_copy(_First1, _Last1, _Dest));
4120		}
4121
4122		#if _SECURE_SCL
4123
4124		template<class _InIt1,
4125		class _InIt2,
4126		class _OutIt> inline
4127		_IF_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4128		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4129		{    // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4130		return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4131		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4132		_Dest, _STD _Range_checked_iterator_tag());
4133		}
4134
4135		template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
4136		inline
4137		_OutElem* set_difference(_InIt1 _First1, _InIt1 _Last1,
4138		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
4139		{    // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4140		return (set_difference(_First1, _Last1, _First2, _Last2,
4141		_STDEXT make_checked_array_iterator(_Dest, _Size)).base());
4142		}
4143
4144		template<class _InIt1,
4145		class _InIt2,
4146		class _OutIt> inline
4147		_SCL_INSECURE_DEPRECATE
4148		_IF_NOT_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4149		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4150		{    // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4151		return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4152		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4153		_Dest, _STD _Range_checked_iterator_tag());
4154		}
4155
4156		#else
4157
4158		template<class _InIt1,
4159		class _InIt2,
4160		class _OutIt> inline
4161		_OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
4162		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4163		{    // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4164		return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4165		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4166		_Dest, _STD _Range_checked_iterator_tag());
4167		}
4168
4169		#endif
4170
4171		// TEMPLATE FUNCTION set_difference WITH PRED
4172		template<class _InIt1,
4173		class _InIt2,
4174		class _OutIt,
4175		class _Pr> inline
4176		_OutIt _Set_difference(_InIt1 _First1, _InIt1 _Last1,
4177		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
4178		{    //  take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4179		_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
4180		_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
4181		_DEBUG_POINTER(_Dest);
4182		for (; _First1 != _Last1 && _First2 != _Last2; )
4183		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
4184		*_Dest++ = *_First1, ++_First1;
4185		else if (_Pred(*_First2, *_First1))
4186		++_First2;
4187		else
4188		++_First1, ++_First2;
4189		return (_STDEXT unchecked_copy(_First1, _Last1, _Dest));
4190		}
4191
4192		#if _SECURE_SCL
4193
4194		template<class _InIt1,
4195		class _InIt2,
4196		class _OutIt,
4197		class _Pr> inline
4198		_IF_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4199		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4200		{    //  take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4201		return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4202		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4203		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4204		}
4205
4206		template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
4207		inline
4208		_OutElem* set_difference(_InIt1 _First1, _InIt1 _Last1,
4209		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
4210		{    //  take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4211		return (set_difference(_First1, _Last1, _First2, _Last2,
4212		_STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
4213		}
4214
4215		template<class _InIt1,
4216		class _InIt2,
4217		class _OutIt,
4218		class _Pr> inline
4219		_SCL_INSECURE_DEPRECATE
4220		_IF_NOT_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4221		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4222		{    //  take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4223		return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4224		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4225		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4226		}
4227
4228		#else
4229
4230		template<class _InIt1,
4231		class _InIt2,
4232		class _OutIt,
4233		class _Pr> inline
4234		_OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
4235		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4236		{    //  take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4237		return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4238		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4239		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4240		}
4241
4242		#endif
4243
4244		// TEMPLATE FUNCTION set_symmetric_difference
4245		template<class _InIt1,
4246		class _InIt2,
4247		class _OutIt> inline
4248		_OutIt _Set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4249		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
4250		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4251		_DEBUG_ORDER(_First1, _Last1);
4252		_DEBUG_ORDER(_First2, _Last2);
4253		_DEBUG_POINTER(_Dest);
4254		for (; _First1 != _Last1 && _First2 != _Last2; )
4255		if (_DEBUG_LT(*_First1, *_First2))
4256		*_Dest++ = *_First1, ++_First1;
4257		else if (*_First2 < *_First1)
4258		*_Dest++ = *_First2, ++_First2;
4259		else
4260		++_First1, ++_First2;
4261		_Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
4262		return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
4263		}
4264
4265		#if _SECURE_SCL
4266
4267		template<class _InIt1,
4268		class _InIt2,
4269		class _OutIt> inline
4270		_IF_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4271		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4272		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4273		return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4274		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4275		_Dest, _STD _Range_checked_iterator_tag());
4276		}
4277
4278		template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
4279		inline
4280		_OutElem* set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4281		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
4282		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4283		return (set_symmetric_difference(_First1, _Last1, _First2, _Last2,
4284		_STDEXT make_checked_array_iterator(_Dest, _Size)).base());
4285		}
4286
4287		template<class _InIt1,
4288		class _InIt2,
4289		class _OutIt> inline
4290		_SCL_INSECURE_DEPRECATE
4291		_IF_NOT_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4292		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4293		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4294		return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4295		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4296		_Dest, _STD _Range_checked_iterator_tag());
4297		}
4298
4299		#else
4300
4301		template<class _InIt1,
4302		class _InIt2,
4303		class _OutIt> inline
4304		_OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4305		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4306		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4307		return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4308		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4309		_Dest, _STD _Range_checked_iterator_tag());
4310		}
4311
4312		#endif
4313
4314		// TEMPLATE FUNCTION set_symmetric_difference WITH PRED
4315		template<class _InIt1,
4316		class _InIt2,
4317		class _OutIt,
4318		class _Pr> inline
4319		_OutIt _Set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4320		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
4321		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4322		_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
4323		_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
4324		_DEBUG_POINTER(_Dest);
4325		for (; _First1 != _Last1 && _First2 != _Last2; )
4326		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
4327		*_Dest++ = *_First1, ++_First1;
4328		else if (_Pred(*_First2, *_First1))
4329		*_Dest++ = *_First2, ++_First2;
4330		else
4331		++_First1, ++_First2;
4332		_Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
4333		return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
4334		}
4335
4336		#if _SECURE_SCL
4337
4338		template<class _InIt1,
4339		class _InIt2,
4340		class _OutIt,
4341		class _Pr> inline
4342		_IF_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4343		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4344		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4345		return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4346		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4347		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4348		}
4349
4350		template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
4351		inline
4352		_OutElem* set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4353		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
4354		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4355		return (set_symmetric_difference(_First1, _Last1, _First2, _Last2,
4356		_STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
4357		}
4358
4359		template<class _InIt1,
4360		class _InIt2,
4361		class _OutIt,
4362		class _Pr> inline
4363		_SCL_INSECURE_DEPRECATE
4364		_IF_NOT_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4365		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4366		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4367		return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4368		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4369		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4370		}
4371
4372		#else
4373
4374		template<class _InIt1,
4375		class _InIt2,
4376		class _OutIt,
4377		class _Pr> inline
4378		_OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4379		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4380		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4381		return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4382		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4383		_Dest, _Pred, _STD _Range_checked_iterator_tag());
4384		}
4385
4386		#endif

Lines 4387 ... 5612 are skipped.

5613		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5614		_Dest, _STD _Range_checked_iterator_tag());
5615		}
5616
5617		template<class _InIt1,
5618		class _InIt2,
5619		class _OutIt,
5620		class _Pr> inline
5621		_OutIt unchecked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5622		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5623		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5624		return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest, _Pred,
5625		_STD _Range_checked_iterator_tag());
5626		}
5627
5628		template<class _InIt1,
5629		class _InIt2,
5630		class _OutIt,
5631		class _Pr> inline
5632		_IF_CHK(_OutIt) checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5633		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5634		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5635		return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5636		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5637		_Dest, _Pred, _STD _Range_checked_iterator_tag());
5638		}
5639
5640		template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
5641		inline
5642		_OutElem* checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5643		_InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
5644		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5645		return (checked_set_symmetric_difference(_First1, _Last1, _First2, _Last2,
5646		_STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
5647		}
5648
5649		template<class _InIt1,
5650		class _InIt2,
5651		class _OutIt,
5652		class _Pr> inline
5653		_SCL_CHECKED_ALGORITHM_WARN
5654		_IF_NOT_CHK(_OutIt) checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5655		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5656		{    // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5657		return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5658		_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5659		_Dest, _Pred, _STD _Range_checked_iterator_tag());
5660		}
5661
5662		#if _HAS_TRADITIONAL_STL
5663		// TEMPLATE FUNCTION count
5664		template<class _InIt,
5665		class _Ty,
5666		class _Diff> inline
5667		void count(_InIt _First, _InIt _Last, const _Ty& _Val, _Diff &_Ans)
5668		{    // count elements that match _Val
5669		_DEBUG_RANGE(_First, _Last);
5670		_Diff _Count = 0;
5671
5672		for (; _First != _Last; ++_First)
5673		if (*_First == _Val)
5674		++_Count;
5675		_Ans = _Count;
5676		}
5677
5678		// TEMPLATE FUNCTION count_if
5679		template<class _InIt,
5680		class _Pr,
5681		class _Diff> inline
5682		void count_if(_InIt _First, _InIt _Last, _Pr _Pred, _Diff &_Ans)
5683		{    // count elements satisfying _Pred
5684		_DEBUG_RANGE(_First, _Last);
5685		_DEBUG_POINTER(_Pred);
5686		_Diff _Count = 0;
5687
5688		for (; _First != _Last; ++_First)
5689		if (_Pred(*_First))
5690		++_Count;
5691		_Ans = _Count;
5692		}
5693
5694		// TEMPLATE FUNCTION is_heap
5695		template<class _RanIt,
5696		class _Diff> inline
5697		bool _Is_heap(_RanIt _First, _RanIt _Last, _Diff *)
5698		{    // test if range is a heap ordered by operator<
5699		_DEBUG_RANGE(_First, _Last);
5700		_Diff _Size = _Last - _First;
5701
5702		if (2 <= _Size)
5703		for (_Diff _Off = 0; ++_Off < _Size; )
5704		if (_DEBUG_LT(*(_First + (_Off - 1) / 2), *(_First + _Off)))
5705		return (false);
5706		return (true);
5707		}
5708
5709		template<class _RanIt>
5710		bool is_heap(_RanIt _First, _RanIt _Last)
5711		{    // test if range is a heap ordered by operator<
5712		return (_Is_heap(_First, _Last, _Dist_type(_First)));
5713		}
5714
5715		// TEMPLATE FUNCTION is_heap WITH PRED
5716		template<class _RanIt,
5717		class _Diff,
5718		class _Pr> inline
5719		bool _Is_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *)
5720		{    // test if range is a heap ordered by _Pred
5721		_DEBUG_RANGE(_First, _Last);
5722		_DEBUG_POINTER(_Pred);
5723		_Diff _Size = _Last - _First;
5724
5725		if (2 <= _Size)
5726		for (_Diff _Off = 0; ++_Off < _Size; )
5727		if (_DEBUG_LT_PRED(_Pred, *(_First + (_Off - 1) / 2),
5728		*(_First + _Off)))
5729		return (false);
5730		return (true);
5731		}
5732
5733		template<class _RanIt,
5734		class _Pr>
5735		bool is_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
5736		{    // test if range is a heap ordered by _Pred
5737		return (_Is_heap(_First, _Last, _Pred, _Dist_type(_First)));
5738		}
5739
5740		// TEMPLATE FUNCTION is_sorted
5741		template<class _FwdIt> inline
5742		bool is_sorted(_FwdIt _First, _FwdIt _Last)
5743		{    // test is range is ordered by operator<
5744		_DEBUG_RANGE(_First, _Last);
5745		for (_FwdIt _Next = _First; _First != _Last && ++_Next != _Last; ++_First)
5746		if (_DEBUG_LT(*_Next, *_First))
5747		return (false);
5748		return (true);
5749		}
5750
5751		// TEMPLATE FUNCTION is_sorted WITH PRED
5752		template<class _FwdIt,
5753		class _Pr> inline
5754		bool is_sorted(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
5755		{    // test if range is ordered by predicate, forward iterators
5756		_DEBUG_RANGE(_First, _Last);
5757		_DEBUG_POINTER(_Pred);
5758		for (_FwdIt _Next = _First; _First != _Last && ++_Next != _Last; ++_First)
5759		if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
5760		return (false);
5761		return (true);
5762		}
5763		#endif /* _HAS_TRADITIONAL_STL */
5764
5765		_STDEXT_END
5766
5767		#pragma warning(default: 4244)
5768
5769		#ifdef _MSC_VER
5770		#pragma warning(pop)
5771		#pragma pack(pop)
5772		#endif  /* _MSC_VER */
5773
5774		#endif /* RC_INVOKED */
5775		#endif /* _ALGORITHM_ */
5776
5777		/*
5778		* This file is derived from software bearing the following
5779		* restrictions:
5780		*
5781		* Copyright (c) 1994
5782		* Hewlett-Packard Company
5783		*
5784		* Permission to use, copy, modify, distribute and sell this
5785		* software and its documentation for any purpose is hereby
5786		* granted without fee, provided that the above copyright notice
5787		* appear in all copies and that both that copyright notice and
5788		* this permission notice appear in supporting documentation.
5789		* Hewlett-Packard Company makes no representations about the
5790		* suitability of this software for any purpose. It is provided
5791		* "as is" without express or implied warranty.
5792		*/
5793
5794		/*
5795		* Copyright (c) 1992-2008 by P.J. Plauger.  ALL RIGHTS RESERVED.
5796		* Consult your license regarding permissions and restrictions.
5797		V5.05:0009 */
5798
5799
5800