Compile-time C++ function to check whether all template argument types are unique

Question

There is a nice question (Which substitution failures are not allowed in requires clauses?) proposing the next problem.

One needs to write a compile-time function template<typename... Ts> constexpr bool allTypesUnique() that will return true if all argument types are unique, and false otherwise. And the restriction is not to compare the argument types pairwise. Unfortunately, the answer only explains why such function cannot be implemented with some particular approach.

I think the solution can be achieved using multiple inheritance. The idea is to make a class inherited from a number of classes: one for each type T in Ts. And each such class defines a virtual function with a signature depending on T. If some T is found more than once in Ts then function f in a child class will override the function in a base class and it can be detected:

template<typename> struct A{};

template<typename T, typename... Ts>
struct B : B<Ts...> {
    using B<Ts...>::f;
    constexpr virtual void f(A<T>, bool & unique) { if( ++count > 1 ) unique = false; }
    int count = 0;
};

template<typename T>
struct B<T> {
    constexpr virtual void f(A<T>, bool & unique) { if( ++count > 1 ) unique = false; }
    int count = 0;
};

template<typename... Ts>
constexpr bool allTypesUnique() {
    B<Ts...> b;
    bool res = true;
    ( b.f( A<Ts>{}, res ), ... );
    return res;
}

int main() {
    static_assert( allTypesUnique<void>() );
    static_assert( allTypesUnique<void, int&>() );
    static_assert( !allTypesUnique<int&, int&>() );
    static_assert( allTypesUnique<char, short, int>() );
    static_assert( !allTypesUnique<char, short, char>() );
}

Demo: https://gcc.godbolt.org/z/8jhnE7P11

Just curious, is the solution correct and is there a simpler solution for this problem?

Answer 1

A single constexpr function can be constructed to answer this question:

template <class T, class... Ts>
constexpr bool unique_types()
{
    if constexpr (sizeof...(Ts)) {
        return !(std::is_same_v<T,Ts> || ...) && unique_types<Ts...>();
    }
    return true;
}

Demo

the code above is the compile time equivalent of

for (int i(0); i < n; ++i)
  for (int j(i + 1); j < n; ++j)
    { /* check type[i] vs type[j] */ }

If you want any variation in comparison (e.g. consider int same as int&) just modify the std::is_same_v (e.g. std::is_same_v<std::decay_t<T>, std::decay_t<Ts>>)

Answer 2

I think you can try to elaborate on using compile-time type ids. Here is a partly implemented C++14 version (compile-time sorting is required):

#include <cstddef>
#include <type_traits>
#include <utility>

namespace detail {
    template<typename T>
    struct type_id {
        constexpr static int value{};
    };

    template<const int *const A, const int *const B>
    struct same_address : std::false_type {};

    template<const int *const A>
    struct same_address<A, A> : std::true_type {};

}// namespace detail

// TODO: implement
template<const int *const... I>
struct sort_array {
    using type = std::integer_sequence<const int *const, I...>;
};

template<typename>
struct find_duplicates;

template<const int *const A, const int *const B, const int *const... I>
struct find_duplicates<std::integer_sequence<const int *const, A, B, I...>> {
    constexpr static bool value = std::conditional_t<detail::same_address<A, B>::value,
                                                     std::true_type,
                                                     find_duplicates<std::integer_sequence<const int *const, B, I...>>>::value;
};

template<>
struct find_duplicates<std::integer_sequence<const int *const>> {
    constexpr static bool value = false;
};

template<const int *const I>
struct find_duplicates<std::integer_sequence<const int *const, I>> {
    constexpr static bool value = false;
};

template<typename... T>
constexpr bool all_types_unique() {
    return !find_duplicates<typename sort_array<&detail::type_id<T>::value...>::type>::value;
};

int main() {
    static_assert(detail::same_address<&detail::type_id<int>::value,
                                       &detail::type_id<int>::value>::value,
                  "");
    static_assert(!detail::same_address<&detail::type_id<int>::value,
                                        &detail::type_id<double>::value>::value,
                  "");

    static_assert(all_types_unique<>(), "");
    static_assert(all_types_unique<int>(), "");
    static_assert(all_types_unique<int, double>(), "");
    static_assert(all_types_unique<int, double, char>(), "");
    static_assert(!all_types_unique<int, int>(), "");
    static_assert(!all_types_unique<int, int, int>(), "");

    return 0;
}

https://godbolt.org/z/E4G6YchE5

Answer 3

A simpler solution can be obtained in compilers supporting class size optimization via C++20 attribute [[no_unique_address]] for empty members. If all class empty members have distinct types, then its sizeof will be 1. If some member types are repeating then they cannot share the same address and sizeof will be more than 1.

Solution code:

template<typename> struct A{};

template<typename T, typename... Ts>
struct B : B<Ts...> {
    [[no_unique_address]] A<T> a;
};

template<typename T>
struct B<T> {
    [[no_unique_address]] A<T> a;
};

template<typename... Ts>
constexpr bool allTypesUnique() {
    if constexpr (sizeof...(Ts) <= 1 )
        return true;
    else
        return sizeof(B<Ts...>) == 1;
}

int main() {
    static_assert( allTypesUnique<void>() );
    static_assert( allTypesUnique<void, int&>() );
    static_assert( !allTypesUnique<int&, int&>() );
    static_assert( allTypesUnique<char, short, int>() );
    static_assert( !allTypesUnique<char, short, char>() );
}

Demo: https://gcc.godbolt.org/z/577EP1774

Answer 4

If you use virtual base classes depending on each of the given types, you will get exact one base class instance for every unique type in the resulting class. If the number of given types is the number of generated base classes, each type was unique. You can "measure" the number of generated base classes by its size but must take care that you have a vtable pointer inside which size is implementation dependent. As this, each generated type should be big enough to hide alignment problems.

BTW: It works also for reference types.

template < typename T> struct AnyT { char i[128]; };

template < typename FIRST, typename ... T>
struct CheckT: virtual AnyT<FIRST>, virtual CheckT<T...> { };

template < typename FIRST >
struct CheckT<FIRST>: virtual AnyT<FIRST> {};


template < typename ... T>
constexpr bool allTypesUnique()
{
    using T1 = CheckT<int>;
    using T2 = CheckT<bool, int>;

    constexpr std::size_t s1 = sizeof( T1 );
    constexpr std::size_t s2 = sizeof( T2 );
    constexpr std::size_t diff = s2 - s1; 
    constexpr std::size_t base = s1 - diff;
    constexpr std::size_t measure = sizeof( CheckT< T...> );

    return !((sizeof...(T)*diff+base) - measure);
}


int main() {
    static_assert( allTypesUnique<void>() );
    static_assert( allTypesUnique<void, int>() );
    static_assert( !allTypesUnique<void, void>() );
    static_assert( allTypesUnique<char, short, int>() );
    static_assert( !allTypesUnique<char, short, char>() );
}

Demo