Janek Kozicki wrote:

Hi,

Is it possible to use those two together? I'm considering storing my polymorphic stuff into ptr_container but vector (or other standard containers) are not enough for my needs.

Using Boost.MultiIndex with Boost.PtrContainer would be great.

It's certainly something I have considered, though I'm not sure what the best approach is. It would take some investigation, and I'm not able to invest that time in the foreseeable future. OTOH, I would be happy to help out with feedback if someone took on the task. -Thorsten

Janek Kozicki wrote:

Thorsten Ottosen said: (by the date of Tue, 21 Nov 2006 00:03:21 +0100)

I'm still thinking how to best refactor my current containers. They are in bad need for refactoring and I'm still not sure where to go. MultiIndex + PtrContainer are one of alternatives. If it turns out that this is the way to go, I will want to try this task.

Also I'm sure that my new container will have to support threading. I was thinking about something like accessor methods that will lock for reading and lock for writing:

template <T> class my_superb_container {

// only one can write to item 'item_index', no reading allowed T& lock_write(int item_index);

// multiple reads of item 'item_index' are allowed, no writing const T& lock_read(int item_index); }

Lock will be released when leaving current block, in the destructor. (destructor of what? - still thinking about that).

It seems like a bad idea to mix threading into the container itself. Threading should be an orthogonal issue; once you have the container design worked out, threading can be added by your-self on top of that. -Thorsten

Thorsten Ottosen wrote:

It seems like a bad idea to mix threading into the container itself.

Unless you're designing lock-free data structures.

Mathias Gaunard said: (by the date of Tue, 21 Nov 2006 19:10:08 +0100)

Thorsten Ottosen wrote:

...

It seems like a bad idea to mix threading into the container itself.

Unless you're designing lock-free data structures.

good point. I didn't mention that. I want multiprocessor support to be transparent for the data structures. The 'bottom' data classes will not have to care about mutexes, etc - just focus on the most important thing that they are doing. -- Janek Kozicki |

Steve Nutt said: (by the date of Tue, 21 Nov 2006 14:53:22 -0500)

If it were desirable to mix the locking with the container, use a locking policy. This would allow no locking, mutexed locking, and perhaps atomic operations when available.

Iterators tend to be a pain. How do you propose the iterator would work when another thread is trying to change the container?

How about doing it in a similar way that I already described element access? To recall, elemnt handling would be: - accessor method for reading a sigle element (no writing can occur when reading, multiple reads are allowed). This means a mutex per every element. - accessor method for writing an element (no reading can occur when writing, and only one writing.) Analogously for whole container: - iterator is acquiared through accessor method for reading whole container (container cannot be changed when there is one or more iterators active - multiple iterators are allowed). This means a mutex per container. - to modify a container first a lock must be acquiared for writing (changing) a container. It will be granted only when there are not active iterators (only one write allowed, no reads allowed) The container will have to provide it's own (internal) versions of algorithms, just like PtrContainer does. In my case adding/removing an element will be rare. So I can live with locking whole container (and waiting till all iterators release the lock) for doing that. -- Janek Kozicki |

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 |

Hello Janek, Janek Kozicki <janek_listy <at> wp.pl> writes:

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). [...] 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?

Well, your proposed structure has reasonable performance and complies with all your requirements except the ability to iterate on interactions involving a given body. In order to get this extra feature, you might need to set up an extra container like std::[unordered_]multimap<int /* body ID */, interaction*> which is kept in sync with the multi-index container: when an interaction is inserted, the multimap must be fed as many entries as bodies the given interaction involves. I can't think of a more elegant solution than this, which is a pity since one of the key goals of B.MI is to elminate the need to manually maintain this kind of composite structures :( [...]

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 use hashed indices instead of ordered ones and also use an unordered_multimap for the additional data structure, you can get the performance you aim for, constant time for A), B), C) and D). HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

----- Mensaje original ----- De: Janek Kozicki <janek_listy@wp.pl> Fecha: Miércoles, Noviembre 29, 2006 8:36 pm Asunto: Re: [boost] [ptr_container] and [multi_index] ? Para: boost@lists.boost.org [...]

Many thanks, it helps me a lot. The additional data structure maybe will be used later if the performace of D becomes more important. Already a constant time for A,B and C is a really good news.

You assured me that going multi_index is the way to go. Therefore I should work my way through using PtrContainer and MultiIndex together. I guess that it will result in a new kind of container (mosty due to fact that PtrContainer is so different from ''typical'' containers), probably PtrMultiIndex ?

To be honest, I don't think there's any sensible way to merge these two from the outside, i.e. without internal changes to the libraries. One critical problem is that both containers (as most other containers do) reclaim element ownership. A humble substitute for PtrContainer would be to store shared_ptr<Base>s in a multi_index_container. Note that B.MI predefined key extractors allow you to handle (smart) pointers with minimal hassle: typedef multi_index_container< boost::shared_ptr<Base>, indexed_by< // note the key extractor does not mention any shared_ptr; // const_mem_fun automatically dereferences the pointers // to get to the Base& needed ordered_unique<const_mem_fun<Base,int,&Base::get_x> >, ... Of course, you lose many advantages Boost.PtrContainer is designed to provide you with, for instance: * Null pointer handling overhead as compared to shared_ptr, * Indirected interface (http://tinyurl.com/y6t7ja ).

Accessing keys through pointers will require the base class of everything that is stored in the container to contain all the necessary keys.

Not necessarily so: you can resort to const_mem_fun<> to use a virtual function as the key provider: class Base { virtual int get_x()const = 0; ... };

Currently I'm working on something else, so I will not start right now. It waits in my 'queue' :) I guess that the real coding will happen not earlier than in one/two months from now. But in the meantimeif you have some useful thoughts about merging MutliIndex and PtrContainer they are welcome. Maybe with your guidance (the authors of those two libraries) we will make it.

Nevertheless, when I will start this task I'll let you know by asking more specific questions about merging those two.

Good luck with your projects, don't hesitate to come back here for further discussion. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo