algorithm

vc6.0完整版

			_V = *_F, *_X++ = _V;
	return (_X); }
template<class _FI, class _OI, class _Pr> inline
	_OI _Unique_copy(_FI _F, _FI _L, _OI _X, _Pr _P,
		forward_iterator_tag)
	{_FI _Fb = _F;
	for (*_X++ = *_Fb; ++_F != _L; )
		if (!_P(*_Fb, *_F))
			_Fb = _F, *_X++ = *_Fb;
	return (_X); }
template<class _BI, class _OI, class _Pr> inline
	_OI _Unique_copy(_BI _F, _BI _L, _OI _X, _Pr _P,
		bidirectional_iterator_tag)
	{return (_Unique_copy(_F, _L, _X, _P,
		forward_iterator_tag())); }
template<class _RI, class _OI, class _Pr> inline
	_OI _Unique_copy(_RI _F, _RI _L, _OI _X, _Pr _P,
		random_access_iterator_tag)
	{return (_Unique_copy(_F, _L, _X, _P,
		forward_iterator_tag())); }
		// TEMPLATE FUNCTION reverse
template<class _BI> inline
	void reverse(_BI _F, _BI _L)
	{_Reverse(_F, _L, _Iter_cat(_F)); }
template<class _BI> inline
	void _Reverse(_BI _F, _BI _L, bidirectional_iterator_tag)
	{for (; _F != _L && _F != --_L; ++_F)
		iter_swap(_F, _L); }
template<class _RI> inline
	void _Reverse(_RI _F, _RI _L, random_access_iterator_tag)
	{for (; _F < _L; ++_F)
		iter_swap(_F, --_L); }
		// TEMPLATE FUNCTION reverse_copy
template<class _BI, class _OI> inline
	_OI reverse_copy(_BI _F, _BI _L, _OI _X)
	{for (; _F != _L; ++_X)
		*_X = *--_L;
	return (_X); }
		// TEMPLATE FUNCTION rotate
template<class _FI> inline
	void rotate(_FI _F, _FI _M, _FI _L)
	{if (_F != _M && _M != _L)
		_Rotate(_F, _M, _L, _Iter_cat(_F)); }
template<class _FI> inline
	void _Rotate(_FI _F, _FI _M, _FI _L,
		forward_iterator_tag)
	{for (_FI _X = _M; ; )
		{iter_swap(_F, _X);
		if (++_F == _M)
			if (++_X == _L)
				break;
			else
				_M = _X;
		else if (++_X == _L)
			_X = _M; }}
template<class _BI> inline
	void _Rotate(_BI _F, _BI _M, _BI _L,
		bidirectional_iterator_tag)
	{reverse(_F, _M);
	reverse(_M, _L);
	reverse(_F, _L); }
template<class _RI> inline
	void _Rotate(_RI _F, _RI _M, _RI _L,
			random_access_iterator_tag)
	{_Rotate(_F, _M, _L, _Dist_type(_F), _Val_type(_F)); }
template<class _RI, class _Pd, class _Ty> inline
	void _Rotate(_RI _F, _RI _M, _RI _L, _Pd *, _Ty *)
	{_Pd _D = _M - _F;
	_Pd _N = _L - _F;
	for (_Pd _I = _D; _I != 0; )
		{_Pd _J = _N % _I;
		_N = _I, _I = _J; }
	if (_N < _L - _F)
		for (; 0 < _N; --_N)
			{_RI _X = _F + _N;
			_RI _Y = _X;
			_Ty _V = *_X;
			_RI _Z = _Y + _D == _L ? _F : _Y + _D;
			while (_Z != _X)
				{*_Y = *_Z;
				_Y = _Z;
				_Z = _D < _L - _Z ? _Z + _D
					: _F + (_D - (_L - _Z)); }
			*_Y = _V; }}
		// TEMPLATE FUNCTION rotate_copy
template<class _FI, class _OI> inline
	_OI rotate_copy(_FI _F, _FI _M, _FI _L, _OI _X)
	{return (copy(_F, _M, copy(_M, _L, _X))); }
		// TEMPLATE FUNCTION random_shuffle
template<class _RI> inline
	void random_shuffle(_RI _F, _RI _L)
	{if (_F != _L)
		_Random_shuffle(_F, _L, _Dist_type(_F)); }
template<class _RI, class _Pd> inline
	void _Random_shuffle(_RI _F, _RI _L, _Pd *)
	{const int _RBITS = 15;
	const int _RMAX = (1U << _RBITS) - 1;
	_RI _X = _F;
	for (_Pd _D = 1; ++_X != _L; ++_D)
		{unsigned long _Rm = _RMAX;
		unsigned long _Rn = rand() & _RMAX;
		for (; _Rm < _D && _Rm != ~0UL;
			_Rm = _Rm << _RBITS | _RMAX)
			_Rn = _Rn << _RBITS | _RMAX;
		iter_swap(_X, _F + _Pd(_Rn % _D)); }}
template<class _RI, class _Pf> inline
	void random_shuffle(_RI _F, _RI _L, _Pf& _R)
	{if (_F != _L)
		_Random_shuffle(_F, _L, _R, _Dist_type(_F)); }
template<class _RI, class _Pf, class _Pd> inline
	void _Random_shuffle(_RI _F, _RI _L, _Pf& _R, _Pd *)
	{_RI _X = _F;
	for (_Pd _D = 1; ++_X != _L; ++_D)
		iter_swap(_X, _F + _Pd(_R(_D))); }
		// TEMPLATE FUNCTION partition
template<class _BI, class _Pr> inline
	_BI partition(_BI _F, _BI _L, _Pr _P)
	{for (; ; ++_F)
		{for (; _F != _L && _P(*_F); ++_F)
			;
		if (_F == _L)
			break;
		for (; _F != --_L && !_P(*_L); )
			;
		if (_F == _L)
			break;
		iter_swap(_F, _L); }
	return (_F); }
		// TEMPLATE FUNCTION stable_partition
template<class _FI, class _Pr> inline
	_FI stable_partition(_FI _F, _FI _L, _Pr _P)
	{return (_F == _L ? _F : _Stable_partition(_F, _L, _P,
		_Dist_type(_F), _Val_type(_F))); }
template<class _FI, class _Pr, class _Pd, class _Ty> inline
	_FI _Stable_partition(_FI _F, _FI _L, _Pr _P, _Pd *, _Ty *)
	{_Pd _N = 0;
	_Distance(_F, _L, _N);
	_Temp_iterator<_Ty> _Xb(_N);
	return (_Stable_partition(_F, _L, _P, _N, _Xb)); }
template<class _FI, class _Pr, class _Pd, class _Ty> inline
	_FI _Stable_partition(_FI _F, _FI _L, _Pr _P, _Pd _N,
		_Temp_iterator<_Ty>& _Xb)
	{if (_N == 1)
		return (_P(*_F) ? _L : _F);
	else if (_N <= _Xb._Maxlen())
		{_FI _X = _F;
		for (_Xb._Init(); _F != _L; ++_F)
			if (_P(*_F))
				*_X++ = *_F;
			else
				*_Xb++ = *_F;
		copy(_Xb._First(), _Xb._Last(), _X);
		return (_X); }
	else
		{_FI _M = _F;
		advance(_M, _N / 2);
		_FI _Lp = _Stable_partition(_F, _M, _P, _N / 2, _Xb);
		_FI _Rp = _Stable_partition(_M, _L, _P, _N - _N / 2, _Xb);
		_Pd _D1 = 0;
		_Distance(_Lp, _M, _D1);
		_Pd _D2 = 0;
		_Distance(_M, _Rp, _D2);
		return (_Buffered_rotate(_Lp, _M, _Rp, _D1, _D2, _Xb)); }}
		// TEMPLATE FUNCTION sort
template<class _RI> inline
	void sort(_RI _F, _RI _L)
	{_Sort_0(_F, _L, _Val_type(_F)); }
template<class _RI, class _Ty> inline
	void _Sort_0(_RI _F, _RI _L, _Ty *)
	{if (_L - _F <= _SORT_MAX)
		_Insertion_sort(_F, _L);
	else
		{_Sort(_F, _L, (_Ty *)0);
		_Insertion_sort(_F, _F + _SORT_MAX);
		for (_F += _SORT_MAX; _F != _L; ++_F)
			_Unguarded_insert(_F, _Ty(*_F)); }}
template<class _RI, class _Ty> inline
	void _Sort(_RI _F, _RI _L, _Ty *)
	{for (; _SORT_MAX < _L - _F; )
		{_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
			_Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1))));
		if (_L - _M <= _M - _F)
			_Sort(_M, _L, _Val_type(_F)), _L = _M;
		else
			_Sort(_F, _M, _Val_type(_F)), _F = _M; }}
template<class _RI, class _Ty> inline
	_RI _Unguarded_partition(_RI _F, _RI _L, _Ty _Piv)
	{for (; ; ++_F)
		{for (; *_F < _Piv; ++_F)
			;
		for (; _Piv < *--_L; )
			;
		if (_L <= _F)
			return (_F);
		iter_swap(_F, _L); }}
template<class _RI> inline
	void _Insertion_sort(_RI _F, _RI _L)
	{_Insertion_sort_1(_F, _L, _Val_type(_F)); }
template<class _BI, class _Ty> inline
	void _Insertion_sort_1(_BI _F, _BI _L, _Ty *)
	{if (_F != _L)
		for (_BI _M = _F; ++_M != _L; )
			{_Ty _V = *_M;
			if (!(_V < *_F))
				_Unguarded_insert(_M, _V);
			else
				{copy_backward(_F, _M, _M + 1);
				*_F = _V; }}}
template<class _BI, class _Ty> inline
	void _Unguarded_insert(_BI _L, _Ty _V)
	{for (_BI _M = _L; _V < *--_M; _L = _M)
		*_L = *_M;
	*_L = _V; }
		// TEMPLATE FUNCTION sort WITH PRED
template<class _RI, class _Pr> inline
	void sort(_RI _F, _RI _L, _Pr _P)
	{_Sort_0(_F, _L, _P, _Val_type(_F)); }
template<class _RI, class _Ty, class _Pr> inline
	void _Sort_0(_RI _F, _RI _L, _Pr _P, _Ty *)
	{if (_L - _F <= _SORT_MAX)
		_Insertion_sort(_F, _L, _P);
	else
		{_Sort(_F, _L, _P, (_Ty *)0);
		_Insertion_sort(_F, _F + _SORT_MAX, _P);
		for (_F += _SORT_MAX; _F != _L; ++_F)
			_Unguarded_insert(_F, _Ty(*_F), _P); }}
template<class _RI, class _Ty, class _Pr> inline
	void _Sort(_RI _F, _RI _L, _Pr _P, _Ty *)
	{for (; _SORT_MAX < _L - _F; )
		{_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
			_Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1)), _P), _P);
		if (_L - _M <= _M - _F)
			_Sort(_M, _L, _P, _Val_type(_F)), _L = _M;
		else
			_Sort(_F, _M, _P, _Val_type(_F)), _F = _M; }}
template<class _RI, class _Ty, class _Pr> inline
	_RI _Unguarded_partition(_RI _F, _RI _L, _Ty _Piv, _Pr _P)
	{for (; ; ++_F)
		{for (; _P(*_F, _Piv); ++_F)
			;
		for (; _P(_Piv, *--_L); )
			;
		if (_L <= _F)
			return (_F);
		iter_swap(_F, _L); }}
template<class _RI, class _Pr> inline
	void _Insertion_sort(_RI _F, _RI _L, _Pr _P)
	{_Insertion_sort_1(_F, _L, _P, _Val_type(_F)); }
template<class _RI, class _Ty, class _Pr> inline
	void _Insertion_sort_1(_RI _F, _RI _L, _Pr _P, _Ty *)
	{if (_F != _L)
		for (_RI _M = _F; ++_M != _L; )
			{_Ty _V = *_M;
			if (!_P(_V, *_F))
				_Unguarded_insert(_M, _V, _P);
			else
				{copy_backward(_F, _M, _M + 1);
				*_F = _V; }}}
template<class _RI, class _Ty, class _Pr> inline
	void _Unguarded_insert(_RI _L, _Ty _V, _Pr _P)
	{for (_RI _M = _L; _P(_V, *--_M); _L = _M)
		*_L = *_M;
	*_L = _V; }
		// TEMPLATE FUNCTION stable_sort
template<class _BI> inline
	void stable_sort(_BI _F, _BI _L)
	{if (_F != _L)
		_Stable_sort(_F, _L, _Dist_type(_F), _Val_type(_F)); }
template<class _BI, class _Pd, class _Ty> inline
	void _Stable_sort(_BI _F, _BI _L, _Pd *, _Ty *)
	{_Pd _N = 0;
	_Distance(_F, _L, _N);
	_Temp_iterator<_Ty> _Xb(_N);
	_Stable_sort(_F, _L, _N, _Xb); }
template<class _BI, class _Pd, class _Ty> inline
	void _Stable_sort(_BI _F, _BI _L, _Pd _N,
		_Temp_iterator<_Ty>& _Xb)
	{if (_N <= _SORT_MAX)
		_Insertion_sort(_F, _L);
	else
		{_Pd _N2 = (_N + 1) / 2;
		_BI _M = _F;
		advance(_M, _N2);
		if (_N2 <= _Xb._Maxlen())
			{_Buffered_merge_sort(_F, _M, _N2, _Xb);
			_Buffered_merge_sort(_M, _L, _N - _N2, _Xb); }
		else
			{_Stable_sort(_F, _M, _N2, _Xb);
			_Stable_sort(_M, _L, _N - _N2, _Xb); }
		_Buffered_merge(_F, _M, _L, _N2, _N - _N2, _Xb); }}
template<class _BI, class _Pd, class _Ty> inline
	void _Buffered_merge_sort(_BI _F, _BI _L, _Pd _N,
		_Temp_iterator<_Ty>& _Xb)
	{_BI _M = _F;
	for (_Pd _I = _N; _CHUNK_SIZE <= _I; _I -= _CHUNK_SIZE)
		{_BI _Mn = _M;
		advance(_Mn, (int)_CHUNK_SIZE);
		_Insertion_sort(_M, _Mn);
		_M = _Mn; }
	_Insertion_sort(_M, _L);
	for (_Pd _D = _CHUNK_SIZE; _D < _N; _D *= 2)
		{_BI _Ft = _F;
		_Chunked_merge(_F, _L, _Xb._Init(), _D, _N);
		_Chunked_merge(_Xb._First(), _Xb._Last(), _Ft,
			_D *= 2, _N); }}
template<class _BI, class _OI, class _Pd> inline
	void _Chunked_merge(_BI _F, _BI _L, _OI& _X, _Pd _D, _Pd _N)
	{_Pd _D2 = _D * 2;
	for (; _D2 <= _N; _N -= _D2)
		{_BI _F1 = _F;
		advance(_F1, _D);
		_BI _F2 = _F1;
		advance(_F2, _D);
		_X = merge(_F, _F1, _F1, _F2, _X);
		_F = _F2; }
	if (_N <= _D)
		copy(_F, _L, _X);
	else
		{_BI _F1 = _F;
		advance(_F1, _D);
		merge(_F, _F1, _F1, _L, _X); }}
		// TEMPLATE FUNCTION stable_sort WITH PRED
template<class _BI, class _Pr> inline
	void stable_sort(_BI _F, _BI _L, _Pr _P)
	{if (_F != _L)
		_Stable_sort(_F, _L,
			_Dist_type(_F), _Val_type(_F), _P); }
template<class _BI, class _Pd, class _Ty, class _Pr> inline
	void _Stable_sort(_BI _F, _BI _L, _Pd *, _Ty *, _Pr _P)
	{_Pd _N = 0;
	_Distance(_F, _L, _N);
	_Temp_iterator<_Ty> _Xb(_N);
	_Stable_sort(_F, _L, _N, _Xb, _P); }
template<class _BI, class _Pd, class _Ty, class _Pr> inline
	void _Stable_sort(_BI _F, _BI _L, _Pd _N,
		_Temp_iterator<_Ty>& _Xb, _Pr _P)
	{if (_N <= _SORT_MAX)
		_Insertion_sort(_F, _L, _P);
	else
		{_Pd _N2 = (_N + 1) / 2;
		_BI _M = _F;
		advance(_M, _N2);
		if (_N2 <= _Xb._Maxlen())
			{_Buffered_merge_sort(_F, _M, _N2, _Xb, _P);
			_Buffered_merge_sort(_M, _L, _N - _N2, _Xb, _P); }
		else
			{_Stable_sort(_F, _M, _N2, _Xb, _P);
			_Stable_sort(_M, _L, _N - _N2, _Xb, _P); }
		_Buffered_merge(_F, _M, _L, _N2, _N - _N2, _Xb, _P); }}
template<class _BI, class _Pd, class _Ty, class _Pr> inline
	void _Buffered_merge_sort(_BI _F, _BI _L, _Pd _N,
		_Temp_iterator<_Ty>& _Xb, _Pr _P)
	{_BI _M = _F;
	for (_Pd _I = _N; _CHUNK_SIZE <= _I; _I -= _CHUNK_SIZE)
		{_BI _Mn = _M;
		advance(_Mn, (int)_CHUNK_SIZE);
		_Insertion_sort(_M, _Mn, _P);
		_M = _Mn; }
	_Insertion_sort(_M, _L, _P);
	for (_Pd _D = _CHUNK_SIZE; _D < _N; _D *= 2)
		{_BI _Ft = _F;
		_Chunked_merge(_F, _L, _Xb._Init(), _D, _N, _P);
		_Chunked_merge(_Xb._First(), _Xb._Last(), _Ft,
			_D *= 2, _N, _P); }}
template<class _BI, class _OI, class _Pd, class _Pr> inline
	void _Chunked_merge(_BI _F, _BI _L, _OI& _X,
		_Pd _D, _Pd _N, _Pr _P)
	{_Pd _D2 = _D * 2;
	for (; _D2 <= _N; _N -= _D2)
		{_BI _F1 = _F;
		advance(_F1, _D);
		_BI _F2 = _F1;