Understand internals of std::expected

In the article about std::expected, I introduced the type and showed some basic examples, and in this text, you’ll learn how it is implemented.

A simple idea with struct  

In short, std::expected should contain two data members: the actual expected value and the unexpected error object. So, in theory, we could use a simple structure:

template <class _Ty, class _Err>
struct expected {
    /*... lots of code ... */
    _Ty _Value;
    _Err _Unexpected;
};

However, there are better solutions than this. Here are some obvious issues for our “struct” approach.

• The size of the object is the sum of the Value type and the Error type (plus padding if needed).
• Two data members are “active” and initialized, which might not be possible - for example, what if the Value type has no default constructor? The Standard requires that std::expected" holds either a value of type Tor an error of typeE` within its storage.
• We’d have to guarantee that _Ty cannot be a reference type or an array type; it must be a Destructible Type.
• Similarly for the _Err type we have to guarantee that it’s also Destructible, and must be a valid template argument for std::unexpected (so not an array, non-object type, nor cv-qualified type).
• Plus, we’d have to write a lot of code that creates an API for the type

How about std::variant?  

Ok, since we want to have a more compact type, why not use std::variant?

std::variant is a tagged union, so it holds only one of the list of types and has an efficient way to switch between them.

We can try with the following code:

template<typename T, typename E>
using expected = std::variant<T, std::unexpected<E>>;

However, std::variant does not provide some specific behaviors that std::expected might need, such as conditional explicit constructors and assignment operators based on the contained types’ properties. So, additional work would be required to implement these properly.

Furthermore, std::variant has to be very generic and offers a way to handle many alternative types in one object, which is “too much” for the expected type, which needs only two alternatives.

Real implementation  

Let’s look at some open implementations and see what’s under the hood.

We can go to the Microsoft STL repository:

https://github.com/microsoft/STL/blob/main/stl/inc/expected

The expected class uses a union to store either a value of type _Ty or an error of type _Err:

_EXPORT_STD template <class _Ty, class _Err>
class expected {
    /*... lots of code ... */
    
    union {
        _Ty _Value;
        _Err _Unexpected;
    };
    bool _Has_value;
};

Here, _Value and _Unexpected are two data members that share the same memory location within an instance of expected. Which member of the union is currently active (i.e., contains valid data) is not tracked by the union itself. Therefore, the expected class maintains an additional boolean member, _Has_value, to track whether the union currently holds a _Ty value (_Has_value is true) or an _Err error (_Has_value is false).

As you can see, this approach is much more advanced than our simple structure and uses some ideas from std::variant.

Size of Objects:  

The size of an expected object depends on several factors:

1. Size of _Ty and _Err: The size of the union will be at least as large as the size of its largest member because the union allocates enough space to hold the largest member.
2. Alignment: we have to honour _Ty’s and _Err’s alignment requirements.
3. Boolean _Has_value: There’s also a boolean member variable _Has_value indicating which member of the union is active. This adds to the total size of the class.

So, the total size of an expected<_Ty, _Err> object will be approximately:

max(sizeof(_Ty), sizeof(_Err)) + sizeof(bool) + possible padding for alignment

Here are some examples of the sizes on GCC x64:

Type: int
Size: 4
Type: std::string
Size: 32
Sizeof std::expected: 40

Type: int
Size: 4
Type: double
Size: 8
Sizeof std::expected: 16

Type: int
Size: 4
Type: std::pair<int, int>
Size: 8
Sizeof std::expected: 12

You can check the code here: @Compiler Explorer.

Going further down  

Let’s have a look at some other member functions:

_NODISCARD constexpr const _Ty& value() const& {
    if (_Has_value) {
        return _Value;
    }

    _Throw_bad_expected_access_lv();
}
_NODISCARD constexpr _Ty& value() & {
    if (_Has_value) {
        return _Value;
    }

    _Throw_bad_expected_access_lv();
}

Those are relatively simple: they check the flag and return the value.

On the other hand, one of the overloads for the assignment operators (see at this line) is more complex:

constexpr expected& operator=(const expected& _Other) noexcept(
    is_nothrow_copy_constructible_v<_Ty> && is_nothrow_copy_constructible_v<_Err>
    && is_nothrow_copy_assignable_v<_Ty> && is_nothrow_copy_assignable_v<_Err>) // strengthened
    requires _Expected_binary_copy_assignable<_Ty, _Err>
{
    if (_Has_value && _Other._Has_value) {
        _Value = _Other._Value;
    } else if (_Has_value) {
        _Reinit_expected(_Unexpected, _Value, _Other._Unexpected);
    } else if (_Other._Has_value) {
        _Reinit_expected(_Value, _Unexpected, _Other._Value);
    } else {
        _Unexpected = _Other._Unexpected;
    }

    _Has_value = _Other._Has_value;
    return *this;
}

The _Reinit_expected template function manages the transition of an std::expected object from one state to another. Because the code uses union, it has to manage the lifetime of alternatives.

Other implementations  

• In GCC libstdc++ - expected @ Github - it also uses union to hold the alternatives
• In LLVM libc++: expected @Github - in many places it uses no_unique_address attribute and Empty Base Class Optimization so in theory if might use less space than the regular union approach.

Summary  

In this text, I covered a rough idea of how to implement the std::expected type. As you can see, it’s not just a simple structure of <ValueT, ErrorT> and contains a lot of tricks to fulfill all of the requirements.

I believe that understanding and appreciating the patterns within the Standard Library can be valuable, even if we don’t need to delve too deeply into its implementation in our everyday C++ tasks.

See the introduction to std::expected in my previous article.