This is a problem that I have hit several times, and I've never found a solution that I really like, so I'm wondering how other people deal with this situation. It's quite a general problem: I have some data structure, and I would like to attach some extra information about the items in the data structure, without (visibly) affecting the original structure. To make it slightly more concrete:

• If the data structure is an array it's relatively easy - just refer to everything by index and keep a second array with the extra data (although even this gets hairy if the items ever move).
• Usually, the data structure I have this problem with is some kind of graph (often more constrained than that, say a DAG or a tree).
• Often, the main data structure will contain only static data (it gets loaded and then doesn't change after that), although I'd prefer solutions that don't rely on this.

Here's a specific example: I'm currently writing an inverse kinematics solver. I have a Skeleton data structure, which is effectively a graph of bones (it's sort of a tree, but not really since it doesn't actually have a root). The skeleton structure is static data - it's loaded and then doesn't change. On top of that I have a Pose, which needs to attach current-orientation information to each bone (and as it stands at the moment a Pose does have a root). Finally I have an IkSolver which is used to update a Pose - it's likely that this will also need some per-bone information for more sophisticated IK algorithms. At the moment I'm dealing with this by storing all the bones in an array (an array of pointers actually so that the individual bone objects won't change location in memory), which lets me set up isomorphic arrays in Pose and IkSolver. Each bone then stores its own index in the array so that I can get back from Bone->array when necessary. I don't really like this solution though - it feels clumsy and maybe slightly fragile, and the data structure isomorphism/data association isn't really encapsulated nicely. For reference, I'm using C++. Any thoughts? John B

Quote:Original post by pinacolada
As a fallback, you can always make a hashmap that stores an association between the address of your existing data structure.

I've been wondering about that, but I was put off by the weight of the association data structure. However, I suspect a carefully implemented hash table is actually likely to be the best way to go.

Do you happen to know of any hash functions that are optimized for hashing pointers?

John B