[boost] [MultiIndex] Random Access mental model?

Subject: [boost] [MultiIndex] Random Access mental model?
From: David Abrahams (dave_at_[hidden])
Date: 2008-10-31 16:37:28

Hi,

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:

   hash_map<key, value>
   deque<hash_map<key, value>::pointer>

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