On Fri, 14 Jan 2011 00:25:17 -0500, %u <[email protected]> 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
