algorithm

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

	_STLCLRDB_RANGE(_First, _Last);
	return (cliext::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 = cliext::find_if_unchecked(_First, _Last, _Pred);
	if (_First == _Last)
		return (_First);	// empty sequence, all done
	else
		{	// nonempty sequence, worth doing
		_FwdIt _First1 = _First;
		return (cliext::remove_copy_if_unchecked(++_First1, _Last,
			_First, _Pred));
		}
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// remove each satisfying _Pred
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Pred);
	return (cliext::remove_if_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION unique
template<class _FwdIt> inline
	_FwdIt unique_unchecked(_FwdIt _First, _FwdIt _Last)
	{	// remove each matching previous
	for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
		if (*_Firstb == *_First)
			{	// copy down
			for (; ++_First != _Last; )
				if (!(*_Firstb == *_First))
					*++_Firstb = *_First;
			return (++_Firstb);
			}
	return (_Last);
	}

template<class _FwdIt> inline
	_FwdIt unique(_FwdIt _First, _FwdIt _Last)
	{	// remove each matching previous
	_STLCLRDB_RANGE(_First, _Last);
	return (cliext::unique_unchecked(
		_Unchecked(_First), _Unchecked(_Last)));
	}

		// 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
	for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
		if (_Pred(*_Firstb, *_First))
			{	// copy down
			for (; ++_First != _Last; )
				if (!_Pred(*_Firstb, *_First))
					*++_Firstb = *_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
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Pred);
	return (cliext::unique_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION unique_copy
template<class _InIt,
	class _OutIt> inline
	_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
		input_iterator_tag)
	{	// copy compressing pairs that match, input iterators
	typedef iterator_traits<_InIt>::value_type _Ty;

	_Ty _Val = *_First;

	for (*_Dest++ = _Val; ++_First != _Last; )
		if (!(_Val == *_First))
			_Val = *_First, *_Dest++ = _Val;
	return (_Dest);
	}

template<class _FwdIt,
	class _OutIt> inline
	_OutIt _Unique_copy(_FwdIt _First, _FwdIt _Last, _OutIt _Dest,
		forward_iterator_tag)
	{	// copy compressing pairs that match, forward iterators
	_FwdIt _Firstb = _First;
	for (*_Dest++ = *_Firstb; ++_First != _Last; )
		if (!(*_Firstb == *_First))
			_Firstb = _First, *_Dest++ = *_Firstb;
	return (_Dest);
	}

template<class _BidIt,
	class _OutIt> inline
	_OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
		bidirectional_iterator_tag)
	{	// copy compressing pairs that match, bidirectional iterators
	return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag()));
	}

template<class _RanIt,
	class _OutIt> inline
	_OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest,
		random_access_iterator_tag)
	{	// copy compressing pairs that match, random-access iterators
	return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag()));
	}

template<class _InIt,
	class _OutIt> inline
	_OutIt unique_copy_unchecked(_InIt _First, _InIt _Last, _OutIt _Dest)
	{	// copy compressing pairs that match
	return (_First == _Last ? _Dest
		: _Unique_copy(_First, _Last, _Dest, _Iter_category(_First)));
	}

template<class _InIt,
	class _OutIt> inline
	_OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
	{	// copy compressing pairs that match
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Dest);
	return (unique_copy_unchecked(
		_Unchecked(_First), _Unchecked(_Last),
		_Unchecked(_Dest)));
	}

		// TEMPLATE FUNCTION unique_copy WITH PRED
template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred,
		input_iterator_tag)
	{	// copy compressing pairs satisfying _Pred, input iterators
	typedef iterator_traits<_InIt>::value_type _Ty;

	_Ty _Val = *_First;

	for (*_Dest++ = _Val; ++_First != _Last; )
		if (!_Pred(_Val, *_First))
			_Val = *_First, *_Dest++ = _Val;
	return (_Dest);
	}

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

	for (*_Dest++ = *_Firstb; ++_First != _Last; )
		if (!_Pred(*_Firstb, *_First))
			_Firstb = _First, *_Dest++ = *_Firstb;
	return (_Dest);
	}

template<class _BidIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest, _Pr _Pred,
		bidirectional_iterator_tag)
	{	// copy compressing pairs satisfying _Pred, bidirectional iterators
	return (_Unique_copy(_First, _Last, _Dest, _Pred,
		forward_iterator_tag()));
	}

template<class _RanIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest, _Pr _Pred,
		random_access_iterator_tag)
	{	// copy compressing pairs satisfying _Pred, random-access iterators
	return (_Unique_copy(_First, _Last, _Dest, _Pred,
		forward_iterator_tag()));
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt unique_copy_unchecked(_InIt _First, _InIt _Last,
		_OutIt _Dest, _Pr _Pred)
	{	// copy compressing pairs satisfying _Pred
	return (_First == _Last ? _Dest
		: _Unique_copy(_First, _Last, _Dest, _Pred, _Iter_category(_First)));
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
	{	// copy compressing pairs satisfying _Pred
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Dest);
	_STLCLRDB_POINTER(_Pred);
	return (unique_copy_unchecked(
		_Unchecked(_First), _Unchecked(_Last),
		_Unchecked(_Dest), _Pred));
	}

		// TEMPLATE FUNCTION reverse
template<class _BidIt> inline
	void _Reverse(_BidIt _First, _BidIt _Last,
		bidirectional_iterator_tag)
	{	// reverse elements in [_First, _Last), bidirectional iterators
	for (; _First != _Last && _First != --_Last; ++_First)
		cliext::iter_swap(_First, _Last);
	}

template<class _RanIt> inline
	void _Reverse(_RanIt _First, _RanIt _Last,
		random_access_iterator_tag)
	{	// reverse elements in [_First, _Last), random-access iterators
	for (; _First < _Last; ++_First)
		cliext::iter_swap(_First, --_Last);
	}

template<class _BidIt> inline
	void reverse_unchecked(_BidIt _First, _BidIt _Last)
	{	// reverse elements in [_First, _Last)
	_Reverse(_First, _Last, _Iter_category(_First));
	}

template<class _BidIt> inline
	void reverse(_BidIt _First, _BidIt _Last)
	{	// reverse elements in [_First, _Last)
	_STLCLRDB_RANGE(_First, _Last);
	reverse_unchecked(_Unchecked(_First), _Unchecked(_Last));
	}

		// 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_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
	{	// copy reversing elements in [_First, _Last)
	_STLCLRDB_RANGE(_First, _Last);
	_STLCLRDB_POINTER(_Dest);
	return (cliext::reverse_copy_unchecked(
		_Unchecked(_First), _Unchecked(_Last), _Unchecked(_Dest)));
	}

		// TEMPLATE FUNCTION rotate
template<class _FwdIt> inline
	void _Rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
		forward_iterator_tag)
	{	// rotate [_First, _Last), forward iterators
	for (_FwdIt _Next = _Mid; ; )
		{	// swap [_First, ...) into place
		cliext::iter_swap(_First, _Next);
		if (++_First == _Mid)
			if (++_Next == _Last)
				break;	// done, quit
			else
				_Mid = _Next;	// mark end of next interval
		else if (++_Next == _Last)
			_Next = _Mid;	// wrap to last end
		}
	}

template<class _BidIt> inline
	void _Rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		bidirectional_iterator_tag)
	{	// rotate [_First, _Last), bidirectional iterators
	cliext::reverse(_First, _Mid);
	cliext::reverse(_Mid, _Last);
	cliext::reverse(_First, _Last);
	}

template<class _RanIt> inline
	void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
			random_access_iterator_tag)
	{	// rotate [_First, _Last), random-access iterators
	typedef iterator_traits<_RanIt>::difference_type _Diff;
	typedef iterator_traits<_RanIt>::value_type _Ty;

	_Diff _Shift = _Mid - _First;
	_Diff _Count = _Last - _First;

	for (_Diff _Factor = _Shift; _Factor != 0; )
		{	// find subcycle count as GCD of shift count and length
		_Diff _Tmp = _Count % _Factor;
		_Count = _Factor, _Factor = _Tmp;
		}

	if (_Count < _Last - _First)
		for (; 0 < _Count; --_Count)
			{	// rotate each subcycle
			_RanIt _Hole = _First + _Count;
			_RanIt _Next = _Hole;
			_Ty _Holeval = *_Hole;
			_RanIt _Next1 = _Next + _Shift == _Last ? _First : _Next + _Shift;
			while (_Next1 != _Hole)
				{	// percolate elements back around subcycle
				*_Next = *_Next1;
				_Next = _Next1;
				_Next1 = _Shift < _Last - _Next1 ? _Next1 + _Shift
					: _First + (_Shift - (_Last - _Next1));
				}
			*_Next = _Holeval;
			}
	}

template<class _FwdIt> inline
	void rotate_unchecked(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last)
	{	// rotate [_First, _Last)
	if (_First != _Mid && _Mid != _Last)
		_Rotate(_First, _Mid, _Last, _Iter_category(_First));
	}

template<class _FwdIt> inline
	void rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last)
	{	// rotate [_First, _Last)
	_STLCLRDB_RANGE(_First, _Mid);
	_STLCLRDB_RANGE(_Mid, _Last);
	if (_First != _Mid && _Mid != _Last)
		_Rotate(_Unchecked(_First), _Unchecked(_Mid), _Unchecked(_Last),
		_Iter_category(_First));
	}

		// 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 = cliext::copy_unchecked(_Mid, _Last, _Dest);
	return (cliext::copy_unchecked(_First, _Mid, _Dest));
	}

template<class _FwdIt,
	class _OutIt> inline
	_OutIt rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
		_OutIt _Dest)
	{	// copy rotating [_First, _Last)
	_STLCLRDB_RANGE(_First, _Mid);
	_STLCLRDB_RANGE(_Mid, _Last);
	_STLCLRDB_POINTER(_Dest);
	return (cliext::rotate_copy_unchecked(
		_Unchecked(_First), _Unchecked(_Mid), _Unchecked(_Last),
		_Unchecked(_Dest)));
	}

		// TEMPLATE FUNCTION random_shuffle
inline int _Rand(void)
	{	/* compute pseudo-random value */
	static long _Randseed = 1;

	_Randseed = _Randseed * 1103515245 + 12345;
	return ((unsigned int)(_Randseed >> 16) & 0x7fff);
	}

template<class _RanIt> inline
	void random_shuffle_unchecked(_RanIt _First, _RanIt _Last)
	{	// shuffle [_First, _Last)
	typedef iterator_traits<_RanIt>::difference_type _Diff;

	if (_First != _Last)
		{	// shuffle nontrivial [_First, _Last)
		const int _RANDOM_BITS = 15;	// minimum random bits from _Rand()
		const int _RANDOM_MAX = (1U << _RANDOM_BITS) - 1;

		_RanIt _Next = _First;
		for (unsigned long _Index = 2; ++_Next != _Last; ++_Index)
			{	// assume unsigned long big enough for _Diff count
			unsigned long _Rm = _RANDOM_MAX;
			unsigned long _Rn = _Rand() & _RANDOM_MAX;
			for (; _Rm < _Index && _Rm != ~0UL;
				_Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX)
				_Rn = _Rn << _RANDOM_BITS
					| (_Rand() & _RANDOM_MAX);	// build random value

			cliext::iter_swap(_Next,
				_First + _Diff(_Rn % _Index));	// swap a pair
			}
		}
	}

template<class _RanIt> inline
	void random_shuffle(_RanIt _First, _RanIt _Last)
	{	// shuffle [_First, _Last)
	_STLCLRDB_RANGE(_First, _Last);
	cliext::random_shuffle_unchecked(
		_Unchecked(_First), _Unchecked(_Last));
	}

		// TEMPLATE FUNCTION random_shuffle WITH RANDOM FN
template<class _RanIt,
	class _Fn1> inline
	void random_shuffle_unchecked(_RanIt _First, _RanIt _Last, _Fn1% _Func)
	{	// shuffle [_First, _Last) using random function _Func
	typedef iterator_traits<_RanIt>::difference_type _Diff;

	if (_First != _Last)
		{	// shuffle nonempty [_First, _Last) using random function _Func
		_RanIt _Next = _First;

		for (_Diff _Index = 2; ++_Next != _Last; ++_Index)
			cliext::iter_swap(_Next, _First + _Diff(_Func(_Index)));
		}
	}

template<class _RanIt,
	class _Fn1> inline
	void random_shuffle(_RanIt _First, _RanIt _Last, _Fn1% _Func)