Undefined reference to ... when linking a static library in C++

Question

I'm implementing an AVL-tree as part of a library and can't figure out whether it is CppUnit, NetBeans 8, my C++ skills (templates) or something else that is the problem, but the code compiles as a static library but when used together with CppUnit or a standalone application I get undefined reference to MyProject::Utilities::AVLTree<int, char>::function.

I've reduced the code as much as possible while still maintaining the same error.

AVLTree.h

namespace MyProject {
    namespace Utilities {
        template <typename KeyType, typename ValueType> class AVLTree {
        public:
            AVLTree();
            AVLTree(const MyProject::Utilities::AVLTree<KeyType, ValueType>& orig);
            virtual ~AVLTree();
            bool hasRoot() const;
            MyProject::Utilities::AVLNode<KeyType, ValueType>* getRoot() const;

        protected:
            void setRoot(MyProject::Utilities::AVLNode<KeyType, ValueType>* _node);

        private:
            MyProject::Utilities::AVLNode<KeyType, ValueType>* _root;
            unsigned int _size;

        };
    };
};

AVLTree.cpp

template <typename KeyType, typename ValueType> MyProject::Utilities::AVLTree<KeyType, ValueType>::AVLTree() {
    this->setRoot(NULL);
    this->_size = 0;
}

template <typename KeyType, typename ValueType> MyProject::Utilities::AVLTree<KeyType, ValueType>::AVLTree(const MyProject::Utilities::AVLTree<KeyType, ValueType>& orig) {
    this->setRoot(orig.getRoot());
    this->_size = orig.size();
}

template <typename KeyType, typename ValueType> MyProject::Utilities::AVLTree<KeyType, ValueType>::~AVLTree() {
    // this->clear();
}

template <typename KeyType, typename ValueType> void MyProject::Utilities::AVLTree<KeyType, ValueType>::setRoot(MyProject::Utilities::AVLNode<KeyType, ValueType>* _root) {
    this->_root = _root;
}

template <typename KeyType, typename ValueType> bool MyProject::Utilities::AVLTree<KeyType, ValueType>::hasRoot() const {
    return this->getRoot() != NULL;
}

template <typename KeyType, typename ValueType> MyProject::Utilities::AVLNode<KeyType, ValueType>* MyProject::Utilities::AVLTree<KeyType, ValueType>::getRoot() const {
    return this->_root;
}

main.cpp

#include <cstdlib>
#include "AVLTree.h"

int main(int argc, char** argv) {
    MyProject::Utilities::AVLTree<int, char> instance;
    for (unsigned int i = 0; i < 20; ++i) {
        instance.hasRoot();
        // instance.insert(i, (char) (65 + i));
    }

    //instance.graphviz("./test.dot");
    return 0;
}

The following error is returned by Netbeans 8 when attempting to build cppapplication_1

g++    -c -g -I../../Documents/MyProject/src/header -MMD -MP -MF "build/Debug/GNU-Linux-x86/main.o.d" -o build/Debug/GNU-Linux-x86/main.o main.cpp
mkdir -p dist/Debug/GNU-Linux-x86
g++     -o dist/Debug/GNU-Linux-x86/cppapplication_1 build/Debug/GNU-Linux-x86/main.o -L../../Documents/MyProject/dist/Debug/GNU-Linux-x86 -lmyproject
build/Debug/GNU-Linux-x86/main.o: In function `main':
/home/.../CppApplication_1/main.cpp:6: undefined reference to `MyProject::Utilities::AVLTree<int, char>::AVLTree()'
/home/.../CppApplication_1/main.cpp:8: undefined reference to `MyProject::Utilities::AVLTree<int, char>::hasRoot() const'
/home/.../CppApplication_1/main.cpp:12: undefined reference to `MyProject::Utilities::AVLTree<int, char>::~AVLTree()'
/home/.../CppApplication_1/main.cpp:12: undefined reference to `MyProject::Utilities::AVLTree<int, char>::~AVLTree()'
collect2: error: ld returned 1 exit status

---

.

.

.

.

.

.

The code below produces about 100 errors of varying content... I don't mean to be daft but for the life of me I can't figure out what is wrong, nor can I find a working example or tutorial to work with...

src/header/AVLTree.h:16:23: error: declaration of ‘class KeyType’
         template <typename KeyType, typename ValueType> AVLTree();
src/header/AVLTree.h:14:19: error:  shadows template parm ‘class KeyType’
     template <typename KeyType, typename ValueType> class AVLTree {
src/header/AVLTree.h:16:41: error: declaration of ‘class ValueType’
         template <typename KeyType, typename ValueType> AVLTree();
src/header/AVLTree.h:14:37: error:  shadows template parm ‘class ValueType’
     template <typename KeyType, typename ValueType> class AVLTree {
In file included from src/AVLTree.cpp:1:0:
src/header/AVLTree.h:18:23: error: declaration of ‘class KeyType’
         template <typename KeyType, typename ValueType> virtual ~AVLTree();

AVLTree.h

namespace MyProject {

    namespace Utilities {

        template <typename KeyType, typename ValueType> class AVLTree {
        public:
            template <typename KeyType, typename ValueType> AVLTree();
            template <typename KeyType, typename ValueType> AVLTree(const MyProject::Utilities::AVLTree<KeyType, ValueType>& orig);
            template <typename KeyType, typename ValueType> virtual ~AVLTree();
            template <typename KeyType, typename ValueType> bool hasRoot() const;
            template <typename KeyType, typename ValueType> MyProject::Utilities::AVLNode<KeyType, ValueType>* getRoot() const;

        protected:
            void setRoot(MyProject::Utilities::AVLNode<KeyType, ValueType>* _node);

        private:
            MyProject::Utilities::AVLNode<KeyType, ValueType>* _root;

        };
    };
};

AVLTree.cpp (with types specified)

MyProject::Utilities::AVLTree<KeyType, ValueType>::AVLTree() {
    this->setRoot(NULL);
}

MyProject::Utilities::AVLTree<KeyType, ValueType>::AVLTree(const MyProject::Utilities::AVLTree<KeyType, ValueType>& orig) {
    this->setRoot(orig.getRoot());
    // this->_size = orig.size();
}

MyProject::Utilities::AVLTree<KeyType, ValueType>::~AVLTree() {
    // this->clear();
}

void MyProject::Utilities::AVLTree<KeyType, ValueType>::setRoot(MyProject::Utilities::AVLNode<KeyType, ValueType>* _root) {
    this->_root = _root;
}

bool MyProject::Utilities::AVLTree<KeyType, ValueType>::hasRoot() const {
    return this->getRoot() != NULL;
}

MyProject::Utilities::AVLNode<KeyType, ValueType>* MyProject::Utilities::AVLTree<KeyType, ValueType>::getRoot() const {
    return this->_root;
}

AVLTree.cpp (with types unspecified)

MyProject::Utilities::AVLTree::AVLTree() {
    this->setRoot(NULL);
}

MyProject::Utilities::AVLTree::AVLTree(const MyProject::Utilities::AVLTree& orig) {
    this->setRoot(orig.getRoot());
    // this->_size = orig.size();
}

MyProject::Utilities::AVLTree::~AVLTree() {
    // this->clear();
}

void MyProject::Utilities::AVLTree::setRoot(MyProject::Utilities::AVLNode<KeyType, ValueType>* _root) {
    this->_root = _root;
}

bool MyProject::Utilities::AVLTree::hasRoot() const {
    return this->getRoot() != NULL;
}

MyProject::Utilities::AVLNode<KeyType, ValueType>* MyProject::Utilities::AVLTree::getRoot() const {
    return this->_root;
}

Answer 1

Templates are not functions. They don't exist in code. They are just sort of blueprints, or instructions on how to actually make a function once all template parameters are known. Because of this all templates must reside in header files, to be visible once all template parameters are known. Move all template code from AVLTree.cpp to AVLTree.h. Not enough to just move, must also change it.

Here is an example that compiles on my Visual Studio:

namespace My {
    namespace Util {
        template <typename KeyType, typename ValueType> class World {
        public:
            World()
            {
            }

            World(const My::Util::World<KeyType, ValueType>& orig)
            {
            }

            virtual ~World()
            {
            }

            bool Hello() const
            {
                return true;
            }
        };
    };
};

Use the code like this:

My::Util::World<int, char> world;
world.Hello();

It is possible to separate all functions from class declaration, but it serves no practical purpose, because all that separated code must be visible anyway. It would look something like this:

namespace My {
    namespace Util {
        template <typename KeyType, typename ValueType> class World {
            ....
            bool Hello() const;
        };
    };
};

template<typename KeyType, typename ValueType>
bool My::Util::World<KeyType, ValueType>::Hello() const
{
    return true;
}

I tried your example, and it works for me. I just placed all function templates just after class template, and commented out all code that deals with AVLNode, and it compiled. So my original statement appears to be valid: just move all template code from source to header. Your second example code is different from your first. All you should have done is move.