-1
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?

mingzi xingshi
  • 35
  • 1
  • 4
  • 1
    Maybe you made a mistake in the `upper_bound` function? – mkrieger1 Apr 04 '23 at 10:05
  • This `upper_bound` is not my code, it's STL @mkrieger1 – mingzi xingshi Apr 04 '23 at 10:07
  • 3
    Related: [why is using namespace std considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Thomas Weller Apr 04 '23 at 10:07
  • 3
    I didn't know that, because you didn't show it. – mkrieger1 Apr 04 '23 at 10:07
  • 3
    Please provide a [mre], i.e. some code that we can actually copy&paste and compile. – Thomas Weller Apr 04 '23 at 10:07
  • 2
    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. A fully-sorted range meets this criterion. – Thomas Weller Apr 04 '23 at 10:10
  • 1
    `x` is at the end so dereferencing it has undefined behaviour: https://godbolt.org/z/cMsjxoqvG – Alan Birtles Apr 04 '23 at 10:10
  • @mingzi xingshi The function expects a sorted sequence. Your sequences are not sorted. So the calls of the function have undefined behavior. – Vlad from Moscow Apr 04 '23 at 10:10
  • 4
    Assuming you mean `std::upper_bound`, your input vectors are not partitioned as described here: https://en.cppreference.com/w/cpp/algorithm/upper_bound. You need to sort the vectors first. – joergbrech Apr 04 '23 at 10:10
  • 1
    You get an iterator to *last*, which means you access memory out of the vector. – Thomas Weller Apr 04 '23 at 10:11
  • 1
    Use [max_element](https://en.cppreference.com/w/cpp/algorithm/max_element) instead. – Thomas Weller Apr 04 '23 at 10:12
  • 2
    @ThomasWeller -- you provided a clearly correct solution in a comment and another constructive comment, but you voted to close because the question isn't clear? How does that make sense? – Pete Becker Apr 04 '23 at 15:50
  • @PeteBecker: as I commented before: I'd like to see a [mre]. As the question stands, it's a guess, probably a good guess, though. – Thomas Weller Apr 04 '23 at 20:04
  • I think this question contains all the information a C++ programmer needs to answer the issue. A MRE is not needed. – Sebastian Redl Apr 05 '23 at 07:39

1 Answers1

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.

Sebastian Redl
  • 69,373
  • 8
  • 123
  • 157