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

Subject: Re: [boost] [MultiIndex] Random Access mental model?
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-02 08:53:38

on Sat Nov 01 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:

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

No, only when coexisting with a "no-up-pointer random access index."  I
wasn't suggesting that should be the only random index structure.

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

How do you erase in O(1) from the middle of a random-access container?

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

Understood.

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

Suppose you wrote a library that provided only deque, and not vector, as
a random access container.  Your premise seems analogous to one that
says, "not having O(1) push_front for a random access container is a
problem."  I'm saying it's not a problem to lose a feature unless you
need it, especially if you get something in exchange.

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

No problem; it helped me think more clearly about what I was doing.

Thanks for taking the time,

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com