c++ - 搜索 vector 成员的前n％个C++

Question

让我们定义

struct A
{ 
int m;
...
}

std::vector<A> vec; //a large vector (magnitude of million members)

我有兴趣找到 vec 的前2％成员，这些成员在 m 方法中具有最高的值(value)。

为此，我在想这样的事情:

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
  }

您是否认为任何更快的解决方案？

Answer 1

std::partial_sort 具有n log m的复杂性，其中n是元素的数量，而m是要排序的元素的数量。您可以使用它对排序，仅将排序为前2％。

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 。