[libc++] Optimize std::find_end

[ldionne]

That algorithm is super slow, I noticed while benchmarking it. We could probably short-circuit it with a std::find for the first element of the needle. We should also consider starting from the end for bidirectional iterators if we don't already (looks like we don't).

[winner245]

I think the current implementation of std::find_end is very slow. It has truly quadratic time complexity, and it always starts from the beginning, assuming forward-only iterators. So it has to exhaust the entire source to ensure that the last occurrence is found. However, if we have bidirectional iterators, we can start from the end and search in the reversed direction, then the first occurrence is our result. In addition to using std::find to determine the starting point, we can directly call std::search to perform the actual work. If std::search is optimized to a linear complexity in some cases (if possible), we could potentially achieve linear performance for std::find_end as well. Moreover, even for forward-only iterators, we can still do better by using std::find to determine the starting point, and call std::search to do the actual work. I believe this should give better performance.

I am going to pursue this idea further.