A little problem with BST implementation

Question

I`m writing STL-like container for binary-search tree. I have template class for Tree itself and nested class TreeNode.
My question is where should I put the binary-predicate function which compairing keys - Into the tree class or into the Node class? If I decide to put it in a Tree class, all of my nodes would not know how to compare their keys:(
And if in a Node class, should I make this function static or not?

Answer 1

the comparison should be made between the values stored inside the nodes, not between the nodes themselves. therefore you dont need a comparator in either of the suggested places. you can either get the comparator class as a templated paramater for your treee (and node), or just rely on the default one to work when you compare values held within nodes.

Answer 2

It is clear that you can't make it static - if you did, then two different trees with two different comparison functions wouldn't work (the later one would overwrite the global).

It is also clear that it shouldn't be per node - you would be duplicating the exact same functionality, with a memory hit per node, for no reason - all the nodes in a single tree would have the same comparer.

So the best choice is to make it part of the container. As to your objection that nodes wouldn't be able to compare themselves, why does that matter? The only time you will ever be comparing two nodes is in the context of an operation on the container, in which case you would have the comparer object handy.