[Bug libstdc++/58358] search_n has a Complexity violation for random access iterator

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58358

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-09-08
     Ever confirmed|0                           |1

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
The indexes of the values that are tested:
9 8 7 6 5 4 3 2 1 0 10 9 8 7 6 5 4 3 2 1

It starts well, first checking 9 because if that one fails we can skip testing
0-8. The backtrack is normal. Once the backtracking fails, the code jumps to a
sensible place (so that backtracking will go precisely to the last place before
we failed) but it forgets that it has already tested many of those values.