链接列表.在哪里分配以及如何应对碎片？

Question

• 地点
  • 在堆中,碎片化(每个节点的malloc) - 以几种不同的方式有效(缓慢分配,慢访问,内存碎片)
  • 在堆中,在一个大块中 - 当需要重新分配时,数据结构获得的所有灵活性都会丢失
  • 在堆栈中 - 堆栈的大小往往相当有限,因此根本不建议在其上分配大型结构

它们的巨大优势,即插入O(1),在碎片化内存的环境中看起来相当无用,并且数千次调用内存分配器给我们另外10个字节.

---

编辑澄清:
在一次采访中询问了这个问题.这不是一个工作场所的问题,所以通常的启发式方法是希望盲目地从一小组标准算法中找出正确的决策,这是不适用的.

现有的答案和评论提到"malloc不是那么慢","malloc部分地与碎片作斗争".好吧,如果我们使用另一种数据结构,例如C++向量的C端口(即 - 分配足够大小的顺序内存,如果数据扩展,重新分配到两倍大的块),所有问题都解决了,但我们放松了快速插入/删除.链接列表(分配在哪里？)的任何场景都具有对向量的巨大优势？

Answer 1

这听起来像是过早的优化.我认为正确的方法是:

1. 尽可能使用最简单的实现;
2. 描述整个计划.
3. 如果分析显示列表存在性能问题,请考虑替代实现(包括备用分配器).