除了std::vector之外，还有保持排序的数据结构吗？

Question

我面临一个需要设计容器的应用程序，容器需要具有随机访问功能（或至少比O(n)更好），插入和删除廉价（O(1)），并按照插入时指定的顺序（等级）存储数据。

例如，如果我有以下数组：

[2, 9, 10, 3, 4, 6]

我可以调用在索引2上删除10，也可以调用在索引1上插入13。

经过这两个操作后，我的内容将变成:

[2, 13, 9, 3, 4, 6]

这些数字存储在一个序列中，插入/删除操作需要一个索引参数来指定应该插入数字的位置或应该删除哪个数字。

我的问题是，除了链表和向量之外，还有哪些数据结构可以维护这样的内容？我倾向于使用堆，在下一个可用索引上优先处理。但我看到一些关于融合树（Fusion Tree）很有用的东西（但更多是在理论上）。

哪种数据结构能够在保持内存消耗的同时给我最优化的运行时间？我已经尝试过保存插入顺序的哈希表，但迄今为止没有成功。

原因是我必须构建出一个在这些基本操作方面优于向量的东西。容器的大小可能会增长到数十万个元素，因此无法承担向量中的位移操作。同样的问题也适用于链表（即使是双向链表），在最坏情况下遍历到给定索引需要O(n/2)，约为O(n)。

我曾考虑过一个包含头、尾和中间指针的双倍链接列表，但感觉不会好太多。

- Code Doggo

---

你想遍历这个集合吗？这个集合的大致大小是多少？ - W.F.

你说“可以通过它们插入的顺序来定义”，但是你也想能够“在索引1处插入”。因此，实际上索引不是由顺序定义的，而是由插入时指定的索引定义的？ - Petr

你尝试使用过 std::vector 吗？它真的是你应用程序的瓶颈吗？你有进行过测量吗？ - MadScientist

std::vector非常快。尽管它是O(n)，但通常比LinkedList快得多。这里有全面的基准测试: http://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html。 也许你应该考虑使用std::map<int, value_tape>。它提供迭代器，大多数操作的复杂度为O(log N)。 - kkamil

@DanielH，请注意我的回答已经更新。 - Petr

Answer 1

在基本使用中，如果想要在任意位置插入和删除元素，可以使用链表。它们允许O(1)的插入/删除，但前提是您已经定位了要插入的列表位置。您可以“在给定元素之后”插入（即给定指向元素的指针），但不能像“在给定索引处”那样高效地插入。

要能够根据索引插入和删除元素，您将需要更先进的数据结构。我知道至少有两种这样的结构。

一种是绳子结构，在某些C++扩展中可用（SGI STL或通过#include <ext/rope>在GCC中）。它允许在任意位置进行O(log N)的插入/删除。

另一种允许O(log N)插入/删除的结构是隐式Treap(也称为隐式笛卡尔树)，您可以在http://codeforces.com/blog/entry/3767、Treap with implicit keys或https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys中找到一些信息。

隐式Treap也可以修改以允许在其中查找最小值(并支持更多操作)。不确定rope是否能处理这个。 更新: 实际上，我想您可以通过将任何O(log N)二叉搜索树(如AVL或红黑树)转换为"隐式键"方案来适应您的请求。一个一般的概述如下。

想象一棵二叉搜索树，每时每刻都将1、2、...、N作为其键存储（其中N是树中节点的数量）。每次更改树（插入或删除节点）时，我们重新计算所有存储的键，使它们仍然从1到新值N。这将允许在任意位置进行插入/删除操作，因为键现在是位置，但会需要太多时间来更新所有键。

为了避免这种情况，我们将不会明确地在树中存储键。相反，对于每个节点，我们将存储其子树中的节点数。因此，每当我们从树根向下移动时，我们可以跟踪当前节点的索引（位置）——我们只需要将我们左侧的子树大小相加。给定 k，这样可以在 O(log N) 时间内找到具有索引 k 的节点（即标准二叉搜索树的第 k 个节点）。然后，我们可以使用标准二叉树程序在该位置执行插入或删除操作。我们只需要更新更新期间更改的所有节点的子树大小即可，在 O(1) 时间内轻松完成，因此总插入或删除时间将像原始二叉搜索树一样为 O(log N)。

因此，使用任何 O(log N) 二叉搜索树作为基础，该方法允许以 O(log N) 时间在给定位置插入/删除/访问节点。您当然可以在节点中存储所需的附加信息（“值”），您甚至可以通过保持每个节点子树的最小值来计算树中这些值的最小值。

然而，前面提到的 treap 和 rope 更加先进，因为它们还允许拆分和合并操作（取子字符串/子数组和连接两个字符串/数组）。

- Petr

Answer 2

考虑使用跳表，在其可索引变体中可以实现线性时间排名操作。

有关算法（伪代码），请参见Pugh的《跳表食谱》。

也许上面@Petr概述的“隐式键”二叉搜索树方法更容易理解，甚至可能表现更好。

- davidbak