Is std::search coding fast enough?

[Dimitris Xochellis]

Hi list,

After reading the following std::search STL algorithm [1] I have got the impression that it can be
coded in a more efficient way. In my opinion, the code in the lines *A* & *C* guaranties that the
condition of the line *B* will be always true. Consequently, we can effectively replace the "while
(__first1 != __last1)" expression of the line *B* with a simpler "for ( ; ; )" expression and the
algorithm will work just fine and significantly faster as well.

References
[1] /tags/gcc_4_2_0_release/libstdc++-v3/include/bits/stl_algo.h


Sorry for wasting your time in case I am wrong,
Jim Xochellis

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


template<typename _ForwardIterator1, typename _ForwardIterator2>
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
		_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
	// concept requirements
	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
		__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
		__glibcxx_function_requires(_EqualOpConcept<
				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) //*A*
		return __first1;

	// Test for a pattern of length 1.
	_ForwardIterator2 __tmp(__first2);
	++__tmp;
	if (__tmp == __last2)
		return std::find(__first1, __last1, *__first2);

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

	while (__first1 != __last1) //*B*
	{
		__first1 = std::find(__first1, __last1, *__first2);
		if (__first1 == __last1)
			return __last1;

		__p = __p1;
		__current = __first1;

		if (++__current == __last1) //*C*
			return __last1;

		while (*__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