Compile-time set subtraction of two tuples

user_5729690 0
Viewed 179

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.

parameter-pack compile-time tuples c++
2 Answers

Here's a compile time set subtraction, use it as set_diff<tuple1, tuple2>::type:

template <class...> class set_diff;

template <class... A, class... B>
struct set_diff<std::tuple<A...>, std::tuple<B...>>
{
    template <class J, class... Js>
    constexpr static bool exists_in = std::disjunction_v<std::is_same<J, Js>...>;

    using type = decltype(tuple_cat(std::declval<
      std::conditional_t<exists_in<A, B...>, std::tuple<>, std::tuple<A>>>()...));
};

Demo

Note that:

  • The order of the operands matters (according to the problem description)
  • There are various "optimizations" of compilation complexity possible (e.g. sorting the types and removing duplicates prior to diff etc.).

My solution works in two steps:

  1. Marks the "unwanted" types as tuple<>
  2. Generates the desired type using tuple_cat, which evicts empty tuples

A more self-explanatory (alas more verbose) demo can be found here Demo

user_42245750

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.

user_87466480
Related