c++ - 从 vector 中获取 n 个最佳元素？

Question

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

检索 vector 中 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()

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

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
                  });