Re: [boost] [MultiIndex] Random Access mental model?

Subject: Re: [boost] [MultiIndex] Random Access mental model?
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-01 09:08:21

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