The n'th element of a set

[Divad]

I am using STL a lot especially set<int>.
But very often I want to get the n'th element of the set, but set has no "at( int)" or "operator[]".
Ofcourse I could iterate over the set but that takes to long time.
It irritates me a lot, since I know that behind the "set" there is a balanced tree, which should make it possible to calculate the value of the n'th element in O(ln) time.
Before I start to make my own template, I would like to see if anyone has a solution to the problem..

[kbw]

See std::advance

[rapidcoder]

std::advance is not really any better than iterating manually - still O(n) instead of O(log n) for sets (according to the spec). I'm afraid you can't do that with STL.

I'm also afraid there are no chances that such operation is added to STL in the near future, keeping in mind that STL almost hasn't been moved forward for the last 10 years. I wonder what these guys have been doing for such a long time. Wow! It is 2011 and no hashmaps in the standard! (I know, I know, there is C++0x, but it is too little, too late, and it is still not there).

[jsmith]

You need random access iterators for that. std::deque and std::vector provide them. Random access in a std::vector<> is constant time; random access in a std::deque<> is amortized constant time.

[simeonz]

What IMO is needed is some way to augment the containers. For this particular case, the OP needs dynamic order statistics augmentation of the nodes. It would increase the memory consumption, so it has to be optional, because there are other things that a person may want. For example, sum of all elements between two iterators. Each augmentation comes with a toll.

I am not sure that this can happen universally. If I were in the committee I would introduce the possibility to provide custom node valuation function, set union/difference functions (that produce the respective values), and optionally a predicate that answers if the sought node is in a set, given the set's value and the target value. Without the predicate, queries for the total value of the elements between two iterators would be possible. With the predicate, custom searches would also be possible.

That's why you have to know data structures even today. Some guy wanted to implement Dijkstra the other day and I just realized that std:: priority queue does not support the decrease key operation.