Subject: [boost] [MultiIndex] Random Access mental model?
From: David Abrahams (dave_at_[hidden])
Date: 2008-10-31 16:37:28
I'm trying to get a grip on what it means when I have a random access
index in a multi_index_container. I have no mental model for what data
structure you're actually creating, which makes it difficult to evaluate
multi-index vs. hand-rolling my own container.
If I was doing this myself, I'd use a combination of these two:
because I need to maintain an LRU cache of what has been put in the map
(i.e. I need O(1) push_back and pop_front). MultiIndex only lets me use
sequenced<> which it implies essentially has the properties of
list<hash_map<key, value>::iterator>... although I can imagine you could
save a lot by using the same nodes for the hash_map and the list. Do
you do that?
Regardless, I could still save roughly one pointer per node with my
deque. I'd think about trying to modify MultiIndex to let it do random
access with deques, but I can't make head or tail of the implementation
code used for random access.
Could someone clarify what's going on in there?
-- 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