c++ - 快速部分排序对象

Question

我有一个例程，我在其中定义了一堆对象(大约 20 个)，称它们为 Jet ，它有一个定义的 <我用来对它们进行排序的。排序后，我取最低的两个。什么是快速的方法来做到这一点？到目前为止我想到的选项:

1. boost::ptr_vector<Jet>使用内置 .sort() , 取前两个,
2. boost::ptr_list<Jet> , 使用 .sort() , 取前两个
3. 使用上面的列表，但不是排序，而是使用 max_element ，删除元素，然后再次运行。

我假设使用 std::vector<Jet>将是最糟糕的选择，因为:我不需要随机访问；排序将在内存中移动对象；调用 push_back(Jet) 时将复制对象.由于需要复制，我还假设 std::list<Jet>会比boost::ptr_list<Jet>差.我进一步假设服用 max_element两次会比排序整个列表更快。

我的逻辑合理吗？性能差异会很大吗？还有其他我没有想到的选择吗？

Answer 1

您的一个假设是正确的，因为存储指针而不是对象会更快。

但是，如果您只需要两个最小的元素，则无需对任何内容进行排序。只需取前两个元素，然后遍历 vector 或 list 的元素并保留较小的元素。