如何在编译时对类型排序？模板元编程实现元组类型归一化问询

当然可以用C++模板元编程实现这个编译期类型排序的需求！我来给你拆解思路并提供一个可运行的实现示例。

核心思路 #

要让元素相同但顺序不同的tuple最终变成同一类型，我们需要在编译期完成三个关键步骤：

1. 从原tuple中提取所有唯一类型并统计每个类型的出现次数
2. 对这些唯一类型按照某个严格弱序规则进行排序（规则只要固定即可，不影响最终唯一性）
3. 将排序后的类型按原次数展开，生成最终的tuple类型

完整实现代码 #

#include <tuple>
#include <type_traits>

// 编译期类型ID生成器（依赖编译器扩展__COUNTER__，GCC/Clang/MSVC均支持）
// 为每个不同类型分配唯一的编译期整数ID
template <typename T>
struct type_id {
    static constexpr int value = __COUNTER__;
};

// 类型比较规则：按类型ID的大小排序，保证严格弱序
template <typename T, typename U>
struct type_less {
    static constexpr bool value = type_id<T>::value < type_id<U>::value;
};

// 统计单个类型在类型列表中的出现次数
template <typename T, typename... Ts>
struct count_occurrences : std::integral_constant<std::size_t, (std::is_same_v<T, Ts> + ...)> {};

template <typename T, typename... Ts>
constexpr std::size_t count_occurrences_v = count_occurrences<T, Ts...>::value;

// 从类型列表中去重，得到唯一类型的tuple
template <typename... Ts>
struct unique_types;

template <typename T, typename... Ts>
struct unique_types<T, Ts...> {
    using type = std::conditional_t<
        (std::is_same_v<T, Ts> || ...),
        typename unique_types<Ts...>::type,
        decltype(std::tuple_cat(std::declval<std::tuple<T>>(), std::declval<typename unique_types<Ts...>::type>()))
    >;
};

template <>
struct unique_types<> {
    using type = std::tuple<>;
};

template <typename... Ts>
using unique_types_t = typename unique_types<Ts...>::type;

// 将单个类型插入到已排序的类型tuple中
template <typename T, typename SortedTuple, typename Less>
struct insert_into_sorted;

template <typename T, typename Less>
struct insert_into_sorted<T, std::tuple<>, Less> {
    using type = std::tuple<T>;
};

template <typename T, typename U, typename... Us, typename Less>
struct insert_into_sorted<T, std::tuple<U, Us...>, Less> {
    using type = std::conditional_t<
        Less::template value<T, U>,
        std::tuple<T, U, Us...>,
        decltype(std::tuple_cat(std::declval<std::tuple<U>>(), std::declval<typename insert_into_sorted<T, std::tuple<Us...>, Less>::type>()))
    >;
};

template <typename T, typename SortedTuple, typename Less>
using insert_into_sorted_t = typename insert_into_sorted<T, SortedTuple, Less>::type;

// 对类型tuple进行编译期插入排序
template <typename Tuple, typename Less>
struct sort_types;

template <typename Less>
struct sort_types<std::tuple<>, Less> {
    using type = std::tuple<>;
};

template <typename T, typename... Ts, typename Less>
struct sort_types<std::tuple<T, Ts...>, Less> {
    using type = insert_into_sorted_t<T, typename sort_types<std::tuple<Ts...>, Less>::type, Less>;
};

template <typename Tuple, typename Less>
using sort_types_t = typename sort_types<Tuple, Less>::type;

// 将单个类型重复N次，生成对应的tuple
template <typename T, std::size_t N>
struct repeat_type;

template <typename T>
struct repeat_type<T, 0> {
    using type = std::tuple<>;
};

template <typename T>
struct repeat_type<T, 1> {
    using type = std::tuple<T>;
};

template <typename T, std::size_t N>
struct repeat_type {
    using type = decltype(std::tuple_cat(std::declval<std::tuple<T>>(), std::declval<typename repeat_type<T, N-1>::type>()));
};

template <typename T, std::size_t N>
using repeat_type_t = typename repeat_type<T, N>::type;

// 将排序后的唯一类型按原次数展开，生成最终tuple
template <typename SortedUniqueTuple, typename OriginalTuple>
struct expand_repeated_types;

template <typename OriginalTuple>
struct expand_repeated_types<std::tuple<>, OriginalTuple> {
    using type = std::tuple<>;
};

template <typename T, typename... Ts, typename... Us>
struct expand_repeated_types<std::tuple<T, Ts...>, std::tuple<Us...>> {
    using type = decltype(std::tuple_cat(
        std::declval<repeat_type_t<T, count_occurrences_v<T, Us...>>>(),
        std::declval<typename expand_repeated_types<std::tuple<Ts...>, std::tuple<Us...>>::type>()
    ));
};

template <typename SortedUniqueTuple, typename OriginalTuple>
using expand_repeated_types_t = typename expand_repeated_types<SortedUniqueTuple, OriginalTuple>::type;

// 最终的ordered工具：输入tuple，返回排序后的唯一tuple类型
template <typename Tuple>
struct ordered;

template <typename... Ts>
struct ordered<std::tuple<Ts...>> {
private:
    using unique_types = unique_types_t<Ts...>;
    using sorted_unique_types = sort_types_t<unique_types, type_less>;
public:
    using type = expand_repeated_types_t<sorted_unique_types, std::tuple<Ts...>>;
};

template <typename Tuple>
using ordered_t = typename ordered<Tuple>::type;

测试验证 #

我们可以用两个元素相同但顺序不同的tuple来验证效果：

// 两个元素相同但顺序不同的tuple
using Tuple1 = std::tuple<int, double, int, char>;
using Tuple2 = std::tuple<char, double, int, int>;

// 生成排序后的类型
using OrderedTuple1 = ordered_t<Tuple1>;
using OrderedTuple2 = ordered_t<Tuple2>;

// 编译期断言：两个排序后的类型必须完全相同
static_assert(std::is_same_v<OrderedTuple1, OrderedTuple2>, "Ordered tuples should be identical!");

自定义排序规则 #

如果你不想用类型ID排序，也可以替换type_less的逻辑，比如按类型大小+对齐方式排序：

template <typename T, typename U>
struct type_less_by_size_alignment {
    static constexpr bool value = sizeof(T) != sizeof(U) 
        ? sizeof(T) < sizeof(U) 
        : alignof(T) < alignof(U);
};

只需要在ordered结构体中把sort_types_t的第二个参数换成这个新的比较规则即可。

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