java - 列表或容器 O(1)-ish 插入/删除性能，具有数组语义

Question

我正在寻找一个既提供列表语义又允许数组语义的集合。假设我有一个包含以下项目的列表:

apple orange carrot pear 

然后我的容器数组将:

container[0] == apple 
container[1] == orangle 
container[2] == carrot 

然后说我删除橙色元素:

container[0] == apple 
container[1] == carrot 

我想折叠数组中的间隙而不必进行显式调整大小，即如果我删除容器 [0]，则容器折叠，因此容器 [1] 现在映射为容器 [0]，并且容器[2] 作为容器 [1]，等等。我仍然需要使用数组语义访问列表，并且不允许空值(在我的特定用例中)。

编辑:

回答一些问题——我知道 O(1) 是不可能的，但我不希望容器的数组语义接近 O(log N)。有点违背了目的，我只能重复列表。

我最初在这里有一些关于排序顺序的废话，我不确定我当时在想什么(最有可能是周五啤酒时间)。其中一个用例是包含图像的 Qt 列表——从列表中删除图像应该会折叠列表，而不必从列表中取出最后一项并将其放在原位。然而，在这种情况下，我确实想保留列表语义。

我认为分离列表和数组的主要区别: 数组 - 恒定时间访问 列表——任意插入

我也不太担心再平衡是否会使迭代器失效。

Answer 1

您可以执行 ArrayList/Vector (Java/C++)，当您删除时，先将最后一个元素与删除的元素交换。因此，如果您有 A B C D E，然后删除 C，您将以 A B E D 结束。请注意，对 E 的引用现在必须查看 2 而不是 4(假设索引为 0)，但您说排序顺序不是问题.

我不知道它是否会自动处理此问题(针对轻松从末尾删除进行了优化)但如果不是，您可以轻松编写自己的数组包装器类。