Sign in to follow this  
JohnBSmall

How to non-intrusively attach extra data to a data structure?

Recommended Posts

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

Share this post


Link to post
Share on other sites
As a fallback, you can always make a hashmap that stores an association between the address of your existing data structure, and whatever extra data you want to record.

It might look vaguely like this:


// these are the existing data structures, which you don't modify
Person* Joe;
Person* Henry;

struct ExtraPersonData {
bool isCool;
ExtraPersonData(bool b) : isCool(b) {}
};

std::map<Person*, ExtraPersonData> extraDataPerPerson;

extraDataPerPerson[Joe] = ExtraPersonData(true);
extraDataPerPerson[Henry] = ExtraPersonData(false);

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this