1

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

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

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

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

4

3 回答 3

3

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

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

于 2012-04-26T21:24:49.057 回答
2

有一个标准库算法可以做到这一点：

std::vector<Jet> v;
// populate v
std::partial_sort(v.begin(), v.begin() + 2, v.end());

v[0]现在是最小的元素，v[1]现在是第二小的元素；其余元素的顺序未指定。std::vector<>可以用 代替std::deque<>，因为后者也有随机访问迭代器。

（请注意，我链接到的页面上提到的复杂性是不正确的；C++11 §25.4.1.3 说复杂性是(last - first) * log(middle - first)。）

于 2012-04-26T23:27:00.913 回答
1

如果您需要最低的两个对象，您可以创建自己的搜索功能，该功能将在 O(N) 时间内运行。使用排序是 O(N log N) 时间。

于 2012-04-26T21:24:34.687 回答