3

我正在用 C++ 编写算法，为此我需要一个数据结构来存储一系列n数据点。也就是说，我想存储元素v[0],v[1],...,v[n-1]。我确实关心订单。

我想要快速的操作是：

  1. 顺序访问（即访问v[0]、 thenv[1]等，并具有编辑值的能力）；

  2. 点重定位，即

    {v[0],v[1],...,v[i],v[i+1],...,v[j-1],v[j],v[j+1],...,v[n-1]}-> {v[0],v[1],...,v[i],v[j],v[i+1],...,v[j-1],v[j+1],...,v[n-1]};

  3. 部分反转，即

    {v[0],...,v[i],v[i+1],...,v[j-1],v[j],v[j+1],...,v[n-1]}-> {v[0],...,v[i],v[j],v[j-1],...,v[i+1],v[j+1],...,v[n-1]}。

看来，我可以使用XOR-linked list来实现我的算法，并且它会给出最小的复杂度（上面的操作将是O(1)，给出O(n^2)我的算法）。但我知道，异或链表被认为是“丑陋的数据结构”（[1]，[2]）。

有什么比这更好的数据结构？更准确地说，有没有其他常用的数据结构，O(1)及时实现这些操作？

4

2 回答 2

1

这取决于您没有提到的更多因素。

首先，这取决于元素的大小及其复制代码。如果您有小元素（大约 64 字节或更少）并且它们的复制（或移动）很便宜（甚至，微不足道（在 POD 类型的意义上）），那么使用std::vector可能是一个非常好的选择，即使使用“更糟”的时间复杂度（顺便说一句，作为未来的提示，不要太执着于追求最小的时间复杂度，这只是整个故事的一部分）。

如果您的元素是微不足道的，则尤其如此，因为向量中的旋转操作将非常快（尽管仍然是 O(n)），而与链表相比，其他操作在时间复杂度方面是相同的.

其次，这取决于您执行您提到的不同操作的频率。通过链表进行顺序访问确实效率低下，如果您经常进行遍历，则通常不建议使用它们。

如果您的元素太小以至于您考虑使用 XOR 链接列表（为每个元素保留一个指针），那么您可能根本不应该使用链接列表。老实说，我不确定 XOR 链接列表是否真的值得（但我不想进入那个）。

总的来说，我不得不说你应该测试这三个选项：链表（std::forward_list或者std::list），std::vector或者指针向量（例如std::vector< std::unique_ptr<T> >）。另一种选择可能是展开的链接列表，但这仅在我提到的特定因素的特定范围内是好的。

我重申，我说过测试它们，因为这确实是你知道什么是最好的唯一方法。根据我最喜欢的一句话，“分析”仅适用于经验法则，仅此而已：

就数学规律而言，它们是关于现实的，它们是不确定的。就它们确定的而言，它们并不涉及现实。（艾尔伯特爱因斯坦）

于 2014-03-17T05:27:37.217 回答
0

如果您发现操作在实践中过于昂贵，我只会使用std::vector<T>, 然后只寻找可能更有效的数据结构。

  1. 的顺序访问std::vector<T>非常有效。
  2. 该std::rotate算法适用于操作 2。
  3. 该std::reverse算法适用于操作 3。

提到的算法在<algorithm>标题中。

于 2014-03-17T04:20:09.570 回答