std：排序vs插入std :: set

我正在读cin的一些线段。每条线段都由一个起点和终点表示。 2D。 X和Y.std：排序vs插入std :: set

输入未排序。它是随机的。（更新：但我需要他们的排序条件为X，然后再由Y）

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

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

来源

2013-03-26 Agnel Kurian

@larsmans感谢您的纠正。从酒吧发布信息。 ;） – 2013-03-26 13:22:38

你为什么不试试呢？真实世界的表现数据>“互联网上的一些人告诉我的” – jalf 2013-03-26 13:24:05

@jalf我认为这是一个普遍接受的答案，这是一个老问题。另外，在做出决定之前，我应该尝试多少个不同的输入集？ – 2013-03-26 13:38:45

你应该测量两种方法的表现予以肯定，但它是一个安全的赌注假设std::sort上std::vector是方式不是插入到std::set由于当地的影响和大常量躲在树快插入算法。而且，随后的查找和迭代将会更快。

（然而，std::set更适合用于支撑的混合系列的插入和缺失/查找/迭代。在向量维持秩序是昂贵的，因为每个插入将就平均线性时间。）

来源

2013-03-26 13:19:24

哦，真的吗？那为什么呢？ – 2013-03-26 13:19:47

它取决于什么？ – 2013-03-26 13:20:07

@LightnessRacesinOrbit：插入树中的常量非常高（认为在红黑树中重新平衡）与优化排序中的常量相比。 – 2013-03-26 13:22:56

使用容器它具有适合您需求的适当语义。效率通常会自动从该选择开始。

如果然后你遇到性能瓶颈，做一些基准测试。

来源

2013-03-26 13:20:29

我的需求是，我应该能够从左到右遍历输入。如果两个输入具有相同的x，则较小的y胜。 – 2013-03-26 13:26:52

+1：语义第一，表现第二。 – 2013-03-26 13:55:44

@AgnelKurian如果您的数据没有固有的顺序，请使用一组。这是一个挤进一个袋子的东西。作为一种令人愉悦的副作用，您可以在迭代时获得字典（或任何您需要的）排序，所以如果您希望在最后使用它，那么也很方便。 – 2013-03-26 14:05:42

它确实不依赖，但它肯定std::set是用于随机插入和删除。在这种情况下，你只能插入。去std::vector。另外，也许更重要的是，如果事先知道有多少片段，则只需分配一次矢量，每次大小加倍时都不会重新分配内存。

来源

2013-03-26 13:27:24

作为一个很好的经验规则，严格的担保提供，性能越差，你会得到。

插入到std::set保证序列在每次插入后被排序。

插入到std::vector，并呼吁std::sort一次毕竟插入已经完成保证了顺序排序一旦上了vector所有操作已经完成。它不需要在所有中间插入过程中对矢量进行排序。

甲std::vector也表现出更好的空间局部性，且需要更少的内存分配。所以我将承担vector方法要快，但是如果性能对你很重要，那么它很重要，足以成为测量。

如果你不在乎什么来衡量你的情况更快为您数据集与您应用您代码，那么你不在乎这是更快。

来源

2013-03-26 13:56:05 jalf

std：排序vs插入std :: set

回答

相关问题