c++ - 我需要一个支持高效随机访问和 O(k) 插入和移除的容器

Question

我又试过问同样的question , 但我没有提供有关我的问题的基本信息，最终问了一个不同的问题。

我实现了一个数据结构，它是一棵树。这棵树的每个节点都有一个数组/vector/(随机访问结构)及其所有子节点，可以是任意多个。元素的插入/删除很容易，因为我们总是将此数组中的元素数加倍/除以二。

这就是 O(k) 插入/删除在此上下文中的含义。我们有 k 元素，我们追加 k 或删除 k/2。到目前为止，重建整个数据结构都很好。 动态数组(或 vector )有效。

提出问题的操作如下。有时我们必须“拆分” 一个有n 个子节点的节点，这意味着我们将子节点“划分”到不同的节点中。我们潜水的方式是连续成群结队。我猜想，这种拆分的最有效方法是在每个新节点的子节点所在的位置以及有多少节点(假设每个节点有 k 个子节点)有一个指针。但是，这些 child 的数量可能会改变，这不应该影响它的 sibling (或者更糟糕的是，整棵树)，即插入的执行时间应该是 O(k) 而不是 O(n)。我们如何做到这一点？

一个简单但低效的解决方法是，每次我们拆分一个节点时，我们用许多(与拆分部分一样多)“小”动态替换“大”children 数组数组。

下面的每一个“盒子”都是一个随机访问结构。

Answer 1

hashmap怎么样？ ？

它有平均 O(1) 访问、插入和删除平均情况； O(n) 最坏情况。