_Ramtin_'s blog

My Big Problem !
By _Ramtin_, history, 9 years ago, In English

Hi everyone , I have a question which i faced a lot while implementing a problem and i usually handled it with segment tree but i think it must have an easier way

think that u have a set s

i want to find out number x position in this set

more formally i want s.find(x) — s.begin()

but c++ set can't handle this ! what should i do ? is there any way without using other structures to solve this ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Ramtin_ (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

http://stackoverflow.com/questions/13505562/getting-index-of-set-element-via-iterator

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh thanks man !

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Be aware that distance function wouldn't be constant-time while given bidirectional iterators.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If there are many such 'queries', then transform std::set into a vector. Vector supports upper_bound/lower_bound functions and by subtracting v.begin() you can get the index.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nope i needed an online sorted array for those problems and vector couldn't do that :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Then you will have to write your own treap. I assume that distance works in linear time and is almost completely useless in your case.

      There are ways to use g++ order statistic tree if you really need it.

      → Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

read this http://codeforces.net/blog/entry/11080

→ Reply
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Your Big Problem is your little penis!

→ Reply