CODEWITHSUNDEEP
c++performancestlsetbinary-search-tree
Frank
Frank

Reputation: 59

How to get which integer is in a certain position in a set?

Given a set of integers, how can I know which integer is in a certain position, if the elements of a set were ordered in an increasing way? For example, given a set of integers how can I obtain the smaller integer or the second smaller integer etc

Is it possible to do this in logarithmic time? I mean, I know there are obvious ways of doing what I asked, but is there any that works in logarithmic time?

Upvotes: 0

Views: 263

Answers (2)

Rahul Manne
Rahul Manne

Reputation: 1249

Yes, if your elements were sorted ("ordered in an increasing way"), then there is a way to search for an arbitrary integer in logarithmic time. Use binary search trees. Obviously, if you want the best possible time span, you will want to use self-balancing trees (such as red-black trees, avl trees, ...). I believe that the C++ options for this are part of std::set.

However, I'm not really sure what you mean by "obtain the smaller integer." If you mean, given a set of integers, find the minimum element, then you will want to look up Heaps. Heaps do the job better than trees, because in the case of Heaps, querying the minimum value will happen in constant time, while insertions and deletions happen in logarithmic time. I believe the C++ options for this are part of std::priority_queue.

Alternatively, if you wanted the fastest way of searching for integers, you can use hash tables, since they allow querying in expected constant time, with constant time insertion. The C++ options for this are std::unordered_set.

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490398

The elements of an std::set are stored in increasing order.

No, you can't find the item at position N in logarithmic time though--it requires linear time.

auto start = your_set.begin();
std::advance(start, N);

In theory it could be done in logarithmic time by having each node of the tree store a count of the nodes to its left (i.e., preceding it in order), but std::set doesn't require that or provide a (standardized) interface to use it even if it were present.

Upvotes: 3

Related Questions