Let's write tagged union in C++

Andrew Andersen — Mon, 29 Jul 2019 18:55:08 +0000

Disclaimer: resulting code will be far more simple than std or boost "variant". This article is more about understanding variadic templates, not about writing full-featured-ready-for-production class. Also, I am not professional programmer (yet), so the following information and code is closer to internet research, than lecture. Comments are very welcome.
For understanding this article you need to know usual (not variadic) C++ templates.

Motivation

I always wanted to "acquire" variadic templates, but thing, that pushed me towards writing this code, is my project. It's a microcontroller, which you can connect to by wi-fi and read information from its sensors. Thing is, different sensors return values of different types. For example, there can be temperature sensor, which gives you short unsigned int, and accelerometer, which gives you long int [3] (three both negative and positive values). As I want universal interface for reading and sending those values, I need a way to store values of different types in single vector/map, etc., and the most common way to do this is tagged union.

Tagged union

Tagged union is a data structure, that can do at least three things:

Store instance of one of specified types;
Check if stored value is instance of some type;
Get the stored value.

Let's imagine how could look code, that uses tagged union:

// Create it
Variant<short unsigned int, long int [3]> v;
// Store value
v = (long int [3]) {100, -10, 925};
// Check type of stored value:
v.is<long int [3]>() // => true
// Get the value
v.as<long int [3]>() // => {100, -10, 925}

What are variadic templates?

Variadic templates let you use any number of template arguments. Their syntax looks similar to * list operator in Python for me:

template<typename... Ts> // Like `def func(*args)`
struct MyClass {
    int field = some_function<Ts...>(); // Like `field = some_f(*args)`
}

Huge difference between python's "star folding" and variadic variable (in example above its Ts) is that python's arguments list is actually list, so you can iterate through it or take element by index (lst[i]). There is no syntax in C++ to do same thing. Let's pretend we have syntax similar to Python's list. How would we write our Variant?

#include <cstddef>
#include <iostream>
#include <exception>


template<typename... Ts>
class Variant {
    // index of currently stored type
    size_t curr_type; 
    // we'll store our data here
    char* data; 
public:
    // "Empty" constructor
    Variant():
        curr_type(0),
        data(nullptr) {}

    // Invoked on `v = ...;`
    template<typename T>
    const T& operator=(const T& x) {
        // The following line will be changed later
        this->curr_type = <py> Ts.find(T) </py>;
        if (data)
            delete[] data;
        // Treat `x` as bytes and copy them
        this->data = new char[sizeof(T)];
        auto ptr = reinterpret_cast<const char*>(&x);
        std::copy(ptr, ptr + sizeof(T), this->data);
        return x;
    }

    // Check type of stored value
    template<typename T>
    bool is() {
        return data != nullptr &&
            <py> Ts.find(T) </py> == this->curr_type;
    }

    // Get value (and catch error if given type is wrong)
    template<typename T>
    T& as() {
        if (!this->is<T>())
            throw std::runtime_error("Wrong type");
        return *reinterpret_cast<T*>(this->data);
    }
};

Okay, so now we need a way to find index of T in Ts. To find it, we need to dive deeper in templating.

Templating: feel the power

C++ allows you to write templates with different template parameters, less and more generic (this is true for class/structure templates, not functional). At compile time compiler takes the most specific template, that matches given parametes. If for some reason it's impossible to compile this template, it moves to more generic one. Sounds complicated, so let's see the code:

// Firstly declare the most generic template
// `A`, first parameter, is type to find. Rest of them are types to search through.
// `value` is result of our search
template<typename A, typename T, typename... Ts>
struct index_type {
    static const size_t value = index_type<A, Ts...>::value + 1;
};

// Then template, matching the situation, when type to be found has index of 0
template<typename A, typename... Ts>
struct index_type<A, A, Ts...> { // attention to `<A, A, Ts...>`
    static const size_t value = 0;
};

Next, in class implementation, we need to replace <py> Ts.find(T) </py> with

index_type<T, Ts...>::value

How does this work? I didn't have serious experience in functional programming, but for me this piece of code has a lot in common with declarative programming.

Second template declaration says "If type to find is the same as head of the type list, set value to 0".
First template (which is executed only if second fails), says "Otherwise, recursively continue searching through tail of list".

Final code is on gist. In opposite to code from above, it uses char[] to store values, and some more variadic templates, but code from above works as well.

OOP vs FP

Andrew Andersen — Thu, 18 Jul 2019 16:55:43 +0000

Today I opened Medium and found this article in "Your Daily Read". I read it and, well, I got angry that Medium recommended it to me. I found it completely unreasoned. I thought this post is one of "if you want hype, just write any article about popular theme". That's why I wrote this comment. Later author banned me :)