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

Help! set stl
Автор slow_coder4, история, 7 лет назад, По-английски

How can find the value from set given an index. suppose our set is st. st.insert(2); st.insert(6); st.insert(1);

Now i want to know the value of index 2 from set. Is there any logarithmic away? Thanks advance .

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

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

See here Your text to link here...

UPD: IGNORE

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

You cannot do it with a set.

However, there is another data structure with can answer such queries. See this blog post.

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

You can find in logarithmic time with policy based data structures. See my this comment.

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

You can use a vector.

Let's define a vector S.

insert a value x like this : S.insert(lower_bound(S.begin( ),S.end( ),x),x);

find the position of x like this : pos = upper_bound(S.begin( ),S.end( ),x)-S.begin( )

The complexity of vector's INSERT can be seen as LOG . However , it's slower than set. And make sure that values in the vector are ordered at the beginning.

→ Ответить