CODEWITHSUNDEEP
c++
radssa
radssa

Reputation: 51

Finding k-th biggest element in set

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,

Upvotes: 1

Views: 6694

Answers (2)

alkurmtl
alkurmtl

Reputation: 149

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

Upvotes: 6

Jerry Coffin
Jerry Coffin

Reputation: 490148

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 Kth largest element, then dereference that to get the element itself.

Upvotes: 3

Related Questions