STL upper_bound doubt.

cin Y Z D;
LL start = lower_bound(A.begin(),A.end(),pair<LL,LL>(Z,0)) - A.begin();
LL fin = upper_bound(A.begin(),A.end(),pair<LL,LL>(Z,0)) - A.begin();
In this snippet, if my pair vector is 1 1 2 2 5 0 1 2 3 4 and Z is 2, lower bound works correctly and returns 2 however, upperbound always gives the same result as lower bound. Can anybody tell me why it is so and how i could fix this? Thanks

Please post working code. I’m not sure I understand what you intend to do.

I think i figured out what you’re trying to do.

In your vector you have pairs {1, 1}, {2, 2}, {5, 0}, {1, 2} and {3, 4}, right?

If you have those elements in that order in your vector, you can’t use upper_bound and lower_bound, because those require a sorted sequence.

But even if you sorted that sequence first, both upper_bound and lower_bound would return an iterator to the same element because there’s no {2, 0} element in the vector. lower_bound returns you an iterator to the first element in the vector that’s equal to or larger than {2, 0}, upper_bound returns you an iterator to the first element that’s larger than {2, 0} - if no element in the sequences equals to the one you’re searching for, upper_bound and lower_bound do exactly the same thing.

The standard sorting mechanic for std::pair is lexicographical order. So:

{1, 1} < {2, 0}

{2, 0} < {2, 1}

and so on.

1 Like