我不知道这样的数据容器是否可能要求的时间复杂度。但是这里有两种方法，几乎​​可以解决这些复杂问题。

第一个是具有O（1）插入和索引但O（sqrt
N）删除的分层向量。由于您期望在此容器中只有大约10000个元素，而sqrt（10000）/ log（10000）=
7，因此您在此处几乎获得了所需的性能。分层向量是作为环形缓冲区的数组实现的，因此删除元素需要将所有元素移动到环形缓冲区中，然后将其移动，并将一个元素从随后的每个环形缓冲区中移到其前一个；在此容器中建立索引意味着在环形缓冲区数组中建立索引，然后在环形缓冲区内部建立索引。

可以创建一个与分层向量非常相似的不同容器，具有完全相同的复杂性，但是由于它对缓存更友好，因此工作速度更快。分配一个N元素数组以存储值。并分配一个sqrt（N）元素数组以存储索引更正（以零初始化）。我将在100个元素的容器示例中展示其工作原理。要删除索引为56的元素，请将元素57..60移至位置56..59，然后在索引更正数组中向元素6..9加1。要找到第84个元素，请在索引更正数组中查找第八个元素（其值为1），然后将其值添加到索引（84
+ 1 =
85），然后从主数组中获取第85个元素。在删除主数组中大约一半的元素后，有必要压缩整个容器以实现连续存储。这仅获得O（1）累积复杂度。对于实时应用，可以在几个较小的步骤中执行此操作。

可以将这种方法扩展到深度为M 的Trie，将O（M）时间用于索引编制，将O（M * N 1 / M）时间用于删除，将O（1）时间用于插入。只需分配一个N元素数组即可存储值N （M-1）/ M，N （M-2）/ M，…，N 1 /
M-element数组以存储索引更正。要删除元素2345，请在主数组中移动4个元素，在最大的“更正”数组中增加5个元素，在下一个中增加6个元素，在最后一个中增加7个元素。要从此容器中获取元素5678，请将元素5、56、567中的所有校正添加到5678，然后使用结果对主数组进行索引。为“
M”选择不同的值，您可以平衡索引操作和删除操作之间的复杂性。例如，对于N = 65000，可以选择M = 4；对于N = 65000，可以选择M =
4。因此建立索引仅需要4次内存访问，而删除更新只需4 * 16 = 64个内存位置。