Finding k-th biggest element in set

Question

I'm using set in C++

set<int> Set;

And I would like to k-thest biggest element. How to do it? Plese give me hand,

You'll have more luck on SO if you provide code and show that you've done at least a little bit of your own research. — genisage, Oct 22 '14 at 22:38
http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on — druckermanly, Oct 22 '14 at 22:40
Please provide some attempt at finding the solution. It doesn't need to be correct, but we need you to show some effort to help us answer where you need help. — ChuckCottrill, Oct 22 '14 at 22:41
This is not a duplicate--finding the largest element is different from finding the Kth element. — Jerry Coffin, Oct 22 '14 at 22:55

score 7 · Answer 1 · answered Mar 28 '16 at 15:03

It's impossible to do it in O(log n) time with std::set, but you can do it using tree from extended STL. Here is how to use it:

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
s.insert(x);
s.erase(x);
s.count(x);
s.find_by_order(k);
// k-th biggest element in set
s.order_of_key(x);
// how many elements in set are less than x

score 2 · Answer 2 · answered Oct 22 '14 at 22:59

Elements in a set are stored in sorted order, so Set.rbegin() yields an iterator to the largest element in the set.

std::next will advance an iterator by a specified number of places, and return an iterator to that position.

You can combine these to get an iterator to the largest item, then advance it K elements back from there to get an iterator to the K^th largest element, then dereference that to get the element itself.

Finding k-th biggest element in set

2 Answers2