algorithm

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

	}

		// TEMPLATE FUNCTION make_heap WITH PRED
template<class _RanIt,
	class _Pr> inline
	void make_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// make [_First, _Last) into a heap, using _Pred
	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)), _Pred);
			}
		}
	}

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

		// TEMPLATE FUNCTION sort_heap
template<class _RanIt> inline
	void sort_heap_unchecked(_RanIt _First, _RanIt _Last)
	{	// order heap by repeatedly popping, using operator<
	for (; 1 < _Last - _First; --_Last)
		cliext::pop_heap_unchecked(_First, _Last);
	}

template<class _RanIt> inline
	void sort_heap(_RanIt _First, _RanIt _Last)
	{	// order heap by repeatedly popping, using operator<
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_HEAP(_First, _Last);
	cliext::sort_heap_unchecked(_Unchecked(_First), _Unchecked(_Last));
	}

		// 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 (; 1 < _Last - _First; --_Last)
		cliext::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
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Pred);
	_STLCLRDB_HEAP_PRED(_First, _Last, _Pred);
	cliext::sort_heap_unchecked(_Unchecked(_First), _Unchecked(_Last),
		_Pred);
	}

		// TEMPLATE FUNCTION lower_bound
template<class _FwdIt,
	class _Ty> inline
	_FwdIt lower_bound_unchecked(_FwdIt _First, _FwdIt _Last,
		/*const */ _Ty% _Val)
	{	// find first element not before _Val, using operator<
	typedef iterator_traits<_FwdIt>::difference_type _Diff;

	_Diff _Count = 0;
	_Iter_distance(_First, _Last, _Count);

	for (; 0 < _Count; )
		{	// divide and conquer, find half that contains answer
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		cliext::advance(_Mid, _Count2);

		if (_STLCLRDB_LT(*_Mid, _Val))
			_First = ++_Mid, _Count -= _Count2 + 1;
		else
			_Count = _Count2;
		}
	return (_First);
	}

template<class _FwdIt,
	class _Ty> inline
	_FwdIt lower_bound(_FwdIt _First, _FwdIt _Last, /*const */ _Ty% _Val)
	{	// find first element not before _Val, using operator<
	_STLCLRDB_ORDER(_First, _Last);
	return (cliext::lower_bound_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val));
	}

		// 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
	typedef iterator_traits<_FwdIt>::difference_type _Diff;

	_Diff _Count = 0;
	_Iter_distance(_First, _Last, _Count);
	for (; 0 < _Count; )
		{	// divide and conquer, find half that contains answer
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		cliext::advance(_Mid, _Count2);

		if (_STLCLRDB_LT_PRED(_Pred, *_Mid, _Val))
			_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
	_STLCLRDB_ORDER_PRED(_First, _Last, _Pred);
	return (cliext::lower_bound_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val, _Pred));
	}

		// TEMPLATE FUNCTION upper_bound
template<class _FwdIt,
	class _Ty> inline
	_FwdIt upper_bound_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty% _Val)
	{	// find first element that _Val is before, using operator<
	typedef iterator_traits<_FwdIt>::difference_type _Diff;

	_Diff _Count = 0;
	_Iter_distance(_First, _Last, _Count);
	for (; 0 < _Count; )
		{	// divide and conquer, find half that contains answer
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		cliext::advance(_Mid, _Count2);

		if (!_STLCLRDB_LT(_Val, *_Mid))
			_First = ++_Mid, _Count -= _Count2 + 1;
		else
			_Count = _Count2;
		}
	return (_First);
	}

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<
	_STLCLRDB_ORDER(_First, _Last);
	return (cliext::upper_bound_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val));
	}

		// 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
	typedef iterator_traits<_FwdIt>::difference_type _Diff;

	_Diff _Count = 0;
	_Iter_distance(_First, _Last, _Count);
	for (; 0 < _Count; )
		{	// divide and conquer, find half that contains answer
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		cliext::advance(_Mid, _Count2);

		if (!_STLCLRDB_LT_PRED(_Pred, _Val, *_Mid))
			_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
	_STLCLRDB_ORDER_PRED(_First, _Last, _Pred);
	return (cliext::upper_bound_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val, _Pred));
	}

		// TEMPLATE FUNCTION equal_range
template<class _FwdIt,
	class _Ty> inline
	_PAIR_TYPE(_FwdIt) equal_range_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty% _Val)
	{	// find range equivalent to _Val, using operator<
	typedef iterator_traits<_FwdIt>::difference_type _Diff;

	_Diff _Count = 0;
	_Iter_distance(_First, _Last, _Count);

	for (; 0 < _Count; )
		{	// divide and conquer, check midpoint
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		cliext::advance(_Mid, _Count2);

		if (_STLCLRDB_LT(*_Mid, _Val))
			{	// range begins above _Mid, loop
			_First = ++_Mid;
			_Count -= _Count2 + 1;
			}
		else if (_Val < *_Mid)
			_Count = _Count2;	// range in first half, loop
		else
			{	// range straddles mid, find each end and return
			_FwdIt _First2 = lower_bound(_First, _Mid, _Val);
			cliext::advance(_First, _Count);
			_FwdIt _Last2 = upper_bound(++_Mid, _First, _Val);
			return (_PAIR_TYPE(_FwdIt)(_First2, _Last2));
			}
		}

	return (_PAIR_TYPE(_FwdIt)(_First, _First));	// empty range
	}

template<class _FwdIt,
	class _Ty> inline
	_PAIR_TYPE(_FwdIt) equal_range(_FwdIt _First, _FwdIt _Last,
		const _Ty% _Val)
	{	// find range equivalent to _Val, using operator<
	_STLCLRDB_ORDER(_First, _Last);
	return (cliext::equal_range_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val));
	}

		// TEMPLATE FUNCTION equal_range WITH PRED
template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	_PAIR_TYPE(_FwdIt) equal_range_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty% _Val, _Pr _Pred)
	{	// find range equivalent to _Val, using _Pred
	typedef iterator_traits<_FwdIt>::difference_type _Diff;

	_Diff _Count = 0;
	_Iter_distance(_First, _Last, _Count);

	for (; 0 < _Count; )
		{	// divide and conquer, check midpoint
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		cliext::advance(_Mid, _Count2);

		if (_STLCLRDB_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(_First, _Mid, _Val, _Pred);
			cliext::advance(_First, _Count);
			_FwdIt _Last2 = upper_bound(++_Mid, _First, _Val, _Pred);
			return (_PAIR_TYPE(_FwdIt)(_First2, _Last2));
			}
		}

	return (_PAIR_TYPE(_FwdIt)(_First, _First));	// empty range
	}

template<class _FwdIt,
	class _Ty,
	class _Pr> inline
	_PAIR_TYPE(_FwdIt) equal_range(_FwdIt _First, _FwdIt _Last,
		const _Ty% _Val, _Pr _Pred)
	{	// find range equivalent to _Val, using _Pred
	_STLCLRDB_ORDER_PRED(_First, _Last, _Pred);
	return (cliext::equal_range_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val, _Pred));
	}

		// TEMPLATE FUNCTION binary_search
template<class _FwdIt,
	class _Ty> inline
	bool binary_search_unchecked(_FwdIt _First, _FwdIt _Last,
		const _Ty% _Val)
	{	// test if _Val equivalent to some element, using operator<
	_First = cliext::lower_bound_unchecked(_First, _Last, _Val);
	return (_First != _Last && !(_Val < *_First));
	}

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<
	_STLCLRDB_ORDER(_First, _Last);
	return (cliext::binary_search_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val));
	}

		// 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 = cliext::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
	_STLCLRDB_ORDER_PRED(_First, _Last, _Pred);
	return (cliext::binary_search_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Val, _Pred));
	}

		// TEMPLATE FUNCTION merge
template<class _InIt1,
	class _InIt2,
	class _OutIt> inline
	_OutIt merge_unchecked(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
	{	// copy merging ranges, both using operator<
	for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
		if (_STLCLRDB_LT(*_First2, *_First1))
			*_Dest = *_First2, ++_First2;
		else
			*_Dest = *_First1, ++_First1;

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

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<
	_STLCLRDB_ORDER(_First1, _Last1);
	_STLCLRDB_ORDER(_First2, _Last2);
	_STLCLRDB_POINTER(_Dest);
	return (cliext::merge_unchecked(
		_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2),
		_Unchecked(_Dest)));
	}

		// 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
	for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
		if (_STLCLRDB_LT_PRED(_Pred, *_First2, *_First1))
			*_Dest = *_First2, ++_First2;
		else
			*_Dest = *_First1, ++_First1;

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

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
	_STLCLRDB_ORDER_PRED(_First1, _Last1, _Pred);
	_STLCLRDB_ORDER_PRED(_First2, _Last2, _Pred);
	_STLCLRDB_POINTER(_Dest);
	return (cliext::merge_unchecked(
		_Unchecked(_First1), _Unchecked(_Last1),
		_Unchecked(_First2), _Unchecked(_Last2),
		_Unchecked(_Dest), _Pred));
	}

		// TEMPLATE FUNCTION inplace_merge
template<class _BidIt,
	class _Diff,
	class _Ty> inline
	_BidIt _XBuffered_rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temp_iterator<_Ty> _Tempbuf)
	{	// rotate [_First, _Last) using temp buffer
	if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
		{	// buffer left partition, then copy parts
		cliext::copy_unchecked(_First, _Mid, _Tempbuf._Init());
		cliext::copy_unchecked(_Mid, _Last, _First);
		return (cliext::copy_backward_unchecked(
			_Tempbuf._First(), _Tempbuf._Last(), _Last));
		}
	else if (_Count2 <= _Tempbuf._Maxlen())
		{	// buffer right partition, then copy parts
		cliext::copy_unchecked(_Mid, _Last, _Tempbuf._Init());
		cliext::copy_backward_unchecked(_First, _Mid, _Last);
		return