I haven't looked at your code, but I came across the idea of a vector map in C++ (based on a std::vector of std::pairs) with some performance advantages over std::map if there aren't a lot of insertions and deletions. The idea is a good one. Whether it's best as a custom store for RedBlackTree or as a separate container I don't know.
The "unsorted binary tree" you mention doesn't sound right. Such a container would need to be kept sorted.
On 14/01/11 15:55, %u 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!
