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