data-structures - 找到合适的数据结构 C++

Question

我正在寻找一些简单实现的数据结构，它可以在最短的时间内满足我的需求( 在最坏的情况下 ):-

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

我不能使用数组，因为它不能弹出，我不想在删除第 i 个元素后有间隙。我试图通过将第 n 个元素与 next 再次与 next 交换直到 last 来消除间隙，但这证明时间效率低下，尽管数组的 O(1) 是无与伦比的。

我尝试使用 vector 并使用 'erase' 用于 popup 和 '.at()' 用于 access ，但即使这在时间效率方面也不便宜，尽管它比 array 好。

Answer 1

您可以尝试的是 skip list - 它支持您在 O(log(n)) 中请求的操作。另一种选择是 tiered vector这只是稍微容易实现并且需要 O(sqrt(n))。两种结构都很酷，但可惜不是很受欢迎。