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