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