Compare two multisets of types for equality
As this question doesn't seem to cover all useful cases, I decided to fill the gap with this little question. Is there a way to answer if two multisets of types are equal?
#include <tuple>
#include <type_traits>
template <typename, typename>
struct type_multiset_eq : std::false_type
{
};
template <typename ... Types1, typename ... Types2>
struct type_multiset_eq<std::tuple<Types1...>, std::tuple<Types2...>>
: std::true_type
{
// Should only be true_type if the multisets of types are equal
};
int main() {
static_assert(type_multiset_eq<std::tuple<char, int, double, float, int, float>, std::tuple<float, char, int, double, int, float>>::value, "err");
static_assert(!type_multiset_eq<std::tuple<char, int, double, float, int, float>, std::tuple<char, int, double, int, float>>::value, "err");
static_assert(type_multiset_eq<std::tuple<char, char, char, float, float, float>, std::tuple<char, float, char, float, char, float>>::value, "err");
static_assert(!type_multiset_eq<std::tuple<int, int>, std::tuple<int, int, int>>::value, "err");
}
+3
source to share
4 answers
Interest Ask...
Inspiring your answer (well ... copying it) in the original question ( type_set_eq
one), adding a type counter ( countT
) and removing the helper and tag structure, I suppose you can just write something like this
#include <tuple>
#include <type_traits>
template <typename ...>
struct countT;
template <typename T>
struct countT<T>
{ static constexpr std::size_t value { 0U }; };
template <typename T, typename T0, typename ... Ts>
struct countT<T, T0, Ts...>
{ static constexpr std::size_t value { countT<T, Ts...>::value }; };
template <typename T, typename ... Ts>
struct countT<T, T, Ts...>
{ static constexpr std::size_t value { 1U + countT<T, Ts...>::value }; };
template <bool ...>
struct bool_pack
{ };
template <bool ... Bs>
using my_and = std::is_same<bool_pack<Bs..., true>, bool_pack<true, Bs...>>;
template <typename, typename, typename = void>
struct type_multiset_eq : std::false_type
{ };
template <template <typename ...> class C1, typename ... Ts1,
template <typename ...> class C2, typename ... Ts2>
struct type_multiset_eq<C1<Ts1...>, C2<Ts2...>,
typename std::enable_if<
(sizeof...(Ts1) == sizeof...(Ts2))
&& (my_and<( countT<Ts1, Ts1...>::value
== countT<Ts1, Ts2...>::value)...>::value)
>::type>
: std::true_type
{ };
int main()
{
static_assert( type_multiset_eq<
std::tuple<char, int, double, float, int, float>,
std::tuple<float, char, int, double, int, float>>::value, "err");
static_assert( ! type_multiset_eq<
std::tuple<char, int, double, float, int, float>,
std::tuple<char, int, double, int, float>>::value, "err");
static_assert( type_multiset_eq<
std::tuple<char, char, char, float, float, float>,
std::tuple<char, float, char, float, char, float>>::value, "err");
static_assert( ! type_multiset_eq<
std::tuple<int, int>,
std::tuple<int, int, int>>::value, "err");
}
If you can use C ++ 14 you can replace the type attribute with the countT
following functionconstexpr
template <typename T, typename ... Ts>
constexpr std::size_t cntT ()
{
using unused = std::size_t[];
std::size_t ret { 0U };
(void)unused { 0U, ret += (std::is_same<T, Ts>::value ? 1U : 0U)... };
return ret;
}
+1
source to share
In the answer, I focused a bit on efficiency. The method can be divided into four main stages:
- Types of ranks in each package
- Sorting types in packages in the base of a given rank
- Create two sets of unique elements (also types) containing information about types and frequencies from the previous version of packages (inheriting from these types)
- Investigate if another multiset of types arises from the same types (with frequencies)
The approach should be O(N log N)
based on the number of types
C ++ 14:
#include <utility>
#include <array>
template <class T>
constexpr T ilog2(T n) {
return n == static_cast<T>(1) ? static_cast<T>(0) : ilog2(n >> static_cast<T>(1)) + 1;
}
template <class T>
constexpr T ipow2(T n) {
return static_cast<T>(1) << n;
}
template <std::size_t N>
struct s_exp {
static constexpr std::size_t exp = ipow2(ilog2(N-1)+1);
};
template <std::size_t I, class T>
struct itag { };
template <std::size_t D, std::size_t I, class T>
struct vvtag { };
template <std::size_t S, std::size_t I, class T>
struct vtag: virtual vvtag<I/S, (I%S) / ((s_exp<S>::exp + (2 << (I/S)) - 1)/(2 << (I/S))), T> { };
template <class... Ts>
struct pack {
static constexpr std::size_t size = sizeof...(Ts);
};
template <class P, class = std::make_index_sequence<P::size>>
struct ipack;
template <class... Ts, std::size_t... Is>
struct ipack<pack<Ts...>, std::index_sequence<Is...>>: itag<Is, Ts>... {
static constexpr std::size_t size = sizeof...(Ts);
};
template <std::size_t I, class T>
T ipack_element(itag<I, T>);
template <class IP, class = std::make_index_sequence<IP::size * (ilog2(IP::size - 1) + 1) >>
struct vpack;
template <class IP, std::size_t... Is>
struct vpack<IP, std::index_sequence<Is...>>: vtag<IP::size, Is, decltype(ipack_element<Is % IP::size>(IP{}))>... {
static constexpr std::size_t size = IP::size;
};
template <class A, class CompArr>
constexpr int partition(A &a, int lo, int hi, const CompArr &ca) {
int x = a[lo];
int i = lo, j = hi;
while (true) {
while (ca[a[j]] > ca[x])
j--;
while (ca[a[i]] < ca[x])
i++;
if (i < j) {
auto w = a[i];
a[i] = a[j];
a[j] = w;
i++;
j--;
} else
return j;
}
}
template <class A, class CompArr>
constexpr void quicksort(A &a, int lo, int hi, const CompArr &ca) {
if (lo < hi) {
auto q = partition(a, lo, hi, ca);
quicksort(a, lo, q, ca);
quicksort(a, q+1, hi, ca);
}
}
template <class... Ts, std::size_t... Is>
constexpr std::array<std::size_t, sizeof...(Ts)> rank(itag<0, ipack<pack<Ts...>, std::index_sequence<Is...>>>) {
return {{!std::is_base_of<vvtag<0, 0, decltype(ipack_element<Is>(ipack<pack<Ts...>>{}))>, vpack<ipack<pack<Ts...>>>>::value...}};
}
template <std::size_t N, class... Ts, std::size_t... Is>
constexpr std::array<std::size_t, sizeof...(Ts)> rank(itag<N, ipack<pack<Ts...>, std::index_sequence<Is...>>>) {
constexpr auto prev = rank(itag<N - 1, ipack<pack<Ts...>>>{});
return {{prev[Is]*2 + !std::is_base_of<vvtag<N, prev[Is]*2, decltype(ipack_element<Is>(ipack<pack<Ts...>>{}))>, vpack<ipack<pack<Ts...>>>>::value...}};
}
template <class... Ts, std::size_t... Is>
constexpr std::array<std::size_t, sizeof...(Ts)> sort_types_impl(ipack<pack<Ts...>, std::index_sequence<Is...>>) {
constexpr std::size_t TS = sizeof...(Ts);
auto compare_enabler = rank(itag<ilog2(TS - 1), ipack<pack<Ts...>, std::index_sequence<Is...>>>{});
std::size_t result[TS] { Is... };
quicksort(result, 0, sizeof...(Is) - 1, compare_enabler);
return {{ result[Is]... }};
}
template <class>
struct sort_types;
template <class... Ts>
struct sort_types<pack<Ts...>>: sort_types<ipack<pack<Ts...>>> { };
template <class... Ts, std::size_t... Is>
struct sort_types<ipack<pack<Ts...>, std::index_sequence<Is...>>> {
static constexpr auto idxs = sort_types_impl(ipack<pack<Ts...>>{});
using type = pack<decltype(ipack_element<idxs[Is]>(ipack<pack<Ts...>>{}))...>;
};
struct dummy { };
template <class... Ts>
struct unique_pack: Ts... {
static constexpr std::size_t size = sizeof...(Ts);
template <class Up>
constexpr bool operator==(Up) {
bool result = size == Up::size;
bool ibo[sizeof...(Ts)] = { std::is_base_of<Ts, Up>::value... };
for (std::size_t i = 0; i < sizeof...(Ts); i++)
result &= ibo[i];
return result;
}
};
template <class>
struct multiset;
template <class... Ts>
struct multiset<pack<Ts...>>: multiset<ipack<pack<Ts...>>> {};
template <class... Ts, std::size_t... Is>
struct multiset<ipack<pack<Ts...>, std::index_sequence<Is...>>> {
using sorted_pack = typename sort_types<pack<Ts..., dummy>>::type;
static constexpr std::array<bool, sizeof...(Ts)> const unique_types() {
return {{ !std::is_same< decltype(ipack_element<Is>(ipack<sorted_pack>{})), decltype(ipack_element<Is + 1>(ipack<sorted_pack>{})) >::value... }};
}
static constexpr std::size_t unique_count() {
constexpr std::array<bool, sizeof...(Ts)> const ut = unique_types();
std::size_t result = 0;
for (std::size_t i = 0; i < sizeof...(Ts); i++)
result += ut[i];
return result;
}
template <std::size_t... Is2>
static constexpr std::array<std::size_t, unique_count()> const unique_idxs(std::index_sequence<Is2...>) {
std::size_t result[unique_count()] {};
std::size_t cur = 0;
constexpr std::array<bool, sizeof...(Ts)> const ut = unique_types();
for (std::size_t i = 0; i < sizeof...(Ts); i++) {
if (ut[i])
result[cur++] = i;
}
return {{ result[Is2]... }};
}
template <std::size_t... Is2>
static constexpr std::array<std::size_t, unique_count()> const unique_counts(std::index_sequence<Is2...>) {
std::size_t result[unique_count()] {};
std::size_t cur = 0;
constexpr auto ut = unique_types();
for (std::size_t i = 0; i < sizeof...(Ts); i++) {
if (ut[i])
result[cur++]++;
else
result[cur]++;
}
return {{ result[Is2]... }};
}
template <std::size_t... Is2>
static auto make_type(std::index_sequence<Is2...>) {
constexpr std::array<std::size_t, unique_count()> const idxs = unique_idxs(std::index_sequence<Is2...>{});
constexpr std::array<std::size_t, unique_count()> const counts = unique_counts(std::index_sequence<Is2...>{});
return unique_pack<itag<counts[Is2], decltype(ipack_element<idxs[Is2]>(ipack<sorted_pack>{}))>...>{};
}
template <class T = multiset, std::size_t UC = T::unique_count()>
using type = decltype(make_type(std::make_index_sequence<UC>{}));
};
template <class P1, class P2>
constexpr bool multiset_equality(P1, P2) {
return typename multiset<P1>::template type<>{} == typename multiset<P2>::template type<>{} && typename multiset<P2>::template type<>{} == typename multiset<P1>::template type<>{};
}
int main() {
static_assert(multiset_equality(pack<char, int, double, float, int, float>{}, pack<float, char, int, double, int, float>{}),"!");
static_assert(!multiset_equality(pack<char, int, double, float, int, float>{}, pack<char, int, double, int, float>{}),"!");
static_assert(multiset_equality(pack<char, char, char, float, float, float>{}, pack<char, float, char, float, char, float>{}),"!");
static_assert(!multiset_equality(pack<int, int>{}, pack<int, int, int>{}),"!");
}
+2
source to share
You can use the following, it strips off both side types until the first is empty, or the second matches:
template <typename T, typename Tuple, typename Res = std::tuple<>>
struct remove_type_from_tuple;
template <typename T, typename ... Ts, typename ...Res>
struct remove_type_from_tuple<T, std::tuple<T, Ts...>, std::tuple<Res...>>
{
using type = std::tuple<Res..., Ts...>;
};
template <typename T, typename T2, typename ... Ts, typename ...Res>
struct remove_type_from_tuple<T, std::tuple<T2, Ts...>, std::tuple<Res...>>
{
using type = typename remove_type_from_tuple<T,
std::tuple<Ts...>,
std::tuple<Res..., T2>>::type;
};
template <typename T, typename Res>
struct remove_type_from_tuple<T, std::tuple<>, Res>
{
using type = void;
};
template <typename T, typename Res>
struct remove_type_from_tuple<T, void, Res>
{
using type = void;
};
template <typename Tuple1, typename Tuple2>
struct diff_types_from_tuple;
template <typename T, typename ...Ts, typename Tuple>
struct diff_types_from_tuple<std::tuple<T, Ts...>, Tuple>
{
using type =
typename diff_types_from_tuple<std::tuple<Ts...>,
typename remove_type_from_tuple<T, Tuple>::type
>::type;
};
template <typename Tuple>
struct diff_types_from_tuple<std::tuple<>, Tuple>
{
using type = Tuple;
};
template <typename Tuple1, typename Tuple2>
struct type_multiset_eq :
std::is_same<std::tuple<>,
typename diff_types_from_tuple<Tuple1, Tuple2>::type>
{
};
+1
source to share
Just for fun, I suggest another type-counting solution (like the first one) with the same complexity (O (n ^ 2) I suppose) but a little smarter (complete the check on first difference)
#include <tuple>
#include <type_traits>
template <typename ...>
struct countT;
template <typename T>
struct countT<T>
{ static constexpr std::size_t value { 0U }; };
template <typename T, typename T0, typename ... Ts>
struct countT<T, T0, Ts...>
{ static constexpr std::size_t value { countT<T, Ts...>::value }; };
template <typename T, typename ... Ts>
struct countT<T, T, Ts...>
{ static constexpr std::size_t value { 1U + countT<T, Ts...>::value }; };
template <typename, typename, typename>
struct eqCountT;
template <template <typename ...> class C, typename T, typename ... Ts1,
typename ... Ts2, typename ... Ts3>
struct eqCountT<C<T, Ts1...>, C<Ts2...>, C<Ts3...>>
: std::integral_constant<bool,
(countT<T, Ts2...>::value == countT<T, Ts3...>::value)>
{ };
template <template <typename ...> class C, typename T2, typename T3>
struct eqCountT<C<>, T2, T3> : std::true_type
{ };
template <typename T1, typename T2, typename T3,
bool = eqCountT<T1, T2, T3>::value>
struct mseqH;
template <template <typename ...> class C, typename T2, typename T3>
struct mseqH<C<>, T2, T3, true> : std::true_type
{ };
template <typename T1, typename T2, typename T3>
struct mseqH<T1, T2, T3, false> : std::false_type
{ };
template <template <typename ...> class C, typename T, typename ... Ts1,
typename T2, typename T3>
struct mseqH<C<T, Ts1...>, T2, T3, true> : mseqH<C<Ts1...>, T2, T3>
{ };
template <typename, typename>
struct type_multiset_eq;
template <template <typename ...> class C1, typename ... Ts1,
template <typename ...> class C2, typename ... Ts2>
struct type_multiset_eq<C1<Ts1...>, C2<Ts2...>>
: std::integral_constant<bool,
(sizeof...(Ts1) == sizeof...(Ts2))
&& mseqH<C1<Ts1...>, C1<Ts1...>, C1<Ts2...>>::value>
{ };
int main()
{
static_assert( type_multiset_eq<
std::tuple<char, int, double, float, int, float>,
std::tuple<float, char, int, double, int, float>>::value, "err");
static_assert( ! type_multiset_eq<
std::tuple<char, int, double, float, int, float>,
std::tuple<char, int, double, int, float>>::value, "err");
static_assert( type_multiset_eq<
std::tuple<char, char, char, float, float, float>,
std::tuple<char, float, char, float, char, float>>::value, "err");
static_assert( ! type_multiset_eq<
std::tuple<int, int>,
std::tuple<int, int, int>>::value, "err");
}
If you can use C ++ 14 you can replace the type attribute with the countT
following functionconstexpr
template <typename T, typename ... Ts>
constexpr std::size_t cntT ()
{
using unused = std::size_t[];
std::size_t ret { 0U };
(void)unused { 0U, ret += (std::is_same<T, Ts>::value ? 1U : 0U)... };
return ret;
}
+1
source to share