My Introduction To Templates In Cpp

A few days ago, on an impulse, I asked Gemini to provide me with a snippet of the source code underlying the std::cout function (which I now know is not a function at all). The implicit goal was to get a feel of the low-leveledness involved in writing foundation tools in C++. The explicit goal was procrastination :) Anyways, I got nothing out of the answer, which was fine with me. I did stumble across the notorious template as being one of the core concepts used.

Ever since I started learning C++, templates have been present in the back of my mind as the end game of proficiency in the language (not true of course). I remember seeing templates being used in random code I encountered and being intimidated by the capital T. Now I know that this fear was sustained entirely by ignorance, like most things in life.

This time, I decided to understand how it actually worked. What the need was. And it turned out to be so damn simple that I had to smile in shame when I realized. Templates are nothing but a tool to create functions and classes where you don't know what kind of specific data you are going to work with. Or you do know, but there are too many and you need to work with them all the same way.

The popular way to put it is that classes are to objects what templates are to classes. In other words, templates are blueprints for creating classes. More accurately, they can be used to create blueprints for functions too (as will be shown later), but we can base our understanding starting from this thought.

Let's consider the following helper function I wrote for testing an LC solution (No. 21):

struct ListNodeInt {
    int val;
    ListNodeInt* next;
    ListNodeInt(int val) : val(val), next(nullptr) {}
};

ListNodeInt* vector_to_LL(std::vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNodeInt* START = nullptr, *q = nullptr;
    START = new ListNodeInt(nums[0]);
    q = START;
    for (int i = 1; i < nums.size(); i++) {
        q->next = new ListNodeInt(nums[i]);
        q = q->next;
    }
    return START;
}

If you are familiar with linked lists, this should feel like a walk in the park. I take a vector of integers, construct a singly non-circular linked list out of it, and return the head.

Now, a true programmer is probably already familiar with the DRY principle. So, I am not going to repeat what it means :) The problem with the given function is that it is hardcoded to work only with vectors containing integer values, as indicated by the single phrase std::vector<int>& nums. Naturally, this would mean that the compiler would throw a type mismatch error if I try to pass a vector of characters in this function. Not only that, but the ListNode definition itself strictly holds integer values in val.

Does this mean that I will have to write an entirely new function that specially accepts character vectors? While this approach is viable and even conceptualized as "function overloading", it is not scalable and affects code readability. Of course, because DRY, I don't want to copy paste 5 versions of the same function so that every supported data type is covered.

I mean, look at this piece of crap:

ListNodeInt* vector_to_LL(std::vector<int>& nums) {
    // 10 lines of code...
}

ListNodeFloat* vector_to_LL(std::vector<float>& nums) {
    // 10 lines of code...
}

ListNodeChar* vector_to_LL(std::vector<char>& chars) {
    // 10 lines of code...
}

ListNodeDouble* vector_to_LL(std::vector<double>& nums) {
    // 10 lines of code...
}

That is about 40 lines of code just because a single word is different in each function.

Well no shit, templates are the answer. They allow you to write a single function that works for any data type. Let's have a look:

Firstly, our new ListNode structure definition:

template <typename T>
struct ListNode {
    T val;
    ListNode* next;
    ListNode(T val) : val(val), next(nullptr) {}
};

Here, template <typename T> is the line that declares that the following class/function is a template, which means there are data type(s) within that are not known yet. Capital T is just the naming convention for that unknown datatype. You are telling the compiler that you are going to refer to this unknown datatype as T. In other words, this line tells that the following function is a template that wants to adapt to the datatype T. If you knew that the function was definitely supposed to accept some kind of container of values like vectors, lists, sets, etc., then it would be a better to use collection as placeholder instead of T (more on that later).

After that, it is just like how you normally define structs. All you do is that you use T wherever you don't know the datatype. In this case, val could hold an integer, a float, a character or anything else, but I don't know that for now, so I will just use the placeholder T. Nothing else unusual here.

Structs are just classes with public access members, so that is how we can write adaptive classes in C++ using templates. Note that such classes are actually called class templates, since they are only blueprints, remember?

Moving on to our function:

template <typename T>
auto vector_to_LL(vector<T>& collection) {

    if (collection.empty()) return (ListNode<T>*)nullptr;

    ListNode<T>* head = new ListNode<T>(collection[0]);
    ListNode<T>* current = head;

    for (int i = 1; i < collection.size(); i++) {
        current->next = new ListNode<T>(collection[i]);
        current = current->next;
    }

    return head;
}

Let's go through this a line at a time to bring it home.

Firstly, this is an example of a function template, and just like with the structure, we start with template <typename T> to indicate that the following function will adapt to the unknown datatype T. Then, we use T in the parameter like so - vector<T>& collection, indicating that we know a vector must be passed, but the datatype is unknown.

In the line ListNode<T>* head = new ListNode<T>(collection[0]); notice that we are clearly using the constructor defined in the structure definition. Wherever we would normally use a specific datatype like int, float or double, we use T instead.

If you look at this new function from a broader perspective, you may notice another problem. I hinted at it a couple hundred words ago: We managed to make the function adapt to the kind of data that the vectors store, but this function only works for vectors. What about any other container that is part of the standard library? Arrays? Lists? Deques?

A vector is technically also a datatype, so templates can definitely be applied to generalize this function further.

This is how it can be done:

// The ListNode structure remains the same as the last version

template <typename Container>
auto container_to_LL(Container& collection) {

    using DataType = typename Container::value_type;

    if (collection.empty()) return (ListNode<DataType>*)nullptr;

    auto it = collection.begin();

    ListNode<DataType>* head = new ListNode<DataType>(*it);
    ListNode<DataType>* current = head;

    for (++it; it != collection.end(); it++) {
        current->next = new ListNode<DataType>(*it);
        current = current->next;
    }

    return head;
}

Here, there are only three major changes that you need to pay attention to:

1. template <typename Container>

   • When we are trying to adapt a function to an unknown container, the template declaration should indicate that. Which is why we use Container as opposed to T, which is normally used for primitive data types. Note that this is just a naming convention used for code readability. The name we use has no effect on execution.

2. using DataType = typename Container::value_type;

   • Using (ha!) this line, we determine which type of data the container stores.
   • The using keyword is just a way for setting an alternative name for a datatype (just like typedef if you are familiar), which becomes necessary here because we don't know the specific datatype. We still need a way to reference it.
   • typename serves different purpose here compared to how it's used in the template declaration. First, let's show some empathy to the compiler. Not only will it have to deal with an unknown container, but it also doesn't know which datatype is stored within! That is a lot of ambiguity which we must help clear. If we had just used using DataType = Container::value_type; (notice that typename is missing), the compiler would have interpreted Container::value_type as a value, when it is actually a type! Thus, using typename is necessary to assure the compiler that Container::value_type returns a type.
   • Now, since the container is definitely a class object in C++, it stores attributes about itself, like the type of data it holds. That is what we access using the phrase Container::value_type.
   • To summarize, we want to use the name DataType (or any other name of your choice, even our beloved T) to reference the type of data stored inside the container.

3. Iteration

   • Finally, notice the way the container is traversed. We don't use the index-based approach being used to specifically target vectors. This is because containers like list don't support index-based traversal. This means that we must use an approach that works for every container, so that our generalized function actually works generally.
   • For this, we use iterators .begin() and .end(). These iterators are built into each sequence-based STL container, which allows us to traverse them all using a single approach.
   • The premise is simple, container.begin() always points to the first element of the container. Notice the word 'points'. This iterator returns a pointer that must be dereferenced to access the actual value, as illustrated in the line new ListNode<DataType>(*it). We call the structure constructor by naturally passing the dereferenced pointer as the value.
   • Similarly, container.end() points to the one past the last element of the container, which is why we loop while the current iterator is not equal to it.

Hopefully, this blog just handed you the blueprint to writing more readable and frankly, impressive-looking C++ code. Templates have truly changed the way I approach writing OOP code in C++.

In order to practice what I had learnt, I wrote some more generalized helper functions using templates. Here they are. Feel free to look through them.

// Traverse any container. 
template <typename Container>
void traverse_container(Container& collection) {
    using DataType = typename Container::value_type;

    if (collection.empty()) return;

    for (auto it = collection.begin(); it != collection.end(); it++) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

• Try to see why this wouldn't work if the data stored inside the container is a structure or a class object.
• Notice how damn general this function is. Any sequential STL container holding any primitive datatype can be passed.
• We are using the exact principles discussed in the previous function. Only instead of building a linked list, we are doing something even simpler: sequential traversal.

// Traverse a linked list with any data type stored inside nodes. 
template <typename T>
void traverse_LL(ListNode<T>* head) {
    ListNode<T>* current = head;

    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }

    std::cout << std::endl;
}

• Nothing special here as well. The only thing we are adapting to is the datatype stored inside each ListNode.

// Delete the linked list and freeing memory
template <typename T>
void delete_LL(ListNode<T>*& START) {

    if (START == nullptr) return;

    while (START != nullptr) {
        ListNode<T>* q = START;
        START = START->next;
        delete q;
    }
}

• Again, we are doing nothing unusual here. It looks just like a normal LL deletion function except for big T.