我如何对列表进行排序并获得前K个元素？(STL)

Question

我有一个双打矢量.我想从最高到最低排序,并获得前K个元素的索引.std :: sort只是就地排序,并没有返回我认为的索引.什么是获得最大元素的前K个指数的快速方法？

Answer 1

你可以使用nth_elementSTL算法 - 这将返回N个最大的元素(这是最快的方式,使用stl)然后在它们上使用.sort,或者如果你想要第一个K元素,你可以使用partial_sort算法排序(:

使用.sort是非常糟糕的 - 它对于你想要的目的来说非常慢.. .sort是很好的STL算法,但是对整个容器进行排序,而不仅仅是前K个元素(;这不是偶然的nth_element和partial_sort的存在;)

Answer 2

首先想到的事情有点hackish，但您可以定义一个存储双精度数及其原始索引的结构，然后重载 < 运算符以基于双精度数进行排序：

struct s {
    double d;
    int index;
    bool operator < (const struct &s) const {
        return d < s.d;
    }
};

然后您可以从结构中检索原始索引。

更完整的例子：

vector<double> orig;
vector<s> v;
...
for (int i=0; i < orig.size(); ++i) {
    s s_temp;
    s_temp.d = orig[i];
    s_temp.index = i;
    v.push_back(s);
}
sort(v.begin(), v.end());
//now just retrieve v[i].index

这将使它们从小到大排序，但您可以重载 > 运算符，然后根据需要将更大的值传递给排序函数。