Since I can't stop thinking about that, I'll try to describe the most difficult data structure that I have here. Maybe you will have some suggestions. And maybe it will help me to sort the thing out. In my program I am calculating bodies collisions and other kind of interactions. This is a physical simualtion stuff. I have a container (an easier one) with bodies where each body has an integer ID number. And the bodies can interact together, there are various kinds of interaction. And I need to store those interactions in a container. The keys are: - interaction type: each polymorphic interaction type stored in this container is a different kind of interaction. Sometimes I need to interate over all interactions of selected type, thus it becomes one of the keys. This is an integer. - a set of interacting bodies: any number of bodies can interact. Two or more bodies, but very rarely as much as four. - Sometimes I need to iterate over all interactions which involve a selected body or, - check if an interaction of given type between bodies 1, 2 and 3 already exists, then get it, or add it, if it didn't exist. This is a list of integer values (IDs of bodies). If I had only two-body interaction of single type then this could ba a (sparse) two dimensional symmetric matrix. Boost.Graph library treats two-body interaction as a graph edge, and the container used is std::vector<std::set<T> > > which works well for that. An example content of this container could be: interaction Type IDs of bodies involved +---------------------+-------------------------------------- | | (2,3) (2,3,4) (8,11,12,15) (13,14) +---------------------+-------------------------------------- | ElasticContact | X X X +---------------------+-------------------------------------- | MagneticInteraction | X X X +---------------------+-------------------------------------- | . | . | . The 'X' means that there is an instance present. One solution (a bit of pseudocode) could be: multi_index_container< interaction*, indexed_by< ordered_non_unique<member<interaction*,int,&interaction::type> > ordered_unique <member<interaction*,std::set<int>,&interaction::bodies> > // non_unique in fact. But uniqe with respect to &interaction::type. // That's why it's pseudocode
;
But how to make this and get a reasonable performance? And how to make that std::set<int> working? :) (or maybe tr1::hash_set<int>, if there is one) How to iterate over all interactions involving a body with ID 3 of type 1 ? For example I could use lazy deletion (only sets the field as unused), with cleaning invoked from time to time. Performance priorities (from most important, to least important): A)iterating over all elements with the same &interaction::type must be constant access time. B)finding if there is an interaction between (1,2,3) - great if it was constant time (N-dimensional matrix gives that), I guess that log(O) is the best we can have. C)deleting and adding an interaction, again I guess that constant time is not possible. D)iterating over all interactions involving a body with given ID is used less often so can be a bit slower. If you have any insights I'd appreciate that :) -- Janek Kozicki |