Doing set operations on C++ types.

Type collections in C++

In the C++ standard there are a few types that work with a collection of types. The standard std::tuple work like a product type, having all the different types represented on it’s instances. Mean while there are also std::variant that represent sum types, where it’s instance can take form of one of it’s forming types.

Okay we can represent type collections, with those two compound type templates. Lets see what kind of operations we can do with them.

Set operations.

∈: "Element of" or "belongs" relation

Element of is a check if type belongs to set ∈ or if doesn’t belongs ∉

Neither the tuple nor a variant provide a nice way to check if a type belongs to the set of types that defines them. The closest you can get it to attempt to use std::get<TYPE> on an instance and check if the result is valid C++.

⊂ & ⊃ : Subset checks or contains relations

This operation checks whether another set is a subset of another, where a set is a subset of another when all it’s elements are present on the other set.

Once again neither tuple or variant can be checked to be subsets. There’s another subtle detail that is relevant here, in math the order of the element is irrelevant. This is not true for C++ tuples or variants, that is a std::tuple<int, char> is different than std::tuple<char, int>.

This means that the equality relationship that C++ provides is not compatible with the mathematical notion of set equality.

∪ : Union operation.

The result of an union of two sets is the set that contains all element of all the original sets and no more elements.

With tuples you can create a union of different tuples using std::tuple_cat^[1]. Variants don’t have any way of creating an union variant type.

∩ : Intersection operation.

The intersection section of two sets is the set of all elements in one that are also present in the other.

This operation is also not possible with neither tuples or variants.

- : Difference operation.

The set difference is a set that has all the elements of the first set that are not elements from the second set. This operation is not commutative, like the intersection or union.

This operation is not available for tuples or variants.

Creating a type collection template with all these operations.

For this exploration I will follow the principles bellow.

Design characteristics:

type collections are ethereal, instances of these types do not have any content.
type collections can be operated with the set operations above.
Both tuple and variant can be used to create a type set.
Both tuple and variant types can be extracted from the type sets.
Creating a tuple or variant from a type set that was created from a tuple or variant should not be different than the original.
void cannot be part of a type set.

Because of the last requirement, not all type set are actual sets. For instance the type set created from std::tuple<int, int> is not a set. The type sets that are indeed sets will satisfy the concept is_type_set.

For this reason I’m calling this template type a type_collection not a type_set.

Type set have the following static values :

class typeset:: operations.

cardinality :

Number of elements
empty :

Is this an empty set? (cardinality == 0)
is_set :

Is this a set?
template count_of<element_type> :

Number of times element_type is present on this set. This value should be either 1 or 0 on actual sets.
same_as_{[_collection]}<other_collection or types…> :

True if this represents the same collection. In this operation the order does not matter. type_collection<int, char>::same_as<char, int> == true.
contains_{[_collection]}<other_collection or types…> :

True when the other collection is contained in this collection.
typename template element<N> :

Type of the element at the N^th index
typename template union_with_{[_collection]}<other_collection or types…> :

Type collection that is the union of this collection with another.
typename template intersection_with_{[_collection]}<other_collection or types…> :

Type collection that is the intersection of this collection with another.
typename template difference_with_{[_collection]}<other_collection or types…> :

Type collection that is the intersection of this collection with another.
as_tuple :

std::tuple created from this type collection.
as_variant :

std::variant created from this type collection, this is not valid for empty type collections.

For the type templates that represent operations with other collections, there are two possible syntaxes. operation_with_collection<other_collection> when operating directly with another collection. Or operation_with<types…> as a short-hand for operation_with_collection<type_collection<types…>>.

Type collection types can be created from std::tuple or std::variant using the aliases:

collection_from_tuple<std::tuple<types…>>:

To create from a std::tuple.
collection_from_variant<std::variant<types…>>:

To create from a std::variant.
collection_from<either<types…>>:

Can be used on either std::tuple or std::variant.

The secret sauce.

For most of the set operations I’ve used a variation of the following construct :

template <is_element_type... TYPEs>
struct type_collection {
…
    template <is_type_collection OTHER>
    using operation = decltype([]<
                typename SELF,
                std::size_t N,
                std::size_t... Ns,(1)
                is_element_type... TYPEs (2)
            > (
                this SELF&& self, (3)
                std::index_sequence<N, Ns...>,
                TYPEs* ...elements)
        {
        static constexpr auto should_contain_element = (4)
        if constexpr (sizeof...(TYPEs) == 0) { (5)
            if constexpr ( should_contain_element) {
                return type_collection<… TYPEs..., OTHER::element<N>>{};
            } else {
                return type_collection<… TYPEs...>{};
            }
        }
        if constexpr (should_contain_element) {
            return self( (2)
                std::index_sequence<Ns...>{},
                elements...,
                static_cast<OTHER::element<N>*>(nullptr)
            );
        } else {
            return self( (2)
                std::index_sequence<Ns...>{},
                elements...
            );
        }
    }(std::make_index_sequence<OTHER::cardinality>())); (6)
…
};

1	The lambda uses a index sequence to consume the elements from the other collection. `N` is the current index, while the `Ns…` are used to invoke the next step.
2	We also keep track of the elements we’re using.
3	The "deducing this" syntax is used to make the lambda recursive.
4	This boolean checks if the current element should be part of the result.
5	Recursion ending cases.
6	In the actual code a `index_set` static variable helps the notation here.

This is a tail recursion, and never backtracks. In other words it grows linearly with the cardinality of the set being operated on.

Samples — or how does it work?

The code bellow show some assertions testing the code.

assertions

namespace static_test {
using test_1 = type_collection<int, char>;
using test_2 = type_collection<char, int>;

static_assert(test_1::cardinality == 2);
static_assert(std::same_as<
    type_collection<int, char>::
        template union_with<unsigned>,
    type_collection<int, char, unsigned>>);
static_assert(
    type_collection<int, char>::
        template union_with<unsigned>::cardinality == 3);
static_assert(
    type_collection<int, char>::
        template union_with<int>::cardinality == 2);
static_assert(std::same_as<type_collection<int, char>::
    template intersection_with<int>,
    type_collection<int>>);
static_assert(std::same_as<
    type_collection<int, char, char*, int*>::template
        intersection_with<int, int*>,
    type_collection<int, int*>>);
static_assert(std::same_as<
    type_collection<int, char>::
        template difference_with<int>,
    type_collection<char>>);
static_assert(std::same_as<
    type_collection<int>::
        template difference_with<int, char>,
    type_collection<>>);
static_assert(std::same_as<
    type_collection<int, char, char*, int*>::
        template intersection_with<int, int*>,
    type_collection<int, int*>>);

static_assert(type_collection<int>::is_set);
static_assert(type_collection<std::vector<int>>::is_set);
static_assert(!type_collection<int, char, int>::is_set);
static_assert(type_collection<int, double, char>::cardinality == 3);
static_assert(type_collection<int, double, char>::is_set);
static_assert(type_collection<int, double, char>::count_of<int&> == 0);
static_assert(type_collection<int, double, char>::belongs<char>);
static_assert(type_collection<int, double, char>::belongs<double>);
}

Sources

You can check out the whole project at my github page. Or if you want just to look at the implementation, it’s a single header file.

1. Not exactly true, since the std::tuple_cat operates on instances, and if instances cannot be copied or moved the std::tuple_cat can fail.

Bogado.net