Jump to content
  • Advertisement
Sign in to follow this  

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

This topic is 3633 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!