### _Ramtin_'s blog

By _Ramtin_, history, 7 years ago,

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 ?

• +3

 » 7 years ago, # |   0 Auto comment: topic has been updated by _Ramtin_ (previous revision, new revision, compare).
 » 7 years ago, # |   +6
•  » » 7 years ago, # ^ |   0 oh thanks man !
•  » » » 7 years ago, # ^ |   0 Be aware that distance function wouldn't be constant-time while given bidirectional iterators.
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   0 nope i needed an online sorted array for those problems and vector couldn't do that :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
 » 7 years ago, # |   +14
 » 7 years ago, # |   -6 Your Big Problem is your little penis!