std::sort与将元素插入std::set的比较

Question

我正在从cin中读取一些线段。每个线段由起点和终点表示。2D坐标系，包括X和Y。

输入的线段没有排序，是随机的。(更新: 但我需要先按X排序，然后再按Y排序)

我可以读取所有线段，将它们存储在一个向量中，然后调用std::sort函数进行排序。另一方面，我可以创建一个空的std::set并在每个线段到达时插入它。集合将自动维护排序顺序。这两种方法哪种更有效率？

更新：输入的总大小（线段数量）预先已知。

- Agnel Kurian

---

@larsmans 谢谢你的纠正。我正在酒吧里发帖。 ;) - Agnel Kurian

为什么不试试呢？真实世界的表现数据要比“互联网上一些人告诉我的”更有说服力。 - jalf

@jalf 我认为这是一个有普遍接受答案的旧问题。还有，在做出决定之前，我应该尝试多少个不同的输入集？ - Agnel Kurian

你应该尝试使用与实际使用相匹配的输入集。这样你就知道它在你的情况下的表现如何。 - jalf

@LightnessRacesinOrbit 是什么？在酒吧里发帖吗？ - Agnel Kurian

Answer 1

为确保效率，应该测量这两种方法的性能，但可以肯定的是，在一个 std::vector 上使用 std::sort 要比插入到 std::set 中要快得多，原因是由于局部性影响和隐藏在树插入算法中的大常数。此外，后续的查找和迭代也会更快。

(然而，std::set 更适合支持混合插入、删除、查找和迭代操作。在向量中维护顺序是很昂贵的，因为每次插入平均需要线性时间。)

- Fred Foo

---

哦，真的吗？那是为什么呢？ - Lightness Races in Orbit

@LightnessRacesinOrbit说，在树插入中的常数相当高（考虑红黑树中的重新平衡），与经过良好优化的排序算法相比。 - Fred Foo

Answer 2

作为一个通用准则，提供越严格的保证，性能就会越差。

将元素插入到std::set中可以确保序列在每次插入后都是有序的。

向std::vector中插入元素并在所有插入完成后调用std::sort一次，可以确保在对vector进行所有操作后，序列被排序一次。它不需要在所有中间插入时对vector进行排序。

std::vector也具有更好的空间局部性，并且需要更少的内存分配。 因此，我认为vector方法更快，但如果性能很重要，则其足以被“测量”。

如果您不关心通过“您的”代码在“您的”应用程序中使用“您的”数据集时哪个更快，那么您就不关心哪个更快。

- jalf

Answer 3

使用适合您需求的具有适当语义的容器。效率通常自动从这个选择中获得。

如果您随后遇到性能瓶颈，请进行一些基准测试。

- Lightness Races in Orbit

---

我的需求是，我应该能够从左到右遍历输入。如果两个输入具有相同的x，则较小的y获胜。 - Agnel Kurian

如果您的数据没有固有的排序，请使用集合。它是一堆东西被挤进一个袋子里。作为一个令人愉悦的副作用，当迭代时，您可以获得词典（或任何您需要的）排序，因此如果您最终需要它，那也很方便。 - Lightness Races in Orbit

Answer 4

确实取决于具体情况，但可以确定的是std::set适用于随机插入和删除。在这种情况下，您只需要进行插入操作，因此应选择std::vector。 此外，更重要的是，如果您预先知道有多少个段落，您只需一次分配向量，它将不会每次增加两倍大小时重新分配内存。

- Pieter van der Meer