Jahid's blog

Position of an element in stl::set
By Jahid, 8 years ago, In English

I am trying to find the position of an element in set using lower bound or binary search i.e, in lg(n) time.

For example, Elements in set are: 1 2 4 5 7.

I need to find the position of 4 which is in 3rd position. I have tried but can't do this. Is there any way ?

Thanks in Advance.

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

Comments Comments (12)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There is a way to do it!
Read under title 'Red black tree' http://mirror.codeforces.com/blog/entry/15729

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

http://mirror.codeforces.com/blog/entry/11080

http://mirror.codeforces.com/blog/entry/10355

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

You can simply use ordered set instead of "simple" set. That's how it works: ordered_set s; cout << s.order_of_key(3) << endl; — the number of elements in s less than 3 (in this case, 0-based index of element 3)

cout << *s.find_by_order(1) << endl; — 1-st elemt in s (in sorted order, 0-based)

P.S. here is some usefull stuff you need to deal with working with ordered set:

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template using ordered_set = tree<T, null_type, less, rb_tree_tag, tree_order_statistics_node_update>;

Hope that it helps;D

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

bro you could use distance() function

ex : s = {2,5,6,8,10}

to find index of 8 , you just do

distance(s.begin(),s.find(8));
   this will return no of elements between two iterators i.e 3
→ Reply