Re: [Algorithms] memory pool algorithms

[Tom P. <ga...@fa...>]

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

You only need to swap the last element into the deleted element, unless
the order of the elements need to match the order of allocation.  Hence
O(1) for all operations, and it can be highly memory-efficient as well.

-tom!