std::vector 以外的保持等级的数据结构？
Rank-Preserving Data Structure other than std:: vector?
我面临一个应用程序，我必须设计一个容器，该容器具有随机访问（或至少优于 O(n)）具有廉价的 (O(1)) 插入和删除，并根据到插入时指定的顺序（等级）。
例如，如果我有以下数组：
[2, 9, 10, 3, 4, 6]
我可以在索引 2 上调用 remove 来删除 10，我还可以通过插入 13 在索引 1 上调用 insert。
在这两个操作之后我会：
[2, 13, 9, 3, 4, 6]
数字存储在一个序列中，insert/remove操作需要一个索引参数来指定应该插入数字的位置或应该删除的数字。
我的问题是，除了链表和向量之外，什么样的数据结构可以维护这样的东西？我倾向于优先考虑下一个可用索引的 Heap。但我一直看到一些关于 Fusion Tree 有用的东西（但更多是在理论上）。
什么样的数据结构可以给我最佳的 运行 时间，同时还能降低内存消耗？我一直在尝试保留哈希的插入顺序table，但到目前为止一直没有成功。
我直接放弃使用 std:: vector 的原因是因为我必须构建一些在这些基本操作方面优于 vector 的东西。 容器的大小有可能增长到数十万个元素，因此在 std::vector 中进行轮班是不可能的。同样的问题用一个链表（即使是双向链表），遍历它到一个给定的索引，最坏情况下需要 O(n/2)，四舍五入为 O(n).
我在想一个包含 Head、Tail 和 Middle 指针的双向链表，但我觉得它不会更好。
在基本用法中，为了能够在任意位置插入和删除，可以使用链表。它们允许 O(1) insert/remove，但前提是您已经在列表中找到要插入的位置。您可以插入 "after a given element"（即给定一个指向元素的指针），但您不能像插入 "at given index".
那样高效
为了能够在给定索引的情况下插入和删除元素，您需要更高级的数据结构。我知道至少存在两个这样的结构。
一个是 rope structure, which is available in some C++ extensions (SGI STL，或者在 GCC 中通过 #include <ext/rope>)。它允许 O(log N) insert/remove 在任意位置。
另一种允许 O(log N) insert/remove 的结构是隐式 treap（又名隐式笛卡尔树），您可以在 http://codeforces.com/blog/entry/3767, Treap with implicit keys or https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.
找到一些信息
也可以修改隐式 treap 以允许在其中找到最小值（并且还支持更多操作）。不确定绳子是否可以处理这个。
UPD：事实上，我猜你可以通过转换为你的请求调整任何 O(log N) 二叉搜索树（例如 AVL 或红黑树）它到 "implicit key" 方案。大纲如下。
想象一棵二叉搜索树，它在每个给定时刻存储连续数 1、2、...、N 作为它的键（N 是树中的节点数）。每次我们更改树（插入或删除节点）时，我们都会重新计算所有存储的键，以便它们仍然是从 1 到 N 的新值。这将允许 insert/remove 在任意位置，因为键现在是位置，但所有密钥更新需要太多时间。
为避免这种情况，我们不会将键显式存储在树中。相反，对于每个节点，我们将存储其子树中的节点数。因此，无论何时我们从树根向下，我们都可以跟踪当前节点的索引（位置）——我们只需要对我们左边的子树的大小求和。这允许我们在给定 k 的情况下找到具有索引 k 的节点（即，它是二进制标准顺序中的第 k 个搜索树），时间为 O(log N)。之后，我们可以使用标准的二叉树程序在该位置进行插入或删除；我们只需要更新在更新期间更改的所有节点的子树大小，但这很容易在每个节点更改的 O(1) 时间内完成，因此总的插入或删除时间将为 O(log N)，如原始二叉搜索树。
因此，此方法允许使用任何 O(log N) 二叉搜索树作为基础，在 O(log N) 时间内 insert/remove/ 访问给定位置的节点。你当然可以在节点中存储你需要的附加信息（"values"），你甚至可以通过保持每个节点的子树的最小值来计算树中这些值的最小值。
然而，前面提到的 treap 和 rope 更高级，因为它们还允许拆分和合并操作（采用 substring/subarray 并连接两个 strings/arrays）。
考虑一个跳跃列表，它可以在其 "indexable" 变体中实现线性时间排序操作。
算法（伪代码）见A Skip List Cookbook, by Pugh。
可能是上面@Petr 概述的 "implicit key" 二叉搜索树方法更容易获得，甚至可能表现更好。
我面临一个应用程序，我必须设计一个容器，该容器具有随机访问（或至少优于 O(n)）具有廉价的 (O(1)) 插入和删除，并根据到插入时指定的顺序（等级）。
例如，如果我有以下数组：
[2, 9, 10, 3, 4, 6]
我可以在索引 2 上调用 remove 来删除 10，我还可以通过插入 13 在索引 1 上调用 insert。
在这两个操作之后我会：
[2, 13, 9, 3, 4, 6]
数字存储在一个序列中，insert/remove操作需要一个索引参数来指定应该插入数字的位置或应该删除的数字。
我的问题是，除了链表和向量之外，什么样的数据结构可以维护这样的东西？我倾向于优先考虑下一个可用索引的 Heap。但我一直看到一些关于 Fusion Tree 有用的东西（但更多是在理论上）。
什么样的数据结构可以给我最佳的 运行 时间，同时还能降低内存消耗？我一直在尝试保留哈希的插入顺序table，但到目前为止一直没有成功。
我直接放弃使用 std:: vector 的原因是因为我必须构建一些在这些基本操作方面优于 vector 的东西。 容器的大小有可能增长到数十万个元素，因此在 std::vector 中进行轮班是不可能的。同样的问题用一个链表（即使是双向链表），遍历它到一个给定的索引，最坏情况下需要 O(n/2)，四舍五入为 O(n).
我在想一个包含 Head、Tail 和 Middle 指针的双向链表，但我觉得它不会更好。
在基本用法中，为了能够在任意位置插入和删除，可以使用链表。它们允许 O(1) insert/remove，但前提是您已经在列表中找到要插入的位置。您可以插入 "after a given element"（即给定一个指向元素的指针），但您不能像插入 "at given index".
那样高效为了能够在给定索引的情况下插入和删除元素，您需要更高级的数据结构。我知道至少存在两个这样的结构。
一个是 rope structure, which is available in some C++ extensions (SGI STL，或者在 GCC 中通过 #include <ext/rope>)。它允许 O(log N) insert/remove 在任意位置。
另一种允许 O(log N) insert/remove 的结构是隐式 treap（又名隐式笛卡尔树），您可以在 http://codeforces.com/blog/entry/3767, Treap with implicit keys or https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.
找到一些信息也可以修改隐式 treap 以允许在其中找到最小值（并且还支持更多操作）。不确定绳子是否可以处理这个。
UPD：事实上，我猜你可以通过转换为你的请求调整任何 O(log N) 二叉搜索树（例如 AVL 或红黑树）它到 "implicit key" 方案。大纲如下。
想象一棵二叉搜索树，它在每个给定时刻存储连续数 1、2、...、N 作为它的键（N 是树中的节点数）。每次我们更改树（插入或删除节点）时，我们都会重新计算所有存储的键，以便它们仍然是从 1 到 N 的新值。这将允许 insert/remove 在任意位置，因为键现在是位置，但所有密钥更新需要太多时间。
为避免这种情况，我们不会将键显式存储在树中。相反，对于每个节点，我们将存储其子树中的节点数。因此，无论何时我们从树根向下，我们都可以跟踪当前节点的索引（位置）——我们只需要对我们左边的子树的大小求和。这允许我们在给定 k 的情况下找到具有索引 k 的节点（即，它是二进制标准顺序中的第 k 个搜索树），时间为 O(log N)。之后，我们可以使用标准的二叉树程序在该位置进行插入或删除；我们只需要更新在更新期间更改的所有节点的子树大小，但这很容易在每个节点更改的 O(1) 时间内完成，因此总的插入或删除时间将为 O(log N)，如原始二叉搜索树。
因此，此方法允许使用任何 O(log N) 二叉搜索树作为基础，在 O(log N) 时间内 insert/remove/ 访问给定位置的节点。你当然可以在节点中存储你需要的附加信息（"values"），你甚至可以通过保持每个节点的子树的最小值来计算树中这些值的最小值。
然而，前面提到的 treap 和 rope 更高级，因为它们还允许拆分和合并操作（采用 substring/subarray 并连接两个 strings/arrays）。
考虑一个跳跃列表，它可以在其 "indexable" 变体中实现线性时间排序操作。
算法（伪代码）见A Skip List Cookbook, by Pugh。
可能是上面@Petr 概述的 "implicit key" 二叉搜索树方法更容易获得，甚至可能表现更好。