C++:容器替换大小的vector/deque

Question

所以我的应用程序拥有包含1亿个元素的容器.

我正在寻找一个容器,它的行为 - 时间方面 - 比std :: deque(更不用说std :: vector)更容易在整个容器中频繁插入和删除...包括在中间附近.对第n个元素的访问时间不需要像vector那样快,但是应该比std :: list(每个元素都有巨大的内存开销)定义要好于完全遍历.

元素应按索引排序(如vector,deque,list),因此std :: set或std :: unordered_set也不能正常工作.

在我坐下来自己编写这样一个容器之前:有没有人见过这样的野兽？我很确定STL没有这样的东西,期待BOOST我找不到我能用的东西,但我可能错了.

任何提示？

Answer 1

我认为您可以通过跳过列表获得您想要的性能特征：

当然，这是您感兴趣的“可索引”部分——您实际上并不希望对项目进行排序。因此需要进行一些修改，我将其作为练习。

您可能会发现 1 亿个列表节点开始使 32 位地址空间紧张，但在 64 位中可能不是问题。