如何实现高效的C++20 Concept以检查参数包类型全唯一？

问题背景 #

我正在寻找一种高效且清晰的方式定义C++20 Concept，用于检查参数包中的所有类型是否唯一。目前已实现了一个可行版本，但它会检查每一对类型，时间复杂度为O(N²)，在处理大型参数包时效率不足。现有实现代码如下：

template <size_t N, typename... Ts>
// 从参数包中提取第N个类型
using get_Nth_type = typename std::tuple_element_t<N, std::tuple<Ts...>>;

template <size_t N, typename... Ts>
// 从参数包中提取第N个值
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 all_same = (std::same_as<get_Nth_type<0, Ts...>, Ts> and ...);

static_assert(all_same<int, float, float>); // 断言失败
static_assert(all_same<float, float, float>); // 断言通过

template <typename T, typename... Ts>
// 检查类型T是否存在于参数包Ts中
concept any_of = (std::same_as<T, Ts> or ...);

template<size_t N, typename... Ts, int... Js>
// 编译期函数：检查第N个类型是否与包中其他类型重复
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：第N个类型是否与包中其他类型重复
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>); // 断言失败
static_assert(any_same_as_Nth<1, int, float, float>); // 断言通过

template<typename... Ts, int... Is>
// 编译期函数：检查参数包中是否存在重复类型
constexpr bool any_same_helper(std::integer_sequence<int, Is...>) { return ((any_same_as_Nth<Is, Ts...>) or ...); }

template<typename... Ts>
// Concept：参数包中所有类型是否唯一
concept all_unique = (not any_same_helper<Ts...>(std::make_integer_sequence<int, sizeof...(Ts)>()));

static_assert(all_unique<int, float, int>); // 断言失败
static_assert(all_unique<float, float, int>); // 断言失败
static_assert(all_unique<int, float, double>); // 断言通过

O(N logN)复杂度的实现方案 #

要实现O(N logN)的复杂度，可以通过编译期排序参数包类型，再检查相邻类型是否重复的思路完成：排序的时间复杂度为O(N logN)，后续线性检查相邻元素为O(N)，整体复杂度由排序主导。

实现代码 #

#include <type_traits>
#include <tuple>
#include <typeindex>

// 辅助：获取元组的尾部（移除第一个元素）
template <typename T, typename... Ts>
constexpr auto tail(std::tuple<T, Ts...>) noexcept {
    return std::tuple<Ts...>{};
}

// 自定义跨平台类型比较函数：基于type_index的哈希值排序
template <typename T, typename U>
constexpr bool type_less() noexcept {
    return std::type_index(typeid(T)).hash_code() < std::type_index(typeid(U)).hash_code();
}

// 辅助：合并两个已排序的类型元组
template <typename... Lhs, typename... Rhs>
constexpr auto merge_sorted(std::tuple<Lhs...> lhs, std::tuple<Rhs...> rhs) noexcept {
    if constexpr (sizeof...(Lhs) == 0) {
        return rhs;
    } else if constexpr (sizeof...(Rhs) == 0) {
        return lhs;
    } else {
        using FirstLhs = std::tuple_element_t<0, std::tuple<Lhs...>>;
        using FirstRhs = std::tuple_element_t<0, std::tuple<Rhs...>>;

        // 提前检测重复，终止合并
        if constexpr (std::is_same_v<FirstLhs, FirstRhs>) {
            return std::tuple<FirstLhs, FirstRhs>{};
        }
        else if constexpr (type_less<FirstLhs, FirstRhs>()) {
            return std::tuple_cat(std::tuple<FirstLhs>{}, merge_sorted(tail(lhs), rhs));
        } else {
            return std::tuple_cat(std::tuple<FirstRhs>{}, merge_sorted(lhs, tail(rhs)));
        }
    }
}

// 辅助：将参数包拆分为左右两部分的元组
template <typename... Ts, size_t... LeftIs, size_t... RightIs>
constexpr auto split_pack(std::index_sequence<LeftIs...>, std::index_sequence<RightIs...>) noexcept {
    constexpr size_t mid = sizeof...(Ts) / 2;
    return std::pair{
        std::tuple<std::tuple_element_t<LeftIs, std::tuple<Ts...>>...>{},
        std::tuple<std::tuple_element_t<mid + RightIs, std::tuple<Ts...>>...>{}
    };
}

// 辅助：归并排序类型参数包
template <typename... Ts>
constexpr auto sort_types() noexcept {
    if constexpr (sizeof...(Ts) <= 1) {
        return std::tuple<Ts...>{};
    } else {
        constexpr size_t mid = sizeof...(Ts) / 2;
        auto [left, right] = split_pack<Ts...>(
            std::make_index_sequence<mid>{},
            std::make_index_sequence<sizeof...(Ts) - mid>{}
        );
        return merge_sorted(sort_types_from_tuple(left), sort_types_from_tuple(right));
    }
}

// 适配元组的排序入口
template <typename Tuple>
constexpr auto sort_types_from_tuple(Tuple) noexcept {
    return []<typename... Ts>(std::tuple<Ts...>) {
        return sort_types<Ts...>();
    }(Tuple{});
}

// 辅助：检查排序后的元组是否存在相邻重复类型
template <typename Tuple>
constexpr bool has_adjacent_duplicates(Tuple) noexcept {
    return []<typename... Ts>(std::tuple<Ts...> t) {
        if constexpr (sizeof...(Ts) <= 1) {
            return false;
        } else {
            using First = std::tuple_element_t<0, decltype(t)>;
            using Second = std::tuple_element_t<1, decltype(t)>;
            if constexpr (std::is_same_v<First, Second>) {
                return true;
            } else {
                return has_adjacent_duplicates(tail(t));
            }
        }
    }(Tuple{});
}

// 最终的all_unique Concept
template <typename... Ts>
concept all_unique = !has_adjacent_duplicates(sort_types<Ts...>());

// 测试用例
static_assert(all_unique<int, float, double, char>); // 无重复，通过
static_assert(!all_unique<int, float, int, double>); // 存在重复，断言失败
static_assert(!all_unique<float, float, int>); // 存在重复，断言失败
static_assert(all_unique<>); // 空参数包，通过
static_assert(all_unique<int>); // 单个类型，通过

核心思路说明 #

1. 归并排序类型：通过编译期递归将参数包拆分为左右两部分，分别排序后合并，归并排序的时间复杂度为O(N logN)，避免了O(N²)的两两比较。
2. 提前终止合并：合并已排序列表时，若发现相同类型则直接返回包含重复的元组，后续检查会直接判定为存在重复，减少不必要计算。
3. 相邻重复检查：排序完成后，线性遍历检查相邻类型是否相同，时间复杂度为O(N)，整体复杂度由排序主导为O(N logN)。

内容的提问来源于stack exchange，提问作者vrbadev