链表基于矢量

Question

我想使用的std::vector容器的缺点，并想知道如果使用的是分块链表的后端可避免当向量扩展发生副本。

类似于this。

我想我的问题是，这是一个实际的想法，我是否正确地认为从容器读取将具有与基于阵列的向量相似的运行时，而“增长”时间会大大减少？

Answer 1

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

为了访问元素N，你可能要经过许多环节才能到适当的块，然后通过块访问的元素。

大型矢量的性能可以通过预先分配更大的尺寸来降低。

如果插入和删除频繁，也许是一个矢量是错误的数据结构。

Answer 2

你可以用std::deque做一些实验，它只是作为你的描述。