Let's write tagged union in C++
Published: 2019-07-29 18:55:08

*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:

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

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

```cpp
// 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:

```cpp
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`?

```cpp
#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:

```cpp
// 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

```cpp
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](https://gist.github.com/Mr-Andersen/cd5f9d8740e03b3a779bd49da281652d). In opposite to code from above, it uses `char[]` to store values, and some more variadic templates, but code from above works as well.