Re: [boost] [ptr_container] and [multi_index] ?

From: Janek Kozicki (janek_listy_at_[hidden])
Date: 2006-11-29 14:35:26

Joaquín M López Munoz said:     (by the date of Fri, 24 Nov 2006 21:04:14 +0000 (UTC))

> [...] 
> > 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,

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 ?

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

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 meantime
if 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.

-- 
Janek Kozicki                                                         |