如何在C++中实现动态可调整大小的数组而不进行复制

Question

我想实现一个动态数组，但我不想在扩展期间发生数组复制。这可以做到吗？

一个想法是生成一个指针数组，每个指针分配一个固定大小的块，但是这个指针数组也不能设计为可扩展的。

Answer 1

如果您希望在恒定时间内进行索引访问，这是不可能的，因为数组可能位于其他堆变量之间。 您能得到的最接近的是

realloc

。这使您可以增加现有的内存分配。但如果这是不可能的，它会将内容复制到新位置。

根据您的问题，可能还有其他解决方案：

• 你提前知道元素的最大数量吗？ =>

  std::vector

  +

  reserve()

• 您想要在恒定时间内插入/删除并且不需要索引访问吗？ =>

  std::list

• 您想在拥有所有数组属性的同时尽可能避免复制吗？ =>

  realloc

• 基于索引的访问在对数时间内是否足够？ => 二叉树

也可以进行一些混合。您可以存储指向例如块的指针列表。 10000 个元素并重载索引运算符。