// algorithm standard header
#pragma once
#ifndef _ALGORITHM_
#define _ALGORITHM_
#ifndef RC_INVOKED
#include <xmemory>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)
 #pragma push_macro("new")
 #undef new
 #pragma warning(disable: 4244 28309 28285)

_STD_BEGIN
		// COMMON SORT PARAMETERS
const int _ISORT_MAX = 32;	// maximum size for insertion sort

template<class _Iter1,
	class _Iter2,
	class _UIter1,
	class _UIter2> inline
	pair<_Iter1, _Iter2>
		_Rechecked_both(_Iter1 _Dest1, _Iter2 _Dest2, pair<_UIter1, _UIter2> _Src)
	{	// reset checked from unchecked, generic
	return (pair<_Iter1, _Iter2>(
		_Rechecked(_Dest1, _Src.first),
		_Rechecked(_Dest2, _Src.second)
		));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _Iter1,
	class _Iter2> inline
	pair<_UNCHECKED_TYPE(_Iter1), _UNCHECKED_TYPE(_Iter2)>
		_Unchecked_both(pair<_Iter1, _Iter2> _Src)
	{	// unchecks iterators in a pair (for _ITERATOR_DEBUG_ARRAY_OVERLOADS)
	return (pair<_UNCHECKED_TYPE(_Iter1), _UNCHECKED_TYPE(_Iter2)>(
		_Unchecked(_Src.first),
		_Unchecked(_Src.second)));
	}

template<class _Iter1,
	class _Iter2> inline
	pair<_UNCHECKED_TYPE(_Iter1), _Iter2>
		_Unchecked_first(pair<_Iter1, _Iter2> _Src)
	{	// unchecks first in a pair (for _ITERATOR_DEBUG_ARRAY_OVERLOADS)
	return (pair<_UNCHECKED_TYPE(_Iter1), _Iter2>(
		_Unchecked(_Src.first),
		_Src.second));
	}

template<class _Iter1,
	class _Iter2> inline
	pair<_Iter1, _UNCHECKED_TYPE(_Iter2)>
		_Unchecked_second(pair<_Iter1, _Iter2> _Src)
	{	// unchecks second in a pair (for _ITERATOR_DEBUG_ARRAY_OVERLOADS)
	return (pair<_Iter1, _UNCHECKED_TYPE(_Iter2)>(
		_Src.first,
		_Unchecked(_Src.second)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION for_each
template<class _InIt,
	class _Fn1> inline
	void _For_each_unchecked(_InIt _First, _InIt _Last, _Fn1& _Func)
	{	// perform function for each element
	for (; _First != _Last; ++_First)
		_Func(*_First);
	}

template<class _InIt,
	class _Fn1> inline
	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
	{	// perform function for each element
	_DEBUG_RANGE_PTR(_First, _Last, _Func);
	_For_each_unchecked(_Unchecked(_First), _Unchecked(_Last), _Func);
	return (_Func);
	}

		// TEMPLATE FUNCTION find_if
template<class _InIt,
	class _Pr> inline
	_InIt _Find_if_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
	{	// find first satisfying _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			break;
	return (_First);
	}

template<class _InIt,
	class _Pr> inline
	_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// find first satisfying _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_First,
		_Find_if_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION adjacent_find WITH PRED
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Adjacent_find_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// find first satisfying _Pred with successor
	if (_First != _Last)
		for (_FwdIt _Firstb; (void)(_Firstb = _First), ++_First != _Last; )
			if (_Pred(*_Firstb, *_First))
				return (_Firstb);
	return (_Last);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find first satisfying _Pred with successor
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER_IF(_First != _Last && _STD next(_First) != _Last, _Pred);
	return (_Rechecked(_First,
		_Adjacent_find_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION adjacent_find
template<class _FwdIt> inline
	_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)
	{	// find first matching successor
	return (_STD adjacent_find(_First, _Last, equal_to<>()));
	}

		// TEMPLATE FUNCTION count_if
template<class _InIt,
	class _Pr> inline
	typename iterator_traits<_InIt>::difference_type
		_Count_if_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
	{	// count elements satisfying _Pred
	typename iterator_traits<_InIt>::difference_type _Count = 0;

	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			++_Count;
	return (_Count);
	}

template<class _InIt,
	class _Pr> inline
	typename iterator_traits<_InIt>::difference_type
		count_if(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// count elements satisfying _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Count_if_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION mismatch WITH PRED
template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	pair<_InIt1, _InIt2>
		_Mismatch_unchecked(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2, _Pr& _Pred)
	{	// return [_First1, _Last1)/[_First2, ...) mismatch using _Pred
	for (; _First1 != _Last1 && _Pred(*_First1, *_First2); )
		{	// point past match
		++_First1;
		++_First2;
		}

	return (pair<_InIt1, _InIt2>(_First1, _First2));
	}

template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	auto _Mismatch_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _Pr& _Pred, input_iterator_tag, input_iterator_tag)
			-> pair<_InIt1, decltype(_Unchecked_idl0(_First2))>
	{	// return [_First1, _Last1)/[_First2, ...) mismatch, input iterators, no deprecation warnings
	return (_Mismatch_unchecked(_First1, _Last1,
		_Unchecked_idl0(_First2), _Pred));
	}

template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	pair<_InIt1, _UNCHECKED_TYPE(_InIt2)>
		_Mismatch_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2, _Pr& _Pred, random_access_iterator_tag, random_access_iterator_tag)
	{	// return [_First1, _Last1)/[_First2, ...) mismatch; random-access iterators, no deprecation warnings
	_CHECK_RANIT_RANGE(_First1, _Last1, _First2);
	return (_Mismatch_unchecked(_First1, _Last1, _Unchecked(_First2), _Pred));
	}

template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	pair<_InIt1, _InIt2>
		_Mismatch_no_deprecate(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2, _Pr& _Pred)
	{	// return [_First1, _Last1)/[_First2, ...) mismatch using _Pred, no deprecation warnings
	_DEBUG_RANGE_PTR(_First1, _Last1, _First2);
	_DEBUG_POINTER_IF(_First1 != _Last1, _Pred);
	return (_Rechecked_both(_First1, _First2,
		_Mismatch_no_deprecate1(_Unchecked(_First1), _Unchecked(_Last1),
			_First2, _Pred, _Iter_cat_t<_InIt1>(), _Iter_cat_t<_InIt2>())));
	}

template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	pair<_InIt1, _InIt2>
		mismatch(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2, _Pr _Pred)
	{	// return [_First1, _Last1)/[_First2, ...) mismatch using _Pred
	_DEPRECATE_UNCHECKED(mismatch, _First2);
	return (_Mismatch_no_deprecate(_First1, _Last1, _First2, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InTy,
	size_t _InSize,
	class _Pr,
	class = enable_if_t<!is_same<_InTy *, _Pr>::value>> inline
	pair<_InIt1, _InTy *>
		mismatch(_InIt1 _First1, _InIt1 _Last1,
			_InTy (&_First2)[_InSize], _Pr _Pred)
	{	// return [_First1, _Last1)/[_First2, ...) mismatch using _Pred
	return (_Unchecked_second(_Mismatch_no_deprecate(_First1, _Last1,
		_Array_iterator<_InTy, _InSize>(_First2), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION mismatch
template<class _InIt1,
	class _InIt2> inline
	pair<_InIt1, _InIt2>
		mismatch(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2)
	{	// return [_First1, _Last1)/[_First2, ...) mismatch
	return (_STD mismatch(_First1, _Last1, _First2,
		equal_to<>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InTy,
	size_t _InSize> inline
	pair<_InIt1, _InTy *>
		mismatch(_InIt1 _First1, _InIt1 _Last1,
			_InTy (&_First2)[_InSize])
	{	// return [_First1, _Last1)/[_First2, ...) mismatch, array input
	return (_STD mismatch(_First1, _Last1, _First2,
		equal_to<>()));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION mismatch WITH TWO RANGES, PRED
template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	pair<_InIt1, _InIt2>
		_Mismatch_unchecked(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2, _InIt2 _Last2, _Pr& _Pred)
	{	// return [_First1, _Last1)/[_First2, _Last2) mismatch using _Pred
	for (; _First1 != _Last1 && _First2 != _Last2
		&& _Pred(*_First1, *_First2); )
		{	// point past match
		++_First1;
		++_First2;
		}

	return (pair<_InIt1, _InIt2>(_First1, _First2));
	}

template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	pair<_InIt1, _InIt2>
		mismatch(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
	{	// return [_First1, _Last1)/[_First2, _Last2) mismatch using _Pred
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_RANGE(_First2, _Last2);
	_DEBUG_POINTER_IF(_First1 != _Last1 && _First2 != _Last2, _Pred);
	return (_Rechecked_both(_First1, _First2,
		_Mismatch_unchecked(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2), _Pred)));
	}

		// TEMPLATE FUNCTION mismatch WITH TWO RANGES
template<class _InIt1,
	class _InIt2> inline
	pair<_InIt1, _InIt2>
		mismatch(_InIt1 _First1, _InIt1 _Last1,
			_InIt2 _First2, _InIt2 _Last2)
	{	// return [_First1, _Last1)/[_First2, _Last2) mismatch
	return (_STD mismatch(_First1, _Last1, _First2, _Last2,
		equal_to<>()));
	}

		// TEMPLATE FUNCTION all_of
template<class _InIt,
	class _Pr> inline
	bool _All_of_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
	{	// test if all elements satisfy _Pred
	for (; _First != _Last; ++_First)
		if (!_Pred(*_First))
			return (false);
	return (true);
	}

template<class _InIt,
	class _Pr> inline
	bool all_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if all elements satisfy _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_All_of_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION any_of
template<class _InIt,
	class _Pr> inline
	bool _Any_of_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
	{	// test if any element satisfies _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			return (true);
	return (false);
	}

template<class _InIt,
	class _Pr> inline
	bool any_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if any element satisfies _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Any_of_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION none_of
template<class _InIt,
	class _Pr> inline
	bool _None_of_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
	{	// test if no elements satisfy _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			return (false);
	return (true);
	}

template<class _InIt,
	class _Pr> inline
	bool none_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if no elements satisfy _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_None_of_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION find_if_not
template<class _InIt,
	class _Pr> inline
	_InIt _Find_if_not_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
	{	// find first element that satisfies !_Pred
	for (; _First != _Last; ++_First)
		if (!_Pred(*_First))
			break;
	return (_First);
	}

template<class _InIt,
	class _Pr> inline
	_InIt find_if_not(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// find first element that satisfies !_Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_First,
		_Find_if_not_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION copy_if
template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Copy_if_unchecked(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr& _Pred)
	{	// copy each satisfying _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			{	// validate _Dest and copy
			_DEBUG_POINTER(_Dest);
			*_Dest++ = *_First;
			}

	return (_Dest);
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Copy_if_no_deprecate(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr& _Pred)
	{	// copy each satisfying _Pred, no deprecation warnings
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_Dest,
		_Copy_if_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Unchecked_idl0(_Dest), _Pred)));
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr _Pred)
	{	// copy each satisfying _Pred
	_DEPRECATE_UNCHECKED(copy_if, _Dest);
	return (_Copy_if_no_deprecate(_First, _Last, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *copy_if(_InIt _First, _InIt _Last, _OutTy (&_Dest)[_OutSize],
		_Pr _Pred)
	{	// copy each satisfying _Pred, array dest
	return (_Unchecked(
		_Copy_if_no_deprecate(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION partition_copy
template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
	pair<_OutIt1, _OutIt2>
		_Partition_copy_unchecked(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr& _Pred)
	{	// copy true partition to _Dest1, false to _Dest2
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			{	// validate _Dest1 and store
			_DEBUG_POINTER(_Dest1);
			*_Dest1++ = *_First;
			}
		else
			{	// validate _Dest2 and store
			_DEBUG_POINTER(_Dest2);
			*_Dest2++ = *_First;
			}

	return (pair<_OutIt1, _OutIt2>(_Dest1, _Dest2));
	}

template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
	pair<_OutIt1, _OutIt2>
		_Partition_copy_no_deprecate(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr& _Pred)
	{	// copy true partition to _Dest1, false to _Dest2, no deprecation warnings
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked_both(_Dest1, _Dest2,
		_Partition_copy_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Unchecked_idl0(_Dest1), _Unchecked_idl0(_Dest2), _Pred)));
	}

template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
	pair<_OutIt1, _OutIt2>
		partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred)
	{	// copy true partition to _Dest1, false to _Dest2
	_DEFINE_DEPRECATE_UNCHECKED(partition_copy);
	_USE_DEPRECATE_UNCHECKED(_Dest1);
	_USE_DEPRECATE_UNCHECKED(_Dest2);
	return (_Partition_copy_no_deprecate(_First, _Last, _Dest1, _Dest2, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy1,
	size_t _OutSize1,
	class _OutIt2,
	class _Pr> inline
	pair<_OutTy1 *, _OutIt2>
		partition_copy(_InIt _First, _InIt _Last,
			_OutTy1 (&_Dest1)[_OutSize1], _OutIt2 _Dest2, _Pr _Pred)
	{	// copy true partition to _Dest1, false to _Dest2, array dest
	_DEPRECATE_UNCHECKED(partition_copy, _Dest2);
	return (_Unchecked_first(
		_Partition_copy_no_deprecate(_First, _Last,
			_Array_iterator<_OutTy1, _OutSize1>(_Dest1), _Dest2, _Pred)));
	}

template<class _InIt,
	class _OutIt1,
	class _OutTy2,
	size_t _OutSize2,
	class _Pr> inline
	pair<_OutIt1, _OutTy2 *>
		partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutTy2 (&_Dest2)[_OutSize2], _Pr _Pred)
	{	// copy true partition to _Dest1, false to _Dest2, array dest
	_DEPRECATE_UNCHECKED(partition_copy, _Dest1);
	return (_Unchecked_second(
		_Partition_copy_no_deprecate(_First, _Last,
			_Dest1, _Array_iterator<_OutTy2, _OutSize2>(_Dest2), _Pred)));
	}

template<class _InIt,
	class _OutTy1,
	size_t _OutSize1,
	class _OutTy2,
	size_t _OutSize2,
	class _Pr> inline
	pair<_OutTy1 *, _OutTy2 *>
		partition_copy(_InIt _First, _InIt _Last,
			_OutTy1 (&_Dest1)[_OutSize1], _OutTy2 (&_Dest2)[_OutSize2],
			_Pr _Pred)
	{	// copy true partition to _Dest1, false to _Dest2, array dest
	return (_Unchecked_both(
		_Partition_copy_no_deprecate(_First, _Last,
				_Array_iterator<_OutTy1, _OutSize1>(_Dest1),
				_Array_iterator<_OutTy2, _OutSize2>(_Dest2), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION is_partitioned
template<class _InIt,
	class _Pr> inline
	bool _Is_partitioned_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
	{	// test if [_First, _Last) partitioned by _Pred
	for (; _First != _Last; ++_First)
		if (!_Pred(*_First))
			break;	// skip true partition
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			return (false);	// found out of place element
	return (true);
	}

template<class _InIt,
	class _Pr> inline
	bool is_partitioned(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if [_First, _Last) partitioned by _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Is_partitioned_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Pred));
	}

		// TEMPLATE FUNCTION partition_point
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Partition_point_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// find beginning of false partition in [_First, _Last)
	_Iter_diff_t<_FwdIt> _Count = _STD distance(_First, _Last);
	while (0 < _Count)
		{	// divide and conquer, find half that contains answer
		_Iter_diff_t<_FwdIt> _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		_STD advance(_Mid, _Count2);

		if (_Pred(*_Mid))
			{	// try top half
			_First = ++_Mid;
			_Count -= _Count2 + 1;
			}
		else
			_Count = _Count2;
		}

	return (_First);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt partition_point(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find beginning of false partition in [_First, _Last)
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_First,
		_Partition_point_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION search WITH PRED
template<class _FwdIt1,
	class _FwdIt2,
	class _Pr> inline
	_FwdIt1 _Search_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred,
		forward_iterator_tag, forward_iterator_tag)
	{	// find first [_First2, _Last2) satisfying _Pred, arbitrary iterators
	for (; ; ++_First1)
		{	// loop until match or end of a sequence
		_FwdIt1 _Mid1 = _First1;
		for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, (void)++_Mid2)
			if (_Mid2 == _Last2)
				return (_First1);
			else if (_Mid1 == _Last1)
				return (_Last1);
			else if (!_Pred(*_Mid1, *_Mid2))
				break;
		}
	}

template<class _FwdIt1,
	class _FwdIt2,
	class _Pr> inline
	_FwdIt1 _Search_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// find first [_First2, _Last2) satisfying _Pred, random-access iterators
	_Iter_diff_t<_FwdIt1> _Count1 = _Last1 - _First1;
	_Iter_diff_t<_FwdIt2> _Count2 = _Last2 - _First2;

	for (; _Count2 <= _Count1; ++_First1, (void)--_Count1)
		{	// room for match, try it
		_FwdIt1 _Mid1 = _First1;
		for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, (void)++_Mid2)
			if (_Mid2 == _Last2)
				return (_First1);
			else if (!_Pred(*_Mid1, *_Mid2))
				break;
		}

	return (_Last1);
	}

template<class _FwdIt1,
	class _FwdIt2,
	class _Pr> inline
	_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
	{	// find first [_First2, _Last2) satisfying _Pred
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_RANGE(_First2, _Last2);
	_DEBUG_POINTER_IF(_First1 != _Last1 && _First2 != _Last2, _Pred);
	return (_Rechecked(_First1,
		_Search_unchecked(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2), _Pred,
			_Iter_cat_t<_FwdIt1>(), _Iter_cat_t<_FwdIt2>())));
	}

		// TEMPLATE FUNCTION search
template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2)
	{	// find first [_First2, _Last2) match
	return (_STD search(_First1, _Last1, _First2, _Last2,
		equal_to<>()));
	}

		// TEMPLATE FUNCTION search_n WITH PRED
template<class _FwdIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	_FwdIt _Search_n_unchecked(_FwdIt _First, _FwdIt _Last,
		_Diff _Count, const _Ty& _Val, _Pr& _Pred, forward_iterator_tag)
	{	// find first _Count * _Val satisfying _Pred, forward iterators
	if (_Count <= 0)
		return (_First);

	for (; _First != _Last; ++_First)
		if (_Pred(*_First, _Val))
			{	// found start of possible match, check it out
			_FwdIt _Mid = _First;

			for (_Diff _Count1 = _Count; ; )
				if (--_Count1 == 0)
					return (_First);	// found rest of match, report it
				else if (++_Mid == _Last)
					return (_Last);	// short match at end
				else if (!_Pred(*_Mid, _Val))
					{	// short match not at end
					break;
					}

			_First = _Mid;	// pick up just beyond failed match
			}

	return (_Last);
	}

template<class _FwdIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	_FwdIt _Search_n_unchecked(_FwdIt _First, _FwdIt _Last,
		_Diff _Count, const _Ty& _Val, _Pr& _Pred, random_access_iterator_tag)
	{	// find first _Count * _Val satisfying _Pred, random-access iterators
	if (_Count <= 0)
		return (_First);

	_FwdIt _Oldfirst = _First;
	for (_Diff _Inc = 0; _Count <= _Last - _Oldfirst; )
		{	// enough room, look for a match
		_First = _Oldfirst + _Inc;
		if (_Pred(*_First, _Val))
			{	// found part of possible match, check it out
			_Diff _Count1 = _Count;
			_FwdIt _Mid = _First;

			for (; _Oldfirst != _First && _Pred(_First[-1], _Val);
				--_First)
				--_Count1;	// back up over any skipped prefix

			if (_Count1 <= _Last - _Mid)
				for (; ; )
					{	// enough left, test suffix
					if (--_Count1 == 0)
						return (_First);	// found rest of match, report it
					else if (!_Pred(*++_Mid, _Val))
						{	// short match not at end
						break;
						}
					}
			_Oldfirst = ++_Mid;	// failed match, take small jump
			_Inc = 0;
			}
		else
			{	// no match, take big jump and back up as needed
			_Oldfirst = _First + 1;
			_Inc = _Count - 1;
			}
		}

	return (_Last);
	}

template<class _FwdIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	_FwdIt search_n(_FwdIt _First, _FwdIt _Last,
		_Diff _Count, const _Ty& _Val, _Pr _Pred)
	{	// find first _Count * _Val satisfying _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_First,
		_Search_n_unchecked(_Unchecked(_First), _Unchecked(_Last), _Count, _Val,
			_Pred, _Iter_cat_t<_FwdIt>())));
	}

		// TEMPLATE FUNCTION search_n
template<class _FwdIt,
	class _Diff,
	class _Ty> inline
	_FwdIt search_n(_FwdIt _First, _FwdIt _Last,
		_Diff _Count, const _Ty& _Val)
	{	// find first _Count * _Val match
	return (_STD search_n(_First, _Last, _Count, _Val,
		equal_to<>()));
	}

		// TEMPLATE FUNCTION find_end WITH PRED
template<class _FwdIt1,
	class _FwdIt2,
	class _Pr> inline
	_FwdIt1 _Find_end_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred)
	{	// find last [_First2, _Last2) satisfying _Pred
	_Iter_diff_t<_FwdIt1> _Count1 = _STD distance(_First1, _Last1);
	_Iter_diff_t<_FwdIt2> _Count2 = _STD distance(_First2, _Last2);
	_FwdIt1 _Ans = _Last1;

	if (0 < _Count2)
		{	// validate _Pred and test
		_DEBUG_POINTER_IF(_Count2 <= _Count1, _Pred);
		for (; _Count2 <= _Count1; ++_First1, (void)--_Count1)
			{	// room for match, try it
			_FwdIt1 _Mid1 = _First1;
			for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1)
				if (!_Pred(*_Mid1, *_Mid2))
					break;
				else if (++_Mid2 == _Last2)
					{	// potential answer, save it
					_Ans = _First1;
					break;
					}
			}
		}

	return (_Ans);
	}

template<class _FwdIt1,
	class _FwdIt2,
	class _Pr> inline
	_FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
	{	// find last [_First2, _Last2) satisfying _Pred
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_RANGE(_First2, _Last2);
	return (_Rechecked(_First1,
		_Find_end_unchecked(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2), _Pred)));
	}

		// TEMPLATE FUNCTION find_end
template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2)
	{	// find last [_First2, _Last2) match
	return (_STD find_end(_First1, _Last1, _First2, _Last2,
		equal_to<>()));
	}

		// TEMPLATE FUNCTION find_first_of WITH PRED
template<class _FwdIt1,
	class _FwdIt2,
	class _Pr> inline
	_FwdIt1 _Find_first_of_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred)
	{	// look for one of [_First2, _Last2) satisfying _Pred with element
	for (; _First1 != _Last1; ++_First1)
		for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
			if (_Pred(*_First1, *_Mid2))
				return (_First1);
	return (_First1);
	}

template<class _FwdIt1,
	class _FwdIt2,
	class _Pr> inline
	_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
	{	// look for one of [_First2, _Last2) satisfying _Pred with element
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_RANGE(_First2, _Last2);
	_DEBUG_POINTER_IF(_First1 != _Last1 && _First2 != _Last2, _Pred);
	return (_Rechecked(_First1,
		_Find_first_of_unchecked(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2), _Pred)));
	}

		// TEMPLATE FUNCTION find_first_of
template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2)
	{	// look for one of [_First2, _Last2) that matches element
	return (_STD find_first_of(_First1, _Last1, _First2, _Last2,
		equal_to<>()));
	}

		// TEMPLATE FUNCTION swap_ranges
template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt2 _Swap_ranges_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _Dest)
	{	// swap [_First1, _Last1) with [_Dest, ...)
	for (; _First1 != _Last1; ++_First1, (void)++_Dest)
		_STD iter_swap(_First1, _Dest);
	return (_Dest);
	}

template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt2 _Swap_ranges1(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _Dest,
		forward_iterator_tag, forward_iterator_tag)
	{	// swap [_First1, _Last1) with [_Dest, ...), arbitrary iterators
	return (_Rechecked(_Dest,
		_Swap_ranges_unchecked(_First1, _Last1, _Unchecked_idl0(_Dest))));
	}

template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt2 _Swap_ranges1(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _Dest,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// swap [_First1, _Last1) with [_Dest, ...), random-access iterators
	_CHECK_RANIT_RANGE(_First1, _Last1, _Dest);
	return (_Rechecked(_Dest,
		_Swap_ranges_unchecked(_First1, _Last1, _Unchecked(_Dest))));
	}

template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt2 swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _Dest)
	{	// swap [_First1, _Last1) with [_Dest, ...)
	_DEPRECATE_UNCHECKED(swap_ranges, _Dest);
	_DEBUG_RANGE_PTR(_First1, _Last1, _Dest);
	return (_Swap_ranges1(_Unchecked(_First1), _Unchecked(_Last1),
		_Dest, _Iter_cat_t<_FwdIt1>(), _Iter_cat_t<_FwdIt2>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _FwdIt1,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1,
		_OutTy (&_Dest)[_OutSize])
	{	// swap [_First1, _Last1) with [_Dest, ...), array dest
	return (_Unchecked(
		_STD swap_ranges(_First1, _Last1,
		_Array_iterator<_OutTy, _OutSize>(_Dest))));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION transform WITH UNARY OP
template<class _InIt,
	class _OutIt,
	class _Fn1> inline
	_OutIt _Transform_unchecked(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Fn1& _Func)
	{	// transform [_First, _Last) with _Func
	for (; _First != _Last; ++_First, (void)++_Dest)
		*_Dest = _Func(*_First);
	return (_Dest);
	}

template<class _InIt,
	class _OutIt,
	class _Fn1> inline
	_OutIt _Transform_no_deprecate1(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Fn1& _Func,
		input_iterator_tag, _Any_tag)
	{	// transform [_First, _Last) with _Func, arbitrary iterators, no deprecation warnings
	return (_Rechecked(_Dest,
		_Transform_unchecked(_First, _Last, _Unchecked_idl0(_Dest), _Func)));
	}

template<class _InIt,
	class _OutIt,
	class _Fn1> inline
	_OutIt _Transform_no_deprecate1(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Fn1& _Func,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// transform [_First, _Last) with _Func, random-access iterators, no deprecation warnings
	_CHECK_RANIT_RANGE(_First, _Last, _Dest);
	return (_Rechecked(_Dest,
		_Transform_unchecked(_First, _Last, _Unchecked(_Dest), _Func)));
	}

template<class _InIt,
	class _OutIt,
	class _Fn1> inline
	_OutIt _Transform_no_deprecate(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Fn1& _Func)
	{	// transform [_First, _Last) with _Func, no deprecation warnings
	_DEBUG_RANGE_PTR(_First, _Last, _Dest);
	_DEBUG_POINTER_IF(_First != _Last, _Func);
	return (_Transform_no_deprecate1(_Unchecked(_First), _Unchecked(_Last),
		_Dest, _Func, _Iter_cat_t<_InIt>(), _Iter_cat_t<_OutIt>()));
	}

template<class _InIt,
	class _OutIt,
	class _Fn1> inline
	_OutIt transform(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Fn1 _Func)
	{	// transform [_First, _Last) with _Func
	_DEPRECATE_UNCHECKED(transform, _Dest);
	return (_Transform_no_deprecate(_First, _Last, _Dest, _Func));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Fn1> inline
	_OutTy *transform(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize], _Fn1 _Func)
	{	// transform [_First, _Last) with _Func, array dest
	return (_Unchecked(
		_Transform_no_deprecate(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Func)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION transform WITH BINARY OP
template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
	_OutIt _Transform_unchecked(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2& _Func)
	{	// transform [_First1, _Last1) and [_First2, ...) with _Func
	for (; _First1 != _Last1; ++_First1, (void)++_First2, ++_Dest)
		*_Dest = _Func(*_First1, *_First2);
	return (_Dest);
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
	_OutIt _Transform_no_deprecate2(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2& _Func,
		input_iterator_tag, _Any_tag)
	{	// transform [_First1, _Last1) and [_First2, ...), arbitrary dest, no deprecation warnings
	return (_Rechecked(_Dest,
		_Transform_unchecked(_First1, _Last1, _First2, _Unchecked_idl0(_Dest), _Func)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
	_OutIt _Transform_no_deprecate2(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2& _Func,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// transform [_First1, _Last1) and [_First2, ...), random-access dest, no deprecation warnings
	_CHECK_RANIT_RANGE(_First1, _Last1, _Dest);
	return (_Rechecked(_Dest,
		_Transform_unchecked(_First1, _Last1, _First2, _Unchecked(_Dest), _Func)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
	_OutIt _Transform_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2& _Func,
		input_iterator_tag, input_iterator_tag)
	{	// transform [_First1, _Last1) and [_First2, ...), arbitrary input, no deprecation warnings
	return (_Transform_no_deprecate2(_First1, _Last1,
		_Unchecked_idl0(_First2), _Dest, _Func,
		_Iter_cat_t<_InIt1>(), _Iter_cat_t<_OutIt>()));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
	_OutIt _Transform_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2& _Func,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// transform [_First1, _Last1) and [_First2, ...), random-access input, no deprecation warnings
	_CHECK_RANIT_RANGE(_First1, _Last1, _First2);
	return (_Transform_no_deprecate2(_First1, _Last1,
		_Unchecked(_First2), _Dest, _Func,
		_Iter_cat_t<_InIt1>(), _Iter_cat_t<_OutIt>()));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
	_OutIt _Transform_no_deprecate(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2& _Func)
	{	// transform [_First1, _Last1) and [_First2, ...) with _Func, no deprecation warnings
	_DEBUG_RANGE_PTR(_First1, _Last1, _First2);
	_DEBUG_POINTER_IF(_First1 != _Last1, _Dest);
	_DEBUG_POINTER_IF(_First1 != _Last1, _Func);
	return (_Transform_no_deprecate1(_Unchecked(_First1), _Unchecked(_Last1),
		_First2, _Dest, _Func,
		_Iter_cat_t<_InIt1>(), _Iter_cat_t<_InIt2>()));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
	_OutIt transform(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
	{	// transform [_First1, _Last1) and [_First2, ...) with _Func
	_DEFINE_DEPRECATE_UNCHECKED(transform);
	_USE_DEPRECATE_UNCHECKED(_First2);
	_USE_DEPRECATE_UNCHECKED(_Dest);
	return (_Transform_no_deprecate(_First1, _Last1, _First2, _Dest, _Func));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InTy,
	size_t _InSize,
	class _OutIt,
	class _Fn2> inline
	_OutIt transform(_InIt1 _First1, _InIt1 _Last1,
		_InTy (&_First2)[_InSize], _OutIt _Dest, _Fn2 _Func)
	{	// transform [_First1, _Last1) and [_First2, ...), array input
	_DEPRECATE_UNCHECKED(transform, _Dest);
	return (_Transform_no_deprecate(_First1, _Last1,
		_Array_iterator<_InTy, _InSize>(_First2), _Dest, _Func));
	}

template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize,
	class _Fn2> inline
	_OutTy *transform(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutTy (&_Dest)[_OutSize], _Fn2 _Func)
	{	// transform [_First1, _Last1) and [_First2, ...), array dest
	_DEPRECATE_UNCHECKED(transform, _First2);
	return (_Unchecked(
		_Transform_no_deprecate(_First1, _Last1,
			_First2, _Array_iterator<_OutTy, _OutSize>(_Dest), _Func)));
	}

template<class _InIt1,
	class _InTy,
	size_t _InSize,
	class _OutTy,
	size_t _OutSize,
	class _Fn2> inline
	_OutTy *transform(_InIt1 _First1, _InIt1 _Last1,
		_InTy (&_First2)[_InSize], _OutTy (&_Dest)[_OutSize], _Fn2 _Func)
	{	// transform [_First1, _Last1) and [_First2, ...), array input/dest
	return (_Unchecked(
		_Transform_no_deprecate(_First1, _Last1,
			_Array_iterator<_InTy, _InSize>(_First2),
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Func)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION replace
template<class _FwdIt,
	class _Ty> inline
	void _Replace_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Oldval, const _Ty& _Newval)
	{	// replace each matching _Oldval with _Newval
	for (; _First != _Last; ++_First)
		if (*_First == _Oldval)
			*_First = _Newval;
	}

template<class _FwdIt,
	class _Ty> inline
	void replace(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Oldval, const _Ty& _Newval)
	{	// replace each matching _Oldval with _Newval
	_DEBUG_RANGE(_First, _Last);
	_Replace_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Oldval, _Newval);
	}

		// TEMPLATE FUNCTION replace_if
template<class _FwdIt,
	class _Pr,
	class _Ty> inline
	void _Replace_if_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred, const _Ty& _Val)
	{	// replace each satisfying _Pred with _Val
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			*_First = _Val;
	}

template<class _FwdIt,
	class _Pr,
	class _Ty> inline
	void replace_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred, const _Ty& _Val)
	{	// replace each satisfying _Pred with _Val
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	_Replace_if_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Pred, _Val);
	}

		// TEMPLATE FUNCTION replace_copy
template<class _InIt,
	class _OutIt,
	class _Ty> inline
	_OutIt _Replace_copy_unchecked(_InIt _First, _InIt _Last,
		_OutIt _Dest, const _Ty& _Oldval, const _Ty& _Newval)
	{	// copy replacing each matching _Oldval with _Newval
	for (; _First != _Last; ++_First, (void)++_Dest)
		*_Dest = *_First == _Oldval ? _Newval : *_First;
	return (_Dest);
	}

template<class _InIt,
	class _OutIt,
	class _Ty> inline
	_OutIt _Replace_copy1(_InIt _First, _InIt _Last,
		_OutIt _Dest, const _Ty& _Oldval, const _Ty& _Newval,
		input_iterator_tag, _Any_tag)
	{	// copy replacing each matching _Oldval, arbitrary iterators
	return (_Rechecked(_Dest,
		_Replace_copy_unchecked(_First, _Last, _Unchecked_idl0(_Dest),
		_Oldval, _Newval)));
	}

template<class _InIt,
	class _OutIt,
	class _Ty> inline
	_OutIt _Replace_copy1(_InIt _First, _InIt _Last,
		_OutIt _Dest, const _Ty& _Oldval, const _Ty& _Newval,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// copy replacing each matching _Oldval, random-access iterators
	_CHECK_RANIT_RANGE(_First, _Last, _Dest);
	return (_Rechecked(_Dest,
		_Replace_copy_unchecked(_First, _Last, _Unchecked(_Dest),
		_Oldval, _Newval)));
	}

template<class _InIt,
	class _OutIt,
	class _Ty> inline
	_OutIt replace_copy(_InIt _First, _InIt _Last,
		_OutIt _Dest, const _Ty& _Oldval, const _Ty& _Newval)
	{	// copy replacing each matching _Oldval with _Newval
	_DEPRECATE_UNCHECKED(replace_copy, _Dest);
	_DEBUG_RANGE_PTR(_First, _Last, _Dest);
	return (_Replace_copy1(_Unchecked(_First), _Unchecked(_Last),
		_Dest, _Oldval, _Newval,
		_Iter_cat_t<_InIt>(), _Iter_cat_t<_OutIt>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Ty> inline
	_OutTy *replace_copy(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize], const _Ty& _Oldval, const _Ty& _Newval)
	{	// copy replacing each matching _Oldval with _Newval, array dest
	return (_Unchecked(
		_STD replace_copy(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Oldval, _Newval)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION replace_copy_if
template<class _InIt,
	class _OutIt,
	class _Pr,
	class _Ty> inline
	_OutIt _Replace_copy_if_unchecked(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred, const _Ty& _Val)
	{	// copy replacing each satisfying _Pred with _Val
	for (; _First != _Last; ++_First, (void)++_Dest)
		*_Dest = _Pred(*_First) ? _Val : *_First;
	return (_Dest);
	}

template<class _InIt,
	class _OutIt,
	class _Pr,
	class _Ty> inline
	_OutIt _Replace_copy_if_no_deprecate1(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred, const _Ty& _Val,
		input_iterator_tag, _Any_tag)
	{	// copy replacing each satisfying _Pred, arbitrary iterators, no deprecation warnings
	return (_Rechecked(_Dest,
		_Replace_copy_if_unchecked(_First, _Last, _Unchecked_idl0(_Dest), _Pred, _Val)));
	}

template<class _InIt,
	class _OutIt,
	class _Pr,
	class _Ty> inline
	_OutIt _Replace_copy_if_no_deprecate1(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred, const _Ty& _Val,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// copy replacing each satisfying _Pred, random-access iterators, no deprecation warnings
	_CHECK_RANIT_RANGE(_First, _Last, _Dest);
	return (_Rechecked(_Dest,
		_Replace_copy_if_unchecked(_First, _Last, _Unchecked(_Dest), _Pred, _Val)));
	}

template<class _InIt,
	class _OutIt,
	class _Pr,
	class _Ty> inline
	_OutIt _Replace_copy_if_no_deprecate(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred, const _Ty& _Val)
	{	// copy replacing each satisfying _Pred with _Val, no deprecation warnings
	_DEBUG_RANGE_PTR(_First, _Last, _Dest);
	_DEBUG_POINTER_IF(_First != _Last, _Pred);
	return (_Replace_copy_if_no_deprecate1(_Unchecked(_First), _Unchecked(_Last),
		_Dest, _Pred, _Val,
		_Iter_cat_t<_InIt>(), _Iter_cat_t<_OutIt>()));
	}

template<class _InIt,
	class _OutIt,
	class _Pr,
	class _Ty> inline
	_OutIt replace_copy_if(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr _Pred, const _Ty& _Val)
	{	// copy replacing each satisfying _Pred with _Val
	_DEPRECATE_UNCHECKED(replace_copy_if, _Dest);
	return (_Replace_copy_if_no_deprecate(_First, _Last, _Dest, _Pred, _Val));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Pr,
	class _Ty> inline
	_OutTy *replace_copy_if(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize], _Pr _Pred, const _Ty& _Val)
	{	// copy replacing each satisfying _Pred with _Val, array dest
	return (_Unchecked(
		_Replace_copy_if_no_deprecate(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred, _Val)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION generate
template<class _FwdIt,
	class _Fn0> inline
	void _Generate_unchecked(_FwdIt _First, _FwdIt _Last, _Fn0& _Func)
	{	// replace [_First, _Last) with _Func()
	for (; _First != _Last; ++_First)
		*_First = _Func();
	}

template<class _FwdIt,
	class _Fn0> inline
	void generate(_FwdIt _First, _FwdIt _Last, _Fn0 _Func)
	{	// replace [_First, _Last) with _Func()
	_DEBUG_RANGE_PTR(_First, _Last, _Func);
	_Generate_unchecked(_Unchecked(_First), _Unchecked(_Last), _Func);
	}

		// TEMPLATE FUNCTION generate_n
template<class _OutIt,
	class _Diff,
	class _Fn0> inline
	_OutIt _Generate_n_unchecked(_OutIt _Dest, _Diff _Count, _Fn0& _Func)
	{	// replace [_Dest, _Dest + _Count) with _Func()
	for (; 0 < _Count; --_Count, (void)++_Dest)
		*_Dest = _Func();
	return (_Dest);
	}

template<class _OutIt,
	class _Diff,
	class _Fn0> inline
	_OutIt generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
	{	// replace [_Dest, _Dest + _Count) with _Func()
	return (_Rechecked(_Dest,
		_Generate_n_unchecked(_Unchecked_n(_Dest, _Count), _Count, _Func)));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _OutTy,
	size_t _OutSize,
	class _Diff,
	class _Fn0> inline
	_OutTy *generate_n(_OutTy (&_Dest)[_OutSize], _Diff _Count, _Fn0 _Func)
	{	// replace [_Dest, _Dest + _Count) with _Func(), array dest
	_DEBUG_ARRAY_SIZE(_Dest, _Count);
	return (_Generate_n_unchecked(_Dest, _Count, _Func));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION remove_copy
template<class _InIt,
	class _OutIt,
	class _Ty> inline
	_OutIt _Remove_copy_unchecked(_InIt _First, _InIt _Last,
		_OutIt _Dest, const _Ty& _Val)
	{	// copy omitting each matching _Val
	for (; _First != _Last; ++_First)
		if (!(*_First == _Val))
			{	// validate _Dest and store
			_DEBUG_POINTER(_Dest);
			*_Dest++ = *_First;
			}

	return (_Dest);
	}

template<class _InIt,
	class _OutIt,
	class _Ty> inline
	_OutIt remove_copy(_InIt _First, _InIt _Last,
		_OutIt _Dest, const _Ty& _Val)
	{	// copy omitting each matching _Val
	_DEPRECATE_UNCHECKED(remove_copy, _Dest);
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_Dest,
		_Remove_copy_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Unchecked_idl0(_Dest), _Val)));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Ty> inline
	_OutTy *remove_copy(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize], const _Ty& _Val)
	{	// copy omitting each matching _Val, array dest
	return (_Unchecked(
		_STD remove_copy(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Val)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION remove_copy_if
template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Remove_copy_if_unchecked(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred)
	{	// copy omitting each element satisfying _Pred
	for (; _First != _Last; ++_First)
		if (!_Pred(*_First))
			{	// validate _Dest and store
			_DEBUG_POINTER(_Dest);
			*_Dest++ = *_First;
			}

	return (_Dest);
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Remove_copy_if_no_deprecate(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred)
	{	// copy omitting each element satisfying _Pred, no deprecation warnings
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_Dest,
		_Remove_copy_if_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Unchecked_idl0(_Dest), _Pred)));
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt remove_copy_if(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr _Pred)
	{	// copy omitting each element satisfying _Pred
	_DEPRECATE_UNCHECKED(remove_copy_if, _Dest);
	return (_Remove_copy_if_no_deprecate(_First, _Last, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *remove_copy_if(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize], _Pr _Pred)
	{	// copy omitting each element satisfying _Pred, array dest
	return (_Unchecked(
		_Remove_copy_if_no_deprecate(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION remove
template<class _FwdIt,
	class _Ty> inline
	_FwdIt _Remove_unchecked(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
	{	// remove each matching _Val
	_First = _Find_unchecked(_First, _Last, _Val);
	_FwdIt _Next = _First;
	if (_First != _Last)
		{
		for (++_First; _First != _Last; ++_First)
			if (!(*_First == _Val))
				*_Next++ = _STD move(*_First);
		}

	return (_Next);
	}

template<class _FwdIt,
	class _Ty> inline
	_FwdIt remove(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
	{	// remove each matching _Val
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Remove_unchecked(_Unchecked(_First), _Unchecked(_Last), _Val)));
	}

		// TEMPLATE FUNCTION remove_if
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Remove_if_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// remove each satisfying _Pred
	_First = _Find_if_unchecked(_First, _Last, _Pred);
	_FwdIt _Next = _First;
	if (_First != _Last)
		{
		for (++_First; _First != _Last; ++_First)
		if (!_Pred(*_First))
			*_Next++ = _STD move(*_First);
		}

	return (_Next);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// remove each satisfying _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Remove_if_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION unique WITH PRED
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Unique_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// remove each satisfying _Pred with previous
	if (_First != _Last)
		for (_FwdIt _Firstb; (void)(_Firstb = _First), ++_First != _Last; )
			if (_Pred(*_Firstb, *_First))
				{	// copy down
				for (; ++_First != _Last; )
					if (!_Pred(*_Firstb, *_First))
						*++_Firstb = _STD move(*_First);
				return (++_Firstb);
				}

	return (_Last);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt unique(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// remove each satisfying _Pred with previous
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER_IF(_First != _Last && _STD next(_First) != _Last, _Pred);
	return (_Rechecked(_First,
		_Unique_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION unique
template<class _FwdIt> inline
	_FwdIt unique(_FwdIt _First, _FwdIt _Last)
	{	// remove each matching previous
	return (_STD unique(_First, _Last, equal_to<>()));
	}

		// TEMPLATE FUNCTION unique_copy WITH PRED
template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Unique_copy_unchecked(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred, input_iterator_tag)
	{	// copy compressing pairs satisfying _Pred, input iterators
	if (_First != _Last)
		{
		_Iter_value_t<_InIt> _Val = *_First;

		for (*_Dest++ = _Val; ++_First != _Last; )
			if (!_Pred(_Val, *_First))
				{	// copy unmatched
				_Val = *_First;
				*_Dest++ = _Val;
				}
		}

	return (_Dest);
	}

template<class _FwdIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Unique_copy_unchecked(_FwdIt _First, _FwdIt _Last,
		_OutIt _Dest, _Pr& _Pred, forward_iterator_tag)
	{	// copy compressing pairs satisfying _Pred, forward iterators
	if (_First != _Last)
		{
		_FwdIt _Firstb = _First;

		for (*_Dest++ = *_Firstb; ++_First != _Last; )
			if (!_Pred(*_Firstb, *_First))
				{	// copy unmatched
				_Firstb = _First;
				*_Dest++ = *_Firstb;
				}
		}

	return (_Dest);
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Unique_copy_no_deprecate(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr& _Pred)
	{	// copy compressing pairs that match, no deprecation warnings
	_DEBUG_RANGE_PTR(_First, _Last, _Dest);
	_DEBUG_POINTER_IF(_First != _Last, _Pred);
	return (_Rechecked(_Dest,
		_Unique_copy_unchecked(_Unchecked(_First), _Unchecked(_Last),
			_Unchecked_idl0(_Dest), _Pred, _Iter_cat_t<_InIt>())));
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt unique_copy(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr _Pred)
	{	// copy compressing pairs that match
	_DEPRECATE_UNCHECKED(unique_copy, _Dest);
	return (_Unique_copy_no_deprecate(_First, _Last, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *unique_copy(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize], _Pr _Pred)
	{	// copy compressing pairs that match, array dest
	return (_Unchecked(
		_Unique_copy_no_deprecate(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION unique_copy
template<class _InIt,
	class _OutIt> inline
	_OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
	{	// copy compressing pairs that match
	return (_STD unique_copy(_First, _Last, _Dest,
		equal_to<>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *unique_copy(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize])
	{	// copy compressing pairs that match, array dest
	return (_STD unique_copy(_First, _Last, _Dest,
		equal_to<>()));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION reverse_copy
template<class _BidIt,
	class _OutIt> inline
	_OutIt _Reverse_copy_unchecked(_BidIt _First, _BidIt _Last,
		_OutIt _Dest)
	{	// copy reversing elements in [_First, _Last)
	for (; _First != _Last; ++_Dest)
		*_Dest = *--_Last;
	return (_Dest);
	}

template<class _BidIt,
	class _OutIt> inline
	_OutIt _Reverse_copy1(_BidIt _First, _BidIt _Last,
		_OutIt _Dest,
		bidirectional_iterator_tag, _Any_tag)
	{	// copy reversing elements in [_First, _Last), arbitrary iterators
	return (_Rechecked(_Dest,
		_Reverse_copy_unchecked(_First, _Last, _Unchecked_idl0(_Dest))));
	}

template<class _BidIt,
	class _OutIt> inline
	_OutIt _Reverse_copy1(_BidIt _First, _BidIt _Last,
		_OutIt _Dest,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// copy reversing elements in [_First, _Last), random-access iterators
	_CHECK_RANIT_RANGE(_First, _Last, _Dest);
	return (_Rechecked(_Dest,
		_Reverse_copy_unchecked(_First, _Last, _Unchecked(_Dest))));
	}

template<class _BidIt,
	class _OutIt> inline
	_OutIt reverse_copy(_BidIt _First, _BidIt _Last,
		_OutIt _Dest)
	{	// copy reversing elements in [_First, _Last)
	_DEPRECATE_UNCHECKED(reverse_copy, _Dest);
	_DEBUG_RANGE_PTR(_First, _Last, _Dest);
	return (_Reverse_copy1(_Unchecked(_First), _Unchecked(_Last),
		_Dest, _Iter_cat_t<_BidIt>(), _Iter_cat_t<_OutIt>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _BidIt,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *reverse_copy(_BidIt _First, _BidIt _Last,
		_OutTy (&_Dest)[_OutSize])
	{	// copy reversing elements in [_First, _Last), array dest
	return (_Unchecked(
		_STD reverse_copy(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest))));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION rotate_copy
template<class _FwdIt,
	class _OutIt> inline
	_OutIt _Rotate_copy_unchecked(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
		_OutIt _Dest)
	{	// copy rotating [_First, _Last)
	_Dest = _Copy_unchecked(_Mid, _Last, _Dest);
	return (_Copy_unchecked(_First, _Mid, _Dest));
	}

template<class _FwdIt,
	class _OutIt> inline
	_OutIt _Rotate_copy1(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
		_OutIt _Dest, forward_iterator_tag, _Any_tag)
	{	// copy rotating [_First, _Last)
	return (_Rechecked(_Dest,
		_Rotate_copy_unchecked(_First, _Mid, _Last, _Unchecked_idl0(_Dest))));
	}

template<class _FwdIt,
	class _OutIt> inline
	_OutIt _Rotate_copy1(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
		_OutIt _Dest, random_access_iterator_tag, random_access_iterator_tag)
	{	// copy rotating [_First, _Last)
	_CHECK_RANIT_RANGE(_First, _Last, _Dest);
	return (_Rechecked(_Dest,
		_Rotate_copy_unchecked(_First, _Mid, _Last, _Unchecked(_Dest))));
	}

template<class _FwdIt,
	class _OutIt> inline
	_OutIt rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
		_OutIt _Dest)
	{	// copy rotating [_First, _Last)
	_DEBUG_RANGE(_First, _Mid);
	_DEBUG_RANGE(_Mid, _Last);
	return (_Rotate_copy1(_Unchecked(_First), _Unchecked(_Mid),
		_Unchecked(_Last), _Dest, _Iter_cat_t<_FwdIt>(), _Iter_cat_t<_OutIt>()));
	}

		// TEMPLATE FUNCTION shuffle WITH URNG
template<class _RanIt,
	class _Fn1> inline
	void _Random_shuffle_unchecked(_RanIt _First, _RanIt _Last, _Fn1& _Func)
	{	// shuffle nonempty [_First, _Last) using random function _Func
	if (_Last - _First < 2)
		return;

	_RanIt _Next = _First;
	for (_Iter_diff_t<_RanIt> _Index = 2; ++_Next != _Last; ++_Index)
		{	// randomly swap element with self or earlier element
		_Iter_diff_t<_RanIt> _Off = _Func(_Index);

 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Off < 0 || _Index <= _Off)
			{	// report error
			_DEBUG_ERROR("random value out of range");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE_RANGE(0 <= _Off && _Off < _Index);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		_STD iter_swap(_Next, _First + _Off);
		}
	}

template<class _RanIt,
	class _Fn1> inline
	void _Random_shuffle1(_RanIt _First, _RanIt _Last, _Fn1& _Func)
	{	// shuffle [_First, _Last) using random function _Func
	_DEBUG_RANGE(_First, _Last);
	_Random_shuffle_unchecked(_Unchecked(_First), _Unchecked(_Last), _Func);
	}

template<class _RanIt,
	class _Urng> inline
	void shuffle(_RanIt _First, _RanIt _Last, _Urng&& _Func)
	{	// shuffle [_First, _Last) using URNG _Func
	typedef typename iterator_traits<_RanIt>::difference_type _Diff;
	typedef typename remove_reference<_Urng>::type _Urng0;
	_Rng_from_urng<_Diff, _Urng0> _Rng(_Func);
	_Random_shuffle1(_First, _Last, _Rng);
	}

 #if _HAS_AUTO_PTR_ETC
		// TEMPLATE FUNCTION random_shuffle WITH RANDOM FN
template<class _RanIt,
	class _Fn1> inline
	void random_shuffle(_RanIt _First, _RanIt _Last, _Fn1&& _Func)
	{	// shuffle [_First, _Last) using random function _Func
	_Random_shuffle1(_First, _Last, _Func);
	}

	// STRUCT _Rand_urng_from_func
struct _Rand_urng_from_func
	{	// wrap rand() as a URNG
	typedef unsigned int result_type;

	static result_type (min)()
		{	// return minimum possible generated value
		return (0);
		}

	static result_type (max)()
		{	// return maximum possible generated value
		return (RAND_MAX);
		}

	result_type operator()()
		{	// invoke rand()
		return (_CSTD rand());
		}
	};

		// TEMPLATE FUNCTION random_shuffle
template<class _RanIt> inline
	void random_shuffle(_RanIt _First, _RanIt _Last)
	{	// shuffle [_First, _Last) using rand()
	_Rand_urng_from_func _Func;
	_STD shuffle(_First, _Last, _Func);
	}
 #endif /* _HAS_AUTO_PTR_ETC */

		// TEMPLATE FUNCTION partition
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Partition_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred,
		forward_iterator_tag)
	{	// move elements satisfying _Pred to front, forward iterators
	while (_First != _Last && _Pred(*_First))
		++_First;	// skip in-place elements at beginning

	if (_First == _Last)
		return (_First);	// done

	for (_FwdIt _Next = _STD next(_First); _Next != _Last; ++_Next)
		if (_Pred(*_Next))
			_STD iter_swap(_First++, _Next);	// out of place, swap and loop

	return (_First);
	}

template<class _BidIt,
	class _Pr> inline
	_BidIt _Partition_unchecked(_BidIt _First, _BidIt _Last, _Pr& _Pred,
		bidirectional_iterator_tag)
	{	// move elements satisfying _Pred to front, bidirectional iterators
	for (; ; ++_First)
		{	// find any out-of-order pair
		for (; _First != _Last && _Pred(*_First); ++_First)
			;	// skip in-place elements at beginning
		if (_First == _Last)
			break;	// done

		for (; _First != --_Last && !_Pred(*_Last); )
			;	// skip in-place elements at end
		if (_First == _Last)
			break;	// done

		_STD iter_swap(_First, _Last);	// out of place, swap and loop
		}

	return (_First);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt partition(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// move elements satisfying _Pred to beginning of sequence
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_First,
		_Partition_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred,
			_Iter_cat_t<_FwdIt>())));
	}

		// TEMPLATE FUNCTION stable_partition
template<class _BidIt,
	class _Diff,
	class _Ty> inline
	_BidIt _Buffered_rotate_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temp_iterator<_Ty>& _Tempbuf)
	{	// rotate [_First, _Last) using temp buffer
	if (_Count1 == 0 || _Count2 == 0)
		{	// do nothing
		_STD advance(_First, _Count2);
		return (_First);
		}
	else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
		{	// buffer left partition, then copy parts
		_Move_unchecked(_First, _Mid, _Tempbuf._Init());
		_Move_unchecked(_Mid, _Last, _First);
		return (_Move_backward_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
			_Last));
		}
	else if (_Count2 <= _Tempbuf._Maxlen())
		{	// buffer right partition, then copy parts
		_Move_unchecked(_Mid, _Last, _Tempbuf._Init());
		_Move_backward_unchecked(_First, _Mid, _Last);
		return (_Move_unchecked(_Tempbuf._First(), _Tempbuf._Last(), _First));
		}
	else
		{	// buffer too small, rotate in place
		return (_Rotate_unchecked(_First, _Mid, _Last));
		}
	}

template<class _BidIt,
	class _Pr,
	class _Diff,
	class _Ty> inline
	_BidIt _Stable_partition_unchecked1(_BidIt _First, _BidIt _Last, _Pr& _Pred,
		_Diff _Count, _Temp_iterator<_Ty>& _Tempbuf)
	{	// partition preserving order of equivalents, using _Pred
	if (_Count == 0)
		return (_First);
	else if (_Count == 1)
		return (_Pred(*_First) ? _Last : _First);
	else if (_Count <= _Tempbuf._Maxlen())
		{	// temp buffer big enough, copy right partition out and back
		_BidIt _Next = _First;
		for (_Tempbuf._Init(); _First != _Last; ++_First)
			if (_Pred(*_First))
				*_Next++ = _STD move(*_First);
			else
				*_Tempbuf++ = _STD move(*_First);

		_Move_unchecked(_Tempbuf._First(), _Tempbuf._Last(), _Next);	// copy back
		return (_Next);
		}
	else
		{	// temp buffer not big enough, divide and conquer
		_BidIt _Mid = _First;
		_STD advance(_Mid, _Count / 2);

		_BidIt _Left = _Stable_partition_unchecked1(_First, _Mid, _Pred,
			_Count / 2, _Tempbuf);	// form L1R1 in left half
		_BidIt _Right = _Stable_partition_unchecked1(_Mid, _Last, _Pred,
			_Count - _Count / 2, _Tempbuf);	// form L2R2 in right half

		_Diff _Count1 = _STD distance(_Left, _Mid);
		_Diff _Count2 = _STD distance(_Mid, _Right);

		return (_Buffered_rotate_unchecked(_Left, _Mid, _Right,
			_Count1, _Count2, _Tempbuf));	// rotate L1R1L2R2 to L1L2R1R2
		}
	}

template<class _BidIt,
	class _Pr> inline
	_BidIt _Stable_partition_unchecked(_BidIt _First, _BidIt _Last, _Pr& _Pred)
	{	// partition preserving order of equivalents, using _Pred
	if (_First == _Last)
		return (_First);
	_Iter_diff_t<_BidIt> _Count = _STD distance(_First, _Last);
	_Temp_iterator<_Iter_value_t<_BidIt>> _Tempbuf(_Count);
	return (_Stable_partition_unchecked1(_First, _Last, _Pred, _Count, _Tempbuf));
	}

template<class _BidIt,
	class _Pr> inline
	_BidIt stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
	{	// partition preserving order of equivalents, using _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Rechecked(_First,
		_Stable_partition_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

 #if _ITERATOR_DEBUG_LEVEL == 2
		// TEMPLATE FUNCTION _Debug_heap WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _Debug_heap(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// test if range is a heap ordered by _Pred
	if (_First != _Last)
		for (_RanIt _Root = _First; ++_First != _Last; ++_Root)
			{	// test a pair
			if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
				_DEBUG_ERROR("invalid heap");
			else if (++_First == _Last)
				break;
			else if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
				_DEBUG_ERROR("invalid heap");
			}
	}

  #define _DEBUG_HEAP_PRED(first, last, pred)	\
	_Debug_heap(_Unchecked(first), _Unchecked(last), pred)

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
  #define _DEBUG_HEAP_PRED(first, last, pred)
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		// TEMPLATE FUNCTION push_heap WITH PRED
template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Push_heap_by_index(_RanIt _First, _Diff _Hole,
		_Diff _Top, _Ty&& _Val, _Pr& _Pred)
	{	// percolate _Hole to _Top or where _Val belongs, using _Pred
	for (_Diff _Idx = (_Hole - 1) / 2;
		_Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val);
		_Idx = (_Hole - 1) / 2)
		{	// move _Hole up to parent
		*(_First + _Hole) = _STD move(*(_First + _Idx));
		_Hole = _Idx;
		}

	*(_First + _Hole) = _STD move(_Val);	// drop _Val into final hole
	}

template<class _RanIt,
	class _Pr> inline
	void _Push_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
	typedef _Iter_diff_t<_RanIt> _Diff;
	_Diff _Count = _Last - _First;
	if (2 <= _Count)
		{
		_Iter_value_t<_RanIt> _Val = _STD move(*--_Last);
		_Push_heap_by_index(_First, --_Count, _Diff(0), _STD move(_Val), _Pred);
		}
	}

template<class _RanIt,
	class _Pr> inline
	void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	_Push_heap_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION push_heap
template<class _RanIt> inline
	void push_heap(_RanIt _First, _RanIt _Last)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using operator<
	_STD push_heap(_First, _Last, less<>());
	}

		// TEMPLATE FUNCTION pop_heap WITH PRED
template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Pop_heap_hole_by_index(_RanIt _First, _Diff _Hole, _Diff _Bottom,
		_Ty&& _Val, _Pr& _Pred)
	{	// percolate _Hole to _Bottom, then push _Val, using _Pred
		// precondition: _Bottom != 0
	const _Diff _Top = _Hole;
	_Diff _Idx = _Hole;

	// Check whether _Idx can have a child before calculating that child's index, since
	// calculating the child's index can trigger integer overflows
	const _Diff _Max_sequence_non_leaf = (_Bottom - 1) / 2;
	while (_Idx < _Max_sequence_non_leaf)
		{	// move _Hole down to larger child
		_Idx = 2 * _Idx + 2;
		if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1))))
			--_Idx;
		*(_First + _Hole) = _STD move(*(_First + _Idx));
		_Hole = _Idx;
		}

	if (_Idx == _Max_sequence_non_leaf && _Bottom % 2 == 0)
		{	// only child at bottom, move _Hole down to it
		*(_First + _Hole) = _STD move(*(_First + (_Bottom - 1)));
		_Hole = _Bottom - 1;
		}

	_Push_heap_by_index(_First, _Hole, _Top, _STD move(_Val), _Pred);
	}

template<class _RanIt,
	class _Ty,
	class _Pr> inline
	void _Pop_heap_hole_unchecked(_RanIt _First, _RanIt _Last, _RanIt _Dest,
		_Ty&& _Val, _Pr& _Pred)
	{	// pop *_First to *_Dest and reheap, using _Pred
		// precondition: _First != _Last
		// precondition: _First != _Dest
	*_Dest = _STD move(*_First);
	_Pop_heap_hole_by_index(_First, _Iter_diff_t<_RanIt>(0), _Iter_diff_t<_RanIt>(_Last - _First),
		_STD move(_Val), _Pred);
	}

template<class _RanIt,
	class _Pr> inline
	void _Pop_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// pop *_First to *(_Last - 1) and reheap, using _Pred
	if (2 <= _Last - _First)
		{
		--_Last;
		_Iter_value_t<_RanIt> _Val = _STD move(*_Last);
		_Pop_heap_hole_unchecked(_First, _Last, _Last,
			_STD move(_Val), _Pred);
		}
	}

template<class _RanIt,
	class _Pr> inline
	void pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// pop *_First to *(_Last - 1) and reheap, using _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	_DEBUG_HEAP_PRED(_First, _Last, _Pred);
	_Pop_heap_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION pop_heap
template<class _RanIt> inline
	void pop_heap(_RanIt _First, _RanIt _Last)
	{	// pop *_First to *(_Last - 1) and reheap, using operator<
	_STD pop_heap(_First, _Last, less<>());
	}

		// TEMPLATE FUNCTION make_heap WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _Make_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// make nontrivial [_First, _Last) into a heap, using _Pred
	_Iter_diff_t<_RanIt> _Bottom = _Last - _First;
	if (2 <= _Bottom)
		{
		for (_Iter_diff_t<_RanIt> _Hole = _Bottom / 2; 0 < _Hole; )
			{	// reheap top half, bottom to top
			--_Hole;
			_Iter_value_t<_RanIt> _Val = _STD move(*(_First + _Hole));
			_Pop_heap_hole_by_index(_First, _Hole, _Bottom,
				_STD move(_Val), _Pred);
			}
		}
	}

template<class _RanIt,
	class _Pr> inline
	void make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// make [_First, _Last) into a heap, using _Pred
	_DEBUG_RANGE(_First, _Last);
	_Make_heap_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION make_heap
template<class _RanIt> inline
	void make_heap(_RanIt _First, _RanIt _Last)
	{	// make [_First, _Last) into a heap, using operator<
	_STD make_heap(_First, _Last, less<>());
	}

		// TEMPLATE FUNCTION sort_heap WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _Sort_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// order heap by repeatedly popping, using _Pred
	for (; 2 <= _Last - _First; --_Last)
		_Pop_heap_unchecked(_First, _Last, _Pred);
	}

template<class _RanIt,
	class _Pr> inline
	void sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// order heap by repeatedly popping, using _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER_IF(2 <= _Last - _First, _Pred);
	_DEBUG_HEAP_PRED(_First, _Last, _Pred);
	_Sort_heap_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION sort_heap
template<class _RanIt> inline
	void sort_heap(_RanIt _First, _RanIt _Last)
	{	// order heap by repeatedly popping, using operator<
	_STD sort_heap(_First, _Last, less<>());
	}

		// TEMPLATE FUNCTION lower_bound WITH PRED
template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	_FwdIt _Lower_bound_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Val, _Pr& _Pred)
	{	// find first element not before _Val, using _Pred
	_Iter_diff_t<_FwdIt> _Count = _STD distance(_First, _Last);

	while (0 < _Count)
		{	// divide and conquer, find half that contains answer
		_Iter_diff_t<_FwdIt> _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		_STD advance(_Mid, _Count2);

		if (_Pred(*_Mid, _Val))
			{	// try top half
			_First = ++_Mid;
			_Count -= _Count2 + 1;
			}
		else
			_Count = _Count2;
		}

	return (_First);
	}

template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	_FwdIt lower_bound(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Val, _Pr _Pred)
	{	// find first element not before _Val, using _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Lower_bound_unchecked(_Unchecked(_First), _Unchecked(_Last), _Val, _Pred)));
	}

		// TEMPLATE FUNCTION lower_bound
template<class _FwdIt,
	class _Ty> inline
	_FwdIt lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
	{	// find first element not before _Val, using operator<
	return (_STD lower_bound(_First, _Last, _Val, less<>()));
	}

		// TEMPLATE FUNCTION upper_bound WITH PRED
template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	_FwdIt _Upper_bound_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Val, _Pr& _Pred)
	{	// find first element that _Val is before, using _Pred
	_Iter_diff_t<_FwdIt> _Count = _STD distance(_First, _Last);

	while (0 < _Count)
		{	// divide and conquer, find half that contains answer
		_Iter_diff_t<_FwdIt> _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		_STD advance(_Mid, _Count2);

		if (!_Pred(_Val, *_Mid))
			{	// try top half
			_First = ++_Mid;
			_Count -= _Count2 + 1;
			}
		else
			_Count = _Count2;
		}

	return (_First);
	}

template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	_FwdIt upper_bound(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Val, _Pr _Pred)
	{	// find first element that _Val is before, using _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Upper_bound_unchecked(_Unchecked(_First), _Unchecked(_Last), _Val, _Pred)));
	}

		// TEMPLATE FUNCTION upper_bound
template<class _FwdIt,
	class _Ty> inline
	_FwdIt upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
	{	// find first element that _Val is before, using operator<
	return (_STD upper_bound(_First, _Last, _Val, less<>()));
	}

		// TEMPLATE FUNCTION equal_range WITH PRED
template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	pair<_FwdIt, _FwdIt>
		_Equal_range_unchecked(_FwdIt _First, _FwdIt _Last,
			const _Ty& _Val, _Pr& _Pred)
	{	// find range equivalent to _Val, using _Pred
	_Iter_diff_t<_FwdIt> _Count = _STD distance(_First, _Last);

	while (0 < _Count)
		{	// divide and conquer, check midpoint
		_Iter_diff_t<_FwdIt> _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		_STD advance(_Mid, _Count2);

		if (_DEBUG_LT_PRED(_Pred, *_Mid, _Val))
			{	// range begins above _Mid, loop
			_First = ++_Mid;
			_Count -= _Count2 + 1;
			}
		else if (_Pred(_Val, *_Mid))
			_Count = _Count2;	// range in first half, loop
		else
			{	// range straddles _Mid, find each end and return
			_FwdIt _First2 = _Lower_bound_unchecked(_First, _Mid, _Val, _Pred);
			_STD advance(_First, _Count);
			_FwdIt _Last2 = _Upper_bound_unchecked(++_Mid, _First, _Val, _Pred);
			return (pair<_FwdIt, _FwdIt>(_First2, _Last2));
			}
		}

	return (pair<_FwdIt, _FwdIt>(_First, _First));	// empty range
	}

template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	pair<_FwdIt, _FwdIt>
		equal_range(_FwdIt _First, _FwdIt _Last,
			const _Ty& _Val, _Pr _Pred)
	{	// find range equivalent to _Val, using _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked_both(_First, _Last,
		_Equal_range_unchecked(_Unchecked(_First), _Unchecked(_Last), _Val, _Pred)));
	}

		// TEMPLATE FUNCTION equal_range
template<class _FwdIt,
	class _Ty> inline
	pair<_FwdIt, _FwdIt>
		equal_range(_FwdIt _First, _FwdIt _Last,
			const _Ty& _Val)
	{	// find range equivalent to _Val, using operator<
	return (_STD equal_range(_First, _Last, _Val, less<>()));
	}

		// TEMPLATE FUNCTION binary_search WITH PRED
template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	bool _Binary_search_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Val, _Pr& _Pred)
	{	// test if _Val equivalent to some element, using _Pred
	_First = _Lower_bound_unchecked(_First, _Last, _Val, _Pred);
	return (_First != _Last && !_Pred(_Val, *_First));
	}

template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	bool binary_search(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Val, _Pr _Pred)
	{	// test if _Val equivalent to some element, using _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Binary_search_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Val, _Pred));
	}

		// TEMPLATE FUNCTION binary_search
template<class _FwdIt,
	class _Ty> inline
	bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
	{	// test if _Val equivalent to some element, using operator<
	return (_STD binary_search(_First, _Last, _Val, less<>()));
	}

		// TEMPLATE FUNCTION merge WITH PRED
template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Merge_unchecked(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred)
	{	// copy merging ranges, both using _Pred
	if (_First1 != _Last1 && _First2 != _Last2)
		for (; ; )
			{	// merge either first or second
			if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
				{
				*_Dest++ = *_First2++;
				if (_First2 == _Last2)
					break;
				}
			else
				{
				*_Dest++ = *_First1++;
				if (_First1 == _Last1)
					break;
				}
			}

	_Dest = _Copy_unchecked(_First1, _Last1, _Dest);	// copy any tail
	return (_Copy_unchecked(_First2, _Last2, _Dest));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Merge_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred, input_iterator_tag,
		input_iterator_tag, _Any_tag)
	{	// copy merging ranges, both using _Pred, arbitrary iterators, no deprecation warnings
	return (_Rechecked(_Dest,
		_Merge_unchecked(_First1, _Last1, _First2, _Last2, _Unchecked_idl0(_Dest), _Pred)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Merge_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred, random_access_iterator_tag,
		random_access_iterator_tag, random_access_iterator_tag)
	{	// copy merging ranges, both using _Pred, random-access iterators, no deprecation warnings
	_CHECK_RANIT_RANGE_N(_Dest, (_Last1 - _First1) + (_Last2 - _First2));
	return (_Rechecked(_Dest,
		_Merge_unchecked(_First1, _Last1, _First2, _Last2, _Unchecked(_Dest), _Pred)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Merge_no_deprecate(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred)
	{	// copy merging ranges, both using _Pred, no deprecation warnings
	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
	_DEBUG_POINTER_IF(_First1 != _Last1 || _First2 != _Last2, _Dest);
	return (_Merge_no_deprecate1(_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2),
		_Dest, _Pred,
		_Iter_cat_t<_InIt1>(), _Iter_cat_t<_InIt2>(), _Iter_cat_t<_OutIt>()));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr _Pred)
	{	// copy merging ranges, both using _Pred
	_DEPRECATE_UNCHECKED(merge, _Dest);
	return (_Merge_no_deprecate(_First1, _Last1, _First2, _Last2, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *merge(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutTy (&_Dest)[_OutSize], _Pr _Pred)
	{	// copy merging ranges, both using _Pred, array dest
	return (_Unchecked(
		_Merge_no_deprecate(_First1, _Last1,
			_First2, _Last2,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION merge
template<class _InIt1,
	class _InIt2,
	class _OutIt> inline
	_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest)
	{	// copy merging ranges, both using operator<
	return (_STD merge(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *merge(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutTy (&_Dest)[_OutSize])
	{	// copy merging ranges, both using operator<, array dest
	return (_STD merge(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION inplace_merge WITH PRED
template<class _BidIt1,
	class _BidIt2,
	class _BidIt3,
	class _Pr> inline
	_BidIt3 _Buffered_merge_backward_unchecked(_BidIt1 _First1, _BidIt1 _Last1,
		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr& _Pred,
		bool _In_place = false)
	{	// merge backwards to _Dest, using _Pred
	if (_First1 != _Last1 && _First2 != _Last2)
		for (; ; )
			{	// merge either first or second
			if (_DEBUG_LT_PRED(_Pred, *--_Last2, *--_Last1))
				{
				*--_Dest = _STD move(*_Last1);
				++_Last2;
				if (_First1 == _Last1)
					break;
				}
			else
				{
				*--_Dest = _STD move(*_Last2);
				++_Last1;
				if (_First2 == _Last2)
					break;
				}
			}

	_Dest = _Move_backward_unchecked(_First2, _Last2, _Dest);	// move any tail
	if (!_In_place)
		_Dest = _Move_backward_unchecked(_First1, _Last1, _Dest);
	return (_Dest);
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Buffered_merge_unchecked(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred, bool _In_place = false)
	{	// move merging ranges, both using _Pred
	if (_First1 != _Last1 && _First2 != _Last2)
		for (; ; )
			{	// merge either first or second
			if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
				{	// merge first
				*_Dest++ = _STD move(*_First2++);
				if (_First2 == _Last2)
					break;
				}
			else
				{	// merge second
				*_Dest++ = _STD move(*_First1++);
				if (_First1 == _Last1)
					break;
				}
			}

	_Dest = _Move_unchecked(_First1, _Last1, _Dest);	// move any tail
	if (!_In_place)
		_Dest = _Move_unchecked(_First2, _Last2, _Dest);
	return (_Dest);
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_merge_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2,
			_Temp_iterator<_Ty>& _Tempbuf, _Pr& _Pred)
	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
	if (_Count1 == 0 || _Count2 == 0)
		;	// do nothing
	else if (_Count1 + _Count2 == 2)
		{	// order two one-element partitions
		if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
			_STD iter_swap(_First, _Mid);
		}
	else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
		{	// buffer left partition, then merge
		_Move_unchecked(_First, _Mid, _Tempbuf._Init());
		_Buffered_merge_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
			_Mid, _Last, _First, _Pred, true);
		}
	else if (_Count2 <= _Tempbuf._Maxlen())
		{	// buffer right partition, then merge
		_Move_unchecked(_Mid, _Last, _Tempbuf._Init());
		_Buffered_merge_backward_unchecked(_First, _Mid,
			_Tempbuf._First(), _Tempbuf._Last(), _Last, _Pred, true);
		}
	else
		{	// buffer too small, divide and conquer
		_BidIt _Firstn, _Lastn;
		_Diff _Count1n, _Count2n;
		if (_Count2 < _Count1)
			{	// left larger, cut it in half and partition right to match
			_Count1n = _Count1 / 2;
			_Firstn = _First;
			_STD advance(_Firstn, _Count1n);
			_Lastn = _Lower_bound_unchecked(_Mid, _Last, *_Firstn, _Pred);
			_Count2n = _STD distance(_Mid, _Lastn);
			}
		else
			{	// right larger, cut it in half and partition left to match
			_Count2n = _Count2 / 2;
			_Lastn = _Mid;
			_STD advance(_Lastn, _Count2n);
			_Firstn = _Upper_bound_unchecked(_First, _Mid, *_Lastn, _Pred);
			_Count1n = _STD distance(_First, _Firstn);
			}
		_BidIt _Midn = _Buffered_rotate_unchecked(_Firstn, _Mid, _Lastn,
			_Count1 - _Count1n, _Count2n, _Tempbuf);	// rearrange middle
		_Buffered_merge_unchecked(_First, _Firstn, _Midn,
			_Count1n, _Count2n, _Tempbuf, _Pred);	// merge each new part
		_Buffered_merge_unchecked(_Midn, _Lastn, _Last,
			_Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf, _Pred);
		}
	}

template<class _BidIt,
	class _Pr> inline
	void _Inplace_merge_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr& _Pred)
	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
	if (_First != _Mid && _Mid != _Last)
		{
		_Iter_diff_t<_BidIt> _Count1 = _STD distance(_First, _Mid);
		_Iter_diff_t<_BidIt> _Count2 = _STD distance(_Mid, _Last);
		_Temp_iterator<_Iter_value_t<_BidIt>> _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
		_Buffered_merge_unchecked(_First, _Mid, _Last,
			_Count1, _Count2, _Tempbuf, _Pred);
		}
	}

template<class _BidIt,
	class _Pr> inline
	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred)
	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
	_DEBUG_ORDER_PRED(_First, _Mid, _Pred);
	_DEBUG_ORDER_PRED(_Mid, _Last, _Pred);
	_Inplace_merge_unchecked(
		_Unchecked(_First), _Unchecked(_Mid), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION inplace_merge
template<class _BidIt> inline
	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last)
	{	// merge [_First, _Mid) with [_Mid, _Last), using operator<
	_STD inplace_merge(_First, _Mid, _Last, less<>());
	}

		// TEMPLATE FUNCTION sort WITH PRED
template<class _BidIt,
	class _Pr> inline
	void _Insertion_sort_unchecked(_BidIt _First, _BidIt _Last, _Pr& _Pred)
	{	// insertion sort [_First, _Last), using _Pred
	if (_First != _Last)
		for (_BidIt _Next = _First; ++_Next != _Last; )
			{	// order next element
			_BidIt _Next1 = _Next;
			_Iter_value_t<_BidIt> _Val = _STD move(*_Next);

			if (_DEBUG_LT_PRED(_Pred, _Val, *_First))
				{	// found new earliest element, move to front
				_Move_backward_unchecked(_First, _Next, ++_Next1);
				*_First = _STD move(_Val);
				}
			else
				{	// look for insertion point after first
				for (_BidIt _First1 = _Next1;
					_DEBUG_LT_PRED(_Pred, _Val, *--_First1);
					_Next1 = _First1)
					*_Next1 = _STD move(*_First1);	// move hole down
				*_Next1 = _STD move(_Val);	// insert element in hole
				}
			}
	}

template<class _RanIt,
	class _Pr> inline
	void _Med3_unchecked(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr& _Pred)
	{	// sort median of three elements to middle
	if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
		_STD iter_swap(_Mid, _First);
	if (_DEBUG_LT_PRED(_Pred, *_Last, *_Mid))
		{	// swap middle and last, then test first again
		_STD iter_swap(_Last, _Mid);
		if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
			_STD iter_swap(_Mid, _First);
		}
	}

template<class _RanIt,
	class _Pr> inline
	void _Guess_median_unchecked(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr& _Pred)
	{	// sort median element to middle
	if (40 < _Last - _First)
		{	// median of nine
		size_t _Step = (_Last - _First + 1) / 8;
		_Med3_unchecked(_First, _First + _Step, _First + 2 * _Step, _Pred);
		_Med3_unchecked(_Mid - _Step, _Mid, _Mid + _Step, _Pred);
		_Med3_unchecked(_Last - 2 * _Step, _Last - _Step, _Last, _Pred);
		_Med3_unchecked(_First + _Step, _Mid, _Last - _Step, _Pred);
		}
	else
		_Med3_unchecked(_First, _Mid, _Last, _Pred);
	}

template<class _RanIt,
	class _Pr> inline
	pair<_RanIt, _RanIt>
		_Partition_by_median_guess_unchecked(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// partition [_First, _Last), using _Pred
	_RanIt _Mid = _First + (_Last - _First) / 2;
	_Guess_median_unchecked(_First, _Mid, _Last - 1, _Pred);
	_RanIt _Pfirst = _Mid;
	_RanIt _Plast = _Pfirst + 1;

	while (_First < _Pfirst
		&& !_DEBUG_LT_PRED(_Pred, *(_Pfirst - 1), *_Pfirst)
		&& !_Pred(*_Pfirst, *(_Pfirst - 1)))
		--_Pfirst;
	while (_Plast < _Last
		&& !_DEBUG_LT_PRED(_Pred, *_Plast, *_Pfirst)
		&& !_Pred(*_Pfirst, *_Plast))
		++_Plast;

	_RanIt _Gfirst = _Plast;
	_RanIt _Glast = _Pfirst;

	for (; ; )
		{	// partition
		for (; _Gfirst < _Last; ++_Gfirst)
			if (_DEBUG_LT_PRED(_Pred, *_Pfirst, *_Gfirst))
				;
			else if (_Pred(*_Gfirst, *_Pfirst))
				break;
			else if (_Plast++ != _Gfirst)
				_STD iter_swap(_Plast - 1, _Gfirst);
		for (; _First < _Glast; --_Glast)
			if (_DEBUG_LT_PRED(_Pred, *(_Glast - 1), *_Pfirst))
				;
			else if (_Pred(*_Pfirst, *(_Glast - 1)))
				break;
			else if (--_Pfirst != _Glast - 1)
				_STD iter_swap(_Pfirst, _Glast - 1);
		if (_Glast == _First && _Gfirst == _Last)
			return (pair<_RanIt, _RanIt>(_Pfirst, _Plast));

		if (_Glast == _First)
			{	// no room at bottom, rotate pivot upward
			if (_Plast != _Gfirst)
				_STD iter_swap(_Pfirst, _Plast);
			++_Plast;
			_STD iter_swap(_Pfirst++, _Gfirst++);
			}
		else if (_Gfirst == _Last)
			{	// no room at top, rotate pivot downward
			if (--_Glast != --_Pfirst)
				_STD iter_swap(_Glast, _Pfirst);
			_STD iter_swap(_Pfirst, --_Plast);
			}
		else
			_STD iter_swap(_Gfirst++, --_Glast);
		}
	}

template<class _RanIt,
	class _Diff,
	class _Pr> inline
	void _Sort_unchecked1(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr& _Pred)
	{	// order [_First, _Last), using _Pred
	_Diff _Count;
	while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)
		{	// divide and conquer by quicksort
		pair<_RanIt, _RanIt> _Mid =
			_Partition_by_median_guess_unchecked(_First, _Last, _Pred);
		_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisions

		if (_Mid.first - _First < _Last - _Mid.second)
			{	// loop on second half
			_Sort_unchecked1(_First, _Mid.first, _Ideal, _Pred);
			_First = _Mid.second;
			}
		else
			{	// loop on first half
			_Sort_unchecked1(_Mid.second, _Last, _Ideal, _Pred);
			_Last = _Mid.first;
			}
		}

	if (_ISORT_MAX < _Count)
		{	// heap sort if too many divisions
		_Make_heap_unchecked(_First, _Last, _Pred);
		_Sort_heap_unchecked(_First, _Last, _Pred);
		}
	else if (2 <= _Count)
		_Insertion_sort_unchecked(_First, _Last, _Pred);	// small
	}

template<class _RanIt,
	class _Pr> inline
	void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// order [_First, _Last), using _Pred
	_Sort_unchecked1(_First, _Last, _Last - _First, _Pred);
	}

template<class _RanIt,
	class _Pr> inline
	void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// order [_First, _Last), using _Pred
	_DEBUG_RANGE(_First, _Last);
	_Sort_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION sort
template<class _RanIt> inline
	void sort(_RanIt _First, _RanIt _Last)
	{	// order [_First, _Last), using operator<
	_STD sort(_First, _Last, less<>());
	}

		// TEMPLATE FUNCTION stable_sort WITH PRED
template<class _BidIt,
	class _OutIt,
	class _Diff,
	class _Pr> inline
	void _Chunked_merge_unchecked(_BidIt _First, _BidIt _Last, _OutIt _Dest,
		_Diff _Chunk, _Diff _Count, _Pr& _Pred)
	{	// copy merging chunks, using _Pred
	for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
		{	// copy merging pairs of adjacent chunks
		_BidIt _Mid1 = _First;
		_STD advance(_Mid1, _Chunk);
		_BidIt _Mid2 = _Mid1;
		_STD advance(_Mid2, _Chunk);

		_Dest = _Buffered_merge_unchecked(_First, _Mid1, _Mid1, _Mid2, _Dest, _Pred);
		_First = _Mid2;
		}

	if (_Count <= _Chunk)
		_Move_unchecked(_First, _Last, _Dest);	// copy partial last chunk
	else
		{	// copy merging whole and partial last chunk
		_BidIt _Mid1 = _First;
		_STD advance(_Mid1, _Chunk);

		_Buffered_merge_unchecked(_First, _Mid1, _Mid1, _Last, _Dest, _Pred);
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_merge_sort_unchecked(_BidIt _First, _BidIt _Last, _Diff _Count,
		_Temp_iterator<_Ty>& _Tempbuf, _Pr& _Pred)
	{	// sort using temp buffer for merges, using _Pred
	_BidIt _Mid = _First;
	for (_Diff _Nleft = _Count; _ISORT_MAX <= _Nleft; _Nleft -= _ISORT_MAX)
		{	// sort chunks
		_BidIt _Midn = _Mid;
		_STD advance(_Midn, (int)_ISORT_MAX);

		_Insertion_sort_unchecked(_Mid, _Midn, _Pred);
		_Mid = _Midn;
		}
	_Insertion_sort_unchecked(_Mid, _Last, _Pred);	// sort partial last chunk

	for (_Diff _Chunk = _ISORT_MAX; _Chunk < _Count; _Chunk *= 2)
		{	// merge adjacent pairs of chunks to and from temp buffer
		_Chunked_merge_unchecked(_First, _Last, _Tempbuf._Init(),
			_Chunk, _Count, _Pred);
		_Chunked_merge_unchecked(_Tempbuf._First(), _Tempbuf._Last(), _First,
			_Chunk *= 2, _Count, _Pred);
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Stable_sort_unchecked1(_BidIt _First, _BidIt _Last, _Diff _Count,
		_Temp_iterator<_Ty>& _Tempbuf, _Pr& _Pred)
	{	// sort preserving order of equivalents, using _Pred
	if (_Count <= _ISORT_MAX)
		_Insertion_sort_unchecked(_First, _Last, _Pred);	// small
	else
		{	// sort halves and merge
		_Diff _Count2 = (_Count + 1) / 2;
		_BidIt _Mid = _First;
		_STD advance(_Mid, _Count2);

		if (_Count2 <= _Tempbuf._Maxlen())
			{	// temp buffer big enough, sort each half using buffer
			_Buffered_merge_sort_unchecked(_First, _Mid, _Count2, _Tempbuf, _Pred);
			_Buffered_merge_sort_unchecked(_Mid, _Last, _Count - _Count2,
				_Tempbuf, _Pred);
			}
		else
			{	// temp buffer not big enough, divide and conquer
			_Stable_sort_unchecked1(_First, _Mid, _Count2, _Tempbuf, _Pred);
			_Stable_sort_unchecked1(_Mid, _Last, _Count - _Count2, _Tempbuf, _Pred);
			}

		_Buffered_merge_unchecked(_First, _Mid, _Last,
			_Count2, _Count - _Count2, _Tempbuf, _Pred);	// merge halves
		}
	}

template<class _BidIt,
	class _Pr> inline
	void _Stable_sort_unchecked(_BidIt _First, _BidIt _Last, _Pr& _Pred)
	{	// sort preserving order of equivalents, using _Pred
	if (_First != _Last)
		{
		_Iter_diff_t<_BidIt> _Count = _STD distance(_First, _Last);
		_Temp_iterator<_Iter_value_t<_BidIt>> _Tempbuf((_Count + 1) / 2);
		_Stable_sort_unchecked1(_First, _Last, _Count, _Tempbuf, _Pred);
		}
	}

template<class _BidIt,
	class _Pr> inline
	void stable_sort(_BidIt _First, _BidIt _Last, _Pr _Pred)
	{	// sort preserving order of equivalents, using _Pred
	_DEBUG_RANGE(_First, _Last);
	_Stable_sort_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION stable_sort
template<class _BidIt> inline
	void stable_sort(_BidIt _First, _BidIt _Last)
	{	// sort preserving order of equivalents, using operator<
	_STD stable_sort(_First, _Last, less<>());
	}

		// TEMPLATE FUNCTION partial_sort WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _Partial_sort_unchecked(_RanIt _First, _RanIt _Mid, _RanIt _Last,
		_Pr& _Pred)
	{	// order [_First, _Last) up to _Mid, using _Pred
	if (_First == _Mid)
		return;	// nothing to do, avoid violating _Pop_heap_hole_unchecked preconditions
	_Make_heap_unchecked(_First, _Mid, _Pred);
	for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
		if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
			{	// replace top with new largest
			_Iter_value_t<_RanIt> _Val = _STD move(*_Next);
			_Pop_heap_hole_unchecked(_First, _Mid, _Next, _STD move(_Val), _Pred);
			}
	_Sort_heap_unchecked(_First, _Mid, _Pred);
	}

template<class _RanIt,
	class _Pr> inline
	void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
	{	// order [_First, _Last) up to _Mid, using _Pred
	_DEBUG_RANGE(_First, _Mid);
	_DEBUG_RANGE(_Mid, _Last);
	_DEBUG_POINTER_IF(2 <= _Last - _First, _Pred);
	_Partial_sort_unchecked(
		_Unchecked(_First), _Unchecked(_Mid), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION partial_sort
template<class _RanIt> inline
	void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last)
	{	// order [_First, _Last) up to _Mid, using operator<
	_STD partial_sort(_First, _Mid, _Last, less<>());
	}

		// TEMPLATE FUNCTION partial_sort_copy WITH PRED
template<class _InIt,
	class _RanIt,
	class _Pr> inline
	_RanIt _Partial_sort_copy_unchecked(_InIt _First1, _InIt _Last1,
		_RanIt _First2, _RanIt _Last2, _Pr& _Pred)
	{	// copy [_First1, _Last1) into [_First2, _Last2) using _Pred
	_RanIt _Mid2 = _First2;
	if (_First1 != _Last1 && _First2 != _Last2)
		{
		for (; _First1 != _Last1 && _Mid2 != _Last2; ++_First1, (void)++_Mid2)
			*_Mid2 = *_First1;	// copy min(_Last1 - _First1, _Last2 - _First2)
		_Make_heap_unchecked(_First2, _Mid2, _Pred);

		for (; _First1 != _Last1; ++_First1)
			if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
				_Pop_heap_hole_by_index(_First2, _Iter_diff_t<_RanIt>(0), _Iter_diff_t<_RanIt>(_Mid2 - _First2),
					_Iter_value_t<_InIt>(*_First1), _Pred);	// replace top with new largest

		_Sort_heap_unchecked(_First2, _Mid2, _Pred);
		}

	return (_Mid2);
	}

template<class _InIt,
	class _RanIt,
	class _Pr> inline
	_RanIt partial_sort_copy(_InIt _First1, _InIt _Last1,
		_RanIt _First2, _RanIt _Last2, _Pr _Pred)
	{	// copy [_First1, _Last1) into [_First2, _Last2) using _Pred
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_RANGE(_First2, _Last2);
	return (_Rechecked(_First2,
		_Partial_sort_copy_unchecked(
			_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2), _Pred)));
	}

		// TEMPLATE FUNCTION partial_sort_copy
template<class _InIt,
	class _RanIt> inline
	_RanIt partial_sort_copy(_InIt _First1, _InIt _Last1,
		_RanIt _First2, _RanIt _Last2)
	{	// copy [_First1, _Last1) into [_First2, _Last2), using operator<
	return (_STD partial_sort_copy(_First1, _Last1, _First2, _Last2,
		less<>()));
	}

		// TEMPLATE FUNCTION nth_element WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _Nth_element_unchecked(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr& _Pred)
	{	// order Nth element, using _Pred
	if (_Nth == _Last)
		return;	// nothing to do

	for (; _ISORT_MAX < _Last - _First; )
		{	// divide and conquer, ordering partition containing Nth
		pair<_RanIt, _RanIt> _Mid =
			_Partition_by_median_guess_unchecked(_First, _Last, _Pred);

		if (_Mid.second <= _Nth)
			_First = _Mid.second;
		else if (_Mid.first <= _Nth)
			return;	// Nth inside fat pivot, done
		else
			_Last = _Mid.first;
		}

	_Insertion_sort_unchecked(_First, _Last, _Pred);	// sort any remainder
	}

template<class _RanIt,
	class _Pr> inline
	void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
	{	// order Nth element, using _Pred
	_DEBUG_RANGE(_First, _Nth);
	_DEBUG_RANGE(_Nth, _Last);
	_DEBUG_POINTER_IF(2 <= _Last - _First, _Pred);
	_Nth_element_unchecked(
		_Unchecked(_First), _Unchecked(_Nth), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION nth_element
template<class _RanIt> inline
	void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last)
	{	// order Nth element, using operator<
	_STD nth_element(_First, _Nth, _Last, less<>());
	}

		// TEMPLATE FUNCTION includes WITH PRED
template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	bool _Includes_unchecked(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _Pr& _Pred)
	{	// test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
	for (; _First1 != _Last1 && _First2 != _Last2; )
		if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
			return (false);
		else if (_Pred(*_First1, *_First2))
			++_First1;
		else
			{	// advance both
			++_First1;
			++_First2;
			}

	return (_First2 == _Last2);
	}

template<class _InIt1,
	class _InIt2,
	class _Pr> inline
	bool includes(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
	{	// test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
	return (_Includes_unchecked(_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2), _Pred));
	}

		// TEMPLATE FUNCTION includes
template<class _InIt1,
	class _InIt2> inline
	bool includes(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2)
	{	// test if all [_First1, _Last1) in [_First2, _Last2), using operator<
	return (_STD includes(_First1, _Last1, _First2, _Last2,
		less<>()));
	}

		// TEMPLATE FUNCTION set_union WITH PRED
template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_union_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr& _Pred)
	{	// OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred, no deprecation warnings
	for (; _First1 != _Last1 && _First2 != _Last2; )
		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
			{	// copy first
			*_Dest++ = *_First1;
			++_First1;
			}
		else if (_Pred(*_First2, *_First1))
			{	// copy second
			*_Dest++ = *_First2;
			++_First2;
			}
		else
			{	// advance both
			*_Dest++ = *_First1;
			++_First1;
			++_First2;
			}
	_Dest = _Copy_no_deprecate(_First1, _Last1, _Dest);
	return (_Copy_no_deprecate(_First2, _Last2, _Dest));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_union_no_deprecate(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr& _Pred)
	{	// OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred, no deprecation warnings
	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
	_DEBUG_POINTER_IF(_First1 != _Last1 || _First2 != _Last2, _Dest);
	return (_Rechecked(_Dest,
		_Set_union_no_deprecate1(_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2),
		_Unchecked_idl0(_Dest), _Pred)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
	{	// OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
	_DEPRECATE_UNCHECKED(set_union, _Dest);
	return (_Set_union_no_deprecate(_First1, _Last1, _First2, _Last2, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *set_union(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutTy (&_Dest)[_OutSize], _Pr _Pred)
	{	// OR sets [_First1, _Last1) and [_First2, _Last2), array dest
	return (_Unchecked(
		_Set_union_no_deprecate(_First1, _Last1,
			_First2, _Last2,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION set_union
template<class _InIt1,
	class _InIt2,
	class _OutIt> inline
	_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
	{	// OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
	return (_STD set_union(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *set_union(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutTy (&_Dest)[_OutSize])
	{	// OR sets [_First1, _Last1) and [_First2, _Last2), array dest
	return (_STD set_union(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION set_intersection WITH PRED
template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_intersection_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr& _Pred)
	{	// AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred, no deprecation warnings
	for (; _First1 != _Last1 && _First2 != _Last2; )
		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
			++_First1;
		else if (_Pred(*_First2, *_First1))
			++_First2;
		else
			{	// validate _Dest and copy equivalent
			_DEBUG_POINTER(_Dest);
			*_Dest++ = *_First1++;
			++_First2;
			}

	return (_Dest);
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_intersection_no_deprecate(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr& _Pred)
	{	// AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred, no deprecation warnings
	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
	return (_Rechecked(_Dest,
		_Set_intersection_no_deprecate1(_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2),
		_Unchecked_idl0(_Dest), _Pred)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
	{	// AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
	_DEPRECATE_UNCHECKED(set_intersection, _Dest);
	return (_Set_intersection_no_deprecate(_First1, _Last1, _First2, _Last2, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *set_intersection(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutTy (&_Dest)[_OutSize], _Pr _Pred)
	{	// AND sets [_First1, _Last1) and [_First2, _Last2), array dest
	return (_Unchecked(
		_Set_intersection_no_deprecate(_First1, _Last1,
			_First2, _Last2,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION set_intersection
template<class _InIt1,
	class _InIt2,
	class _OutIt> inline
	_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
	{	// AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
	return (_STD set_intersection(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *set_intersection(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutTy (&_Dest)[_OutSize])
	{	// AND sets [_First1, _Last1) and [_First2, _Last2), array dest
	return (_STD set_intersection(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION set_difference WITH PRED
template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_difference_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred)
	{	// take set [_First2, _Last2) from [_First1, _Last1), using _Pred, no deprecation warnings
	for (; _First1 != _Last1 && _First2 != _Last2; )
		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
			{	// validate _Dest and copy first
			_DEBUG_POINTER(_Dest);
			*_Dest++ = *_First1;
			++_First1;
			}
		else if (_Pred(*_First2, *_First1))
			++_First2;
		else
			{	// advance both
			++_First1;
			++_First2;
			}

	return (_Copy_no_deprecate(_First1, _Last1, _Dest));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_difference_no_deprecate(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred)
	{	// take set [_First2, _Last2) from [_First1, _Last1), using _Pred, no deprecation warnings
	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
	return (_Rechecked(_Dest,
		_Set_difference_no_deprecate1(_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2),
		_Unchecked_idl0(_Dest), _Pred)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr _Pred)
	{	// take set [_First2, _Last2) from [_First1, _Last1), using _Pred
	_DEPRECATE_UNCHECKED(set_difference, _Dest);
	return (_Set_difference_no_deprecate(_First1, _Last1, _First2, _Last2, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *set_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutTy (&_Dest)[_OutSize], _Pr _Pred)
	{	// take set [_First2, _Last2) from [_First1, _Last1), array dest
	return (_Unchecked(
		_Set_difference_no_deprecate(_First1, _Last1,
			_First2, _Last2,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION set_difference
template<class _InIt1,
	class _InIt2,
	class _OutIt> inline
	_OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest)
	{	// take set [_First2, _Last2) from [_First1, _Last1), using operator<
	return (_STD set_difference(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *set_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutTy (&_Dest)[_OutSize])
	{	// take set [_First2, _Last2) from [_First1, _Last1), array dest
	return (_STD set_difference(_First1, _Last1, _First2, _Last2, _Dest,
		less<>()));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION set_symmetric_difference WITH PRED
template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_symmetric_difference_no_deprecate1(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred)
	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred, no deprecation warnings
	for (; _First1 != _Last1 && _First2 != _Last2; )
		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
			{	// validate _Dest and copy first
			_DEBUG_POINTER(_Dest);
			*_Dest++ = *_First1;
			++_First1;
			}
		else if (_Pred(*_First2, *_First1))
			{	// validate _Dest and copy second
			_DEBUG_POINTER(_Dest);
			*_Dest++ = *_First2;
			++_First2;
			}
		else
			{	// advance both
			++_First1;
			++_First2;
			}
	_Dest = _Copy_no_deprecate(_First1, _Last1, _Dest);
	return (_Copy_no_deprecate(_First2, _Last2, _Dest));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt _Set_symmetric_difference_no_deprecate(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr& _Pred)
	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred, no deprecation warnings
	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
	return (_Rechecked(_Dest,
		_Set_symmetric_difference_no_deprecate1(
		_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2),
		_Unchecked_idl0(_Dest), _Pred)));
	}

template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Pr> inline
	_OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest, _Pr _Pred)
	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
	_DEPRECATE_UNCHECKED(set_symmetric_difference, _Dest);
	return (_Set_symmetric_difference_no_deprecate(
		_First1, _Last1, _First2, _Last2, _Dest, _Pred));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutTy (&_Dest)[_OutSize], _Pr _Pred)
	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), array dest
	return (_Unchecked(
		_Set_symmetric_difference_no_deprecate(_First1, _Last1,
			_First2, _Last2,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION set_symmetric_difference
template<class _InIt1,
	class _InIt2,
	class _OutIt> inline
	_OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutIt _Dest)
	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
	return (_STD set_symmetric_difference(_First1, _Last1, _First2, _Last2,
		_Dest, less<>()));
	}

 #if _ITERATOR_DEBUG_ARRAY_OVERLOADS
template<class _InIt1,
	class _InIt2,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2,
		_OutTy (&_Dest)[_OutSize])
	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), array dest
	return (_STD set_symmetric_difference(_First1, _Last1, _First2, _Last2,
		_Dest, less<>()));
	}
 #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */

		// TEMPLATE FUNCTION max_element WITH PRED
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Max_element_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// find largest element, using _Pred
	_FwdIt _Found = _First;
	if (_First != _Last)
		for (; ++_First != _Last; )
			if (_DEBUG_LT_PRED(_Pred, *_Found, *_First))
				_Found = _First;
	return (_Found);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt max_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find largest element, using _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Max_element_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION max_element
template<class _FwdIt> inline
	_FwdIt max_element(_FwdIt _First, _FwdIt _Last)
	{	// find largest element, using operator<
	return (_STD max_element(_First, _Last, less<>()));
	}

		// TEMPLATE FUNCTION min_element WITH PRED
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Min_element_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// find smallest element, using _Pred
	_FwdIt _Found = _First;
	if (_First != _Last)
		for (; ++_First != _Last; )
			if (_DEBUG_LT_PRED(_Pred, *_First, *_Found))
				_Found = _First;
	return (_Found);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt min_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find smallest element, using _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Min_element_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION min_element
template<class _FwdIt> inline
	_FwdIt min_element(_FwdIt _First, _FwdIt _Last)
	{	// find smallest element, using operator<
	return (_STD min_element(_First, _Last, less<>()));
	}

		// TEMPLATE FUNCTION minmax_element WITH PRED
template<class _FwdIt,
	class _Pr> inline
	pair<_FwdIt, _FwdIt>
		_Minmax_element_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// find smallest and largest elements, using _Pred
	pair<_FwdIt, _FwdIt> _Found(_First, _First);

	if (_First != _Last)
		for (; ++_First != _Last; )
			{	// process one or two elements
			_FwdIt _Next = _First;
			if (++_Next == _Last)
				{	// process last element
				if (_DEBUG_LT_PRED(_Pred, *_First, *_Found.first))
					_Found.first = _First;
				else if (!_DEBUG_LT_PRED(_Pred, *_First, *_Found.second))
					_Found.second = _First;
				}
			else
				{	// process next two elements
				if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
					{	// test _Next for new smallest
					if (_DEBUG_LT_PRED(_Pred, *_Next, *_Found.first))
						_Found.first = _Next;
					if (!_DEBUG_LT_PRED(_Pred, *_First, *_Found.second))
						_Found.second = _First;
					}
				else
					{	// test _First for new smallest
					if (_DEBUG_LT_PRED(_Pred, *_First, *_Found.first))
						_Found.first = _First;
					if (!_DEBUG_LT_PRED(_Pred, *_Next, *_Found.second))
						_Found.second = _Next;
					}
				_First = _Next;
				}
			}

	return (_Found);
	}

template<class _FwdIt,
	class _Pr> inline
	pair<_FwdIt, _FwdIt>
		minmax_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find smallest and largest elements, using _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked_both(_First, _Last,
		_Minmax_element_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION minmax_element
template<class _FwdIt> inline
	pair<_FwdIt, _FwdIt>
		minmax_element(_FwdIt _First, _FwdIt _Last)
	{	// find smallest and largest elements, using operator<
	return (_STD minmax_element(_First, _Last, less<>()));
	}

		// TEMPLATE FUNCTION max WITH PRED
template<class _Ty,
	class _Pr> inline
	constexpr const _Ty& (max)(const _Ty& _Left, const _Ty& _Right,
		_Pr _Pred)
		_NOEXCEPT_OP(_NOEXCEPT_OP(_DEBUG_LT_PRED(_Pred, _Left, _Right)))
	{	// return larger of _Left and _Right using _Pred
	return (_DEBUG_LT_PRED(_Pred, _Left, _Right) ? _Right : _Left);
	}

template<class _Ty,
	class _Pr> inline
	/* constexpr */	// TRANSITION
	_Ty (max)(_XSTD initializer_list<_Ty> _Ilist, _Pr _Pred)
	{	// return leftmost/largest
	const _Ty *_Res = _Max_element_unchecked(_Ilist.begin(), _Ilist.end(), _Pred);
	return (*_Res);
	}

		// TEMPLATE FUNCTION max
template<class _Ty> inline

	_Post_equal_to_(_Left < _Right ? _Right : _Left)

	constexpr const _Ty& (max)(const _Ty& _Left, const _Ty& _Right)
		_NOEXCEPT_OP(_NOEXCEPT_OP(_DEBUG_LT(_Left, _Right)))
	{	// return larger of _Left and _Right
	return (_DEBUG_LT(_Left, _Right) ? _Right : _Left);
	}

template<class _Ty> inline
	/* constexpr */	// TRANSITION
	_Ty (max)(_XSTD initializer_list<_Ty> _Ilist)
	{	// return leftmost/largest
	return ((_STD max)(_Ilist, less<>()));
	}

		// TEMPLATE FUNCTION min WITH PRED
template<class _Ty,
	class _Pr> inline
	constexpr const _Ty& (min)(const _Ty& _Left, const _Ty& _Right,
		_Pr _Pred)
		_NOEXCEPT_OP(_NOEXCEPT_OP(_DEBUG_LT_PRED(_Pred, _Right, _Left)))
	{	// return smaller of _Left and _Right using _Pred
	return (_DEBUG_LT_PRED(_Pred, _Right, _Left) ? _Right : _Left);
	}

template<class _Ty,
	class _Pr> inline
	/* constexpr */	// TRANSITION
	_Ty (min)(_XSTD initializer_list<_Ty> _Ilist, _Pr _Pred)
	{	// return leftmost/smallest
	const _Ty *_Res = _Min_element_unchecked(_Ilist.begin(), _Ilist.end(), _Pred);
	return (*_Res);
	}

		// TEMPLATE FUNCTION min
template<class _Ty> inline

	_Post_equal_to_(_Right < _Left ? _Right : _Left)

	constexpr const _Ty& (min)(const _Ty& _Left, const _Ty& _Right)
		_NOEXCEPT_OP(_NOEXCEPT_OP(_DEBUG_LT(_Right, _Left)))
	{	// return smaller of _Left and _Right
	return (_DEBUG_LT(_Right, _Left) ? _Right : _Left);
	}

template<class _Ty> inline
	/* constexpr */	// TRANSITION
	_Ty (min)(_XSTD initializer_list<_Ty> _Ilist)
	{	// return leftmost/smallest
	return ((_STD min)(_Ilist, less<>()));
	}


		// TEMPLATE FUNCTION minmax WITH PRED
template<class _Ty,
	class _Pr> inline
	constexpr pair<const _Ty&, const _Ty&>
		minmax(const _Ty& _Left, const _Ty& _Right, _Pr _Pred)
	{	// return pair(leftmost/smaller, rightmost/larger) of _Left and _Right
	return (_Pred(_Right, _Left)
		? pair<const _Ty&, const _Ty&>(_Right, _Left)
		: pair<const _Ty&, const _Ty&>(_Left, _Right));
	}

template<class _Ty,
	class _Pr> inline
	/* constexpr */	// TRANSITION
	pair<_Ty, _Ty> minmax(_XSTD initializer_list<_Ty> _Ilist,
		_Pr _Pred)
	{	// return {leftmost/smallest, rightmost/largest}
	pair<const _Ty *, const _Ty *> _Res = _Minmax_element_unchecked(
		_Ilist.begin(), _Ilist.end(), _Pred);
	return (pair<_Ty, _Ty>(*_Res.first, *_Res.second));
	}

		// TEMPLATE FUNCTION minmax
template<class _Ty> inline
	constexpr pair<const _Ty&, const _Ty&>
		minmax(const _Ty& _Left, const _Ty& _Right)
	{	// return pair(leftmost/smaller, rightmost/larger) of _Left and _Right
	return (_Right < _Left
		? pair<const _Ty&, const _Ty&>(_Right, _Left)
		: pair<const _Ty&, const _Ty&>(_Left, _Right));
	}

template<class _Ty> inline
	/* constexpr */	// TRANSITION
	pair<_Ty, _Ty> minmax(_XSTD initializer_list<_Ty> _Ilist)
	{	// return {leftmost/smallest, rightmost/largest}
	return (_STD minmax(_Ilist, less<>()));
	}

		// TEMPLATE FUNCTION next_permutation WITH PRED
template<class _BidIt,
	class _Pr> inline
	bool _Next_permutation_unchecked(_BidIt _First, _BidIt _Last, _Pr& _Pred)
	{	// permute and test for pure ascending, using _Pred
	_BidIt _Next = _Last;
	if (_First == _Last || _First == --_Next)
		return (false);

	for (; ; )
		{	// find rightmost element smaller than successor
		_BidIt _Next1 = _Next;
		if (_DEBUG_LT_PRED(_Pred, *--_Next, *_Next1))
			{	// swap with rightmost element that's smaller, flip suffix
			_BidIt _Mid = _Last;
			for (; !_DEBUG_LT_PRED(_Pred, *_Next, *--_Mid); )
				;
			_STD iter_swap(_Next, _Mid);
			_Reverse_unchecked(_Next1, _Last);
			return (true);
			}

		if (_Next == _First)
			{	// pure descending, flip all
			_Reverse_unchecked(_First, _Last);
			return (false);
			}
		}
	}

template<class _BidIt,
	class _Pr> inline
	bool next_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
	{	// permute and test for pure ascending, using _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Next_permutation_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION next_permutation
template<class _BidIt> inline
	bool next_permutation(_BidIt _First, _BidIt _Last)
	{	// permute and test for pure ascending, using operator<
	return (_STD next_permutation(_First, _Last, less<>()));
	}

		// TEMPLATE FUNCTION prev_permutation WITH PRED
template<class _BidIt,
	class _Pr> inline
	bool _Prev_permutation_unchecked(_BidIt _First, _BidIt _Last, _Pr& _Pred)
	{	// reverse permute and test for pure descending, using _Pred
	_BidIt _Next = _Last;
	if (_First == _Last || _First == --_Next)
		return (false);

	for (; ; )
		{	// find rightmost element not smaller than successor
		_BidIt _Next1 = _Next;
		if (_DEBUG_LT_PRED(_Pred, *_Next1, *--_Next))
			{	// swap with rightmost element that's not smaller, flip suffix
			_BidIt _Mid = _Last;
			for (; !_DEBUG_LT_PRED(_Pred, *--_Mid, *_Next); )
				;
			_STD iter_swap(_Next, _Mid);
			_Reverse_unchecked(_Next1, _Last);
			return (true);
			}

		if (_Next == _First)
			{	// pure ascending, flip all
			_Reverse_unchecked(_First, _Last);
			return (false);
			}
		}
	}

template<class _BidIt,
	class _Pr> inline
	bool prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
	{	// reverse permute and test for pure descending, using _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	return (_Prev_permutation_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION prev_permutation
template<class _BidIt> inline
	bool prev_permutation(_BidIt _First, _BidIt _Last)
	{	// reverse permute and test for pure descending, using operator<
	return (_STD prev_permutation(_First, _Last, less<>()));
	}

		// TEMPLATE FUNCTIONS is_heap AND is_heap_until WITH PRED
template<class _RanIt,
	class _Pr> inline
	_RanIt _Is_heap_until_unchecked(_RanIt _First, _RanIt _Last, _Pr& _Pred)
	{	// find extent of range that is a heap ordered by _Pred
	_Iter_diff_t<_RanIt> _Size = _Last - _First;

	if (2 <= _Size)
		for (_Iter_diff_t<_RanIt> _Off = 0; ++_Off < _Size; )
			if (_DEBUG_LT_PRED(_Pred, *(_First + (_Off - 1) / 2),
				*(_First + _Off)))
				return (_First + _Off);
	return (_Last);
	}

template<class _RanIt,
	class _Pr> inline
	_RanIt is_heap_until(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// find extent of range that is a heap ordered by _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Is_heap_until_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

template<class _RanIt,
	class _Pr> inline
	bool is_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// test if range is a heap ordered by _Pred
	_DEBUG_RANGE(_First, _Last);
	return (_Is_heap_until_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred) == _Unchecked(_Last));
	}

		// TEMPLATE FUNCTIONS is_heap AND is_heap_until
template<class _RanIt> inline
	_RanIt is_heap_until(_RanIt _First, _RanIt _Last)
	{	// find extent of range that is a heap ordered by operator<
	return (_STD is_heap_until(_First, _Last, less<>()));
	}

template<class _RanIt> inline
	bool is_heap(_RanIt _First, _RanIt _Last)
	{	// test if range is a heap ordered by operator<
	return (_STD is_heap(_First, _Last, less<>()));
	}

		// TEMPLATE FUNCTIONS is_sorted AND is_sorted_until WITH PRED
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Is_sorted_until_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
	{	// find extent of range that is ordered by predicate
	if (_First != _Last)
		for (_FwdIt _Next = _First; ++_Next != _Last; ++_First)
			if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
				return (_Next);
	return (_Last);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt is_sorted_until(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find extent of range that is ordered by predicate
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Is_sorted_until_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

template<class _FwdIt,
	class _Pr> inline
	bool is_sorted(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// test if range is ordered by predicate
	_DEBUG_RANGE(_First, _Last);
	return (_Is_sorted_until_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred) == _Unchecked(_Last));
	}

		// TEMPLATE FUNCTIONS is_sorted AND is_sorted_until
template<class _FwdIt> inline
	_FwdIt is_sorted_until(_FwdIt _First, _FwdIt _Last)
	{	// find extent of range that is ordered by operator<
	return (_STD is_sorted_until(_First, _Last, less<>()));
	}

template<class _FwdIt> inline
	bool is_sorted(_FwdIt _First, _FwdIt _Last)
	{	// test if range is ordered by operator<
	return (_STD is_sorted(_First, _Last, less<>()));
	}

#if _HAS_CXX17
		// FUNCTION TEMPLATE clamp
template<class _Ty,
	class _Pr>
	constexpr const _Ty& clamp(const _Ty& _Val, const _Ty& _Min_val,
		const _Ty& _Max_val, _Pr _Pred)
	{	// returns _Val constrained to [_Min_val, _Max_val] ordered by _Pred
#if _ITERATOR_DEBUG_LEVEL == 2
	return (_DEBUG_LT_PRED(_Pred, _Max_val, _Min_val)
		? (_DEBUG_ERROR("invalid bounds arguments passed to std::clamp"), _Val)
		: _DEBUG_LT_PRED(_Pred, _Max_val, _Val)
			? _Max_val
			: _DEBUG_LT_PRED(_Pred, _Val, _Min_val)
				? _Min_val
				: _Val);
#else /* ^^^ _ITERATOR_DEBUG_LEVEL == 2 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 2 vvv */
	return (_Pred(_Max_val, _Val)
		? _Max_val
		: _Pred(_Val, _Min_val)
			? _Min_val
			: _Val);
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
	}

template<class _Ty>
	constexpr const _Ty& clamp(const _Ty& _Val, const _Ty& _Min_val,
		const _Ty& _Max_val)
	{	// returns _Val constrained to [_Min_val, _Max_val]
	return (_STD clamp(_Val, _Min_val, _Max_val, less<>()));
	}
#endif /* _HAS_CXX17 */

_STD_END
 #pragma pop_macro("new")
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _ALGORITHM_ */

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
