列表或容器 O(1)-ish 插入/删除性能，具有数组语义 [英] list or container O(1)-ish insertion/deletion performance, with array semantics

问题描述

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

I'm looking for a collection that offers list semantics, but also allows array semantics. Say I have a list with the following items:

apple orange carrot pear 

那么我的容器数组将:

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

然后说我删除橙色元素:

Then say I delete the orange element:

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

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

I want to collapse gaps in the array without having to do an explicit resizing, Ie if I delete container[0], then the container collapses, so that container[1] is now mapped as container[0], and container[2] as container[1], etc. I still need to access the list with array semantics, and null values aren't allow (in my particular use case).

回答一些问题 - 我知道 O(1) 是不可能的，但我不想要一个数组语义接近 O(log N) 的容器.有点违背了目的，我可以迭代列表.

To answer some questions - I know O(1) is impossible, but I don't want a container with array semantics approaching O(log N). Sort of defeats the purpose, I could just iterate the list.

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

I originally had some verbiage here on sort order, I'm not sure what I was thinking at the time (Friday beer-o-clock most likely). One of the use-cases is Qt list that contains images - deleting an image from the list should collapse the list, not necessary take the last item from the list and throw it in it's place. In this case, yet, I do want to preserve list semantics.

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

The key differences I see as separating list and array: Array - constant-time access List - arbitrary insertion

我也不太担心重新平衡是否会使迭代器失效.

I'm also not overly concerned if rebalancing invalidates iterators.

推荐答案

你可以做一个 ArrayList/Vector (Java/C++)，当你删除时，先将最后一个元素与被删除的元素交换.因此，如果您有 ABCDE，并且您删除了 C，您最终会得到 ABE D.请注意，对 E 的引用现在必须查看 2 而不是 4(假设索引为 0)但您说排序顺序不是问题.

You could do an ArrayList/Vector (Java/C++) and when you delete, instead swap the last element with the deleted element first. So if you have A B C D E, and you delete C, you'll end up with A B E D. Note that references to E will have to look at 2 instead of 4 now (assuming 0 indexed) but you said sort order isn't a problem.

我不知道它是否会自动处理这个问题(优化后可以轻松删除)，但如果不是，您可以轻松编写自己的数组包装类.

I don't know if it handles this automatically (optimized for removing from the end easily) but if it's not you could easily write your own array-wrapper class.

这篇关于列表或容器 O(1)-ish 插入/删除性能，具有数组语义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！