You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 23 Dec '17, 20:07

kriskhundu's gravatar image

3★kriskhundu
83
accept rate: 0%

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

(23 Dec '17, 22:39) schleppel4★

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.

link

answered 23 Dec '17, 23:25

schleppel's gravatar image

4★schleppel
813
accept rate: 22%

edited 23 Dec '17, 23:36

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,540
×290
×275

question asked: 23 Dec '17, 20:07

question was seen: 768 times

last updated: 23 Dec '17, 23:36