The k-th smallest element of a set.

[hackinghorn]

I have a question about set (again :D)
I want to find the k-th element of a set<int> s. I do it like this:

set<int> s;
int k;
// sth...
set<int>::iterator it=s.begin();
for (int i=1;i<=k-1;i++) it++;
cout<<*it;

Since set is actually RB-tree inside, I think there must be a way to have an O(logn) way to do it, not an O(n) way like this (n is the size of the set). Can you help me find an O(log n) way :D

[JMJAtlanta]

I know this is not an answer to your original question, but...

Must you use set?

Set's iterator is a bidirectional iterator. It sounds as if you need a collection that provides a random access iterator. You could then use:

it += k;

[webJose]

A binary tree is sorted by some key. Since the data is integers, the tree is ordered by the value of this integer. If you want the kth element where k is the INDEX, then O(n) is what you'll get, but if you mean to search in the tree the element with value k, then you can achieve this in O(log n). See the difference? O(log n) is achievable only when searching for the tree's key.

If you don't need super fast insertion/deletion, move to std::vector since it provides random access iterators, and if you need to search for a value, you can keep the vector sorted using std::sort(), and the search will also be O(log n) (Quicksort).