2022-05-08

C++ Template

How Templates Works

It is important to remember templates are compiled during compile-time. The compiler generates all the required versions and includes them in the compiled executable.

For example, a template LinkedListNode is provided.

template <class T>
class LinkedListNode{
private:
    LinkedListNode<T> *m_prev;
    LinkedListNode<T> *m_next;
    T m_value;
}

When it is used in another source code as LinkedListNode<int>, the following code will be generated by the compiler:

class LinkedListNode{
private:
    LinkedListNode<int> *m_prev;
    LinkedListNode<int> *m_next;
    int m_value;
}

Compile and Link Process

Taking the fact that template parsing happens in the compile-time, the way we normally compile classes may lead to some problems.

Normally, classes can be compiled separately and linked afterwords.

Static Linking Example

Here, I choose static linking as an example. For dynamic linking, although the relocatable object files are not linked before execution, the same problem still exists.

Taking a sample class as example:

// "IntNode.hpp"
class IntNode{
private:
    IntNode *m_prev;
    IntNode *m_next;
    int m_value;
public:
    IntNode(int value);
    int GetValue();
    void SetValue(int val);
    IntNode *GetNext();
    void SetNext(IntNode *next);
    IntNode *GetPrev();
    void SetPrev(IntNode *prev);
}

// "IntNode.cpp"
IntNode::IntNode(int value){
    // ...
}

int IntNode::GetValue(){
    // ...
}

// ...

// "main.cpp"
int main(int, char **){
    IntNode *head = new IntNode(0);
    head->SetNext(new IntNode(1));
    head->GetNext()->SetValue(2);
}

Compiling the Relocatable Object File

When compiling the IntNode.hpp and IntNode.cpp, a relocatable file will be generated containing all the .rel.text and .rel.data segment. Also, the symbol table will be included in the relocatable object file ¹.

Static Linking

When performing the static linking, two major stages are performed²:

Symbol resolution: The linker will try to find all the definitions and references. The linker requires all the references have exactly one definition. Notice that the linker requires the definition instead of declaration, and the number of dedications cannot be 0 or greater than 1.
Relocation: After finding all the definitions, the linker can relocate the function reference by relocating the reference jump address to the function defined in other source code. During this process, the linker may also allocate memory for those function definitions.

In the example, the IntNode constructor, destructor, SetNext method, and SetValue method in the main.cpp source code need to be reallocated. But in the symbol resolution stage, the linker will try to find the definition (implementation) of these functions at first. And it can successfully find them in the IntNode.cpp source code.

How Templates Lead to Problems

When using template like this:

// "LinkedListNode.hpp"
template <class T>
class LinkedListNode{
private:
    LinkedListNode<T> *m_prev;
    LinkedListNode<T> *m_next;
    T m_value;
public:
    LinkedListNode(T value);
    T GetValue();
    void SetValue(T val);
    LinkedListNode<T> *GetNext();
    void SetNext(LinkedListNode<T> *next);
    LinkedListNode<T> *GetPrev();
    void SetPrev(LinkedListNode<T> *prev);
}

// "LinkedListNode.cpp"
template<class T>
LinkedListNode<T>::LinkedListNode(T value){
    // ...
}

// ...

The compiler will finish compiling all the functions into machine code and the corresponding symbol table during compile stage. No original source code will be kept.

However, in the main.cpp:

// "main.cpp"
int main(int, char **){
    LinkedListNode<int> *head = new LinkedListNode<int>(0);
    head->SetNext(new LinkedListNode<int>(1));
    head->GetNext()->SetValue(2);
}

the main function is using specifically LinkedListNode<int> constructor and destructor.

So during the linking stage, the linker will try to find this definition while no such constructor exists in the relocatable object file. So an unreferenced definition error will be raised by the linker.

Solution

1. Explicitly Define Template Implementation

One solution to the problem mentioned above is listing all the possible implementations of the template at the end of LinkedListNode.cpp file ³.

// "LinkedListNode.cpp"
template<class T>
LinkedListNode<T>::LinkedListNode(T value){
    // ...
}

// ...

template class LinkedListNode<int>;
template class LinkedListNode<char>;

By doing this, the template class and executable can still be compiled separately. If you are using the shared library compiling option (dynamic linking during the load stage), you can make the executable as small as possible.

But doing this is also complicated and wastes the flexibility of the template.

2. Implement in Header File

The second option is implementing everything inside the header file. Thus, the code will be included in the required module instead of compiled into a relocatable object file and linked afterwords.

However, this can also be problematic. Since doing so will increase the size of the final executable. And the implementation of the code will be in the same place as the declaration.

3. Include Implementation in Header File

The final solution is used by my project currently⁴: including the implementation inside the header file.

This is similar to solution 2 from the perspective of the final result. But separating the implementation from the declaration can lead to a clear project structure.