Does lower_bound() return the same result with reverse iterators of a vector in increasing order vs forward iterators of a vector in decreasing order?

Question

If I have 2 vectors, one in increasing order, and other decreasing:

vector<int> inc{1,2,3,4,6,7}, dec{7,6,4,3,2,1};

Do the following 2 expressions always give the same result? Or, is there any difference in how they work?

lower_bound(inc.rbegin(), inc.rend(), some_number, greater<int>()) // #1

lower_bound(dec.begin(), dec.end(), some_number, greater<int>()) // #2

I feel they are the same, but during a recent contest on Codeforces, one got accepted while the other didn't.

Answer 1

From the algorithm's, std::lower_bounds's, perspective, there is no differance other than the iterator type (one is a reverse iterator and the other one is not), but it doesn't care about that.

It will perform the same algorithmic steps in both cases and return an iterator pointing at an element that carries the same value in both cases - or the end()/rend() iterator.

One minor difference could be in speed. I'd expect the version using reverse iterators to be a tad slower, but I haven't measured.

So, other than the difference in the returned iterator type and possibly one being slower than the other, you will get the same value out of both versions.

---

For fun, here's a quick-bench measurement of the two versions. You can play around with the ranges to see if and how that effects the outcome. The lower the bar, the faster it is. Blue is for the reverse iterator and yellow is for the normal iterator.