列表或容器的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
然后我的容器阵列将：
then my container array would:
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（日志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名单 - 从列表中删除的图像应折叠列表，从列表中没有采取必要的最后一个项目，并把它扔在它的地方。在这种情况下，然而，我确实想preserve列表语义。
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 /矢量（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屋！
