Thread: 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!

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).