c++ templates and polymorphism no sutiable user-defined conversion

Question

Having trouble understanding how (and why) this conversion will not work.

I have class A, class B derived from class A, and class C derived from class B.

class A {};
class B : public A {};
class C : public B {};

I want to make a HashTable that has two template typenames <K, V>, where the K is a char and V is a binary search tree template class (BST<T>). These BSTs will have typenames A, B, and C.

template <typename K, typename V>
class HashTable {
public:
    bool put(K key, V value);   // adds key value pair to table
private:
    V* table;   // table stores values
    int size;   // size of table
};

template <typename T>
class BST {
public:
    bool insert(T item);    // adds item to tree
private:
    struct BSTNode {        // node structure
        R data;             // item data
        BSTNode *left;      // left child pointer
        BSTNode *right;     // right child pointer
    };
    BSTNode *root;          // pointer to root of tree
};

The following code has an error with putting a BST<C> in the hashtable because it cannot convert from BST<C> to BST<A>. However, the last line in main is legal.

int main() {
    HashTable<char, BST<A>> inventory;
    BST<C> foo;
    inventory.put('C', foo);

    A *bar= new C();
}

I though because of polymorphism, BST<C> is-a BST<A>? How can I get around this type difference so I can add BST, BST, and BST to my hashmap?

I've already tried using typedef in the declaration and that did not work.

Looks like you're storing `A` in your custom container, which will slice the subclass away. — Sam Varshavchik, Nov 23 '16 at 20:22
Wait... what? This is the wrong dupe. The related question has noting to do with this one. Vote to reopen. — Guillaume Racicot, Nov 23 '16 at 20:23
I edited it so you can see the things in the alligator brackets, but it seems like everyone understood my question. — , Nov 23 '16 at 20:35

score 0 · Answer 1 · answered Nov 23 '16 at 20:25

0

This is because even when B has an is-a relationship with A, BST<A> has no relationship with BST<B>. Those two template instances or not related to each other in any way, and, in fact, might be completely different from each other.

answered Nov 23 '16 at 20:25

SergeyA

61,605
5
78
137

score 0 · Accepted Answer · answered Nov 23 '16 at 20:34

The conversion can't happen. BST<C> cannot be converted to a BST<A>, as they are completely different, unrelated classes.

When the template is instanciated, it look like this (grossely):

template <>
struct BST_C {
    bool insert(C item);    // adds item to tree
    // ...
};

template <>
struct BST_A {
    bool insert(A item);    // adds item to tree
    // ...
};

As you can see, there is no relation between the two.

What can you do about this?

Well, you could define a conversion operator, limited to base classes:

template <typename T>
struct BST {
    bool insert(T item);

    // only enable for base classes ------------v
    template<typename To, std::enable_if_t<std::is_base_of<To, T>>* = nullptr>
    operator BST<To> () const {
        // implement the conversion operator...
    }
};

With that conversion operator, your class BST<C> is convertible to BST<B> and BST<A> respectively.

This solved the syntax error, and that explanation makes the type difference very clear, thank you! I will have to read more about conversion operators to learn to implement. — , Nov 23 '16 at 20:44

c++ templates and polymorphism no sutiable user-defined conversion

2 Answers2