RE: [boost] Pool Iterators?

From: Geoff Leyland (geoff.leyland_at_[hidden])
Date: 2002-11-11 12:52:33

Hi Steve,

Thanks for the reply.

On Lundi, novembre 11, 2002, at 06:00 , scleary_at_[hidden] wrote:

> 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.

This pretty much what I've got.  There's an object that talks to a the 
pool, and remembers everything that I've allocated in a vector (actually 
a holey_vector).
This was really slow for deleting something, because searching through a 
list of 20000 pointers for the one you want is a waste of time.
I solved that my sticking a back-pointer in the object itself. This is a 
sufficient solution, but I think it lacks elegance compared to a 
possible pool_iterator, but, if you think it's the best idea, I'll go 
that way.

One of the reasons I like the pool_iterator is that I store the pointers 
themselves in a vector with "holes".  This makes insertion and deletion 
in the vector very fast, and you can iterate through it very quickly.  
The free list is a map of free indexes, which means it's easy to work 
out as you walk through the list which elements are free, and also, that 
any new allocations into free space are at the bottom of the list, so, 
with a bit of luck, you can cut the end off a shrinking list.
I was pretty much of the opinion that this was just a cheap and nasty 
substitute for a real pool allocator (it's what I was using before I 
used pool), not in the least because when the vector resizes the whole 
thing moves.

There's stuff in the code and comments about an "ordered" free list.  If 
you can excuse my ignorance, does this mean that it's potentially 
possible to walk through the pool's storage at the same time as walking 
through the ordered free list and find out fairly cheaply which blocks 
are free?

> 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.

That's not a bad idea.  The easiest would be to just stick next and prev 
pointers in the objects themselves.  But even so, if pool_iterators were 
possible in a generic way, everyone would benefit, and my code would 
"just work".

cheers,
goof

--
"To a man with a hammer, everything looks like a nail."
- Mark Twain
Geoff Leyland, Village Idiot
Laboratoire d'energetique industrielle
LENI-DGM-EPFL, CH-1015, Lausanne, Switzerland
Phone: [phone], Fax: [phone]