Re: avltree / genalloc

From: Olivier Brunel <>
Date: Fri, 13 Apr 2018 12:35:53 +0200

> Then genalloc is indeed the right data structure from you, but
> I don't have helpers to arbitrarily remove an object in the middle.
> Note that if you don't need index stability, it's trivial, and O(1):
> you can just overwrite the ith object with the (n-1)th, and decrement
> the length. No need to copy len-i-1 objects, just copy one.

Ah, yes. But when I said I don't need index stability, I meant current
4 can become 2, but I actually want to preserve the order of elements
within the array... hence moving the whole data block.
(I guess for a generic genalloc_delete_size an extra flag indicating
whether to move all elements or just move the last one might be good.)

Received on Fri Apr 13 2018 - 10:35:53 UTC

This archive was generated by hypermail 2.3.0 : Sun May 09 2021 - 19:38:49 UTC