Is std::search coding fast enough?
Dimitris Xochellis
jimxoch@yahoo.gr
Wed Jul 4 17:58:00 GMT 2007
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
More information about the Libstdc++
mailing list