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

[chris at bubblescope dot net]

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

--- Comment #13 from Chris Jefferson <chris at bubblescope dot net> ---
Created attachment 30767
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30767&action=edit
Bug patch

Patch attached.

This features:

1) As well as checking backwards when we find a match, check forwards too.
Improve so we never do more than n checks in an array of size n.

2) Improve the existing tester (which tries all arrays up to length 15) to
check the number of predicate calls.

3) Add the test included in this bug as a new test, just for completeness.