Re: [Algorithms] memory pool algorithms

[Olivier G. <gal...@po...>]

On Thu, Apr 23, 2009 at 01:05:39PM +0100, Pau...@sc... wrote:
> I was just wondering if anyone knew of an algorithm/method which 
> facilitated simple memory pool allocation of a single type but with 
> constant time allocation/deallocation/item retrieval by index and also 
> provided a 'nice' way to iterate through the used elements?
> 
> We have a class which gives us everything but the last two together. We 
> can add a linked list of used elements (giving us the iteration) but then 
> you can't retrieve by index in constant time. Or we can retrieve by index 
> in constant time but then you can't iterate cleanly because there will be 
> holes in the memory pool.

Could you define "retrieve by index" further?  Do you mean that if "n"
elements are allocated they must be reachable by a number with 0 and
n-1?  If yes, you obviously can't have constant-time deletion, since
you'll have a mean of n/2 references to change for every deletion.
And if you allow holes to get constant-time deletion, what properties
do you want from your index that a pointer would not have?

  OG.