Compare two sets of types for equality

Question

How can one check if two parameter packs are the same, ignoring their internal order?

So far I only have the frame (using std::tuple), but no functionality.

#include <tuple>
#include <type_traits>

template <typename, typename>
struct type_set_eq : std::false_type
{
};

template <typename ... Types1, typename ... Types2>
struct type_set_eq<std::tuple<Types1...>, std::tuple<Types2...>>
    : std::true_type
{
    // Should only be true_type if the sets of types are equal
};

int main() {
    using t1 = std::tuple<int, double>;
    using t2 = std::tuple<double, int>;
    using t3 = std::tuple<int, double, char>;

    static_assert(type_set_eq<t1, t1>::value, "err");
    static_assert(type_set_eq<t1, t2>::value, "err");
    static_assert(!type_set_eq<t1, t3>::value, "err");
}

Every type is not allowed to occur more than once in a set.

Answer 1

With C++17 we can use fold expressions to solve this fairly simply:

template <typename T, typename... Rest>
constexpr bool is_one_of_v = (std::is_same_v<T, Rest> || ...);

// Given:
// typename... Types1, typename... Types2
constexpr bool is_same_set_v = 
    // |{Types1...}| == |{Types2...}| and {Types1...} subset of {Types2...}:
    sizeof...(Types1) == sizeof...(Types2)
    && (is_one_of_v<Types1, Types2...> && ...);

// Alternative if you want to allow repeated set elements; more mathematical:
constexpr bool is_same_set_v = 
    // {Types1...} subset of {Types2...} and vice versa.
    (is_one_of_v<Types1, Types2...> && ...)
    && (is_one_of_v<Types2, Types1...> && ...);

Backporting to C++14 is straightforward:

template <bool...> struct bools {};

template <bool... Vs>
constexpr bool all_of_v = std::is_same<bools<true, Vs...>, bools<Vs..., true>>::value;

template <bool... Vs>
constexpr bool any_of_v = !all_of_v<!Vs...>;

template <typename T, typename... Rest>
constexpr bool is_one_of_v = any_of_v<std::is_same<T, Rest>::value...>;

// Given:
// typename... Types1, typename... Types2
constexpr bool is_same_set_v = 
    // |{Types1...}| == |{Types2...}| and {Types1...} subset of {Types2...}:
    sizeof...(Types1) == sizeof...(Types2)
    && all_of_v<is_one_of_v<Types1, Types2...>...>;

// Alternative if you want to allow repeated set elements; more mathematical:
constexpr bool is_same_set_v = 
    // {Types1...} subset of {Types2...} and vice versa.
    all_of_v<is_one_of_v<Types1, Types2...>...>
    && all_of_v<is_one_of_v<Types2, Types1...>...>;

Downgrading to C++11 can be done by changing these template variables to go through a struct, like so:

template <bool... Vs>
struct all_of {
    static constexpr bool value =
        std::is_same<bools<true, Vs...>, bools<Vs..., true>>::value;
};

Answer 2

If types in tuples are unique you could make use of inheritance to answer if all types from the first tuple are involved as a base of the helper struct. E.g. (C++11 approach):

#include <tuple>
#include <type_traits>

template <class T>
struct tag { };

template <class... Ts>
struct type_set_eq_helper: tag<Ts>... { };

template <class, class, class = void>
struct type_set_eq: std::false_type { };

template <bool...>
struct bool_pack { };

template <bool... Bs>
using my_and = std::is_same<bool_pack<Bs..., true>, bool_pack<true, Bs...>>;

template <class... Ts1, class... Ts2>
struct type_set_eq<std::tuple<Ts1...>, std::tuple<Ts2...>, typename std::enable_if< (sizeof...(Ts1) == sizeof...(Ts2)) && my_and< std::is_base_of<tag<Ts2>, type_set_eq_helper<Ts1...>>::value...  >::value  >::type  >:
   std::true_type { };

int main() {
    using t1 = std::tuple<int, double>;
    using t2 = std::tuple<double, int>;
    using t3 = std::tuple<int, double, char>;

    static_assert(type_set_eq<t1, t1>::value, "err");
    static_assert(type_set_eq<t1, t2>::value, "err");
    static_assert(!type_set_eq<t1, t3>::value, "err");
}

[Live demo]

Answer 3

It is not perfectly clear if OP wants to care of number of occurrences (like subject suggests - "unordered list", or not - like type_set_eq suggests.

So, I will present both variants.

---

Starting from set - number of occurrences not important, then the algorithm is as follows:

1. For each type from T1 check if it is present in T2
2. For each type from T2 check if it is present in T1

Both points are important - because when checking only point 1 - we have counterexample of empty T1 list that would be equal to anything and, of course, the same counterexample for point 2 (the points are symmetric).

To check presence of one type in some list of types - use this simple class template:

template <typename V, typename ...T> struct is_present;

template <typename V> // <- type is not present in empty list
struct is_present<V> : std::false_type {};

template <typename V, typename F, typename ...T> 
struct is_present<V,F,T...> : std::integral_constant<bool,
// type is present in non-empty list
// if it is first element
std::is_same<V,F>::value 
//  or it is present in the remaining list-but-first
|| is_present<V,T...>::value> {};

Since we are in pre-C++17 era - then fold expression are not yet available, so something like this below is necessary to represent fold-and:

template <bool ...v> struct all_trues;
template <> struct all_trues<> : std::true_type {};
template <bool f, bool ...v> struct all_trues<f,v...> : 
    std::integral_constant<bool, 
                           f && all_trues<v...>::value> 
{};

Then definition of comparing for equality of two set of types is as follow:

template <typename ...T1>
struct are_set_of_types 
{
    template <typename ...T2> 
    struct equal_to : all_trues<is_present<T1, T2...>::value...,  /*1*/
                                is_present<T2, T1...>::value...>  /*2*/
   {};

};

It can be done with std::tuple as OP started to implement, in this way:

template <typename T1, typename T2>
struct type_set_eq;
template <typename ...T1, typename ...T2>
struct type_set_eq<std::tuple<T1...>, std::tuple<T2...>> 
      : are_set_of_types <T1...>::template equal_to<T2...> 
{};

---

When number of occurrences matters, then algorithm is as follow:

1. Check that sizes of both sequences are equal
2. Check that occurrence number of each value from left sequence is equal to number of occurrences of this value in second sequence

These 2 points should guarantee that sequences are equal without regards to order of elements.

So, the difference from set-comparison is in this class template:

template <typename V, typename ...T>
struct count_occurences;

template <typename V> 
// number of occurrences in empty list is 0
struct count_occurences<V> : std::integral_constant<std::size_t, 0u> {};

template <typename V, typename F, typename ...T> 
// number of occurrences in non-empty list is 
struct count_occurences<V,F,T...> : std::integral_constant<std::size_t, 
// 1 if type is same as first type (or 0 otherwise)
(std::is_same<V,F>::value ? 1u : 0u) 
// plus number of occurrences in remaining list
+ count_occurences<V,T...>::value> {};

And the template to check two sequences equality w/o regards to order:

template <typename ...T1>
struct are_unordered_types_sequences 
{
    // when number of occurrences is important
    template <typename ...T2> 
    struct equal_to : all_trues<
            /*1*/ sizeof...(T1) == sizeof...(T2), 
            /*2*/ (count_occurences<T1, T1...>::value == count_occurences<T1, T2...>::value)...>
   {};
};

And tuple variant:

template <typename T1, typename T2>
struct type_set_eq;
template <typename ...T1, typename ...T2>
struct type_set_eq<std::tuple<T1...>, std::tuple<T2...>> 
      : are_unordered_types_sequences<T1...>::template equal_to<T2...> 
{};

---

Wandbox example I used to play with these templates

Answer 4

Boost.Hana solution:

constexpr auto t1 = hana::tuple_t<int, double>;
constexpr auto t2 = hana::tuple_t<double, int>;
constexpr auto t3 = hana::tuple_t<int, double, char>;

auto same = [](auto a, auto b)
{
    auto to_occurrences_map = [](auto t)
    {
        return hana::fold(t, hana::make_map(), [](auto m, auto x)
        { 
            if constexpr(!hana::contains(decltype(m){}, x)) 
            { 
                return hana::insert(m, hana::make_pair(x, 1)); 
            }
            else { return ++(m[x]); }
        });
    };

    return to_occurrences_map(a) == to_occurrences_map(b);
};

static_assert(same(t1, t1));
static_assert(same(t1, t2));
static_assert(!same(t1, t3));

live wandbox example

Answer 5

Certainly not the best solution, but we can just go one type at a time and see if it's in the other list. If we don't find it, they're not equal. If we do, repeat with the two smaller lists:

template <class A, class B>
struct type_set_eq : std::false_type { };

// base case: two empty packs are equal
template <>
struct type_set_eq<std::tuple<>, std::tuple<>> : std::true_type { };

template <class Lhs, class Done, class Rhs>
struct type_set_eq_impl;

// at least one element in each - we use the middle type to keep track 
// of all the types we've gone through from the Ys
template <class X, class... Xs, class... Ds, class Y, class... Ys>
struct type_set_eq_impl<std::tuple<X, Xs...>, std::tuple<Ds...>, std::tuple<Y, Ys...>>
    : std::conditional_t<
        std::is_same<X,Y>::value,
        type_set_eq<std::tuple<Xs...>, std::tuple<Ds..., Ys...>>,
        type_set_eq_impl<std::tuple<X, Xs...>, std::tuple<Ds..., Y>, std::tuple<Ys...>>>
{ };

// if we run out, we know it's false
template <class X, class... Xs, class... Ds>
struct type_set_eq_impl<std::tuple<X, Xs...>, std::tuple<Ds...>, std::tuple<>>
    : std::false_type
{ };

template <class... Xs, class... Ys>
struct type_set_eq<std::tuple<Xs...>, std::tuple<Ys...>>
    : std::conditional_t<
        (sizeof...(Xs) == sizeof...(Ys)),
        type_set_eq_impl<std::tuple<Xs...>, std::tuple<>, std::tuple<Ys...>>,
        std::false_type>
{ };

// shortcut to true
template <class... Xs>
struct type_set_eq<std::tuple<Xs...>, std::tuple<Xs...>>
    : std::true_type 
{ };