Vishal Chovatiya

Posted on Jun 15, 2020 • Originally published at vishalchovatiya.com

Variadic Template C++: Implementing Unsophisticated Tuple

#cpp #tutorial #programming #codenewbie

From C++11, std::tuple is an incredible expansion to Modern C++, that offers a fixed-size collection of heterogeneous values. Unfortunately, tuples can be somewhat dubious to manage in a conventional fashion. But, subsequently released C++ standard introduced a few features & helpers that greatly reduce the necessary boilerplate. So, in this article, I will explain the variadic template in C++ with the help of unsophisticated tuple implementation. And also walks you through a tricky part of tuple i.e. loop through tuple element. In spite of the fact that I have shrouded the variadic template in my prior article i.e. C++ Template: A Quick UpToDate Look. So, my focus here would be a blend of variadic template & tuple implementation with more up to date C++ gauges.

/!\: Originally published @ www.vishalchovatiya.com.

Motivation

It is often useful to define class/struct/union/function that accepts a variable number and type of arguments.
If you have already used C you'll know that printf function can accept any number of arguments. Such functions are entirely implemented through macros or ellipses operator. And because of that it has several disadvantages like type-safety, cannot accept references as arguments, etc.

Variadic Class Template: Implementing Tuple Class

So, let's build our own ADT same as std::tuple with the help of variadic template.
The variadic template in C++ usually starts with the general (empty) definition, that also serves as the base-case for template recursion termination in the later specialisation:

template <typename... T>
struct Tuple { };

This already allows us to define an empty structure i.e. Tuple<> object;, albeit that isn't very useful yet. Next comes the recursive case specialisation:

template<
            typename T, 
            typename... Rest    // Template parameter pack
        >
struct Tuple<T, Rest...> {      // Class parameter pack
    T first;
    Tuple<Rest...> rest;        // Parameter pack expansion

    Tuple(const T& f, const Rest& ... r)
        : first(f)
        , rest(r...) {
    }
};

Tuple<bool>                 t1(false);           // Case 1
Tuple<int, char, string>    t2(1, 'a', "ABC");   // Case 2

How Does Variadic Class Template Works?

To understand variadic class template, consider use case 2 above i.e. Tuple<int, char, string> t2(1, 'a', "ABC");

The declaration first matches against the specialization, yielding a structure with int first; and Tuple<char, string> rest; data members.
The rest definition again matches with specialization, yielding a structure with char first; and Tuple<string> rest; data members.
The rest definition again matches this specialization, creating its own string first; and Tuple<> rest; members.
Finally, this last rest matches against the base-case definition, producing an empty structure.

You can visualize this as follows:

Tuple<int, char, string>
-> int first
-> Tuple<char, string> rest
    -> char first
    -> Tuple<string> rest
        -> string first
        -> Tuple<> rest
            -> (empty)

Variadic Function Template: Implementing get<>() Function for Tuple Class

So far we have designed data structure with variable number and type of data members. But still, it isn't useful as there is no mechanism to retrieve data from our Tuple class. So let's design one:

template<
            size_t idx, 
            template <typename...> class Tuple, 
            typename... Args
        >
auto get(Tuple<Args...> &t) {
    return GetHelper<idx, Tuple<Args...>>::get(t);
}

As you can see this get function is templatized on the idx. So usage can be like get<1>(t), similar to std::tuple. Though, the actual work is done by a static function in a helper class i.e. GetHelper.
Note also the use of a C++14-style auto return type that makes our lives significantly simpler as otherwise, we would need quite a complicated expression for the return type.
So on to the helper class. This time we will need an empty forward declaration and two specializations. First the empty declaration:

template<
            size_t idx, 
            typename T
        >
struct GetHelper;

Now the base-case (when idx==0). In this specialisation, we just return the first member:

template<
            typename T, 
            typename... Rest
        >
struct GetHelper<0, Tuple<T, Rest...>> {
    static T get(Tuple<T, Rest...> &data) {
        return data.first;
    }
};

In the recursive case, we decrement idx and invoke the GetHelper for the rest member:

template<
            size_t idx, 
            typename T, 
            typename... Rest
        >
struct GetHelper<idx, Tuple<T, Rest...>> {
    static auto get(Tuple<T, Rest...> &data) {
        return GetHelper<idx - 1, Tuple<Rest...>>::get(data.rest);
    }
};

To work through an example, suppose we have Tuple data and we need get<1>(data).
This invokes GetHelper<1, Tuple<T, Rest...>>>::get(data) (the 2nd specialization).
Which in turn invokes GetHelper<0, Tuple<T, Rest...>>>::get(data.rest).
And finally returns (by the 1st specialization as now idx is 0) data.rest.first.

So that's it! Here is the whole functioning code, with some example use in the main function:

// Forward Declaration & Base Case -----------------------------------------
template<
            size_t idx,
            typename T
        >
struct GetHelper { };

template <typename... T>
struct Tuple { };
// -------------------------------------------------------------------------

// GetHelper ---------------------------------------------------------------
template<
            typename T,
            typename... Rest
        >
struct GetHelper<0, Tuple<T, Rest...>> { // Specialization for index 0
    static T get(Tuple<T, Rest...> &data) {
        return data.first;
    }
};

template<
            size_t idx,
            typename T,
            typename... Rest
        >
struct GetHelper<idx, Tuple<T, Rest...>> { // GetHelper Implementation
    static auto get(Tuple<T, Rest...> &data) {
        return GetHelper<idx - 1, Tuple<Rest...>>::get(data.rest);
    }
};
// -------------------------------------------------------------------------

// Tuple Implementation ----------------------------------------------------
template<
            typename T,
            typename... Rest
        >
struct Tuple<T, Rest...> {
    T                   first;
    Tuple<Rest...>      rest;

    Tuple(const T &f, const Rest &... r)
        : first(f)
        , rest(r...) {
    }
};
// -------------------------------------------------------------------------


// get Implementation ------------------------------------------------------
template<
            size_t idx, 
            template <typename...> class Tuple, 
            typename... Args
        >
auto get(Tuple<Args...> &t) {
    return GetHelper<idx, Tuple<Args...>>::get(t);
}
// -------------------------------------------------------------------------


int main() {
    Tuple<int, char, string> t(500, 'a', "ABC");
    cout << get<1>(t) << endl;
    return 0;
}

Variadic Template vs Fold Expression

There is two way to process C++ parameter pack i.e.
1. Recursion
2. Fold Expression(From C++17)
At whatever point conceivable, we should process a parameter pack with fold expression instead of using recursion. Because it has some benefits as:
- Less code to write
- Faster code (without optimizations), as you just have a single expression instead of multiple function calls
- Faster to compile, as you deal with fewer template instantiation

Processing a Parameter Pack With Recursion

As we have seen earlier, variadic template starts with empty definition i.e. base case for recursion.

void  print()  {}

Then the recursive case specialisation:

template<   
            typename First, 
            typename... Rest                    // Template parameter pack
        >     
void print(First first, Rest... rest) {         // Function parameter pack
    cout << first << endl;
    print(rest...);                             // Parameter pack expansion
}

This is now sufficient for us to use the print function with variable number and type of arguments. For example:

print(500, 'a', "ABC");

Processing a Parameter Pack With Fold Expression

template <typename... Args>
void print(Args... args) {
    (void(cout << args << endl), ...);
}

See, no cryptic boilerplate required. Isn't this solution looks neater?
There are total 3 types of folding: Unary fold, Binary fold & Fold over a comma. Here we have done left folding over a comma. You can read more about Fold Expression here.

Loop-Through/Iterate Over Tuple Elements in C++

If I give you a task to print the elements of tuple, the first thing that comes to your mind is:

template <typename... Args>
void print(const std::tuple<Args...> &t) {
    for (const auto &elem : t) // Error: no begin/end iterator
        cout << elem << endl;
}

But, this just can't work. std::tuple doesn't have begin & end iterator.
OK! So, now you might try raw loop right?

template <typename... Args>
void print(const std::tuple<Args...>&   t) {
    for (int i = 0; i < sizeof...(Args); ++i)
        cout << std::get<i>(t) << endl;    // Error :( , `i` needs to be compile time constant
}

No! you can't. I know that std::get<> works with a number as non-type template argument.
But, that number has to be compile-time constant to make this working. So there are many solutions & we will go through quite enough ones.

C++11: Loop Through Tuple Elements

// Template recursion
template <size_t i, typename... Args>
struct printer  {
    static void print(const tuple<Args...> &t) {
        cout << get<i>(t) << endl;
        printer<i + 1, Args...>::print(t);
    }
};

// Terminating template specialisation
template <typename... Args>
struct printer<sizeof...(Args), Args...> {
    static void print(const tuple<Args...> &) {}
};

template <typename... Args>
void print(const tuple<Args...> &t) {
    printer<0, Args...>::print(t);
}

tuple<int, char, string> t(1, 'A', "ABC");
print(t);
// Note: might not work in GCC, I've used clang

This isn't that complicated as it looks, believe me. If you know recursion & template specialisation, it won't take you more than 30 seconds to figure out what's going on here.
For our example tuple<int, char, string> t(1, 'A', "ABC");, printer::print() calls template recursion i,e, template<size_t i, typename... Args> struct printer{}; each time with incremented non-type template parameter i. And when i == sizeof...(Args), our recusion stops by calling template specialization i.e. template<typename... Args> struct printer<sizeof...(Args), Args...> { };.

C++17: Loop Through Tuple Elements

With C++ 17, it's slightly better because we have Fold Expressions. So, we don't need recursion any more.

template <typename... Args>
void print(const std::tuple<Args...> &t) {
    std::apply([](const auto &... args) {
        ((cout << args << endl), ...);
    }, t);
}

std::apply designed as tuple helper that accepts functor or lambda expression. Though you can do better if wants to dispatch to different implementation according to type, you might use overloaded class as:

template <class... Ts>
struct overloaded : Ts... {
    using Ts::operator()...;
};

// Deduction guide, google `CTAD for aggregates` for more info
template <class... Ts>
overloaded(Ts...) -> overloaded<Ts...>;   // not needed from C++20

auto f = overloaded {
    [](const int &a)        { cout << "From int: " << a << endl; },
    [](const char &b)       { cout << "From char: " << b << endl; },
    [](const string &c)     { cout << "From string: " << c << endl; },
};

tuple<int, char, string>    t(1, 'A', "ABC");
std::apply([&](const auto &... e) { (f(e), ...); }, t);

C++23: Loop Through Tuple Elements

template <typename... Args>
void print(const std::tuple<Args...> &t) {
    for... (const auto &elem : t)
        cout << elem << endl;
}

So, from C++23 we might have expansion statement i.e. for...(). That looks like a loop, though it isn't. It just stencil out each call with scope as:

template <typename... Args>
void print(const tuple<Args...> &t) {
    {
        const auto &elem = get<0>(t);
        cout << elem << endl;
    }
    {
        const auto &elem = get<1>(t);
        cout << elem << endl;
    }
    {
        const auto &elem = get<2>(t);
        cout << elem << endl;
    }
}

And it is obvious that there is no break & continue as it isn't loop.
It basically works for every standard container which can access by std::get<>(). For example, a plain array, std::tuple, std::pair, std::array, unexpanded argument packs, constexpr ranges, etc.

Closing Words

There are still many things missing in our tuple class like copy constructor, move constructors, some operators and helper classes(like std::tuple_size). But I hope now you get the idea of how it can be implemented using the variadic template. By the way, implementing those missing things will be a good start for learning variadic template on your own.

Have Any Suggestions, Query or Wants to Say Hi? Take the Pressure Off, You Are Just a Click Away.🖱️

Top comments (1)

Sergiy Yevtushenko • Jun 16 '20 • Edited

I have an impression that there is no need to loop through tuple elements nor access tuple elements via getters of any kind. Instead tuple should have method (for example, 'map') which accepts lambda with the number and order of arguments equal to number/order of elements in tuple. Method returns whatever returns passed lambda. This method makes something like 'destructuring' of tuple into set of locally named elements - lambda parameters. At first this approach looks somewhat strange, but in practice it appears to be far more convenient and much less error prone than getters.
With this approach it's convenient to think about tuples as a set of "frozen" parameters prepared for function invocation. The invocation itself is deferred (and often unknown at the moment when tuple is created). The 'map' method then is the way to perform that deferred invocation.

Disclaimer: I've used this approach in Java with my own implementation of tuples. My implementation is quite "C++ - like" (i.e. types of all tuple elements are preserved as class type parameters), so approach should be applicable to C++.

EDIT: The approach is described in more details here.

DEV Community