c++ - 存储反转数据的向量

Question

我使用一个按索引引用列表中事物的协议。存储这些东西的自然方式是在向量中，所以我可以在恒定时间内随机访问。但是从本质上讲，向量的开头有很多摆弄，包括插入和删除。指数越低，越摆弄。结果是大量复制向量的其余部分。

我想以相反的方式存储东西，在更高的向量索引（即更高的地址）上存储更低的协议索引，以最大限度地减少内容移动，但仍然能够通过协议索引透明地随机访问元素。理想的容器将是 std::vector 的直接替代品，指针算术等除外。我仍然想要指针算术，但可以自己处理相反的顺序。

周围有这样的课吗？

也许是一些我找不到的提升容器或一些晦涩难懂的政策？

编辑：实际上，让我感到震惊的是，我可以使用一种在 index之前和index0之后保留空间的向量length-1。双端队列不像我想的那样构建，它使用大块内存代替，防止指针算术。

Answer 1

根据您的描述，听起来好像在向量的前面插入和删除了项目，导致向量的其余部分被移动。如果是这样，这意味着您不依赖于停留在特定索引的项目。这就提出了为什么插入和删除位于向量前面的问题——以保持排序顺序？

C++ 标准库中有许多容器维护对数时间插入和删除的排序顺序，例如std::multi_set.

当插入和删除非常本地化时，听起来像（但你不是很清楚），您可能可以使用游标间隙结构，也称为间隙缓冲区，将插入和删除减少到恒定时间，保持恒定时间索引。一个成本是索引涉及额外的间接。但这可能是过早的优化，所以如果性能很重要，请测量。