slow_coder4's blog

Help! set stl
By slow_coder4, history, 7 years ago, In English

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 .

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

See here Your text to link here...

UPD: IGNORE

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

You cannot do it with a set.

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

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

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

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

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.

→ Reply