从向量中获取 n 个最佳元素？

Question

我有一个结构向量，为此我重载了所有比较运算符。我不知道编译时结构的大小。

检索向量中 n 个最佳（其中“最佳”可以是最小或最大）元素的快速方法是什么？我知道 max_element 和 min_element 但它们只返回一个元素。我宁愿不循环 n 次，检索最佳元素，将其删除，然后获取下一个。这种方法似乎太慢了。

谢谢。

Answer 1

您可以使用std::nth_element, 将最小的n元素移动到n范围内的第一个位置（注意这些n元素的相对顺序未定义）。

std::vector<T> objects;
std::nth_element( objects.begin(), objects.begin() + n, objects.end() );

// Now the range [objects.begin(), objects.begin() + n) contains the lowest n elements
// Obviously n must be <= objects.size()

当您编写在编译时不知道结构的大小时，我假设您有一个多态对象的集合，并且您有一个指针向量而不是元素。没什么大不了的，您仍然可以使用std::nth_elementlambda。

std::vector<T*> objects;
std::nth_element( objects.begin(),
                  objects.begin() + n,
                  objects.end(),
                  [](const T * lhs, const T * rhs)
                  {
                      return (*lhs) < (*rhs); // Or (*lhs) > (*rhs) for the greatest n elements
                  });