We recently started learning about binary search trees. We created one of our own using integers as our Key/Data. It's easy to achieve the BST property using an int key, but what happens when we template our tree? How do we achieve our BST property with say a char, string or foo? - These don't seem fitting for keys. Do we simply keep an int on our node and use that as our Key instead of our T data? Or, am I completely misunderstanding this concept all together?

In the following code example, the coder implements a template binary search tree, and he is using T as his key. He proceeds to run comparisons between T when inserting, etc. But what happens when T has no overload for comparison operators? This code falls apart correct?



Yes, it fails to compile, which is a totally fine and correct outcome. His BST is a valid implementation for any valid key type, and fails to compile for incorrect key types. There's no reason to desire any other behaviour. It's the best possible outcome.

These don't seem fitting for keys.

You're wrong. Any T with a comparison operator and a couple other bits like copy/move constructors is a fitting key.

  • Okay thanks for your answer. So if we want to pass in our own T into our tree, we must assure our T has the appropriate qualities so it can be handled by the tree? – Sebastian King May 7 '16 at 11:49
  • @SebastianKing: If by appropriate qualities you mean "Any T with a comparison operator and copy/move constructors," then yes. – Robert Harvey May 7 '16 at 13:43
  • @SebastianKing Yep. You don't need to do this explicitly in C++ as the compiler will error. – DeadMG May 7 '16 at 14:23
  • yep that's what I meant. Alright thanks for the responses guys. Much appreciated. I'd upvote but I don't have the privileges. – Sebastian King May 7 '16 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.