Creating a list that contains different types in C++ 😎

Hi! Let's say you are trying to create a list of people and information about them (name, age, gender, address, etc.).

Notice all of these are different types! In Python, lists can handle different types, so you could store all of these.

In C++, you cannot store all of these in a vector or array because these container require the same types for each element. However, you can make a class or struct to represent a person like this:

struct Person{
std::string name;
std::string address
uint8_t age;
char gender;
};

Great you could store all this info together in your program.

However, what if later I told you we are adding email to person?

You would have to stop your program, store the program data somewhere, update the Person struct to have email and reload the program data into the struct properly. Ughhh, so much extra work!

What if I told you, I wanted to iterate through all the fields of Person and print them out. You would have to manually type something like this:

void print(Person p){
std::cout << p.name << std::endl;
std::cout << p.age << std::endl;
...
}

Ughhh, so much extra typing :(

If only, there was some solution.......

There is. Today we are going to try to make a list that can maintain different types of values.

This is inspired from std::tuple which already can hold different types of data. However, you can't add/remove elements to it or iterate through it.

std::tuple<int, char, double> = std::make_tuple(1, 'a', 4.2);

With this new container, we'll try to support all of this. And also try to make operations have fast O(1) constant access where we can with the help of the C++20 compiler!

In order to build this, we'll talk a bit about C++ variadic templates.

Basics of templates

Okay cool. Let me just show you a template. If you already know how templates work, skip past this intro.

template<typename T>
void print(T arg){
     std::cout << arg << std::endl;
}

In this example, we made a template function. Here, we say that the argument has type T. T could be any type.

T could be an int. T could be char. But everything inside the function has to work for the given types.

The compiler looks for the usages of print and creates versions of functions for types that were used.

For instance, if you had in your program:

print('a');
....
print(2.5);

The compiler will expand print by creating functions that essentially look like this behind the scenes:

void print(double arg){
    std::cout << arg << std::endl;
}

void print(char arg){
    std::cout << arg << std::endl;
}

In fact we can even templatize structs and class declarations, and those will expand out to the specialized versions of the declarations after the compiler sees all use cases.

template<typename T>
struct test{
    T val;
};

could expand to something like this if you use test<double> or test<char>:

struct test<double>{
   double val;
};

struct test<char>{
   char val;
};

This will be useful when constructing our tuple as we may want to declare different types that our tuple can store at compile time so that the compiler knows how much memory to use. (In the test struct example, test<double> is a different memory size than test<char>, 8 bytes vs 1 byte)

Now let's talk about custom template specialization. We can declare a template, but create our own specialization of that template for certain types if we want it to behave differently.

template<typename T>
void print(T arg){
     std::cout << arg << std::endl;
}

template<>
void print<int>(int arg){
     std::cout << arg << " is an int. " << std::endl;
}

The compiler won't create a new print<int> implementation. Instead, it'll use our custom specialized one.

Okay, that's enough of basic templates.

Let's talk about advanced templates with variadic templates.

Variadic templates

If you already know variadic templates, jump ahead and we'll start making our list! But for you noobs like me, stick around :).

We'll be very brief about it. There's a lot to explore in this world.

Variadic templates/packs have been around since C++11.

template<typename... Pack>
void print(Pack... args){
     (std::cout << ... << args) << std::endl;
}

Here we show that print is using a pack in its template for its arguments. Pack... args shows that the print function can use any number of arguments. So:

print('a', 2, "abc");
print(2, 1, '3', 3.5, true);
print(); // empty line

All of these are valid! The example also had this line:

     (std::cout << ... << args) << std::endl;

This is an example of a (binary right) fold expression. Basically, it is syntax to expand out to its full form:
std::cout << arg1 << arg2 ... etc << std::endl;

If you would like to learn more about fold expressions please read here.

Okay, this was a very very basic intro, but I think we can start building our list data-structure and learn the rest on the way.

Building a tuple list

Let's make a tuple list!

template<typename...>
struct TupleList;

At the very basic level, this is all the TupleList is.

Here you may notice something weird. We use typename... as opposed to typename... Args.

This is because we are only declaring it here and we don't intend to use pack in the declaration which is valid.

We'll be specializing TupleList and you will see us introduce named packs like typename... Args.

Okay, let's specialize the TupleList so we can actually understand how it works lol. The declaration wasn't very informative.

// delcaration
template<typename...>
struct TupleList;

// base case, empty tuple, empty pack
template<>
struct TupleList<>{};

// recursive inheritance case
template<typename T, typename... Rem>
struct TupleList<T, Rem...>: TupleList<Rem...>{
    T val;
};

Here is an implementation of the TupleList. There may be other ways to implement it, but for now we will talk about this method.

After declaring the TupleList, we created a specialization for the empty TupleList. This is our base case, the smallest/simplest unit of TupleList.

All other TupleList branches off the empty TupleList<>.

Let's talk about the non empty TupleList, the recursive case. All non-empty TupleList store a T val.

This represents our TupleList element that we store.

You may also notice that the recursive case is child of another TupleList, TupleList<Rem...>.

Yes templated structs can inherit from itself only if the template parameters are different (and if there is no infinite recursion/inheritence).

The inheritence must come to an end, which in our case is the base case.

Every non empty TupleList inherits from its parent which has one less template argument. So it here is an example visualization of how this may look:

TupleList<int, char, double> -> TupleList<char, double> -> TupleList<double> -> TupleList<>

The arrows show its next immediate parent. This means that TupleList<int, char, double> is also a type TupleList<> at the very base layer.

But each parent has a different T val because its first template parameter is different.

Okay cool, we have a TupleList. How do we create one in our code?

Creating a TupleList

To create a TupleList instance, we will need some constructors.

We'll have to add a constructor to our non empty TupleList so that we can pass values into our new container.

template<typename T, typename... Rem>
struct TupleList<T, Rem...>: TupleList<Rem...>{
    T val;
    TupleList<T, Rem...>(T val, Rem... rem): TupleList<Rem...>(rem), val(val){}
};

This constructor takes in a value, and a pack of remaining values.

The remaining values are passed into its parents constructor.

And its parents will pass it to its parents... and so on.

We strip away one value for each parent until it becomes an empty pack at which point the TupleList parent will be the base case.

Isn't this cool?

It's like a type linked list.

One TupleList stores one types value and links to the next via inheritance which stores the next value.

The constructor traverses this linked list of parents that stores various types.

So now if I want to construct a TupleList, it would look like this:

TupleList<int, double, char> tuple(1, 2.5, 'c');

Yayyyy! Now we can store multiple types of values contiguously in memory like a list.

Now how do I get values out?

get values from TupleList

The ideal interface for getting values from a list would be with indexes. We'd like to randomly access different indexes.

It gets weird though because we want a get function, but depending on the index, get is going to have different return types....

Oh no, .... how can we fix this????

Well good thing we have templates.

We'll be able to generate many types of get functions with minimal implementations.

First we need to figure out how to translate indexes to a specific parent of TupleList so that we can extract its value.

I find this part very interesting...

template<size_t idx, typename TupleList>
struct GetIndex;

template<template T, template... Rem>
struct GetIndex<0, TupleList<T, Rem...>>{
     using type = T;
};

template<size_t idx, template T, template... Rem>
struct GetIndex<idx, TupleList<T, Rem..>>{
     using type = typename GetIndex<idx-1, TupleList<Rem...>>::type;
};

We created a struct called GetIndex.

GetIndex is a templated empty struct. It is defined by a pair, index and a TupleList.

Let's start with the base case here. When index is 0, we have reached our element in this TupleList.

But to get to index 0, we have to keep decrementing index as we strip away an element in the TupleList type.

As we saw earlier, to get to the next element, we have to go to our parent TupleList. By stripping an element and decrementing an index, we go one step into our parent.

Hence each of these GetIndex empty structs are nodes in a type linked list that takes you from one element to another with an index for each parent.

Great. We have indexes, now how do we implement get using GetIndex?

template<size_t idx, typename TupleList>
struct GetIndex;

template<template T, template... Rem>
struct GetIndex<0, TupleList<T, Rem...>>{
     using type = T;
     static type get(TupleList<T, Rem...>& tuple){
          return tuple.val;
     }
};

template<size_t idx, template T, template... Rem>
struct GetIndex<idx, TupleList<T, Rem..>>{
     using type = typename GetIndex<idx-1, TupleList<Rem...>>::type;
     static type get(TupleList<T, Rem...>& tuple){
          return GetIndex<idx-1, TupleList<Rem...>>(tuple);
     }
};

template<size_t idx, typename T, typename... Rem>
GetIndex<idx, TupleList<T, Rem...>::type get(TupleList<T, Rem...>& tuple){
     return GetIndex<idx, TupleList<T, Rem...>>::get(tuple);
}

So we just implemented the get function.

The main one that gets called is the non-member get function, the one outside the GetIndex struct.

This main get function calls the get functions of the GetIndex structs to recursively go through the linkedlist and grab the value.

The compiler should optimize this into an O(1) operation as each get function only has 1 line which is to call the next get function or return the value.

But here is the interesting part. The main get function is a templated function. It's return type is dependent on the GetIndex<idx, TupleList<T, Rem...>::type type.

The return type goes through the templates and runs through the GetIndex type alias recursive chain (of decrementing index and looking at the parent's type) until it hits the definition for type in the base class (index is 0).

The compiler will create definitions by recursing through GetIndex to determine the function's return type.

Now the only part that sucks about this is that the compiler requires you to know the index you want to access at compile time.

Templates are evaluated and specialized by the compiler when you compile your program.

So when you call this get function like this:

TupleList<int, double, char> list(1, 2.5, 'c');
double val = get<1>(list);

The compiler determines at compile time that this get function returns type double and also wants index 1.

(Template parameters must be constant r-values or constexpr values.) So you can't do get<variable>.

Great, if I have a for loop then, how do I access each index one by one?

You have two options:

1. implement a loop function
2. have a get function that we can give an index at runtime

Okay let's try to both:

a runtime get function

Remember the idea here is we want to use our index at runtime to get the value out of our tuple.

It gets tricky because we no longer get to use our templated index where 0 is our base case. We'll have to check for 0 at runtime.

This makes our return type a bit tricky.

We'll now have to use type erasure because our compiler won't know the return type at compile time anymore without compile time indexes.

What is type erasure? It's where the type of the value is unknown until you query for it.

C++ has std::any and std::variant for this.

template<typename...>
struct TupleList;

template<>
struct TupleList<> {
    std::any get(size_t) const {
        throw std::out_of_range("Index out of bounds");
    }
};

template<typename T, typename... Rem>
struct TupleList<T, Rem...> : TupleList<Rem...> {
    T val;
    TupleList(T val, Rem... rem): TupleList<Rem...>(rem...), val(val) {}

    std::any get(size_t index) const {
        if (index == 0)
            return val;
        else
            return TupleList<Rem...>::get(index - 1);
    }
};

Great! With this, you can call get like this:

TupleList<int, double, char> t(1,2.5,'c');
int idx = 2;
std::any res = t.get(idx);

The difference now is that we can pass in variable indexes at runtime.

We can also optionally make the get function static, so that it is used as before with get(tuple, idx).

Another main thing to note, is that std::any is returned. Now we have to check the type before extracting the value out.

This is an annoying part with a runtime get function.

if (res.type() == typeid(char)) std::cout << std::any_cast<char>(res) << std::endl;

Another annoying part about this function is that the compiler can't optimize it.

So accessing indexes is worst case O(n) now because each time we enter the next parent, we have to check if index is 0 at runtime.

It shouldn't be a problem however if your TupleLists tend to be small. But if possible, prefer the smarter compile time get function.

Okay let's explore the loop option.

Can we loop without runtime indices?

The answer is yes.

template<typename...>
struct TupleList;

template<>
struct TupleList<> {
     static void loop(size_t idx, TupleList<T, Rem...>& tuple, auto&& func){}
};

template<typename T, typename... Rem>
struct TupleList<T, Rem...> : TupleList<Rem...> {
    T val;
    TupleList(T val, Rem... rem): TupleList<Rem...>(rem...), val(val) {}

    static void loop(size_t idx, TupleList<T, Rem...>& tuple, auto&& func ){
         func(idx, tuple.val);
         TupleList<Rem...>::loop(idx+1, tuple, func);
    }
};

template<typename T, typename... Rem>
void loop(TupleList<T, Rem...>& tuple, auto&& func){
    TupleList<T, Rem...>::loop(0, tuple, func);
}

Cool. We have a loop function that takes in a reference to a function.

Honestly, we could also put std::function instead of auto&& as well.

But we can see that we iterate into the static function of the parent which lets us extract the next value as we increment indices. This makes this function O(n).

We can provide both to our function for processing.

The only problem is now your func is expected to handle multiple types of values when looping through.

No need to fear we can have templates. Here are some examples:

TupleList<int, double, char> tuple(1,2.5,'c');
// lambda 'auto' arg becomes a templated arg
auto print = [](size_t idx, auto arg){
     std::cout << arg << std::endl;
}
loop(tuple, print); 

auto int_nonint_print = [](size_t idx, auto arg){
     if constexpr (std::is_same_v<decltype(arg), int>){
          std::cout << arg << " is an int" << std::endl;
     }else{
          std::cout << arg << " is not an int" <<std::endl;
     }
}
loop(tuple, int_nonint_print);

// template lambda
template<typename T>
auto print2 = [](size_t idx, T arg){
     std::cout << arg << std::endl;
}
loop(tuple, print2);

Here I show 3 examples of using loop:

1. auto lambda will become a functor with a templated argument for its function, so it acts like example 3.
2. int_nonint_print shows we can use constexpr with type traits to create different functions for ints and nonints, so we can have type based logic implicitly (C++20)
3. a explicit template lambda is used. The compiler will specialize and generate versions of the function based on the types in the TupleList

Conclusion

Ok we've talked about a lot for this blog. This topic is not over yet.

I want to build out the rest of TupleList including adding/removing elements.

But right now we have a TupleArray. And we can loop through it and access different elements at runtime or compile time.

Let's talk about the differences between the TupleList and std::vector as a baseline.

1. TupleList is created on the stack (but it could be heap as well) whereas std::vector allocates its elements on the heap
2. TupleList can store different types and std::vector cannot (unless it uses std::any)
3. TupleList can have constant compile time access or O(n) runtime access whereas std::vector has constant random access O(1).
4. You can loop through both.
5. As of right now, you can only change the size of std::vector until part 2 :)

Okay overall, I hope you liked this mini lesson and cool usage of variadic templates.

And we'll explore more of this another part.

As usual, drop your questions below :)

And here's example code, with an additional hash example if you want to mess around with it: https://pastebin.com/rERy1avn

Until next time
-absterdabster

Comments

[absterdabster]

Drop your questions here!