C - 是否将数组重新分配到数组,其大小是动态数据结构中的两倍？

Question

最近我用C编写了很多代码,我注意到,在我的程序中花费大部分时间的事情是调整动态数据结构的大小.假设我们有一个包含字符的数组,我想在这个数组的末尾添加一些字符.我这样做:

1. 检查是否分配了足够的内存.
2. 如果没有,realloc数组到大小两倍的数组(使用realloc)
3. 如果现在有足够的内存,请附加字符,否则转到第2点.

我只是想知道这是否足够有效.例如,我可以想到像树结构这样的东西,我将数组保存在树的节点中,这样,而不是在追加东西之前将旧元素复制到新数组,我只是将新的malloc'ed元素添加到下一个树的节点并在那里附加字符.这样我就可以避免不必要的复制......

所以这只是以不同方式调整大小的一种方式.我应该寻找其他的东西,还是我只是将旧元素复制到新数组的两倍大小的解决方案？

Answer 1

与所有"最有效"的问题一样,唯一可以知道的方法是衡量现实条件下的实际表现.

一般来说,在连续的内存位置中拥有项目可以获得很大的性能提升,因为对于任何一个接一个地处理项目的算法来说,这几乎总是缓存最友好的布局.总的来说,连续数组也占用较少的空间,因为您不需要额外的空间来存储其他数据(如树节点).

虽然在需要增长时将尺寸加倍是一种常见的方法,但它可能会占用地址空间.一些STL实现将向量之类的结构增长1.5倍而不是2倍以避免某些病态情况.在短期内,这会导致更多的分配,但可以减少内存碎片.如果您使用realloc,这可能适用也可能不适用.这取决于realloc成功执行的频率.