我面临一个需要设计容器的应用程序,容器需要具有随机访问功能(或至少比O(n)更好),插入和删除廉价(O(1)),并按照插入时指定的顺序(等级)存储数据。
例如,如果我有以下数组:
这些数字存储在一个序列中,插入/删除操作需要一个索引参数来指定应该插入数字的位置或应该删除哪个数字。
我的问题是,除了链表和向量之外,还有哪些数据结构可以维护这样的内容?我倾向于使用堆,在下一个可用索引上优先处理。但我看到一些关于融合树(Fusion Tree)很有用的东西(但更多是在理论上)。
哪种数据结构能够在保持内存消耗的同时给我最优化的运行时间?我已经尝试过保存插入顺序的哈希表,但迄今为止没有成功。
原因是我必须构建出一个在这些基本操作方面优于向量的东西。容器的大小可能会增长到数十万个元素,因此无法承担向量中的位移操作。同样的问题也适用于链表(即使是双向链表),在最坏情况下遍历到给定索引需要O(n/2),约为O(n)。
我曾考虑过一个包含头、尾和中间指针的双倍链接列表,但感觉不会好太多。
例如,如果我有以下数组:
[2, 9, 10, 3, 4, 6]
我可以调用在索引2上删除10,也可以调用在索引1上插入13。
经过这两个操作后,我的内容将变成:
[2, 13, 9, 3, 4, 6]
这些数字存储在一个序列中,插入/删除操作需要一个索引参数来指定应该插入数字的位置或应该删除哪个数字。
我的问题是,除了链表和向量之外,还有哪些数据结构可以维护这样的内容?我倾向于使用堆,在下一个可用索引上优先处理。但我看到一些关于融合树(Fusion Tree)很有用的东西(但更多是在理论上)。
哪种数据结构能够在保持内存消耗的同时给我最优化的运行时间?我已经尝试过保存插入顺序的哈希表,但迄今为止没有成功。
原因是我必须构建出一个在这些基本操作方面优于向量的东西。容器的大小可能会增长到数十万个元素,因此无法承担向量中的位移操作。同样的问题也适用于链表(即使是双向链表),在最坏情况下遍历到给定索引需要O(n/2),约为O(n)。
我曾考虑过一个包含头、尾和中间指针的双倍链接列表,但感觉不会好太多。
std::vector
吗?它真的是你应用程序的瓶颈吗?你有进行过测量吗? - MadScientist