Using template for nested class in C++

Question

In the following piece of code, I have a doubt and an error which I am unable to resolve:

When defining the function root() outside class BST, why do I have to use typename bst::Node*? Had BST not been templated, I would have been able to use just BST::Node right?
While overloading operator<< for BST outside the class throws the following error:

Undefined symbols for architecture x86_64: "operator<<(std::__1::basic_ostream >&, BST::Node*)", referenced from: BST::inorderTreeWalk(BST::Node*) in bst_raw.cpp.o ld: symbol(s) not found for architecture x86_64

Can someone please help clarify my doubts?

#define T template <typename K, typename V>
#define bst BST<K,V>

T
class BST {
public:
    class Node;
private:
    Node* _root;
public:
    BST():_root(NULL) {};
    bool empty() ;
    Node* root();
    void set_root(Node* z);
    void insert(K key, V value);
    void inorderTreeWalk(Node* x);
};
T
class bst::Node {
public:
    Node(K k, V v) : _key(k), _val(v) {};
    K key() const { return _key; }
    V val() const { return _val; }
    Node* left() { return l;}
    void set_left(Node* n) { l = n;}
    Node* right() { return r;}
    void set_right(Node* n) { r = n; }
    Node* parent();
    void set_parent(Node* n) { p = n; }

    friend ostream &operator<< (ostream &os, Node* x);
private:
    Node *l, *r, *p;
    K _key;
    V _val;
};

T
typename bst::Node* bst::root() { return _root; }  // why typename?

T
ostream &operator<<(ostream &os, typename bst::Node& x) {
    os << x.key();
    return os;
} // runs into an error

1. _Had BST not been templated, I would have been able to use just BST::Node right?_ right 2. Friending is done in a bit another way, see https://stackoverflow.com/a/4014424/3365922 — fas, Apr 08 '20 at 06:58
1. See [this](https://stackoverflow.com/questions/610245/where-and-why-do-i-have-to-put-the-template-and-typename-keywords) for an explanation. — cigien, Apr 08 '20 at 13:14

john · Answer 1 · 2020-04-08T07:05:42.630

Yes, it's called dependent name look up.

If C is a template, then in the construct C<T>::N N could be a typename, or it could be a static member of the class. There's no way for the compiler to know which without knowing the type of T. This is because C could be specialised so that N had different meanings dependent on the type of T.

When the compiler first sees template <typename K, typename V> typename BST<K,V>::Node* bst<K,V>::root() it doesn't know what types K and V are so it has to be told that Node is a type in order to parse the code. That's what the third typename is doing.

Using template for nested class in C++

1 Answers1