Creating a Compile-Time Set Data Structure in C++

This is my learning notes from the course - Mastering C++ Standard Library Features.

Creating a Compile-Time Set Data Structure

How to implement a simple compile-time set data structure

The Plan

Our data structure will be called ct_set
It will allow users to add/remove/check elements
Every element will have a unique type

It will use a familiar constexpr - based syntax:

constexpr auto s0 = ct_set{};
constexpr auto s1 = s0.add(c<42>);

static_assert(s1.contains(c<42>));
static_assert(!s1.contains(c<120>));

Implementation

We will need following headers:

1
2
3

#include <tuple>
#include <type_traits>
#include <utilities>

Using C++17’s “auto non-type template parameters” and inline variables, we can easily define convenient shorthand notation for std::integral_constant
1
2
3
template <auto X>
inline constexpr std::integral_constant<decltype(X), X> c{};
// c<10> -> std::integral_constant<decltype(10), 10>

Our ct_set data structure will store items thanks to a variadic parameter pack Items...

template <typename... Items>
struct ct_set
{
    // Since `this` is not usable as part of a constant expression
    // we'll define a `static` `self()` member function
    // that return a new instance of the current set
    static constexpr auto self() noexcept
    {
        return ct_set<Items...>{};
    }

    // In order to check whether or not an item is in the set, we'll define a
    // `contains` function that takes an arbitrary item of type `T` and uses
    // `std::disjunction` to check if any of the stored `Items...` match `T`
    template <typename T>
    constexpr bool contains(T) const noexcept
    {
        return std::disjunction_v<std::is_same<T, Items>...>;
    }

    // Adding an item `x` to the set will return a new instance of:
    // * The same set, if the item is already available
    // * A new set of `T, Items...`, if the item is not available
    template <typename T>
    constexpr auto add(T x) const noexcept
    {
        if constexpr(self().contains(x))
        {
            return self();
        }
        else
        {
            return ct_set<T, Items...>{};
        }
    }

    // Removing an item `x` from the set will return a new instance of:
    // * The same set, if the item is not available
    // * A new set of `Items... - {T}`, if the item is already available
    template <typename T>
    constexpr auto remove(T x) const noexcept
    {
        if constexpr(!self().contains(x))
        {
            return self();
        }
        else
        {
            // clang-format off
            // A simple way of removing a particular type from a type list
            // is by using `std::tuple` and `std::tuple_cat`.
            // Firstly, we'll wrap every item that is not `T` in an `std::tuple`.
            // The item that matches `T` will be transformed to an empty tuple.
            // Then `std::tuple_cat` will concatenate and flatten the tuples.
            constexpr auto filtered = std::tuple_cat(
                std::conditional_t<
                    std::is_same_v<T, Items>,
                    std::tuple<>,
                    std::tuple<Items>
                >{}...
            );

            // Now that we have a tuple containing all types except `T`
            // we can use `std::apply` in order to extract those types
            // and get back a new instance of `ct_set` without `T`
            return std::apply([](auto... xs)
            {
                return ct_set<decltype(xs)...>{};
            }, filtered);
            // clang-format on
        }
    }
};

int main()
{
    constexpr auto s0 = ct_set{};
    static_assert(!s0.contains(c<42>));

    constexpr auto s1 = s0.add(c<42>);
    static_assert(s1.contains(c<42>));

    constexpr auto s2 = s1.add(c<100>);
    static_assert(s2.contains(c<42>));
    static_assert(s2.contains(c<100>));

    constexpr auto s3 = s2.remove(c<42>);
    static_assert(!s3.contains(c<42>));
    static_assert(s3.contains(c<100>));
}

Summary

Using <type_traits>, <utilities>, and <tuple>, it is possible to easily implement compile-time data structures
Every element needs to have a unique type - std::integral_constant is helpful to achieve that
This is not usable in constant expressions - defining a static self() member function circumvents the issue
It is possible to achieve a familiar syntax by using constexpr member functions

Guidelines

When necessary and possible, consider creating compile-time data structures for your domain problem
Compile-time errors are better than run-time errors
Possible performance improvements
std::tuple is useful even when storing simple empty classes
Consider using production-ready libraries, such as boost::hana

Section Summary

Learned that metafunctions are functions that operate on types. They can be used to manipulate or adapt types in templates
Studied that the Standard Library provides many metafunctions and metaprogramming utilities in the <type_traits> and <utilities> headers
The <type_traits> header can be used to mutate types or check what properties/operations they satisfy
It is possible to create convenient compile-time data structures by combining constexpr and metaprogramming utilities from Standard Library

Reference Link

Mastering C++ Standard Library Features