RE: [boost] Pool Iterators?

From: scleary_at_[hidden]
Date: 2002-11-11 11:22:43

> I'm using boost::pool for (evidently) allocating memory for a whole 
> bunch of objects (thanks Stephen Cleary for pool).  Most of the time the 
> objects are entirely independent, however, from time to time, I'd like 
> to iterate through all the allocated objects (in this case to generate 
> some test statistics over then).  To do this I keep a list of pointers 
> to everything I've allocated.  The time spent keeping this list up to 
> date, particularly removing an object, is significant.
>
> One possible (and very nice fix) would be to have a pool_iterator that 
> let me, as I said, iterated through the allocated objects.  As far as I 
> can tell, this doesn't exist.  Does anyone have any comments on whether 
> this is a good idea, whether it's feasible, and perhaps how I might go 
> about it?

One possibility is to write an object type that sits between your object and
the pool allocator, which adds a single pointer to your object.  Something
similar to what a doubly-linked list container would do when rebinding its
Allocator.  This gives you the ability to iterate over them, and also allows
fast insertion and deletion.

A similar approach, if you're willing to more seriously change the code that
allocates/deallocates the objects, is to keep a doubly-linked list of
pointers to the allocated objects.  But then reference the objects
indirectly through iterators of that list.  If you reference them in this
way, then deletion should be fast.

> The pools don't seem to have a bit-map of free blocks - and traversing 
> the free list at every increment would be horribly slow.  I have a 
> "holey_vector" that uses a vector as storage, and keeps a sorted list of 
> free indexes, but I can't imagine this approach would work in a pool, 
> where the storage is a list of blocks at non-increasing addresses.  
> Marking blocks as free at the beginning of the block would take up at 
> worst a whole alignment worth of memory, kind of defeating the point of 
> the pool.
> 
> So I'm guessing the best approach would be a bit map of free blocks.  
> Comments?

I think that if you want to iterate over allocated objects, then keeping a
list of allocated objects is the best bet (whether it's a list of allocated
objects or a list of pointers to allocated objects).

        -Steve