Re: [boost] [MultiIndex] Random Access mental model?

Subject: Re: [boost] [MultiIndex] Random Access mental model?
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2008-10-31 17:39:57

David Abrahams <dave <at> boostpro.com> writes:
> 
> Hi,

Hi Dave, allow me to address this post of yours first and defer
the answer to the others you've send on Boost.MultiIndex, as
those will need more elaboration.

> I'm trying to get a grip on what it means when I have a random access
> index in a multi_index_container.  I have no mental model for what data
> structure you're actually creating, which makes it difficult to evaluate
> multi-index vs. hand-rolling my own container.
> 
> If I was doing this myself, I'd use a combination of these two:
> 
>    hash_map<key, value>
>    deque<hash_map<key, value>::pointer>
> 
> because I need to maintain an LRU cache of what has been put in the map
> (i.e. I need O(1) push_back and pop_front). MultiIndex only lets me use
> sequenced<> which it implies essentially has the properties of
> list<hash_map<key, value>::iterator>... although I can imagine you could
> save a lot by using the same nodes for the hash_map and the list.  Do
> you do that?

Yep, this is done. Only one node per element is allocated. This is
true regardless of the indices used, including random
access indices. If you want to visualize this, each element node
has as many node headers as indices are, each one stacked on top
of the next. Some indices (namely, hashed and random access) use
additional data structures external to the nodes themselves (this
is obvious in the case of hashed indices, as they are entirely
similar to unordered_set).

> Regardless, I could still save roughly one pointer per node with my
> deque.  I'd think about trying to modify MultiIndex to let it do random
> access with deques, but I can't make head or tail of the implementation
> code used for random access.

The data structure of a random access index is basically the
same as depicted for a little container I call stable_vector:

http://bannalia.blogspot.com/2008/08/stable-vectors.html

So, each element is stored in its own node (as is been already
said) and there is an additionally internal vector of pointers
that keeps the elements together while providing O(1)
access. The up-pointers described in the aforementioned article
are necessary to provide stable iterators.

The overhead of a random access index is one pointer per
node (the up-pointer) plus the size of the internal pointer
vector. Some figures are calculated at:

http://bannalia.blogspot.com/2008/09/introducing-stablevector.html

The deque-based structure you propose would save, as you
say, roughly one pointer per node with respect to sequenced
indices and also with respect to random access indices,
which have the up-pointer your proposed data structure lacks,
while on the other hand it requires an extra pointer as the deque
stores pointers while multi_index_containers enjoy the header
stacking property referred to above. So, roughly speaking, things
are even.

On the other hand, this up-pointer is essential to ensure
iterator stability and iterator projection, which are features
that currently the lib take for granted for all the different
index types available.

> Could someone clarify what's going on in there?

Hope the answer helped clarify the issue. Please come
back otherwise.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo