Probably Dance

In graph like data structures (explicit or implicit) there is a problem of memory safety when you remove a node. You have to clean up all the connections pointing to you. If your graph structure is explicit this is easy, otherwise it can often be annoying to find all pointers pointing to you. A while ago I thought that you could solve that by introducing a two way pointer, which has to be the same size as a normal pointer, but which knows how to disconnect itself on the other side, so that you don’t have to write any clean up code.

The reason why it turned out surprisingly useful is that if both ends of the connection know about each other, I can make them keep the connection alive even if one of them is moved around. So if one of them lives in a std::vector and the vector reallocates, the TwoWayPointer can handle that case and just change the pointer on the other end to point to the new location. That can dramatically simplify code.

One example is that I’m now using it in my signal/slot class which I’ve also included in this blog post. It allowed me to simplify the signal/slot implementation a lot. Compare it to your favourite signal implementation if you want. There is usually a lot of code overhead associated with memory safety. That all went away in this implementation.

Read the rest of this entry »