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.
Hacker News