Change to search_n

[Chris Jefferson]

Dimitris Xochellis wrote:

>Hi Chris, hi list,
>
>  
>
Hello!
<snip>

>A) Slow skip process.
>
>  
>
I should have pointed out that my code wasn't as optimised as it could 
be.. that is a good improvement however!

>B) Slow performance when the probability of meeting a
>matching element is high.
>
>  
>
I'll address this at the end :)

>3) A serious bug.
>
>  
>
Woops! I've actually checked it and that is caught by the libstdc++ test 
suite, I should have however checked it passed testsuite before 
submitting it :)

>4) Incompatible to unsigned integers.
>
>  
>
I'm going to have to check that carefully... one problem with your 
implementation is that you store a temporary value in int, and this 
isn't allowed, I'm fairly certain you have to use 
iterator_traits<>::difference_type. Is it this that is causing the problem?

>--------------------------------------------------------
>
>  
>
>Recommendations:
>
>  
>
My recommendation to you would be:
1) Ask for a FSF copyright form
2) Fill in FSF copyright form and post back
3) Fix your search_n version up so that it is "libstdc++"ish (I'd be 
happy to help, there is already a test suite!)
4) Submit code, see name in changelog, get warm glow! :)

Chris

PS Below here for those interested is my opinion on the mine and 
Dimitris algorithm for search_n(T* first, T* end, length, predicate).

The broad definition of Dimitris' algorithm is (skiping the obvious step 
where you return if you find a solution!)
1) Go backward as far as you can while predicate is still true.
2) Go forward as far as you can while predicate is still true
3) Skip forward n steps from the end of where you finished at 2.

The broad definition of my algorithm is:
1) Go backwards while predicate is still true.
2) if you got "a" predicate accepts in the first step, jump forward 
"n-a" steps.

I thought the improvement of my algorithm is that whenever possible I 
jump forward, so that this would mean I'd get through the vector faster. 
However as I get to jump further less far, then overall the gain isn't 
worth it (it is for some densities of values, but not all, and it 
greatly increases the complexity)