让我们定义
struct A
{
int m;
...
}
std::vector<A> vec; //a large vector (magnitude of million members)
我有兴趣找到vec的前2％成员，这些成员的m方法价值最高。
为此，我在想这样的事情：
std::multimap<int, A> top_members;
const auto nr_top = std::lround(vec.size() * 0.02);
for (auto it = vec.begin(); it != vec.end(); ++it)
{
if(top_members.size() == nr_top + 1)
top_members.erase(std::prev(top_members.end()));
else
top_members[it->m] = *it
}
您是否认为任何更快的解决方案？
std::partial_sort元素的数量和要排序的元素的数量的复杂性在n log m哪里。您可以使用它仅对前2％进行排序。nm
const auto nr_top = std::lround(vec.size() * 0.02);
std::partial_sort(vec.begin(), vec.begin() + nr_top, vec.end(),
[](auto a, auto b){return a > b}
);
// the top 2% will be at the front of the vector
如果您需要使用其他容器中的前2％，则可以std::partial_sort_copy改用。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句