我面临一个应用程序,我必须设计一个随机访问(或至少优于O(n))具有廉价(O(1))插入和删除的容器,并根据顺序存储数据(排名)插入时指定.
例如,如果我有以下数组:
[2, 9, 10, 3, 4, 6]
我可以调用索引2上的remove来删除10,我也可以通过插入13来调用索引1上的insert.
在我完成这两项操作之后:
[2, 13, 9, 3, 4, 6]
数字存储在一个序列中,插入/删除操作需要一个索引参数来指定应插入数字的位置或应删除的数字.
我的问题是,除了链接列表和向量之外,什么样的数据结构可以维护这样的东西？我倾向于优先考虑下一个可用索引的Heap.但我一直在看一些关于融合树有用的东西(但在理论意义上更多).
什么样的数据结构可以在保持内存消耗的同时为我提供最佳的运行时间？我一直在玩一个保留哈希表的插入顺序,但到目前为止它还没有成功.
我直接使用std :: vector折腾的原因是因为我必须根据这些基本操作构造一些预先形成向量的东西.容器的大小有可能增长到数十万个元素,因此承诺在std :: vector中进行转换是不可能的.带有链接列表的相同问题行(即使是双重链接),将其遍历给定索引将采用最坏情况O(n/2),其舍入为O(n).
我想到了一个包含Head,Tail和Middle指针的双倍链表,但我觉得它不会好多了.