不使用realloc实现动态数组是否可行？避免扩容整体拷贝的方案咨询

下面是几种完全满足你需求的可行实现：

方案1：分块动态数组（Chunked Array） #

这是最适配需求的实现，完全规避了全量拷贝操作，访问效率也远高于你能接受的O(logN)标准：

• 核心思路：不申请整块连续内存存储元素，而是将元素拆分到多个固定大小的内存块（Chunk）中，再用一个独立的指针数组管理所有Chunk的起始地址。
• 扩容逻辑：当现有Chunk全部存满时，仅需要新申请一个空Chunk，把新Chunk的地址追加到指针数组末尾即可，全程不需要拷贝任何已存储的元素，完全避免realloc带来的重量级拷贝操作。
• 访问逻辑：访问下标为i的元素时，只需要做两次简单计算：
  1. 块索引：chunk_idx = i / CHUNK_SIZE
  2. 块内偏移：offset = i % CHUNK_SIZE
     最终通过chunks[chunk_idx][offset]即可访问到目标元素，时间复杂度为O(1)。
• 额外开销说明：仅需要维护的Chunk指针数组体积极小，比如将Chunk大小设为4096字节时，存储100万个元素仅需要维护200+个指针，哪怕指针数组需要扩容，拷贝成本也可以忽略不计。

方案2：间接索引动态数组 #

如果你需要对外暴露每个元素的独立指针，可以选择该方案：

• 核心思路：维护一个指针数组，每个数组位置存储对应下标的元素的堆内存地址，新增元素时仅为新元素单独申请内存，把地址追加到指针数组末尾即可。
• 访问逻辑：直接通过pointers[i]即可获取目标元素，时间复杂度为O(1)。
• 适用场景：适合元素本身尺寸较大的场景，指针数组的扩容拷贝成本同样极低。

方案3：平衡二叉树实现 #

如果你能接受O(logN)的访问复杂度，也可以用平衡二叉树（红黑树、AVL树均可）实现：

• 核心思路：每个树节点存储对应下标和元素值，新增元素时直接插入新节点，不需要任何已有数据的拷贝。
• 访问逻辑：通过树的查找逻辑定位对应下标的节点，时间复杂度为O(logN)，符合你的接受范围。
• 缺点：插入、访问、顺序遍历的开销都远高于分块数组，仅在特殊场景下推荐使用。

你之前考虑的哈希表方案并不适配需求，一来哈希表本身有哈希冲突、rehash的额外开销，二来无法很好支持数组的顺序遍历、下标连续访问等语义，上述三种方案都比哈希表更适合你的场景。

内容的提问来源于stack exchange，提问作者Alexander Vtyurin