Compile-time set subtraction of two tuples

Question

I have an application where I am constructing tuple out of a parameter pack:

template<class... T>
struct foo {
 typedef std::tuple<T...> A;
}

And I have another tuple-type B defined as:

typedef std::tuple<char, int> B;

Is there a way to obtain a new tuple C, such that C is a set subtraction of the types in the sets A and B at compile-time?

A = {int, double, float, bool}
B = {char, int}
C = A - B = {double, float, bool} // answer

Some more context to the complete problem:

template<class... T>
struct foo {
 using first_type = typename std::tuple_element<0, // n'th type 
                     std::tuple<T...>>::type;
}

I can do the above to find the 0th type, but I am interested in the first type that is not contained in set B above. So, somewhat like a compile-time search to find the first valid type.

Answer 1

Disclaimer. Please don't put code like this into an actual code base. If you do, this implementation is by no means "optimal" and should be cleaned up before use (maybe add an answer if you do).

I found this an interesting challenge, and found the following solution:

// Try this live at https://compiler-explorer.com/z/cqebd81ss

#include <type_traits>

template <typename... Pack>
struct ClassList;

template<typename...>
struct Join {
};
template<typename... Pack1, typename... Pack2>
struct Join<ClassList<Pack1...>, ClassList<Pack2...>> {
    using Type = ClassList<Pack1..., Pack2...>;
};

template<typename...>
struct RemoveSingleTypeFromList {
};
template<typename Target, typename... Pack>
struct RemoveSingleTypeFromList<Target, ClassList<Pack...>> {
    using Type = ClassList<Pack...>;
};
template<typename Target, typename Parameter, typename... Pack>
struct RemoveSingleTypeFromList<Target, ClassList<Parameter, Pack...>> {
    using Type = typename Join<
        std::conditional_t<
            std::is_same_v<Target, Parameter>,
            ClassList<>,
            ClassList<Parameter>
        >,
        typename RemoveSingleTypeFromList<Target, ClassList<Pack...>>::Type
    >::Type;
};

template<typename... Pack>
struct RemoveTypesFromList {
};
template<typename... Types>
struct RemoveTypesFromList<ClassList<>, ClassList<Types...>> {
    using Type = ClassList<Types...>;
};
template<typename Target, typename... RemainingTargets, typename... Types>
struct RemoveTypesFromList<ClassList<Target, RemainingTargets...>, ClassList<Types...>> {
    using Type = typename RemoveSingleTypeFromList<
        Target,
        typename RemoveTypesFromList<
            ClassList<RemainingTargets...>,
            ClassList<Types...>
        >::Type
    >::Type;
};

// A few test cases to verify that it works

static_assert(std::is_same_v<
    typename RemoveTypesFromList<
        ClassList<int, float>,
        ClassList<float, double, int, long>
    >::Type,
    ClassList<double, long>>);

static_assert(std::is_same_v<
    typename RemoveTypesFromList<
        ClassList<float>,
        ClassList<float, double, float>
    >::Type,
    ClassList<double>>);

static_assert(std::is_same_v<
    typename RemoveTypesFromList<
        ClassList<int, int>,
        ClassList<float, double, float>
    >::Type,
    ClassList<float, double, float>>);

If you are interested in understanding exactly how this works, remember that this is a solution and not something you could write top-to-bottom. When reading template code like this, I find it most useful to build a similar implementation step by step.