Subject: Re: [boost] [pool] an O(1) implementation of object_pool::destroy()
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-02-05 21:32:36
Ben Muzal wrote:
> I was looking at object_pool and noticed that there is a way to make
> object_pool::destroy() an O(1) operation instead of an O(n) operation.
> If I understand the problem correctly, object_pool::destroy() is O(n)
> because it keep the free list sorted. It keeps the free list sorted so
> that object_pool::~object_pool() runs in O(n) time instead of in
> O(n^2) time. However, I believe there is an implementation of
> object_pool::~object_pool() that will run in O(n) time without
> requiring a sorted free list.
> My suggestion is that ~object_pool() could use a mark-sweep strategy:
> It would first step through the free list and mark each free chunk as
> such. It would then go back and examine each chunk in the pool and
> call the destructor on the ones not marked as free. The each chunk's
> 'next' pointer could be used to store the marked-as-free flag so that
> no extra memory is needed.
Extra memory is needed because only the free list contains
next pointers. The chunks that are in use do not.
What would be possible is to make object_pool::destroy O(1)
and object_pool::~object_pool O(n log n) by sorting the free list
only on destruction.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk