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.

Feisty

Which constraint is more important to you, time or memory? Are you allowed to modify the sequence? – Flesher

One possible (slow) approach: pop x from the first tuple, look for x in the second tuple and remove if it found. Repeat until the first tuple is empty or until you don't find x in the second one. – Hako

Even more awesome: the function could also "return" (i.e. define a second typedef) of an integer sequence that allows remaping the first tuple onto the second. That would allow constructing one tuple type from the other if they're an exact match, which sounds like a possible end-application of this question. – Horsley

If get<T> was SFINAE friendly, there would be a neater solution. – Ora

Is <int,int,float> equal to <float,int>? I mean, do you want to ignore not only order or values but also their number of occurences? – Woken

What do you mean by "unique types" in the new title? Needs more clarification. – Decoteau

Answer 1

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]

Oneidaoneil

Nice solution, especially the idea with the 'tag-ellipsis' – Danit

The multiset example doesn't work. It considers tuple<int> to be equal to tuple<int, int>. – Decoteau

@Decoteau well it really depends on the definition of equality. Yes I assumed tuple<int> is equal to tuple<int, int> and the behaviour here is expected (by me). I will try to adjust the approach to your assumption that it isn't... – Oneidaoneil

@Oneidaoneil That's now how multisets define equality. – Decoteau

@Decoteau so your suggesting that I should change the wording in my answer or that I should find another solution?... – Oneidaoneil

Thank you very much. This is exactly what I was looking for. Especially the fact that it works without C++14. – Feisty

@TobiasHermann Glad it helped... If you don't mind I will amend the solution if I'd find efficient solution to fulfil the equality of multisets. – Oneidaoneil

Sure, go for it. :) – Feisty

Answer 2

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

Hako

@akappa: and I'm strongly confident it could be a lot prettier, just need to spend some more time on it :) – Hako

wondering why same and to_occurences_map aren't marked as constexpr? Is the compiler figuring it out on its own? – Khartoum

@akappa: in C++17 lambdas are implicitly constexpr if they can be. – Hako

@akappa: nope, but it wouldn't take much to make it work with C++14. Just replace the if constexpr with a similar static branching facility (hana provides one) and use decltype(lambda()){} where appropriate to get a constant expression out of a non-constexpr lambda's return value. – Hako

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

Woken

The size of the lists is irrelevant, because they represent a set, i.e. duplication should not change semantics. – Ora

@Ora Well, you can only guess thatr from this OP // should only be true_type if the sets of types are equal comment. Anyway - I'll ask. – Woken

No, I'm not guessing. If the OP wanted a multiset, he would've called it that. Just bluntly assuming he wants multiset behavior is a bad default. – Ora

@Ora I do not agree: "compare two unordered type lists for equality " - comparing two unordered lists (not sets) w/o regards to internal order is well known operation and it does not mean that number of occurrences does not matter – Woken

Fair enough (I haven't read the question thoroughly, just extrapolated from the name of his template). However, I also haven't downvoted your answer, I was just raising a point. – Ora

Btw. "should only be true_type if the sets of types are equal" directly contradicts your quote. Asking is justified. – Ora

Answer 4

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 
{ };

Decoteau

Answer 5

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;
};

Baryram