Блог пользователя Dabagh

Question about search in sets (C++)
Автор Dabagh, 8 лет назад, По-английски

Hi.

Consider a set of integers S and an integer X.

How to find the maximum integer less than X in S using lower_bound and/or upper_bound?!

How to find the minimum integer greater than X in S using lower_bound and/or upper_bound?! Example :

S = {2 , 3 , 4 , 7 , 8 , 9} , X = 5

maximum integer less than 5 = 4

minimum integer grater than 5 = 7.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

1)

auto it = s.lower_bound(x);
if (it != s.begin()) ans = *(-- it);

2)

auto it = s.upper_bound(x);
if (it != s.end()) ans = *it;
→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Good day to you!

Here are a few usages, too see, how to get elements around :)

i.e:

upper_bound finds first higher

lower_bound finds first higher/equal

You can use "--/++" to move around

PS: Beware of begin/end (not to "get" these elements) .. one can check by "==S.end()" / "S.begin()" :)

Hope I have not made any mistake ^_^

Good Luck!

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Just to note: it is OK to dereference begin(), but you shouldn't do it with end(). Also avoid doing --begin().

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Thanks haposiwe and -Morass- .

I didn't know --it works!

→ Ответить