Hi Steve, Thanks for the reply.
On Lundi, novembre 11, 2002, at 06:00 , [EMAIL PROTECTED] wrote:
One possibility is to write an object type that sits between your object andThis 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).
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 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 thatThat'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".
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.
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: +41 (21) 693 3505, Fax: +41 (21) 693 35 02
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
