Quickest way to learn is to be inquisitive about everything!

2021-11-23 1045 words 5 minutes

Contents

It starts with “how?”

std::variant is a new addition to C++ standard library adopted from ominous boost libraries. Just as a reminder, std::variant is a type safe union with a very cool visitor interface, thanks to which handling its state is very convenient. The type itself wouldn’t be very special to me until I stumbled upon this sentence on cppreference

As with unions, if a variant holds a value of some object type T, the object representation of T is allocated directly within the object representation of the variant itself. Variant is not allowed to allocate additional (dynamic) memory.

I was not aware of that… and here comes the, “how?”. For some reason, I’ve always assumed that runtime polymorphism is employed under the bonnet to change the internal representation on assignments to std::variant, but how to achieve that without any allocations at all? After a bit of googling, I’ve came across std::aligned_union which I’ve never heard of, even though it’s been introduced with C++11. I didn’t implement anything yet and the curiosity already pays off - I’m learning new stuff!

Dive into the details

std::aligned_union and placement new may be the missing magic ingredients required to implement std::variant and I don’t want to have a nosy around STL headers and spoil everything for myself. Let’s start with a use case. I want my variant to support the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


my::variant<int, double, bool, std::string> v;

v = 123;
std::cout << v.get<int>() << std::endl;

v = 123.456;
std::cout << v.get<double>() << std::endl;

try {
    v.get<int>();
}
catch(const std::exception&) {
    std::cout << "variant doesn't hold an <int>" << std::endl;
}

v = std::string("some string mate");
std::cout << v.get<std::string>() << std::endl;

Let’s start with a basic skeleton:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


namespace my
{
    template <typename ... Ts>
        class variant {
            using SelfT = variant<Ts...>;

        public:
            constexpr variant() {
            }

            template <typename AssignT>
                constexpr SelfT& operator=(AssignT&& other) {
                    return *this;
                }

            template <typename DesiredT>
                constexpr const DesiredT& get() {
                }
        };
} /* namespace my */

So far so good, I’m gonna declare some storage as well:

1
2
3


using StorageT = typename std::aligned_union<0, Ts...>::type;

StorageT storage;

I’ve got storage! Now I can just use placement new to allocate types for new data inside operator= right? Technically yes, but there’s a gotcha: it would never be possible to verify what type the variant is actually storing since the information about the type is lost once the execution goes outside the operator= scope. I’m gonna use runtime polymorphism to store details about the original type. A base type is needed and a small wrapper around the value:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


struct Container {
public:
    virtual ~Container() = default;
};

template <typename T>
struct TypeContainer : public Container {
    TypeContainer(T&& v) :
        v{std::move(v)}
    {
    }

    // keep a copy
    const T v;
};

Thanks to that, the type information is preserved. The storage has to be slightly altered though:

1

using StorageT = typename std::aligned_union<0, TypeContainer<Ts>...>::type;

Now it’s possible to implement operator= and get() functions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


template <typename AssignT>
constexpr SelfT& operator=(AssignT&& other) {
    std::launder(reinterpret_cast<Container*>(&storage))->~Container();
    new(&storage) TypeContainer<AssignT>(std::forward<AssignT>(other));
    return *this;
}

template <typename DesiredT>
constexpr const DesiredT& get() {
    auto c = std::launder(reinterpret_cast<Container*>(&storage));
    if (auto tc = dynamic_cast<TypeContainer<DesiredT>*>(c); tc == nullptr) {
        throw std::runtime_error("bad variant access");
    } else {
        return tc->v;
    }
}

This code assumes that storage always contains an instance of Container which initially is not true, since without explicit assignment there’s nothing there. To fix that, I’m gonna define a private placeholder type:

1

class NullType {};

And with all that in hands, here’s the complete code, where I’ve removed some of the duplication and added a static_assert in operator= to only allow for assignments of types with which the variant was originally declared with. Here’s the complete code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99


#include <string>
#include <type_traits>
#include <new>

#include <iostream>

namespace my
{
        struct Container {
        public:
            virtual ~Container() = default;
        };

        template <typename T>
            struct TypeContainer : public Container {
                TypeContainer(T&& v) :
                    v{std::move(v)}
                {
                }

                // keep a copy
                const T v;
            };

        class NullType {};

    template <typename ... Ts>
        class variant {
            using SelfT = variant<Ts...>;
            using StorageT = typename std::aligned_union<0, TypeContainer<Ts>...>::type;

            StorageT storage;
        public:
            constexpr variant() {
                allocContainer(NullType{});
            }

            constexpr ~variant() {
                destroyContainer();
            }

            constexpr Container* asContainer() {
                return std::launder(reinterpret_cast<Container*>(&storage));
            }

            constexpr void destroyContainer() {
                asContainer()->~Container();
            }

            template <typename AssignT>
                constexpr void allocContainer(AssignT&& other) {
                    new(&storage) TypeContainer<AssignT>(std::forward<AssignT>(other));
                }

            template <typename AssignT>
                constexpr SelfT& operator=(AssignT&& other) {
                    static_assert(
                            std::disjunction<std::is_same<AssignT, Ts>...>::value || std::is_same<AssignT, NullType>::value,
                            "invalid type");

                    destroyContainer();
                    allocContainer(std::forward<AssignT>(other));
                    return *this;
                }

            template <typename DesiredT>
                constexpr const DesiredT& get() {
                    if (auto tc = dynamic_cast<TypeContainer<DesiredT>*>(asContainer());
                            tc == nullptr) {
                        throw std::runtime_error("bad variant access");
                    } else {
                        return tc->v;
                    }
                }
        };
} /* namespace my */

int main(int argc, const char *argv[])
{
    my::variant<int, double, bool, std::string> v;

    v = 123;
    std::cout << v.get<int>() << std::endl;

    v = 123.456;
    std::cout << v.get<double>() << std::endl;

    try {
        v.get<int>();
    }
    catch(const std::exception&) {
        std::cout << "variant doesn't hold an <int>" << std::endl;
    }

    v = std::string("some string mate");
    std::cout << v.get<std::string>() << std::endl;

    return 0;
}

One additional detail requiring a word is the presence of std::launder which is a recent addition to C++ as well. It prevents the compiler from introducing optimisations on the memory addresses it is applied to, which is probably a good thing in case of any usage of reinterpret_cast.