Is std::search coding fast enough?

[Dimitris Xochellis]

Hi Paolo,

The code of the predicate version seems even less efficient to me. I am rather tired and maybe I
am not thinking straight right now, but what is the reasoning behind of the two loops *A* & *B*
that seems to do the same thing?

Best regards,
Jim Xochellis

------------------------

template<typename _ForwardIterator1, typename _ForwardIterator2, typename _BinaryPredicate>
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
		_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate  __predicate)
{
	// concept requirements
	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
		__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
		__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
				typename iterator_traits<_ForwardIterator1>::value_type,
				typename iterator_traits<_ForwardIterator2>::value_type>)
		__glibcxx_requires_valid_range(__first1, __last1);
	__glibcxx_requires_valid_range(__first2, __last2);

	// Test for empty ranges
	if (__first1 == __last1 || __first2 == __last2)
		return __first1;

	// Test for a pattern of length 1.
	_ForwardIterator2 __tmp(__first2);
	++__tmp;
	if (__tmp == __last2)
	{
		while (__first1 != __last1 && !__predicate(*__first1, *__first2))
			++__first1;
		return __first1;
	}

	// General case.
	_ForwardIterator2 __p1, __p;
	__p1 = __first2; ++__p1;
	_ForwardIterator1 __current = __first1;

	while (__first1 != __last1)
	{
		while (__first1 != __last1)  *A*
		{
			if (__predicate(*__first1, *__first2))
				break;
			++__first1;
		}

		while (__first1 != __last1 && !__predicate(*__first1, *__first2))  *B*
			++__first1;

		if (__first1 == __last1)
			return __last1;

		__p = __p1;
		__current = __first1;
		if (++__current == __last1)
			return __last1;

		while (__predicate(*__current, *__p))
		{
			if (++__p == __last2)
				return __first1;
			if (++__current == __last1)
				return __last1;
		}

		++__first1;
	}

	return __first1;
}



      
___________________________________________________________ 
×ñçóéìïðïéΓ₯ΓŸΓ΄Γ₯ Yahoo!; 
ÂÑñΓ₯Γ¨ΓžΓͺÑôΓ₯ ôÑ Γ₯íï÷ëçôéΓͺΓœ ìçíýìÑôÑ (spam); Ôï Yahoo! Mail 
ÀéÑèÝôΓ₯Γ© ôçí ΓͺÑëýôΓ₯Γ±Γ§ Γ€Γ΅Γ­Γ‘Γ΄Γž Γ°Γ±Γ―Γ³Γ΄Γ‘Γ³ΓŸΓ‘ ΓͺΓ‘Γ΄Γœ ôùí Γ₯íï÷ëçôéΓͺΓΎΓ­ 
Γ¬Γ§Γ­Γ΅Γ¬ΓœΓ΄ΓΉΓ­ http://login.yahoo.com/config/mail?.intl=gr