c++ - 基于链表的向量

Question

我在考虑使用std::vector容器的缺点，并且想知道使用分块链表作为后端是否可以避免在向量扩展时发生的复制。

像这样的东西。

我想我的问题是，这是一个实用的想法吗？我是否可以假设从容器中读取的运行时间与基于数组的向量相似，而“增长”时间会大大减少？

Answer 1

您可以使用 做一些实验std::deque，这只是您的描述。

Answer 2

您的解决方案的运行时（随机）访问将大于std::vector.

为了访问 element N，您可能必须通过许多链接才能到达相应的块，然后通过该块访问一个元素。

可以通过预先分配更大的大小来降低大向量的性能。

如果插入和删除频繁，则向量可能是错误的数据结构。