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
>> > 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
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
> 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.
>> > 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk