c++ - C ++：从容器中提取N个最高元素

Question

我经常需要从未排序的 STL 容器中提取 N (> 1) 个最高元素。天真的方法是使用<queue>.

有没有更快、更少样板的方法？

Answer 1

要获得n最小的元素，请使用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

确保#include <algorithm>. 可以提供一个可选的谓词来定制排序顺序（例如std::greater<int>）。

Answer 2

std::partial_sort如果您按顺序需要它们，否则std::nth_element，greater在任何一种情况下都将其用作谓词。

我不知道提取是否意味着您要删除，但如果您这样做，那么另一个选择是使用您的容器堆积make_heap，然后将N元素从其中拉出。