Good practices for managing references to dynamically allocated arrays

Hi!

I'd like to know what's considered today a good practice when you have dynamically allocated arrays, that can grow and shrink at run time, and the items in some arrays are references to the items in other ones.

In the past, I have always done this by using array indices as references. The drawback is that if some indices change (imagine some items are deleted in the middle of some array), other arrays referencing the modified one, need to be notified, and their indices values updated.

If you need a clear example, think of the typical array of vertices and the typical array of triangles built from vertex IDs from the array of vertices. Now you delete some triangles in the middle of the triangles array, which causes some vertices to become unused. Next, you delete the unused vertices. And then you need to update the indices in the triangle array, because they have potentially changed.

Another possibility is using unique always incrementing IDs that don't match array indices, but that are "object names" instead. However, this has the drawback that searching for a given ID is much more costly, because you need to loop through the whole array looking for it.

Yet another possibility is using arrays not of structs, but of pointers to structs. So, the vertices array would be an array of pointers to vertex structs, and the array of triangles could be made as pointers to the vertices too: these pointers would never change even if you delete or add more vertices in the middle of the array.

However, even if this approach is quite common (specially in C++), I don't completely like it because it's potentially very cache unfriendly, as every vertex can be very away from each other in memory, in random locations.

So, back to my question, what's considered the best practice today for this kind of situations?

Also, is there any established, widely used, mechanism or library for conveniently managing updates to arrays that depend on the array that was just modified? I mean, maybe some callback for notifying somethink like "your indices need to be updated in this way".

Thanks a lot!

The question isn't really about arrays. It's about graphs. A graph is a structure whereby nodes contain links to other nodes similar to themselves. Binary trees are the simplest non-degenerate graphs.
In C, it's natural to use a pointer to indicate a link. However sometimes this is a mistake, and it's better to hold your nodes in arrays and use an index as the link. It all depends. If you allow deletions, then either you have to mark nodes as "deleted" or you have to recalculate all your indices. One adds a lot of programming complexity, the ohter is very slow. So pointers might be a better option. If you allow insertions, you have to have a strategy for expanding the array, and that can take time and memory. On the other hand calling malloc() for every node is also likely to waste memory and kill cache performance. The trade-offs are many and it's impossible to give a definite answer.

However one thing that is always a good idea is to isolate the graph in a single master structure, that contains all the references to all the memory the
nodes use. Then you can delete the whole graph cleanly. You can also easily clone it, or serialise it to disk, and the structure of your program will benefit.

Thanks a lot, Malcolm. Let me express it this way: If N good programmers had to write in C a program where vertices and triangles that point to vertices could be created and deleted dynamically at run time, do you think all these N programmers would take the same implementation choice nowadays, or would they choose N different solutions?

I have read a bit about the difference between "structs of arrays" and "arrays of structs" (whose performance depends on how you access your data, obviously), but I'd like to read on recommended practices for updating references when the array they point to grows or shrinks (not only at the end of the array, which wouldn't need updating the references).