c++ - std:sort 与插入 std::set

Question

我正在从 cin 中读取一些线段。每条线段由起点和终点表示。二维。X 和 Y。

输入未排序。它是随机顺序的。（更新：但我需要它们先按 X 排序，然后按 Y）

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

更新：输入的总大小（段数）是预先知道的。

Answer 1

您应该确定这两种方法的性能，但可以肯定的是，由于局部效应和隐藏在树插入算法中的大常数，假设on比std::sort插入到 an 中要快得多std::vector。此外，后续的查找和迭代会更快。std::set

（然而，std::set更适合支持混合的插入和删除/查找/迭代系列。维护向量中的顺序很昂贵，因为每次插入平均需要线性时间。）

Answer 2

作为一个好的经验法则，提供的保证越严格，您获得的性能就越差。

插入 astd::set可以保证在每次插入之后对序列进行排序。

插入到 astd::vector中并在所有插入完成后调用std::sort 一次可确保在完成所有操作后对序列进行排序vector。它不需要在所有中间插入期间对向量进行排序。

Astd::vector还表现出更好的空间局部性，并且需要更少的内存分配。所以我会假设这种vector方法更快，但如果性能对你很重要，那么它就足够重要了，可以衡量。

如果您不在乎使用应用程序中的代码来衡量您的数据集在您的情况下哪个更快，那么您不在乎哪个更快。

Answer 3

它确实取决于，但可以肯定的是，它std::set是用于随机插入和删除的。在这种情况下，您只是插入。一起去std::vector。此外，也许更重要的是，如果您事先知道有多少段，您只需分配一次向量，它不会在每次大小翻倍时重新分配内存。

Answer 4

根据您的需要使用具有适当语义的容器。效率通常会自动从该选择中产生。

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