RedBlackTree with Array Store

[Steven Schveighoffer]

On Fri, 14 Jan 2011 00:25:17 -0500, %u <wfunction at hotmail.com> wrote:

> Hi,
>
> I've noticed that, just as you can have a heap with an array-backed  
> store, you
> can also have a binary search tree with the same store (although  
> structured
> differently; see attachment for a bare-bones unsorted binary tree
> implementation -- which I have NOT yet tested, but which I can test if  
> it will
> be used). The improvement will be in data locality, and while it may  
> seem to
> use a bit more space than a link-based tree, I think it's worth it to  
> let the
> RedBlackTree class use a custom store, such as any store that has
> getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.
>
> How does this idea sound?
> Thank you!

Didn't look at your code exactly, but from reading this discussion, what  
you have implemented is basically a memory pool ;)  Yes it's possible, and  
dcollections does this.  in our discussions on bringing dcollections' red  
black tree to std.container, I asked if my custom allocator that uses an  
array for storage should be ported or not, and we decided to defer custom  
allocation until later.  I fully expect that a custom allocation scheme  
will be introduced at some point in std.container.

-Steve