"Best" (idiomatic) way to select the k smallest elements from a container in C++ [duplicate]

Question

I find myself with this problem quite often : given a sequence, find the k-smallest element.The question is not that hard , but what i am looking for is an "idiomatic" way of doing it that is both safe (few place for error) and that communicate intent well. So end-up doing is sorting the sequence , then taking the first k element :

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

This seems to me both safe and easy to understand, but the complexity in here is nlogn + k, instead of just n. How do you guys do this, is there an idomatic way (using some obscure function from maybe) that would give the optimal complexity without having to re-implement the wheel

Answer 1

std::nth_element() - linear complexity on average.

nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that:

• The element pointed at by nth is changed to whatever element would occur in that position if [first, last) was sorted.
• All of the elements before this new nth element are less than or equal to the elements after the new nth element.