Thursday, September 03, 2009


Ever wanted to know what the N:th element in a sorted version of the sequence [first,last) is, without sorting the whole thing? I sure did. Unfortunately I didn't know about std::nth_element!
std::nth_element( first, nth, last );
Paraphrasing, after this function is applied, nth is guaranteed to be the same as if the entire sequence was sorted. Meanwhile, non of the (first,nth] elements are larger than the nth element, and so logically the opposite goes for the [nth+1,last) elements. This method does less work than both std::sort and std::partial_sort, and thus is likely to be faster.

No comments:

Post a Comment