我正在用 C++ 编写算法，为此我需要一个数据结构来存储一系列 n 数据点。也就是说，我想存储元素 v[0],v[1],...,v[n-1]。我确实关心顺序。
我想要快速的操作是:
- 顺序访问(即访问
v[0]，然后是v[1]等等，并具有编辑值的能力)； 点重定位，即
{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]};部分还原，即
{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) 时间内实现这些操作？
最佳答案
这取决于您没有提到的更多因素。
首先，这取决于元素的大小及其复制代码。如果你有小元素(大约 64 字节或更少)并且它们的复制(或移动)很便宜(或者甚至是微不足道的(在 POD 类型的意义上))，那么使用 std::vector可能是一个很好的选择，即使时间复杂度“更差”(顺便说一句，作为 future 的提示，不要过于追求最小的时间复杂度，这只是整个故事的一部分).
如果您的元素微不足道，则尤其如此，因为 vector 中的旋转操作将非常快(尽管仍然是 O(n))，而其他操作在与链表相比的时间复杂度。
其次，这取决于您执行上述不同操作的频率。通过链表进行顺序访问确实效率低下，如果您经常进行遍历，通常不建议使用它们。
如果您的元素太小以至于您考虑使用 XOR 链表(为每个元素保留一个指针)，那么您可能根本不应该使用链表。老实说，我不确定 XOR 链表是否真的值得(但我不想谈这个)。
总的来说，我不得不说您应该测试这三个选项:链表(std::forward_list 或 std::list )、std::vector ，或指针 vector (例如 std::vector< std::unique_ptr<T> > )。另一个选择可能是 unrolled linked-list ，但这只会在我提到的因素的特定范围内是好的。
我重申，我说的是测试，因为这是您真正了解什么是最好的唯一方法。根据我最喜欢的引述之一，“分析”仅用于经验法则，仅此而已:
As far as the laws of mathematics refer to reality, they are not certain; as far as they are certain, they do not refer to reality. (Albert Einstein)
关于c++ - 什么是快速插入+删除和部分反转的好数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22446831/