1

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?

https://codereview.stackexchange.com/questions/56188/binary-search-tree-implementation-using-templates

1 Answer 1

1

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.

4
  • 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? May 7, 2016 at 11:49
  • @SebastianKing: If by appropriate qualities you mean "Any T with a comparison operator and copy/move constructors," then yes. May 7, 2016 at 13:43
  • @SebastianKing Yep. You don't need to do this explicitly in C++ as the compiler will error.
    – DeadMG
    May 7, 2016 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. May 7, 2016 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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