[v3] Fix libstdc++/58358

[Paolo Carlini <paolo dot carlini at oracle dot com>]

Hi,

thus we have this conformance issue with the optimized, "skipping", 
search_n overloads for random access iterators: in some cases too many 
comparisons are performed. We have on the table two different fixes: one 
proposed by bug submitter, which actually simplifies what we have got; 
another proposed by Chris (Jefferson) which extends the current code to 
handle the problem. As you can see in the audit trail, we ran various 
tests, we compared code size and performance, and all in all today I'm 
going to propose Mitsuru's fix. I ran myself further tests, and I'm 
finding that only in some cases, like the existing performance test, it 
runs a littler slower of what we have got (but still so much faster of 
the overload for forward iterators, our baseline), in other cases, like 
iterator.cc in the main testsuite tweaked to TEST_DEPTH 23, I actually 
find Mitsuru's solution faster than Chris' on at least a machine (an 
i7-980X). Add to this the simplicity of the code, the smaller code size.

I'm attaching below the complete patch I tested on x86_64-linux and I 
mean to commit later today. I'm also attaching Chris' code changes 
alone, if you want to run your own comparison and give feedback.

Thanks!
Paolo.

PS: Mitsuru doesn't have a Copyright assignment but I think that the 
size of the "invention" is small enough, assuming he is not going to 
contribute more (and the real size is just half, because the version for 
the search_n taking a predicate is conceptually identical)

///////////////////////

Attachment: CL_58358
Description: Text document

Attachment: patch_58358_mitsuru
Description: Text document