CODEWITHSUNDEEP
c++algorithmstl
Jo So
Jo So

Reputation: 26501

C++: Extract N highest elements from container

Quite frequently I need to extract the N (> 1) highest elements from an unsorted STL container. The naive way to do this is using <queue>.

Is there a quicker, less boilerplate way?

Upvotes: 1

Views: 133

Answers (2)

Kerrek SB
Kerrek SB

Reputation: 476980

To get the n smallest elements, use nth_element:

std::vector<int> v = { 2, 6, 1, 13, 51, 5, 0, -1 };

std::nth_element(v.begin(), v.begin() + 3, v.end());

// now v[0], v[1], v[2] are the smallest, not otherwise sorted

Make sure to #include <algorithm>. An optional predicate may be supplied for customizing the sort order (e.g. std::greater<int>).

Upvotes: 4

Mark B
Mark B

Reputation: 96241

std::partial_sort if you need them in order, otherwise std::nth_element, using greater as your predicate in either case.

I can't tell if by extract you mean you want to remove, but if you do then another option is heapifying your container with make_heap and then yanking the N elements out of it.

Upvotes: 3

Related Questions