Splitting template class definitions and declarations fails for nested templates

I know what I want, but I don't know how to tell the compiler what I want. I have split declarations and method definitions in .h and .cpp file, but the .cpp file gets included in the header, so all I did was separate declarations and definitions.

header file (avltree.h) - it includes the source file!:

template < class KEY_T, class DATA_T >
class CAvlTree {
    public:

        //----------------------------------------

        template < class KEY_T, class DATA_T >
        class CNode;

        typedef CNode< KEY_T, DATA_T> * tNodePtr;

        template < class KEY_T, class DATA_T >
        class CNode {
            public:
                KEY_T       key;
                DATA_T      data;
                CNode< KEY_T, DATA_T > *    left;
                CNode< KEY_T, DATA_T > *    right;
                char        balance;

                CNode() : left(nullptr), right(nullptr), balance(0) {}

                CNode(KEY_T key, DATA_T data) : 
                    key (key), data (data), left(nullptr), right(nullptr), balance(0) {}
            };

        //----------------------------------------

        template < class KEY_T, class DATA_T >
        struct tAvlInfo {
            CNode< KEY_T, DATA_T> * root;
            CNode< KEY_T, DATA_T> * current;
            KEY_T       key;
            bool        isDuplicate;
            bool        branchChanged;
        };

        typedef bool (* tNodeProcessor) (CNode< KEY_T, DATA_T> * nodePtr);

    private:

        tAvlInfo< KEY_T, DATA_T >   m_info;

        //----------------------------------------

    public:

        DATA_T* Find(KEY_T& key);

    private:

        CNode< KEY_T, DATA_T> * AllocNode(void);
};

#include "avltree.cpp"

source file (avltree.cpp):

template < typename KEY_T, typename DATA_T >
DATA_T* CAvlTree< KEY_T, DATA_T >::Find (KEY_T& key)
E0276   name followed by '::' must be a class or namespace name
{
   CNode* root;

   for (CNode* node = m_info.root; node; ) {
       if (key < node->key)
           node = node->left;
       else if (key > root->key)
           node = node->right;
       else {
           m_info.current = node;
           return &node->data;
       }
   }
return nullptr;
}


template < typename KEY_T, typename DATA_T >
CNode* CAvlTree< KEY_T, DATA_T >::AllocNode (void)
E0020   identifier "CNode" is undefined
E0864   CAvlTree is not a template
{
    if (m_info.current = new CNode < KEY_T, DATA_T >) {
        m_info.branchChanged = true;
        return m_info.current;
    }
    return nullptr;
}

What the compiler says (VS 2019 community, c++2020 enabled):

E0276   name followed by '::' must be a class or namespace name
E0020   identifier "CNode" is undefined
E0864   CAvlTree is not a template

I have no bloody clue how to write this down the correct way. Please enlighten me.

I have similar code for a template class with a single typename which works, but cannot conclude from that how to do this for two typenames.

Using the tNodePtr type instead of CNode< KEY_T, DATA_T > * in my source code also doesn't work.

Btw, I know that the compiler doesn't "transfer" KEY_T and DATA_T from the CAvlTree declaration just because I am using the same names.

Your problem is the:

template < class KEY_T, class DATA_T >
class CNode;

Those KEY_T and DATA_T are unrelated to the one of CAvlTree.

clang and gcc even emit an error for those because of name shadowing (I don't know if VS does that too).

Due to CNode being a class template, the compiler expects you to provide template arguments for it (like you did for CNode< KEY_T, DATA_T> * AllocNode(void);) at all places where you use CNode.

But if you use KEY_T and DATA_T of CAvlTree for every CNode in your code, then the question is why did you define CNode as a class template in the first place.

And this part of the code indicates that you don't want CNode to be a class template:

template < class KEY_T, class DATA_T >
class CNode;

typedef CNode< KEY_T, DATA_T> * tNodePtr;

// …
CNode< KEY_T, DATA_T> * AllocNode(void);

The same seems to be true for template < class KEY_T, class DATA_T > struct tAvlInfo.

Due to that, I would assume that the code you want to have should look like this:

template <class KEY_T, class DATA_T>
class CAvlTree {
public:
  //----------------------------------------
  class CNode {
  public:
    KEY_T key;
    DATA_T data;
    CNode *left;
    CNode *right;
    char balance;

    CNode() : left(nullptr), right(nullptr), balance(0) {}

    CNode(KEY_T key, DATA_T data)
        : key(key), data(data), left(nullptr), right(nullptr), balance(0) {}
  };

  //----------------------------------------

  struct tAvlInfo {
    CNode *root;
    CNode *current;
    KEY_T key;
    bool isDuplicate;
    bool branchChanged;
  };

  typedef bool (*tNodeProcessor)(CNode *nodePtr);

private:
  tAvlInfo m_info;

  //----------------------------------------

public:
  DATA_T *Find(KEY_T &key);

private:
  CNode *AllocNode(void);
};

template <typename KEY_T, typename DATA_T>
DATA_T *CAvlTree<KEY_T, DATA_T>::Find(KEY_T &key) {
  CNode *root;

  for (CNode *node = m_info.root; node;) {
    if (key < node->key)
      node = node->left;
    else if (key > root->key)
      node = node->right;
    else {
      m_info.current = node;
      return &node->data;
    }
  }
  return nullptr;
}

template <typename KEY_T, typename DATA_T>
auto CAvlTree<KEY_T, DATA_T>::AllocNode(void) -> CNode * {
  if (m_info.current = new CNode) {
    m_info.branchChanged = true;
    return m_info.current;
  }
  return nullptr;
}

And using the auto identifier ( argument-declarations... ) -> return_type syntax allows you to use the CName name directly. Otherwise, you would need to write template <typename KEY_T, typename DATA_T> typename CAvlTree<KEY_T, DATA_T>::CNode* CAvlTree<KEY_T, DATA_T>::AllocNode(void)