The "best" (idiomatic) way to select k smallest items from a container in C ++

Question

I often run into this problem: given the sequence, find the k-smallest element. The question is not so complicated, but what I'm looking for is an “idiomatic” way to do this, which is safe (there is little room for error) and well communicate intentions. So the final result sorts the sequence and then takes the first element k:

std::sort(container.begin(),container.end()); std::vector<T> k_smallest(container.begin(),container.begin() + k); 

It seems safe and understandable to me, but the complexity here is nlogn + k, not just n. As you guys do this, there is an idomatic way (perhaps using some kind of obscure function) that would provide optimal complexity without having to reuse the wheel

Answer 1

std :: nth_element () - average linear complexity.

nth_element is a partial sorting algorithm that rebuilds elements in [first, last), which:

• The element pointed to by nth changes to any element that will occur at this position if the sorting was [first, last).
• All elements before this new nth element are less than or equal to the elements after the new nth element.

Answer 2

Maybe you should take a look at partial_sort ()

It is easy to understand and requires no additional work, and it is expected that it will be better [or at least no worse] sort() if you only care about the kth element.

For optimal performance - you can use the selection algorithm , but this requires more work.

Answer 3

The first algorithm:

Steps:

• Use the selection algorithm to find the k_th element.
• Select it as a summary and execute the section (from the quick sort algorithm ), resulting in fewer k elements remaining on the top.

Difficulty: O (n) worst case

The second algorithm:

Steps:

• Use make_heap to create a bunch of array elements.
• Do the following k times:
  • read the first element.
  • enter it pop_heap

you can use priorty queue ( c'tor , top , pop ) methods to achieve the same without knowing the algorithm behind.

Difficulty: O (n + k * log (n)) worst case