C++ Metaprogramming: Recursive Template Classes

Case study in C++ template metaprogramming using class recursion.

Because the template mechanism in C++ is Turing Complete, we can do some interesting things like creating classes using recursion. This technique is ideal for creating a tuple class that can store an arbitrary number of non-heterogenous elements.

Variadic Template Classes

Using parameter packs we can also create template classes that accept a variable number of types. Defining such classes usually involves recursive class and function definitions. We typically will make use of the first template type then recurse on the remaining types. The prototypical case is to define a tuple type. While the standard library now contains a tuple type, it is instructive to explore how such a type can be defined.

tuple.cpp
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>

using namespace std;

// Variadic class template definition
template<typename... Types>
class Tuple;

// Base case: when there are no types (empty tuple)
template<>
class Tuple<> {
public:
    template<std::size_t N>
    auto& get() {
        static_assert(true, "Tuple index out of range");
    }

    size_t size() const {
        return 0;
    }

protected:
    string to_string(bool) const {
        return "";
    }
};

// Recursive case: stores the first type and inherits from the Tuple with the remaining types
template<typename First, typename... Rest>
class Tuple<First, Rest...> : private Tuple<Rest...> {
    using super = Tuple<Rest...>;
    First value;  // Store the first value

public:
    // Constructor to initialize the values
    Tuple(First firstValue, Rest... restValues)
        : Tuple<Rest...>(restValues...), value(firstValue) {}

    // Recursive get<N>() template method
    template<std::size_t N>
    const auto& get() const {
        if constexpr (N == 0) {
            return value;              // Return the first element when N is 0
        } else {
            return Tuple<Rest...>::template get<N - 1>();  // Recurse through the tuple
        }
    }

    size_t size() const {
        return 1 + Tuple<Rest...>::size();
    }

    // Return the tuple as a string
    string to_string() const {
        return to_string(true);
    }    

protected:
    // Recursive to_string() method
    string to_string(bool isFirst) const {
        string result;
        if (isFirst) {
            result = "(";
        }
        result += fmtValue(value) + ", ";
        result += super::to_string(false);
        if (isFirst) {
            result.erase(result.end() - 2, result.end());  // Remove the last comma and space
            result += ")";
        }
        return result;
    }

private:
    template<class T>
    static string fmtValue(T const& v) {
        std::ostringstream oss;
        if constexpr (std::is_same_v<T, std::decay_t<std::string>>) {
            oss << quoted(v);
        } else if constexpr (std::is_same_v<std::decay_t<T>, char>) {
            oss << quoted(string(1, v), '\'');
        } else {
            oss << std::to_string(v);
        }
        return oss.str();
    }
};

int main() {
    Tuple<int, double, std::string, char> myTuple(42, 3.14, "Hello", 'L');
    Tuple<int, int, int> myTuple2(100, 200, 300);

    std::cout << "First: " << myTuple.get<0>() << std::endl;
    std::cout << "Second: " << myTuple.get<1>() << std::endl;
    std::cout << "Third: " << myTuple.get<2>() << std::endl;
    std::cout << "Fourth: " << myTuple.get<3>() << std::endl;

    std::cout << "Tuple size: " << myTuple.size() << std::endl;
    std::cout << "Tuple2 size: " << myTuple2.size() << std::endl;

    std::cout << "Tuple: " << myTuple.to_string() << std::endl;
    std::cout << "Tuple2: " << myTuple2.to_string() << std::endl;
    return 0;
}
First: 42
Second: 3.14
Third: Hello
Fourth: L
Tuple: (42, 3.140000, "Hello", 'L')

We start off in line 9 by declaring that we are going to define a variadic class named Tuple. Next, because we are going to setup a recursive definition, we need to establish the base case when we no longer have any variadic types left to process. We do this starting at line 13 by defining the Tuple<> class, i.e. the Tuple with no elements. There are no data members to declare but there are base cases for the recursive template functions get<>() and to_string<>(). The get<>() should never be instantiated so we use a compile time static_assert() to flag us if it ever is. The base case for the to_string<>() method is to return an empty string.

At line 28 we start the recursive class definition for the Tuple type. We store the first value of the tuple and then recursively use Tuple<> with the rest of the parameter pack types as the base class. We do this by using a template declaration that explicitly defines the first template parameter as the template type First, then using a new parameter pack named Rest... for the remaining parameters. This way we can declare a member of type First and the base class will store the remaining values one at a time using recursion. We use the same recursion trick when defining the constructor for Tuple<> in line 34. We initialize the value member with the explicit first argument to the constructor and pass the rest of the constructor arguments to the base class constructor.

The getter is defined in line 38 as a recursive template function that takes an integer literal as its parameter. We decrement this integer each time we recurse and when it reaches 0 we return the value stored in that Tuple<> base. Because it returns a reference it could also be used to set the tuple although tuples in most languages are immutable. To make our Tuple<> class immutable we declare the get<>() method const and make its returned reference const also.

The to_string() method in line 48 is just a wrapper around a call to the recursive version to_string<0>(). The recursive to_string<>() uses the same integer literal template parameter trick that we used with get<>(). In this case when N == 0, i.e. the first call into to_string<>(), we want to add the parenthesis around the tuple value list that is generated. Otherwise we just want to return the current tuple value, a comma and then recurse to get the remaining values.