Representing Hierarchies(gpfault.net)

14 pointsby ibobevil y a 6 mois2 comments

https://gpfault.net/posts/first-child-next-sibling.html

3 comments

I don't really love this solution since it runs into all the usual linked list issues, and is only 'allocation free' in the sense that the pointers are allocated with the structure if doing the intrusive thing they are talking about. Using the std::vector of pointers approach isn't going to be using crazily more memory.

Myself, I like to just allocate a too big block and shove everything into that then deal with indicies into that array if I care about performance. you can even flatten the tree in a way to get better locality if you care about that.

[deleted]il y a 6 mois

nice_byteil y a 6 mois

whether you allocate a big array and store indices into it or whether you keep pointers to dynamically allocated memory is orthogonal to how you actually represent the hierarchy.