algorithm

C语言库函数的原型,有用的拿去

	{	// shuffle [_First, _Last) using random function _Func
	_STLCLRDB_RANGE(_First, _Last);
	cliext::random_shuffle_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Func);
	}

		// TEMPLATE FUNCTION partition
template<class _BidIt,
	class _Pr> inline
	_BidIt partition_unchecked(_BidIt _First, _BidIt _Last, _Pr _Pred)
	{	// move elements satisfying _Pred to beginning of sequence
	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

		cliext::iter_swap(_First, _Last);	// swap out-of-place pair and loop
		}
	return (_First);
	}

template<class _BidIt,
	class _Pr> inline
	_BidIt partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
	{	// move elements satisfying _Pred to beginning of sequence
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Pred);
	return (cliext::partition_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION stable_partition
template<class _BidIt,
	class _Pr,
	class _Diff,
	class _Ty> inline
	_BidIt _XStable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
		_Diff _Count, _Temp_iterator<_Ty> _Tempbuf)
	{	// partition preserving order of equivalents, using _Pred
	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++ = *_First;
			else
				*_Tempbuf++ = *_First;

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

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

		_Diff _Count1 = 0;
		_Iter_distance(_Left, _Mid, _Count1);
		_Diff _Count2 = 0;
		_Iter_distance(_Mid, _Right, _Count2);

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

#if __cplusplus_cli
template<class _BidIt,
	class _Pr,
	class _Diff,
	class _Ty> inline
	_BidIt _XStable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
		_Diff _Count, _Temp_gc_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++ = *_First;
			else
				*_Tempbuf++ = *_First;

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

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

		_Diff _Count1 = 0;
		_Iter_distance(_Left, _Mid, _Count1);
		_Diff _Count2 = 0;
		_Iter_distance(_Mid, _Right, _Count2);

		return (cliext::_XBuffered_rotate(_Left, _Mid, _Right,
			_Count1, _Count2, _Tempbuf));	// rotate L1R1L2R2 to L1L2R1R2
		}
	}
#endif	// __cplusplus_cli

template<class _BidIt,
	class _Pr> inline
	_BidIt stable_partition_unchecked(_BidIt _First, _BidIt _Last,
		_Pr _Pred)
	{	// partition preserving order of equivalents, using _Pred
	typedef iterator_traits<_BidIt>::difference_type _Diff;
	typedef iterator_traits<_BidIt>::value_type _Ty;

	if (_First == _Last)
		return (_First);
	else
		{	// partition nontrivial sequence
		_Diff _Count = 0;
		_Iter_distance(_First, _Last, _Count);
		_TEMP_ITER(_BidIt, _Ty) _Tempbuf(_Count);

		return (cliext::_XStable_partition(_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
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Pred);
	return (cliext::stable_partition_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Pred));

	}

 #if _HAS_ITERATOR_DEBUGGING
		// TEMPLATE FUNCTION _XDebug_heap
template<class _RanIt> inline
	void _XDebug_heap(_RanIt _First, _RanIt _Last)
	{	// test if range is a heap ordered by operator<
	typedef iterator_traits<_RanIt>::difference_type _Diff;

	_Diff _Size = _Last - _First;
	if (2 <= _Size)
		for (_Diff _Off = 0; ++_Off < _Size; )
			if (_STLCLRDB_LT(*(_First + (_Off - 1) / 2), *(_First + _Off)))
				_STLCLRDB_ERROR(L"invalid heap");
	}

		// TEMPLATE FUNCTION _XDebug_heap WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _XDebug_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// test if range is a heap ordered by _Pred
	typedef iterator_traits<_RanIt>::difference_type _Diff;

	_Diff _Size = _Last - _First;
	if (2 <= _Size)
		for (_Diff _Off = 0; ++_Off < _Size; )
			if (_STLCLRDB_LT_PRED(_Pred, *(_First + (_Off - 1) / 2),
				*(_First + _Off)))
				_STLCLRDB_ERROR(L"invalid heap");
	}

  #define _STLCLRDB_HEAP(first, last)	\
	_XDebug_heap(first, last)
  #define _STLCLRDB_HEAP_PRED(first, last, pred)	\
	_XDebug_heap(first, last, pred)

 #else /* _HAS_ITERATOR_DEBUGGING */
  #define _STLCLRDB_HEAP(first, last)
  #define _STLCLRDB_HEAP_PRED(first, last, pred)
 #endif /* _HAS_ITERATOR_DEBUGGING */

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

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

template<class _RanIt> inline
	void push_heap_unchecked(_RanIt _First, _RanIt _Last)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using operator<
	typedef iterator_traits<_RanIt>::difference_type _Diff;
	typedef iterator_traits<_RanIt>::value_type _Ty;

	--_Last;
	_Diff _Count = _Last - _First;
	if (0 < _Count)
		cliext::_XPush_heap(_First, _Count, _Diff(0), _Ty(*_Last));
	}

template<class _RanIt> inline
	void push_heap(_RanIt _First, _RanIt _Last)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using operator<
	typedef iterator_traits<_RanIt>::difference_type _Diff;
	typedef iterator_traits<_RanIt>::value_type _Ty;

	_STLCLRDB_RANGE(_First, _Last);
	if (_First != _Last)
		{	// check and push non-empty heap+addition
		_STLCLRDB_HEAP(_First, _Last - 1);
		cliext::push_heap_unchecked(_Unchecked(_First), _Unchecked(_Last));
		}
	}

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

	*(_First + _Hole) = _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 iterator_traits<_RanIt>::difference_type _Diff;
	typedef iterator_traits<_RanIt>::value_type _Ty;

	--_Last;
	_Diff _Count = _Last - _First;
	if (0 < _Count)
		cliext::_XPush_heap(_First, _Count, _Diff(0), _Ty(*_Last), _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
	typedef iterator_traits<_RanIt>::difference_type _Diff;
	typedef iterator_traits<_RanIt>::value_type _Ty;

	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Pred);
	if (_First != _Last)
		{	// check and push non-empty heap+addition
		_STLCLRDB_HEAP_PRED(_First, _Last - 1, _Pred);
		cliext::push_heap_unchecked(_Unchecked(_First), _Unchecked(_Last),
			_Pred);
		}
	}

		// TEMPLATE FUNCTION pop_heap
template<class _RanIt,
	class _Diff,
	class _Ty> inline
	void _XAdjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom, _Ty _Val)
	{	// percolate _Hole to _Bottom, then push _Val, using operator<
	_Diff _Top = _Hole;
	_Diff _Idx = 2 * _Hole + 2;

	for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
		{	// move _Hole down to larger child
		if (_STLCLRDB_LT(*(_First + _Idx), *(_First + (_Idx - 1))))
			--_Idx;
		*(_First + _Hole) = *(_First + _Idx), _Hole = _Idx;
		}

	if (_Idx == _Bottom)
		{	// only child at bottom, move _Hole down to it
		*(_First + _Hole) = *(_First + (_Bottom - 1));
		_Hole = _Bottom - 1;
		}
	cliext::_XPush_heap(_First, _Hole, _Top, _Val);
	}

template<class _RanIt,
	class _Ty> inline
	void _XPop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
		_Ty _Val)
	{	// pop *_First to *_Dest and reheap, using operator<
	typedef iterator_traits<_RanIt>::difference_type _Diff;

	*_Dest = *_First;
	cliext::_XAdjust_heap(_First, _Diff(0), _Diff(_Last - _First), _Val);
	}

template<class _RanIt> inline
	void pop_heap_unchecked(_RanIt _First, _RanIt _Last)
	{	// pop *_First to *(_Last - 1) and reheap, using operator<
	typedef iterator_traits<_RanIt>::value_type _Ty;

	_XPop_heap(_First, _Last - 1, _Last - 1, _Ty(*(_Last - 1)));
	}

template<class _RanIt> inline
	void pop_heap(_RanIt _First, _RanIt _Last)
	{	// pop *_First to *(_Last - 1) and reheap, using operator<
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_HEAP(_First, _Last);

	if (1 < _Last - _First)
		cliext::pop_heap_unchecked(_Unchecked(_First), _Unchecked(_Last));
	}

		// TEMPLATE FUNCTION pop_heap WITH PRED
template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _XAdjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom,
		_Ty _Val, _Pr _Pred)
	{	// percolate _Hole to _Bottom, then push _Val, using _Pred
	_Diff _Top = _Hole;
	_Diff _Idx = 2 * _Hole + 2;

	for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
		{	// move _Hole down to larger child
		if (_STLCLRDB_LT_PRED(_Pred, *(_First + _Idx),
			*(_First + (_Idx - 1))))
			--_Idx;
		*(_First + _Hole) = *(_First + _Idx), _Hole = _Idx;
		}

	if (_Idx == _Bottom)
		{	// only child at bottom, move _Hole down to it
		*(_First + _Hole) = *(_First + (_Bottom - 1));
		_Hole = _Bottom - 1;
		}
	cliext::_XPush_heap(_First, _Hole, _Top, _Val, _Pred);
	}

template<class _RanIt,
	class _Ty,
	class _Pr> inline
	void _XPop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
		_Ty _Val, _Pr _Pred)
	{	// pop *_First to *_Dest and reheap, using _Pred
	typedef iterator_traits<_RanIt>::difference_type _Diff;

	*_Dest = *_First;
	cliext::_XAdjust_heap(_First, _Diff(0), _Diff(_Last - _First),
		_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
	typedef iterator_traits<_RanIt>::value_type _Ty;

	if (1 < _Last - _First)
		_XPop_heap(_First, _Last - 1, _Last - 1, _Ty(*(_Last - 1)), _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
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Pred);
	_STLCLRDB_HEAP_PRED(_First, _Last, _Pred);
	cliext::pop_heap_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Pred);
	}

		// TEMPLATE FUNCTION make_heap
template<class _RanIt> inline
	void make_heap_unchecked(_RanIt _First, _RanIt _Last)
	{	// make [_First, _Last) into a heap, using operator<
	typedef iterator_traits<_RanIt>::difference_type _Diff;
	typedef iterator_traits<_RanIt>::value_type _Ty;

	if (1 < _Last - _First)
		{	// make nontrivial heap
		_Diff _Bottom = _Last - _First;

		for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
			{	// reheap top half, bottom to top
			--_Hole;
			cliext::_XAdjust_heap(_First, _Hole, _Bottom,
				_Ty(*(_First + _Hole)));
			}
		}
	}

template<class _RanIt> inline
	void make_heap(_RanIt _First, _RanIt _Last)
	{	// make [_First, _Last) into a heap, using operator<
	_STLCLRDB_RANGE(_First, _Last);
	cliext::make_heap_unchecked(_Unchecked(_First), _Unchecked(_Last));