According to my tests, my new implementation seems to
perform better than the old one in most cases (though
there are circumstances when it performs slightly
worse) and is testing less elements in all cases.
Particularly, when the probability of meeting a
matching element is high, it performs great. In the
example I have mentioned in a previous mail (test D of
my article) your implementation is testing 16% of the
overtaken elements, my old implementation is testing
14% of the overtaken elements and my newest one only
10.7% of the overtaken elements. I have to admit that
when the element comparison itself is very fast, then
my new implementation is not always faster in all
compilers, but in case that the comparison is
non-trivial then it really takes off. :)
Bellow I include a draft of this new implementation
and I waiting for your comments.
//---------------------------------------------------
template <class _RandomAccessIter, class _Integer,
class _Tp> inline
_RandomAccessIter search_n(_RandomAccessIter __first,
_RandomAccessIter __last,
_Integer __count, const _Tp&
__val)
{
if (__count <= 0)
return __first;
if (__count == 1)
return std::find(__first, __last, __val);
typedef
std::iterator_traits<_RandomAccessIter>::difference_type
iter_diff;
iter_diff __tailSize = __last - __first;
iter_diff __pattSize = __count;
if (__tailSize >= __pattSize)
{
_RandomAccessIter __backTrack;
iter_diff __remainder, __prevRemainder;
iter_diff __skipOffset = __pattSize - 1;
_RandomAccessIter __lookAhead = __first +
__skipOffset;
for ( ; ; __lookAhead += __pattSize ) // the main
loop...
{
//__lookAhead here is always pointing to the last
element of next possible match.
assert( __tailSize >= __pattSize );
__tailSize -= __pattSize;
for ( ; ; ) // the skip loop...
{
if (*__lookAhead == __val)
break;
if (__tailSize < __pattSize)
return __last;
__lookAhead += __pattSize;
__tailSize -= __pattSize;
}
assert( __tailSize == (__last - __lookAhead) - 1 );
__remainder = __skipOffset;
for ( __backTrack = __lookAhead - 1; *__backTrack
== __val; --__backTrack )
{
if (--__remainder == 0)
return (__lookAhead - __skipOffset); //Success
}
for ( ; ; )
{
if (__remainder > __tailSize)
return __last; //failure
__lookAhead += __remainder;
__tailSize -= __remainder;
if (*__lookAhead == __val)
{
__prevRemainder = __remainder;
__backTrack = __lookAhead;
do
{
if (--__remainder == 0)
return (__lookAhead - __skipOffset); //Success
} while ( *--__backTrack == __val);
//adjust remainder for next comparison
__remainder += __skipOffset - __prevRemainder;
}
else
break;
}
//__lookAhead here is always pointing to the
element of the last mismatch.
if (__tailSize < __pattSize)
return __last;
}
}
return __last; //failure
}