列表或容器O（1） – 插入/删除性能，具有数组语义
我正在寻找一个提供列表语义的集合，但也允许数组语义。 说我有一个包含以下项目的列表：
apple orange carrot pear 然后我的容器数组将：
container[0] == apple container[1] == orangle container[2] == carrot
然后说我删除了橙色元素：
container[0] == apple container[1] == carrot
我想在不必显式resize的情况下折叠数组中的间隙，即如果我删除容器[0]，则容器会崩溃，因此容器[1]现在被映射为容器[0]和容器[2]作为容器[1]等我仍然需要使用数组语义访问列表，并且不允许空值（在我的特定用例中）。
编辑：
回答一些问题 – 我知道O（1）是不可能的，但我不希望容器的数组语义接近O（log N）。 排序失败的目的，我可以迭代列表。
我最初在排序顺序上有一些措辞，我不确定我当时的想法（周五啤酒时钟最有可能）。 其中一个用例是包含图像的Qt列表 – 从列表中删除图像应该折叠列表，不必从列表中取出最后一项并将其放入其中。 在这种情况下，我确实希望保留列表语义。
我看到的主要区别是分隔列表和数组：数组 – 常量时间访问列表 – 任意插入
如果重新平衡使迭代器失效，我也不会过分担心。
您可以执行ArrayList / Vector（Java / C ++），当您删除时，首先将最后一个元素与deleted元素交换。 因此，如果您有ABCDE，并且您删除了C，那么您最终将使用ABE D.请注意，对E的引用现在必须查看2而不是4（假设0已编入索引），但您说排序顺序不是问题。
我不知道它是否自动处理（优化后可以轻松地从最终删除），但如果不是，你可以轻松编写自己的数组包装类。
O（1）可能要求太多。
O（logn）插入/删除/访问时间是否正常？ 然后你可以得到一个平衡的红黑树，其中包含订单统计信息： http ： //www.catonmat.net/blog/mit-introduction-to-algorithms-part-seven/
它允许您按位置插入/删除/访问元素。
正如Micheal所指出的那样，Java Treemap支持它： http ： //java.sun.com/j2se/1.5.0/docs/api/java/util/TreeMap.html
另外，不确定为什么你认为O（logN）和迭代列表一样糟糕！
从我对你的其他答案的评论：
对于100万件物品，使用平衡的红黑树，最坏的情况是2log（n + 1），即~40。 你需要做的不超过40比较找到你的元素，这是绝对最坏的情况。 红黑树也迎合洞/间隙消失。 这比重复列表要早几英里（平均约为1/2万！）。
使用AVL树而不是红黑树，最坏的情况保证甚至更好：1.44 log（n + 1），对于一百万个项目是~29。
您应该使用HashMap ，您将拥有O（1） – 预期的插入时间，只需执行从整数到任何的映射。
如果订单不重要，那么vector就可以了。 访问是O（1），使用push_back插入，并删除如下：
swap(container[victim], container.back()); container.pop_back();
编辑：刚刚注意到这个问题被标记为C ++和Java。 这个答案仅适用于C ++。
我不知道任何提供O(1)随机访问，插入和删除的数据结构，所以我怀疑你必须接受一些权衡。
Java中的LinkedList提供从列表的头部或尾部的O(1)插入/删除是O(1) ，但是随机访问是O(n) 。
ArrayList提供O(1)随机访问，但插入/删除只是列表尾部的O(1) 。 如果从列表中间插入/删除，则必须移动列表中的其余元素。 从好的方面来说，它使用System.arraycopy来移动元素，而我的理解是这在现代架构上基本上是O(1) ，因为它实际上只是复制内存块而不是单独处理每个元素。 我说的主要是因为仍然有工作要找到足够的连续自由空间块等等，而且我不确定那个大O可能是什么。
由于你似乎想在（接近）恒定时间插入任意位置，我认为使用std::deque是你在C ++中最好的选择。 与std::vector不同，deque（双端队列）被实现为内存页面列表，即分块矢量。 这使得在任意位置插入和删除是恒定时间操作（仅取决于双端队列中使用的页面大小）。 数据结构还在接近恒定的时间内提供随机访问（“arrays访问”） – 它必须搜索正确的页面，但这在实践中是非常快速的操作。
Java的标准容器库没有提供类似的东西，但实现很简单。
http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html中描述的数据结构是否可以执行您想要的任何操作？
Concurent SkipList Map怎么样？ 它做O（Log N）？