on Fri Oct 31 2008, David Abrahams <dave-AT-boostpro.com> wrote:
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.
Actually, MultiIndex could give me *almost* everything I need by threading a singly-linked list through the hash nodes (instead of doubly-linked). That's enough for a FIFO queue. Turns out I need a little more than that; I essentially need a bool that tells me whether the node is in the FIFO queue yet. Since I can use a NULL queue pointer for that purpose, it looks like I'll be rolling my own. -- Dave Abrahams BoostPro Computing http://www.boostpro.com