什么是临时排序矢量的好方法？

我有一个std :: vector，我需要通过选定的算法对某些操作进行排序，但在其余时间保持其原始状态（例如，当它们进入时排序的项目）。什么是临时排序矢量的好方法？

很显然，我可以使用std ::副本创建一个临时矢量和排序，但我不知道是否有更好的方法，可能是通过时间戳的项目进入。

干杯

来源

2010-02-22 deworde

为什么？排序是'O（N log N）'，更不用说常数因子;复制是直接'N * sizeof（T）'内存写入假设POD元素。另外，您可以轻松地从基准测试中排除复制时间。 – kennytm 2010-02-22 17:37:18

假设POD元素，复制是恒定时间（提示：think * memcpy *），并且相当快。 – 2010-02-22 19:27:04

拷贝不是固定时间，@Stingray。这是O（N）。 – 2010-02-22 19:40:58

您可以创建一个std ::矢量保持第一向量的所有索引。然后，您可以按照您的喜好对索引向量进行排序。这应该是快速和最重要的，并不意味着你必须复制第一个向量（这可能更昂贵！）。

来源

2010-02-22 17:33:05 monoceres

对于最快的手指+1，张贴或多或少相同的答案。 – 2010-02-22 17:36:13

我会用一个老式的malloc'd指针数组，并称为qsort，但是这也可以。 – Joshua 2010-02-22 17:47:13

@Joshua：大多数时候，这会更好 - qsort通常比std :: sort慢很多。 – 2010-02-22 18:02:41

任何给定的矢量将在任何时候以最多一种方式排序。

有两个备选方案：

复制到一个临时的载体，那种任意的。除非矢量非常大并且空间有限，否则这几乎肯定是最好的方法。即使你担心性能，制作副本的成本也会小于排序的成本，而且如果复制的成本很高，排序将比复制慢得多。

或者，你可以保持某种方式（你提到的时间戳？）是能够向量进行排序回原来的顺序。这会很慢，因为如果矢量非常大，你只想这样做，但如果你不能创建临时矢量，这是实现它的唯一方法。

来源

2010-02-22 17:33:12

如果复制代码不是指针向量，则复制代价可能很高，也取决于副本是如何实现的。 – 2010-02-22 17:37:35

@Binary Worrier：我认为David的观点是，当矢量移动元素时，矢量上的排序操作会执行一堆副本。如果排序为O（n log n），则最初添加O（n）复制操作不会改变总体时间复杂度。 – 2010-02-22 18:15:41

如果复制是昂贵的，那么排序更是如此。您如何期望得到一个排序的向量而不将每个元素复制到新的位置？（实际上，复制构造函数可能比赋值运算符要贵得多，在这种情况下，正确的做法是修复复制构造函数。我没有想到复制构造函数应该更昂贵的情况。） – 2010-02-22 18:18:08

无论项目正在排序，你可以在有多个排序字段的结构包裹。

struct someThing 
{ 
    int sortOrder1; 
    int sortOrder2; 
    ... 
    int sortOrderN; 
    //payload data object here 
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear

（或可能的排序顺序添加到基础结构本身？）

当您需要可以计算出不同的排序顺序，并重新排序，这取决于排序顺序，你需要你的列表。

来源

2010-02-22 17:33:57 FrustratedWithFormsDesigner

如果你不介意的Boost一点点就可以使用多指标库。见我的this answer，你会发现一些示例代码。

基本上，它可以让你保持几个相同的数据的“意见”，每一个不同的顺序。在你的情况下，你可以保留一个“序列”视图，其中数据按照插入的顺序（如向量）和一个“排序”视图，其中数据按照某种标准排序（如地图）。

来源

2010-02-22 17:42:22 Manuel

我建议存储智能指针，原始数据，在每个vector。 std::vector允许您提供不同的排序方法。此外，使用智能指针时，将在删除对该项目的所有引用时自动销毁它们。

来源

2010-02-22 18:12:46

什么是临时排序矢量的好方法？

回答

相关问题