C++：從容器中提取N個最高元素

經常需要從未排序的STL容器中提取N（> 1）個最高元素。天真的做法是使用<queue>。C++：從容器中提取N個最高元素

有沒有更快，更少樣板的方式？

來源

2013-01-11 Jo So

考慮維護一個排序的包含，如果它頻繁。 – andre

std::partial_sort如果你需要它們，否則std::nth_element，使用greater作爲你的謂詞。

我不能說是否通過提取你的意思是你想要刪除，但如果你這樣做，然後另一個選項是使用make_heap heapting你的容器，然後從其中排除N元素。

來源

2013-01-11 20:23:09

方面的問題是：'partial_sort（it，it + K，it + N）'總是比combo'nth_element（it，it + K，it + N）便宜'，後面跟'sort（it + it）足夠大的'K TemplateRex

@rhalbersma：第二個變體應該有漸進時間複雜度「O（K * log K + N）」，它漸近地小於第一個變量的「O（N log K）」。如果它（不）總是便宜，我不能說。簡介。 – jpalecek

要獲得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>）。

來源

2013-01-11 20:23:53

C++：從容器中提取N個最高元素

回答

相關問題