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

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++),当您删除时,首先将最后一个元素与deleted元素交换.因此,如果您有ABCDE,并且您删除了C,那么您最终将使用ABE D.请注意,对E的引用现在必须查看2而不是4(假设0已编入索引),但您说排序顺序不是问题.

我不知道它是否自动处理(优化后可以轻松地从最终删除),但如果不是,你可以轻松编写自己的数组包装类.