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-11-01 15:03:41

>

Let me begin by commenting on the final part of the post:
you're absolutely right the overhead of deque<pointer> is less than
two pointers per element, not two as I was stating in a moment
of mental confusion. So, yes, hash_map+deque<pointer> is more
memory efficient than a multi_index_container<hashed,sequenced>
or a multi_index_container<hashed,random_access>. Sorry for
my error, I was thinking less carefully than I should.

Now with the rest of the post:

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

> 
> 
> on Sat Nov 01 2008, "JOAQUIN M. LOPEZ MUÑOZ" <joaquin-AT-tid.es> wrote:
> 
> > It is very difficult (I suspect impossible) to come up with a satisfactory
global
> > picture without this up-pointer. Consider just the following scenario:
> >
> > I have a multi_index_container<hashed,random_access> m and an
> > iterator to the hashed index it. m.erase(it) cannot be implemented
> > without the up-pointer in the random-access index. (If you don't
> > immediately realize why, picture yourself the hand-rolled composition
> > of a hashed_map and a deque<pointer>: you can't erase an element
> > from the combined structure given only a hash_map::iterator).
> 
> Yes, yes, I understood all that.  It's exactly what I was referring to
> when I wrote "look up a key in the hash index and delete that element."
> If you don't immediately see why that is the same thing you're talking
> about, well, please tell me.

OK, perfect; Let me elaborate a little more the potential
implications of having a random_index without up pointers:
hashed, ordered and sequenced indices all feature O(1) erase()
member functions mimicking those of std::unordered_set, std::set
and std::list, respectively. If I were to allow a no-up-pointer
random_access index, that'd mean that the interface of
the rest of the indices should elmiminate their erase member
functions, be it at compile time (the preferred way) or by
throwing or something at run time, or else provide O(N) erase
behavior, *when* they are coexisting with a randon_access
index. Not that this can't be done, at least in principle, but
it breaks the current index orthogonality in (IMHO) nasty ways.
What's more, the following type

  multi_index_container<random_access,random_access>

couldn't provide any O(1) erase method. Again, this is feasible
and in fact a natural implication of the data structures
involved, but my design choice was to avoid this kind of
anomalies and go for regularity and orthogonality. This
also implies that you can devise smarter data structures for
some particular purposes, like the case you're dealing with.
 
> > There are lots of additional problems, 
> 
> I disagree with your premise.  It's only a problem if it's a problem for
> me, 

I honestly don't understand what this statement means.

> and since I don't need that functionality I can use a lighter-weight
> data structure with no up-pointers, just like I'll use a vector instead
> of a deque when I don't need O(1) modification at the front.
> 
> > but I think this is sufficiently
> > serious to justify my decision. Basically, Boost.MultiIndex assumes
> > O(1) inter-index iterator projection (getting from an iterator in
> > an index to an iterator in another index pointing to the same element,
> > in constant time).
> 
> That's fine; it's not the right library for my application, then.

This is correct. For your purposes you can have a hand-rolled data
structure that beats any possible realization based on Boost.MultiIndex
in terms of memory efficiency. Sorry for having dragged this
thread longer than necessary with my initial confusion on the
ha_map+deque<pointer> issue.

[rest snipped as it was addressed at the beginning of this post]

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