Change to search_n

[Chris Jefferson]

Hi :)
> Hi Chris, hi list,
> 
> <snip>
> 
> Its mainly the expressions like (__last - __first >
> __count) that are producing these warnings. These
> expression will fail to work as expected in case
> __first > __last.
> 
I think we just have to careful with these tests :)

<snip>
> 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. :)

I'm of the opinion that a slight decrease in performance in some cases 
is acceptable as long as many other cases increase dramatically :)

The main problem I had with my previous version was that i wasn't 
getting much improvement for when the integer parameter was 2..


> Bellow I include a draft of this new implementation
> and I waiting for your comments.
> 
> //---------------------------------------------------
> 
> template <class _RandomAccessIter, class _Integer,
> class _Tp> inline
Only a tiny thing, I think this is perhaps a little large to 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;
> 
I know quite a lot of people don't like do { ... } while loops, although 
in this case it looks like the sensible option.
> 					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
> }

Generally it looks good to me, I don't really have much else to say :) 
My only very slight worry is that as these algorithms are fiddled with 
they get ever larger :)

Chris