Polymorphic Objects, Templates, and Data Abstraction

[edge6768]

Hi all,

I started working on a binary search tree for a school project. Initially,I had planned to make it templated as I also wanted to make AVL/Splay trees derive from this class for my own studying. However, I started running into problems maintaining the data abstraction for my school project, which is supposed to store polymorphic objects in the BST.

I can't seem to wrap my head around how to generalize my code to work for polymorphic objects and simpler data types, all the while not returning direct pointers to the polymorphic objects being stored in the tree.

template<class T>
class BST
{
public:
    // Default CTors/DTors and all that good stuff...

    T retrieve(int key) const; // Source of my confusion

private:
    // TreeNode struct, root, and whatever else...
};

Is there a simple way to do this? Am I just completely missing some obvious thing?

In any case, my projects' BST doesn't have to be templated, but it would really save me some time rewriting it all to work for int types to help me study more complex BST structures. I'm also one of those people who can't stand when I can't understand something seemingly simple (my professor suggested the n-queens problem and "How many ways are there to make change with for x dollars given y set of coins" - messed me up for weeks...), so any input would be greatly appreciated!

[edge6768]

*bump*

[MZH]

Can you be more specific with your confusion? What you have here makes sense. Just remember that any member or function for this class that refers to the specific type of data stored needs to use the template parameter T. Specifically, the TreeNode member variables will have to be listed as TreeNode<T>, and your declaration for the TreeNode class/struct will also need to be templated

template<class T>
class TreeNode
{
    public:
        T get_data() const; // for example

    private:
        T data;
}

When you go to create an instance of the BST somewhere else in your program, you have to indicate the type your are storing.

BST<int> integer_bst;
BST<std::string> string_bst;
BST<Custom_Class> custom_class_bst;

You will have a compliation error if your call functions or methods on T if the type doesn't support an operation. For a BST, perhaps you would need to write

T t1;
T t2;
if(t1 < t2)
{
   // do stuff
}

If Custom_Class doesn't have operator<() defined, the code won't compile.

[goosestuf]

The BST can't store the data then, you'd have to use something else like std::unique_ptr so that the data is stored else where. Polymorphic data can be of different size so there isn't a one size fit all, you could make it allocate for polymorphic data but you'd then need to include a "bool" in the template. You just end up over complicating it. Just look at how std::map<> would work.

http://ideone.com/40yook

You could do the same thing with just using a pointer "Base*" but then you would have to free the memory yourself, unique_ptr takes care of that. So you don't have to implement anything specially, just don't pass by value. Making a copy unique_ptr<> for example isn't possible.

const T& retrieve(int key) const; // otherwise won't work with T = std::unique_ptr<Base> 

[edge6768]

@goosestuf

Thank you! I thought I was overlooking something... I'll try the std::unique_ptr implementation and see how it goes

[MZH]

Quick note: templates and polymorphism are entirely separate strategies. If you go for the polymorphic storage of data, then you do have to use pointers. In fact, your BST will only be able to store data types derived from a single base class. If you use templates, then you can store any data type, both built-ins and custom classes. Any inheritance relationships don't matter.

Although, the only thing that matters is which strategy solves your problem.

[edge6768]

The issue I was having was finding a way to use polymorphism with a templated container WITHOUT using pointers. In short, I don't want whomever uses the container to have direct access to the stored data. I definitely think I'm overthinking the whole situation though...

[goosestuf]

I don't want whomever uses the container to have direct access to the stored data

What's the point of a container if you can't access the contents? Do you want them to have access to it but not to be able to modify it? Then that's what const T& is good for. Of course if they really wanted to they could just do const_cast, though you should probably never use it.