c - realloc 与链表 : no random access

Question

我正在编写一个包含这种结构的应用程序:

typedef struct Triangle{
    struct Triangle* Neighbor[3];

    some other datas...
} Triangle;

每个三角形都有 3 个邻居。请注意，三角形是双重连接的，因为三角形的邻居包含当前三角形作为其邻居。我的算法将遍历图表，有时添加一个新三角形，有时删除一个。它以 1 个三角形开始，到最后，我们将有 N 个三角形。

我事先知道 M 是 N 的平均值，我们也知道 N 很少大于 2M(可能有 5% 的时间)

---

为了给您一个更好的 View ，这段代码更新了三角形的邻居。

void update_triangle_neighbors(Triangle* T, Triangle* oldptr, Triangle* newptr){
    if(T->Neighbor[0]==oldptr)
        T->Neighbor[0] = newptr;
    else if(T->Neighbor[1]==oldptr)
        T->Neighbor[1] = newptr;
    else
        T->Neighbor[2] = newptr;
}

---

我有两个选择:

• 1: 一次分配一个 2M 的三角形数组，如果数组已经满了，当我们想添加一个新的三角形时，重新分配 1.5 倍以前的大小.

  要删除指针为 *toRemove 的三角形，我必须:

  • 1.1: 我更新 Neighbors:

    for(i=0; i<3; i++)
        update_triangle_neighbors(&(toRemove->Neighbor[i]), toRemove, NULL)
    

  • 1.2:将最后一个三角形的邻居更新为链接到*toRemove，而不是像以前那样链接到最后一个三角形

    for(i=0; i<3; i++)
        update_triangle_neighbors(&(LastTriangle->Neighbor[i]), LastTriangle, toRemove)
    

  • 1.3:将 *LastTriangle 复制到 *toRemove 中并减少包含数组大小的变量

• 2:每次我必须添加或删除三角形时，都使用malloc 和free。要删除指针为 *toRemove 的三角形，我必须:

  • 2.1:引用1.1.
  • 2.2 释放内存:free(toRemove)

---

1 方法的优点是它仅在 95% 的时间内执行一次 malloc，并且可以通过仅分配一个大数组来改善空间局部性。缺点是删除有点复杂，如果三角形太多，我们将不得不做一个realloc。

你认为最好的主意是什么？ (这是一个大学项目，我不知道我是否有时间同时实现和做一个基准测试)

TL;DR:当您几乎知道数组的大小时但不知道必须进行随机访问时的预分配链表或普通链表。

---

编辑:感谢大家的宝贵建议!之后我在这里回答了我自己的问题，但我仍然愿意接受建议:)

Answer 1

作为Andrew Henle指出，realloc() 将不起作用，因为它可能会更改整个数组在内存中的位置，并且所有 Triangle* 指针都会指向错误的地址。我可以用数组中的索引替换 Triangle* 指针，但这会使我所有的东西变得复杂，尤其是对于调试。

因此，我想我会选择第二种方法，这是迄今为止最简单的方法。此外，没有任何证据表明第一种方法可以更快。

---

加速

如果我想在我的程序运行良好时稍微加快它的速度，我仍然可以用这种方式实现我的“自己的 malloc”(如 hexasoft 建议的那样):

• 在开头分配一个2M的三角形数组
• 对于每个 malloc 调用:
  • 如果该数组中还有空间，则给出一个指向可用空间的指针
  • 如果没有剩余空间，就分配到其他地方(在 95% 的情况下，程序将终止，即使这种情况不会发生一次)

why do you even think of doing a realloc in this case ?

我真的不知道，回想起来真的很傻。地方在这里并不是那么重要，我准备移山去获得一点地方。