找到合适的数据结构c ++

Question

我正在寻找一些简单实现的数据结构,它可以在最短的时间内完成我的需求(在最糟糕的情况下): -

(1)弹出第n个元素(我必须保持元素的相对顺序完整)
(2)访问第n个元素.

我无法使用数组,因为它不能弹出,我不想在删除ith元素后有一个间隙.我试图消除差距,通过将下一个元素与下一个元素交换到下一个直到最后,但这证明时间无效,尽管数组的O(1)是无与伦比的.

我尝试使用vector并使用'erase'进行弹出,使用'.at()'进行访问,但即使这对时间效率也不便宜,尽管它比数组更好.

Answer 1

您可以尝试的是跳过列表- 它支持您在 O(log(n)) 中请求的操作。另一种选择是分层向量，它更容易实现，并且需要 O(sqrt(n))。这两种结构都很酷，但可惜不是很受欢迎。