Boost logo

Boost :

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:

   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

Boost list run by bdawes at, gregod at, cpdaniel at, john at