algorithm

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

template<class _InIt,
	class _OutTy1,
	size_t _OutSize1,
	class _OutIt2,
	class _Pr> inline
	_STD pair<_OutTy1 *, _OutIt2>
		partition_copy(_InIt _First, _InIt _Last,
			_OutTy1 (&_Dest1)[_OutSize1], _OutIt2 _Dest2, _Pr _Pred)
	{	// copy true partition *_Dest1++, false to *_Dest2++, array dest
	_STD pair<_Array_iterator<_OutTy1, _OutSize1>, _OutIt2> _Ans =
		_STD partition_copy(_First, _Last,
			_Array_iterator<_OutTy1, _OutSize1>(_Dest1), _Dest2, _Pred);
	return (_STD pair<_OutTy1 *, _OutIt2>(
		_Unchecked(_Ans.first),
		_Ans.second));
	}

template<class _InIt,
	class _OutIt1,
	class _OutTy2,
	size_t _OutSize2,
	class _Pr> inline
	_STD pair<_OutIt1, _OutTy2 *>
		partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutTy2 (&_Dest2)[_OutSize2], _Pr _Pred)
	{	// copy true partition *_Dest1++, false to *_Dest2++, array dest
	_STD pair<_OutIt1, _Array_iterator<_OutTy2, _OutSize2> > _Ans =
		_STD partition_copy(_First, _Last,
			_Dest1, _Array_iterator<_OutTy2, _OutSize2>(_Dest2), _Pred);
	return (_STD pair<_OutIt1, _OutTy2 *>(
		_Ans.first,
		_Unchecked(_Ans.second)));
	}

template<class _InIt,
	class _OutTy1,
	size_t _OutSize1,
	class _OutTy2,
	size_t _OutSize2,
	class _Pr> inline
	_STD pair<_OutTy1 *, _OutTy2 *>
		partition_copy(_InIt _First, _InIt _Last,
			_OutTy1 (&_Dest1)[_OutSize1], _OutTy2 (&_Dest2)[_OutSize2],
			_Pr _Pred)
	{	// copy true partition *_Dest1++, false to *_Dest2++, array dest
	_STD pair<_Array_iterator<_OutTy1, _OutSize1>,
		_Array_iterator<_OutTy2, _OutSize2> > _Ans =
			_STD partition_copy(_First, _Last,
				_Array_iterator<_OutTy1, _OutSize1>(_Dest1),
				_Array_iterator<_OutTy2, _OutSize2>(_Dest2), _Pred);
	return (_STD pair<_OutTy1 *, _OutTy2 *>(
		_Unchecked(_Ans.first),
		_Unchecked(_Ans.second)));
	}

 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */

		// TEMPLATE FUNCTION is_partitioned
template<class _InIt,
	class _Pr> inline
	bool _Is_partitioned(_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(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_Is_partitioned(_Unchecked(_First), _Unchecked(_Last),
		_Pred));
	}

		// TEMPLATE FUNCTION partition_point
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Partition_point(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find beginning of false partition in [_First, _Last)
	for (; _First != _Last; ++_First)
		if (!_Pred(*_First))
			break;	// skip true partition
	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(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_Rechecked(_First,
		_Partition_point(_Unchecked(_First), _Unchecked(_Last),
			_Pred)));
	}
 #endif /* _HAS_CPP0X */

		// TEMPLATE FUNCTION search
template<class _FwdIt1,
	class _FwdIt2,
	class _Diff1,
	class _Diff2> inline
	_FwdIt1 _Search(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Diff1 *, _Diff2 *)
	{	// find first [_First2, _Last2) match
	_Diff1 _Count1 = 0;
	_Distance(_First1, _Last1, _Count1);
	_Diff2 _Count2 = 0;
	_Distance(_First2, _Last2, _Count2);

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

template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2)
	{	// find first [_First2, _Last2) match
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_RANGE(_First2, _Last2);
	return (_Rechecked(_First1,
		_Search(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2),
			_Dist_type(_First1), _Dist_type(_First2))));
	}

		// TEMPLATE FUNCTION search WITH PRED
template<class _FwdIt1,
	class _FwdIt2,
	class _Diff1,
	class _Diff2,
	class _Pr> inline
	_FwdIt1 _Search(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
	{	// find first [_First2, _Last2) satisfying _Pred
	_Diff1 _Count1 = 0;
	_Distance(_First1, _Last1, _Count1);
	_Diff2 _Count2 = 0;
	_Distance(_First2, _Last2, _Count2);

	for (; _Count2 <= _Count1; ++_First1, --_Count1)
		{	// room for match, try it
		_FwdIt1 _Mid1 = _First1;
		for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_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(_Pred);
	return (_Rechecked(_First1,
		_Search(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2), _Pred,
			_Dist_type(_First1), _Dist_type(_First2))));
	}

		// TEMPLATE FUNCTION search_n
template<class _FwdIt1,
	class _Diff2,
	class _Ty> inline
	_FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
		_Diff2 _Count, const _Ty& _Val, forward_iterator_tag)
	{	// find first _Count * _Val match, forward iterators
	if (_Count <= 0)
		return (_First1);

	for (; _First1 != _Last1; ++_First1)
		if (*_First1 == _Val)
			{	// found start of possible match, check it out
			_FwdIt1 _Mid1 = _First1;

			for (_Diff2 _Count1 = _Count; ; )
				if (--_Count1 == 0)
					return (_First1);	// found rest of match, report it
				else if (++_Mid1 == _Last1)
					return (_Last1);	// short match at end
				else if (!(*_Mid1 == _Val))
					break;	// short match not at end

			_First1 = _Mid1;	// pick up just beyond failed match
			}
	return (_Last1);
	}

template<class _FwdIt1,
	class _Diff2,
	class _Ty> inline
	_FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
		_Diff2 _Count, const _Ty& _Val, random_access_iterator_tag)
	{	// find first _Count * _Val match, random-access iterators
	if (_Count <= 0)
		return (_First1);

	_FwdIt1 _Oldfirst1 = _First1;
	for (_Diff2 _Inc = 0; _Count <= _Last1 - _Oldfirst1; )
		{	// enough room, look for a match
		_First1 = _Oldfirst1 + _Inc;
		if (*_First1 == _Val)
			{	// found part of possible match, check it out
			_Diff2 _Count1 = _Count;
			_FwdIt1 _Mid1 = _First1;

			for (; _Oldfirst1 != _First1 && _First1[-1] == _Val; --_First1)
				--_Count1;	// back up over any skipped prefix

			if (_Count1 <= _Last1 - _Mid1)
				for (; ; )	// enough left, test suffix
					if (--_Count1 == 0)
						return (_First1);	// found rest of match, report it
					else if (!(*++_Mid1 == _Val))
						break;	// short match not at end

			_Oldfirst1 = ++_Mid1;	// failed match, take small jump
			_Inc = 0;
			}
		else
			{	// no match, take big jump and back up as needed
			_Oldfirst1 = _First1 + 1;
			_Inc = _Count - 1;
			}
		}
	return (_Last1);
	}

template<class _FwdIt1,
	class _Diff2,
	class _Ty> inline
	_FwdIt1 search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
		_Diff2 _Count, const _Ty& _Val)
	{	// find first _Count * _Val match
	_DEBUG_RANGE(_First1, _Last1);
	return (_Rechecked(_First1,
		_Search_n(_Unchecked(_First1), _Unchecked(_Last1), _Count, _Val,
			_Iter_cat(_First1))));
	}

		// TEMPLATE FUNCTION search_n WITH PRED
template<class _FwdIt1,
	class _Diff2,
	class _Ty,
	class _Pr> inline
	_FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
		_Diff2 _Count, const _Ty& _Val, _Pr _Pred, forward_iterator_tag)
	{	// find first _Count * _Val satisfying _Pred, forward iterators
	if (_Count <= 0)
		return (_First1);

	for (; _First1 != _Last1; ++_First1)
		if (_Pred(*_First1, _Val))
			{	// found start of possible match, check it out
			_FwdIt1 _Mid1 = _First1;

			for (_Diff2 _Count1 = _Count; ; )
				if (--_Count1 == 0)
					return (_First1);	// found rest of match, report it
				else if (++_Mid1 == _Last1)
					return (_Last1);	// short match at end
				else if (!_Pred(*_Mid1, _Val))
					break;	// short match not at end

			_First1 = _Mid1;	// pick up just beyond failed match
			}
	return (_Last1);
	}

template<class _FwdIt1,
	class _Diff2,
	class _Ty,
	class _Pr> inline
	_FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
		_Diff2 _Count, const _Ty& _Val, _Pr _Pred, random_access_iterator_tag)
	{	// find first _Count * _Val satisfying _Pred, random-access iterators
	if (_Count <= 0)
		return (_First1);

	_FwdIt1 _Oldfirst1 = _First1;
	for (; _Count <= _Last1 - _Oldfirst1; )
		{	// enough room, look for a match
		if (_Pred(*_First1, _Val))
			{	// found part of possible match, check it out
			_Diff2 _Count1 = _Count;
			_FwdIt1 _Mid1 = _First1;

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

			if (_Count1 <= _Last1 - _Mid1)
				for (; ; )	// enough left, test suffix
					if (--_Count1 == 0)
						return (_First1);	// found rest of match, report it
					else if (!_Pred(*++_Mid1, _Val))
						break;	// short match not at end

			_Oldfirst1 = ++_Mid1;	// failed match, take small jump
			_First1 = _Oldfirst1;
			}
		else
			{	// no match, take big jump and back up as needed
			_Oldfirst1 = _First1 + 1;
			_First1 += _Count;
			}
		}
	return (_Last1);
	}

template<class _FwdIt1,
	class _Diff2,
	class _Ty,
	class _Pr> inline
	_FwdIt1 search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
		_Diff2 _Count, const _Ty& _Val, _Pr _Pred)
	{	// find first _Count * _Val satisfying _Pred
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_POINTER(_Pred);
	return (_Rechecked(_First1,
		_Search_n(_Unchecked(_First1), _Unchecked(_Last1), _Count, _Val,
			_Pred, _Iter_cat(_First1))));
	}

		// TEMPLATE FUNCTION find_end
template<class _FwdIt1,
	class _FwdIt2,
	class _Diff1,
	class _Diff2> inline
	_FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Diff1 *, _Diff2 *)
	{	// find last [_First2, _Last2) match
	_Diff1 _Count1 = 0;
	_Distance(_First1, _Last1, _Count1);
	_Diff2 _Count2 = 0;
	_Distance(_First2, _Last2, _Count2);
	_FwdIt1 _Ans = _Last1;

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

template<class _FwdIt1,
	class _FwdIt2> inline
	_FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2)
	{	// find last [_First2, _Last2) match
	_DEBUG_RANGE(_First1, _Last1);
	_DEBUG_RANGE(_First2, _Last2);
	return (_Rechecked(_First1,
		_Find_end(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2),
			_Dist_type(_First1), _Dist_type(_First2))));
	}

		// TEMPLATE FUNCTION find_end WITH PRED
template<class _FwdIt1,
	class _FwdIt2,
	class _Diff1,
	class _Diff2,
	class _Pr> inline
	_FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
	{	// find last [_First2, _Last2) satisfying _Pred
	_Diff1 _Count1 = 0;
	_Distance(_First1, _Last1, _Count1);
	_Diff2 _Count2 = 0;
	_Distance(_First2, _Last2, _Count2);
	_FwdIt1 _Ans = _Last1;

	if (0 < _Count2)
		for (; _Count2 <= _Count1; ++_First1, --_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);
	_DEBUG_POINTER(_Pred);
	return (_Rechecked(_First1,
		_Find_end(_Unchecked(_First1), _Unchecked(_Last1),
			_Unchecked(_First2), _Unchecked(_Last2), _Pred,
			_Dist_type(_First1), _Dist_type(_First2))));
	}

		// 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
	for (; _First1 != _Last1; ++_First1)
		for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
			if (*_First1 == *_Mid2)
				return (_First1);
	return (_First1);
	}