Best concept to check that all types in a parameter pack are unique

I am trying to find the most efficient and clear way to define a C++20 concept to check that all types in a parameter pack are unique.

So far I have managed to do it like this (code excerpt):

template <size_t N, typename... Ts>
// recovers N-th typename from a parameter pack
using get_Nth_type = typename std::tuple_element_t<N, std::tuple<Ts...>>;

template <size_t N, typename... Ts>
// recovers N-th value of a corresponding type from a parameter pack
constexpr get_Nth_type<N, Ts...> get_Nth_value(Ts&&... values) { return std::get<N>(std::forward_as_tuple(std::forward<Ts>(values)...)); }

template<typename... Ts>
// concept is valid when all types in a parameter pack are the same
concept all_same = (std::same_as<get_Nth_type<0, Ts...>, Ts> and ...);

static_assert(all_same<int, float, float>); // fail
static_assert(all_same<float, float, float>); // OK

template <typename T, typename... Ts>
// concept is valid when a type T is among types in a parameter pack Ts
concept any_of = (std::same_as<T, Ts> or ...);

template<size_t N, typename... Ts, int... Js>
// compile-time boolean is true when N-th type in a parameter pack is equal to any other type in the pack
constexpr bool any_same_as_Nth_helper(std::integer_sequence<int, Js...>) { return ((Js != N && std::same_as<get_Nth_type<N, Ts...>, Ts>) or ...); }

template<size_t N, typename... Ts>
// concept is valid when N-th type in a parameter pack is equal to any other type in the pack
concept any_same_as_Nth = (any_same_as_Nth_helper<N, Ts...>(std::make_integer_sequence<int, sizeof...(Ts)>()));

static_assert(any_same_as_Nth<0, int, float, float>); // fail
static_assert(any_same_as_Nth<1, int, float, float>); // OK

template<typename... Ts, int... Is>
// compile-time boolean is true is valid when any type in a parameter pack Ts contains a duplicate
constexpr bool any_same_helper(std::integer_sequence<int, Is...>) { return ((any_same_as_Nth<Is, Ts...>) or ...); }

template<typename... Ts>
// concept is valid when all types in a parameter pack are unique
concept all_unique = (not any_same_helper<Ts...>(std::make_integer_sequence<int, sizeof...(Ts)>()));

static_assert(all_unique<int, float, int>); // fail
static_assert(all_unique<float, float, int>); // fail
static_assert(all_unique<int, float, double>); // OK

This works, but I am not sure about its efficiency for large packs, since it tests every possible pair from the parameter pack (with O(N^2) complexity).

Could anybody show me how to implement the same concept with, e.g., O(N log(N)) complexity - maybe using a binary tree search?

Starting with a base that looks like this:

#include <cstddef>

template<typename T>
constexpr const void* constexpr_typeid = &constexpr_typeid<T>;

template<typename... T>
concept all_unique = []{
    std::array<const void*, sizeof...(T)> tinfo = { constexpr_typeid<T>... };
    for (std::size_t i = 0; i < sizeof...(T); ++i) {
        for (std::size_t j = i+1u; j < sizeof...(T); ++j) {
            if (tinfo[i] == tinfo[j])
                return false;
        }
    }
    return true;
}();

Which is already a lot more readable. To get an O(n lg n) solution from this, we need to be able to order the types at compile time.

Using something from How to order types at compile-time?

#include <cstddef>
#include <algorithm>
#include <array>

#if defined __GNUC__
#define CONSTEXPR_TYPE_ID_ORDERED true
template<typename T>
constexpr const char* get_string_with_type() {
    return __PRETTY_FUNCTION__;
}

template<typename T>
constexpr const char* constexpr_typeid = get_string_with_type<T>();
using constexpr_typeid_type = const char*;
#else
#define CONSTEXPR_TYPE_ID_ORDERED false
template<typename T>
constexpr const void* constexpr_typeid = &constexpr_typeid<T>;
using constexpr_typeid_type = const void*;
#endif


template<typename... T>
concept all_unique = []{
    std::array<constexpr_typeid_type, sizeof...(T)> tinfo = { constexpr_typeid<T>... };
#if CONSTEXPR_TYPE_ID_ORDERED
    std::ranges::sort(tinfo, [](const char* l, const char* r) -> bool {
        return __builtin_strcmp(l, r) < 0;
    });
    return std::ranges::adjacent_find(tinfo) == tinfo.end();
#else
    for (std::size_t i = 0; i < sizeof...(T); ++i) {
        for (std::size_t j = i+1u; j < sizeof...(T); ++j) {
            if (tinfo[i] == tinfo[j])
                return false;
        }
    }
    return true;
#endif
}();

static_assert(!all_unique<int, float, int>);
static_assert(!all_unique<float, float, int>);
static_assert(all_unique<int, float, double>);
static_assert(all_unique<>);

(std::ranges::sort did not seem to work during constant evaluation with the Microsoft STL, so that uses the O(n^2) algorithm)

I find O(n×log n) too restrictive for this purpose. Associating parameter pack elements with indice normally involves complications that lead to elongated compile times. C++26 is about to introduce pack index operator(pack...[n]), but I doubt it is helpful in regards with present question. If the OP lifts complexity constraint from the question, I can provide a simpler O(n²) implementation:

template<typename occurrence,typename ... sample>
constexpr auto find_type_index = []{
    std::array test{ not std::same_as<sample, occurrence>..., false };
    return std::ranges::size(test
         | std::views::take_while(std::identity{}));
}(/*IILE*/);

template<typename ... sample>
constexpr auto duplicate_count = []{
    std::array<bool, sizeof...(sample)> test{};
    ((test[find_type_index<sample,sample...>] = true), ...);
    return std::ranges::count(test,false);
}(/*IILE*/);

template<typename occurrence,typename ... sample>
concept any_of = find_type_index<occurrence,sample...> < sizeof...(sample);

template<typename ... sample>
concept all_unique = 0 == duplicate_count<sample...>;

For all_same I use the fastest implementation:

template<typename sample0, typename ... sample>
concept all_same = ((std::same_as<sample0, sample>) and ...);

Edit:

I am undecided about the complexity of:

template<typename sample0, typename ... sample>
concept all_same = std::same_as<
     void(std::type_identity<sample0>, std::type_identity<sample>...),
     void(std::type_identity<sample>..., std::type_identity<sample0>)>;

It involves one type comparison, but the compared types are complicated. This is copied from implementation of std::conjunction before introduction of C++17 fold expressions.

template<class T, std::size_t I>
struct type_index {};

template<class Indexes, class...Ts>
struct type_indexes;
template<std::size_t...Is, class...Ts>
struct type_indexes< std::index_sequence<Is...>, Ts... >:
  type_index<Ts, Is>...
{};

template<class...Ts>
using get_type_indexes = type_indexes<std::make_index_sequence<sizeof...(Ts)>, Ts...>;

get_type_indexes<Ts...> returns a type that inherits from type_index<T0, 0> through type_index<Tn, n>. We can now check for conflicts.

template<class T, std::size_t N>
constexpr std::integral_constant<std::size_t, N> index_of_type( type_index<T, N> const& ) { return {}; }

template<class...Ts>
constexpr auto no_dupes(get_type_indexes<Ts...> indexes)->decltype(
  (index_of_type<Ts>(indexes) + ...), std::integral_constant<bool, true>{}
) { return {}; }

template<class...Args>
constexpr std::integral_constant<bool, false> no_dupes(Args&&...) { return {}; }

now, no_dupes( get_type_indexes<Ts...>{} ) returns true iff there are no duplicates in Ts....

How efficient this is depends on how efficient your compilers overload resolution mechanics are.

Things we can measure:

1. The total symbol size generated by this is linear in the number of types.
2. #Ts function call overload resolutions occur; base classes must be considered, and there are #Ts base classes, only 1+#Conflicts of which match.

This technique is similar to how I have seen std::tuple been implemented, so it is plausible that this kind of lookup is is optimized by compilers to be faster than a linear naive search.