最近我一直在用 C 编写大量代码，我注意到，在我的程序中花费最多时间的事情是调整动态数据结构的大小。假设我们有一个包含字符的数组，我想将一些字符附加到该数组的末尾。我这样做:
- 检查是否分配了足够的内存。
- 如果不是，则将数组重新分配为两倍大小的数组(使用重新分配)
- 如果现在有足够的内存，追加字符，否则转到第 2 点。
我只是想知道这是否足够有效。例如，我可以想到类似树结构的东西，我会在树的节点中保存数组，这样我就不会在附加内容之前将旧元素复制到新数组，而是将新的 malloc'ed 元素添加到下一个树的节点并将字符附加到那里。这样我就可以避免不必要的复制......
所以这只是以不同方式调整大小的一种方法。我应该寻找其他东西还是我的解决方案只是将旧元素复制到新数组的两倍大小是否足够有效？
最佳答案
与所有“最有效”的问题一样，唯一的了解方法是衡量现实生活条件下的实际表现。
一般来说，将项目放在连续的内存位置可以带来很大的性能提升，因为对于一个接一个地处理项目的任何算法来说，这几乎总是对缓存最友好的布局。总的来说，连续数组使用的空间也更少，这仅仅是因为您不需要额外的空间来存储额外的数据(如树节点)。
虽然在需要增长时将大小加倍是一种常见的方法，但它可能往往会耗尽地址空间。一些 STL 实现将 vector 等结构增长 1.5 倍而不是 2 倍以避免某些病态情况。在短期内，这会导致更多的分配，但会导致更少的内存碎片。如果您使用的是 realloc，那可能适用也可能不适用。这取决于 realloc 成功执行的频率。
关于C - 在动态数据结构中将数组重新分配为两倍大小的数组是否有效？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30649066/