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

How to use lower_bound in set<pair<int,int>> ?
Автор anajin, 10 лет назад, По-английски

I search it in google , but i can't find it. Can somebody tell me how to use lower_bound in set<pair<int,int>> , so i can find the fist pair whose first element is not small than the element i search for ?

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

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

x.lower_bound({first, -inf});

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    got it! Thanks.

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you explain the reasoning behind using that ? Also could you tell how you would do it for upper_bound ? Thanks :)

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      x.upper_bound({first, inf});

      → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In these implementations we only care about the first value.

      pair<int,int> will compare the first int first, then the second int. We want ALL second integers to work

      As for upperbound Na2a uses {first, inf} because we want the value to be greater than first, and {first, inf} is the highest pair with first as its first value. (again, we only care about the first value)

      → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to get the index of that pair,i mean we can't do this:x.lower_bound({first,-inf})-x.begin()?

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

This is a pretty good site : http://bit.ly/1DMMnub

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

How can i call lower_bound on pair<int,int> to get the last occurence of pair if element is repeating ?

For eg :

[7,1,5,3,1,1]

[ {1,1,} , {1,4} , {1,5}, {3,3}, {5,2}, {7,0} ]

if i do lower_bound for should get pair {1,5}

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

    try auto it = st. upper_bound({first+1,-inf})
    if(it == st.begin()) element not found
    else element in it--

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can u explain more ?

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        upper bound return an iterator that points to the first element strictly bigger than {x,y}
        st. upper_bound({first+1,-inf}) return an iterator to the first element strictly bigger than the element we are looking for
        for example :

        [ {1,1,} , {1,4} , {1,5}, {3,3}, {5,2}, {7,0} ]
        auto it = st. upper_bound({2,-inf})
        *it = {3,3}
        so to get {1,5} all we need to do is it--;
        A corner case is :
        [ {3,3}, {5,2}, {7,0} ]
        auto it = st. upper_bound({2,-inf})
        *it = {3,3} (it = st.begin())
        in this case it-- is not defined so this will cause a runtime error
        tha's why we need to test if (it == st.begin())
        PS : in our case lower_bound will give the same result as we are sure that no pair have the second element equals -inf so stricly bigger ( < ) or stricly bigger or equal ( <= ) gives the same result

        → Ответить
»
5 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

you can do it this way : s.lower_bound(make_pair(x, y)) or s.lower_bound(pair(x, y)). (the last case just in c++17).

→ Ответить