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

Position of an element in stl::set
Автор Jahid, 8 лет назад, По-английски

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.

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

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

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

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

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

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

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

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

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

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
→ Ответить