检查参数包中的所有类型是否唯一的最佳概念

Question

我正在尝试找到最有效、最清晰的方法来定义 C++20 概念，以检查参数包中的所有类型是否唯一。

到目前为止，我已经设法这样做了（代码摘录）：

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

这可行，但我不确定它对于大型包的效率，因为它测试参数包中每个可能的对（复杂度为 O(N^2)）。

任何人都可以告诉我如何实现相同的概念，例如 O(N log(N)) 复杂度 - 也许使用二叉树搜索？

Answer 1

简单：

template<typename... Ts>
class inheritor : public std::type_identity<Ts>... {};

template<typename... Ts>
// concept is valid when all types in a parameter pack are different
concept all_different = requires ( inheritor<Ts...> i ) { i, true; };

Answer 2

从看起来像这样的底座开始：

#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;
}();

这已经更具可读性了。为了从中获得 O(n lg n) 解决方案，我们需要能够在编译时对类型进行排序。

使用如何在编译时排序类型？

#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

在使用 Microsoft STL 进行持续评估期间似乎不起作用，因此使用 O(n^2) 算法）