________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de David Abrahams [dave@boostpro.com] Enviado el: sábado, 01 de noviembre de 2008 0:47 Para: boost@lists.boost.org Asunto: Re: [boost] [MultiIndex] Random Access mental model? on Fri Oct 31 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:
Yep, this is done. Only one node per element is allocated. This is true regardless of the indices used, including random access indices. If you want to visualize this, each element node has as many node headers as indices are, each one stacked on top of the next.
I think random access shouldn't need to add a node header unless you want to do something like look up a key in the hash index and delete that element. Maybe a feature-model interface would be a more powerful way to approach this space, so we don't have to pay for what we don't use.
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). There are lots of additional problems, 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). [...]
The deque-based structure you propose would save, as you say, roughly one pointer per node with respect to sequenced indices and also with respect to random access indices, which have the up-pointer your proposed data structure lacks, while on the other hand it requires an extra pointer as the deque stores pointers while multi_index_containers enjoy the header stacking property referred to above.
So, roughly speaking, things are even.
Sorry, I don't see it. Since I need O(1) pop-front I am using sequenced<> which IIUC is a doubly-linked list. Therefore your nodes have this overhead:
next-in-list, prev-in-list, and next-in-hash-bucket = 3 pointers
and mine have only next-in-hash-bucket. Add one pointer of overhead in the deque and I am storing 2 pointers.
But your deque is a deque of *pointers*, so the (amortized) penalty of the deque is 2 pointers per element. Please take a look at the attached figure, where the resulting data structures are depicted for: * Boost.MultiIndex (hashed + sequenced), * Boost.MultiIndex (hashed + random access), * Hand-rolled composition (hash_map + deque). (The array labeled "deque<pointer>" does not do merit to the actual chunk-based structure used by most deque implementations, but you get the idea, there's on average one pointer per element). Do you see you've got four pointers (black dots) per element in the three structures? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
