incorrect behavior of upper_bound

Question

vector<int> v = {0,1,3,2};
auto x = upper_bound(v.rbegin(), v.rend(), 1);
cout<<(*x);

This block of code gives output 24576

vector<int> v = {0,1,3,2,2};
auto x = upper_bound(v.rbegin(), v.rend(), 1);
cout<<(*x);

This block gives output 2.

Why?

Answer 1

std::upper_bound has a precondition. Quoting cppreference here, not the standard:

The range [first, last) must be partitioned with respect to the expression !(value < element) or !comp(value, element), i.e., all elements for which the expression is true must precede all elements for which the expression is false.

It is up to you, the caller, to make sure this precondition is satisfied, and your program has undefined behavior if you fail to do so.

Since you pass reverse iterators, the sequence for the algorithm is 2, 3, 1, 0 for the first example. (The second has exactly the same issue.) The expression !(1 < element) evaluates for this sequence to false, false, true, true, which means the true values don't precede the false values, i.e. the precondition is violated. Your program has undefined behavior, and the exact resulting values are unpredictable and irrelevant.