Common types in two TypeSets / Tuples

Question

I have two tuples -- TypeSets modeled as tuples, and thus guaranteed to contain each type at maximum once in their parameter packs, to be exact -- (say A = std::tuple<T1, T2> and B = std::tuple<T2, T3>), and I wish to obtain a typedef that corresponds to a tuple of types in the intersection of A and B (in this case, tuple_intersect<A,B>::type = std::tuple<T2>). How do I go about this?

Answer 1

You can use the indices trick along with has_type (from here):

#include <tuple>
#include <type_traits>

// ##############################################
// from https://stackoverflow.com/a/25958302/678093
template <typename T, typename Tuple>
struct has_type;

template <typename T>
struct has_type<T, std::tuple<>> : std::false_type {};

template <typename T, typename U, typename... Ts>
struct has_type<T, std::tuple<U, Ts...>> : has_type<T, std::tuple<Ts...>> {};

template <typename T, typename... Ts>
struct has_type<T, std::tuple<T, Ts...>> : std::true_type {};
// ##############################################


template <typename S1, typename S2>
struct intersect
{
template <std::size_t... Indices>
static constexpr auto make_intersection(std::index_sequence<Indices...> ) {

    return std::tuple_cat(
        std::conditional_t<
            has_type<
                std::tuple_element_t<Indices, S1>,
                S2
                >::value,
                std::tuple<std::tuple_element_t<Indices, S1>>,
                std::tuple<>

    >{}...);
}
using type = decltype(make_intersection(std::make_index_sequence<std::tuple_size<S1>::value>{}));
};


struct T1{};
struct T2{};
struct T3{};
using A = std::tuple<T1, T2>;
using B = std::tuple<T2, T3>;

int main()
{
   static_assert(std::is_same<std::tuple<T2>, intersect<A, B>::type>::value, "");
}

live example

Answer 2

This problem is tackled in several parts.

In the first part, let's create a template<typename type_2_search, typename ...all_types> class type_search; that determines if type_2_search is any of the types in ...all_types

#include <type_traits>
#include <iostream>
#include <tuple>

template<typename type_2_search, typename ...all_types> class type_search;

template<typename type_2_search,
     typename type_2_compare,
     typename ...all_types> class type_compare
    : public type_search<type_2_search, all_types...>
{
};

template<typename type_2_search,
     typename ...all_types>
class type_compare<type_2_search, type_2_search, all_types...>
    : public std::true_type {};

template<typename type_2_search>
class type_search<type_2_search> : public std::false_type {};

template<typename type_2_search, typename first_type, typename ...all_types>
class type_search<type_2_search, first_type, all_types...> :
    public type_compare<type_2_search, first_type, all_types...>
{
};

int main()
{
    std::cout << type_search<int, char, double, int *>::value << std::endl;
    std::cout << type_search<int, int, char, double, int *>::value << std::endl;
    std::cout << type_search<int, char, double, int *, int>::value << std::endl;
    std::cout << type_search<int, char, int, double, int *>::value << std::endl;
}

The resulting output is:

0
1
1
1

The next part is a template<typename type, bool value, typename tuple_bag> class add_2_bag_if_type_in_tuple;. The first parameter is a type. The third parameter is a std::tuple<types...>. If the second bool is true, the template gives you back a std::tuple<type, types...>, it adds the type of the tuple. Otherwise, it gives you back the same tuple. Fairly straightforward:

template<typename type, bool value, typename tuple_bag>
class add_2_bag_if_type_in_tuple;

template<typename type, typename tuple_bag>
class add_2_bag_if_type_in_tuple<type, false, tuple_bag> {
 public:

    typedef tuple_bag type_t;
};

template<typename type, typename ...types>
class add_2_bag_if_type_in_tuple<type, true, std::tuple<types...>> {
 public:

    typedef std::tuple<type, types...> type_t;
};

We now have all the missing pieces to create a tuple_intersection template, in the final part. We iterate over the first tuple's types, check each type against the types in the second tuple, using the first template, then pass the results to the second template.

First, the specialization, when we reached the end of the first tuple's types:

template<typename tuple1_types,
     typename tuple2_types> class compute_intersection;

template<typename ...tuple2_types>
class compute_intersection<std::tuple<>,
               std::tuple<tuple2_types...>> {
public:

    typedef std::tuple<> type_t;
};

And for the final piece of the jigsaw puzzle: pluck off the first type from the first tuple, use compute_intersection recursively to compute the intersection of the rest of the first tuple with the second tuple, then type_search the plucked-off type, then `add_2_bag_if_type_in_tuple:

template<typename tuple1_type,
     typename ...tuple1_types, typename ...tuple2_types>
class compute_intersection<std::tuple<tuple1_type, tuple1_types...>,
               std::tuple<tuple2_types...>> {
public:

    typedef typename compute_intersection<std::tuple<tuple1_types...>,
                          std::tuple<tuple2_types...>>
        ::type_t previous_bag_t;

    typedef typename add_2_bag_if_type_in_tuple<
        tuple1_type,
        type_search<tuple1_type, tuple2_types...>::value,
        previous_bag_t>::type_t type_t;
};

Complete test program:

#include <type_traits>
#include <iostream>
#include <tuple>

template<typename type_2_search, typename ...all_types> class type_search;

template<typename type_2_search,
     typename type_2_compare,
     typename ...all_types> class type_compare
    : public type_search<type_2_search, all_types...>
{
};

template<typename type_2_search,
     typename ...all_types>
class type_compare<type_2_search, type_2_search, all_types...>
    : public std::true_type {};

template<typename type_2_search>
class type_search<type_2_search> : public std::false_type {};

template<typename type_2_search, typename first_type, typename ...all_types>
class type_search<type_2_search, first_type, all_types...> :
    public type_compare<type_2_search, first_type, all_types...>
{
};

// add_2_bag_if_type_in_tuple adds the type to tuple_bag
//
// The third template parameter is a tuple_bag
//
// If the 2nd template parameter is true, add the first parameter to the
// bag of types, otherwise the bag of types is unchanged.

template<typename type, bool value, typename tuple_bag>
class add_2_bag_if_type_in_tuple;

template<typename type, typename tuple_bag>
class add_2_bag_if_type_in_tuple<type, false, tuple_bag> {
 public:

    typedef tuple_bag type_t;
};

template<typename type, typename ...types>
class add_2_bag_if_type_in_tuple<type, true, std::tuple<types...>> {
 public:

    typedef std::tuple<type, types...> type_t;
};

/////////


template<typename tuple1_types,
     typename tuple2_types> class compute_intersection;

template<typename ...tuple2_types>
class compute_intersection<std::tuple<>,
               std::tuple<tuple2_types...>> {
public:

    typedef std::tuple<> type_t;
};

template<typename tuple1_type,
     typename ...tuple1_types, typename ...tuple2_types>
class compute_intersection<std::tuple<tuple1_type, tuple1_types...>,
               std::tuple<tuple2_types...>> {
public:

    typedef typename compute_intersection<std::tuple<tuple1_types...>,
                          std::tuple<tuple2_types...>>
        ::type_t previous_bag_t;

    typedef typename add_2_bag_if_type_in_tuple<
        tuple1_type,
        type_search<tuple1_type, tuple2_types...>::value,
        previous_bag_t>::type_t type_t;
};

int main()
{
    // Test case: no intersection

    typedef compute_intersection<std::tuple<int>, std::tuple<char>>::type_t
        one_type;

    std::tuple<> one=one_type();

    // Test case: one of the types intersect

    typedef compute_intersection<std::tuple<int, char>,
                     std::tuple<char, double>>::type_t
        two_type;

    std::tuple<char> two = two_type();

    // Test case, two types intersect, but in different order:

    typedef compute_intersection<std::tuple<int, char, int *>,
                     std::tuple<int *, char, double>>::type_t
        three_type;

    std::tuple<char, int *> three = three_type();
}

Answer 3

The answer from @m.s. does not work if one type that is returned is not default constructible. This is due to the fact that make_intersection try to create the resulting tuple before we get the return type.

We can avoid this by working only on types:

#include <tuple>
#include <type_traits>

// ##############################################
// from https://stackoverflow.com/a/25958302/678093
// (c++17 version)
template <typename T, typename Tuple>
struct has_type;

template <typename T, typename... Us>
struct has_type<T, std::tuple<Us...>>
    : std::disjunction<std::is_same<T, Us>...> {};

// ##############################################

template <typename... Ts>
using tuple_cat_t =
    decltype(std::tuple_cat(std::declval<Ts>()...));

template <typename S1, typename S2> struct intersect {
    template <typename>
    struct build_intersection;
    template <std::size_t... Indices>
    struct build_intersection<std::index_sequence<Indices...>> {
        using type = tuple_cat_t<
           std::conditional_t<
                has_type<std::tuple_element_t<Indices, S1>, S2>::value,
                std::tuple<std::tuple_element_t<Indices, S1>>, std::tuple<>

               >...>;
    };

    using type = typename build_intersection<
        std::make_index_sequence<std::tuple_size<S1>::value>>::type;
};

struct T1{};
struct T2{
  T2(int) {};
};
struct T3{};
using A = std::tuple<T1, T2>;
using B = std::tuple<T2, T3>;

int main()
{
   static_assert(std::is_same<std::tuple<T2>, intersect<A, B>::type>::value, "");
}