Recently I've come across a C++ template class that implemented a red-black tree. I expected its template parameter to be the type to be stored in the tree:
struct MyData {
// data to be stored
};
template <class T>
class RbTree {
// implementation
};
// usage:
RbTree<MyData> treeInstance;
Instead, I found that it expected a node type with specific requirements:
struct MyDataNode {
MyDataNode* rbe_left;
MyDataNode* rbe_ight;
char rbe_color;
// data to be stored
};
template <class Entry>
class RbTree {
// implementation
};
// usage:
RbTree<MyDataNode> treeInstance;
My question is: why would you want to implement a container this way? Does this/Can this have better performance as opposed to the 'standard' way (described above)?
