C++ 的类型排序

0.前言

在 C++ 中，我编写了一个 tuple-like 模板，这个模板能容纳任意多且可重复的类型：

template<typename... Ts>
struct TypeList {};// usage:
using List1 = TypeList<int, double, char, double>;
using List2 = TypeList<>;

因为 C++ 的模板系统是图灵完备的，所以我可以判断某个类型是否存在某个列表中：

#include <type_traits>template<typename T, typename TpList>
struct Belong;
template<typename T>
struct Belong<T, TypeList<>> : std::false_type {};
template<typename T, typename Head, typename... Tail>
struct Belong<T, TypeList<Head, Tail...>>: std::conditional<std::is_same<T, Head>::value, std::true_type, Belong<T, TypeList<Tail...>>>::type {};static_assert( Belong<int, TypeList<double, void, int>>::value, "true" );
static_assert( !Belong<long long, TypeList<double, void, int>>::value, "false" );

类似的，我也可以为这个 TypeList 添加一系列用于增删查改的模板：

// 在一个 TypeList 首部插入一个元素
template<typename TpList, typename T>
struct PushFront;
template<typename TpList, typename T>
using PushFront_t = typename PushFront<TpList, T>::type;template<typename... Ts, typename T>
struct PushFront<TypeList<Ts...>, T> {using type = TypeList<T, Ts...>;
};// 提取第 I 个类型
template<std::size_t Pos, typename... Ts>
struct TypeAt {static_assert( static_cast<bool>( Pos < sizeof...( Ts ) ), "Position overflow" );
};
template<std::size_t Pos, typename... Ts>
using TypeAt_t = typename TypeAt<Pos, Ts...>::type;
// C++26 后可以用 Ts...[Pos] 取代这里的递归遍历template<std::size_t Pos, typename T, typename... Ts>
struct TypeAt<Pos, T, Ts...> : TypeAt<Pos - 1, Ts...> {};
template<typename T, typename... Ts>
struct TypeAt<0, T, Ts...> {using type = T;
};

很显然，因为 TypeList 是一个线性容器，从中查找某个元素时需要从头遍历整个列表。

但可以注意到：当我们使用 std::is_base_of 检查某个类型是否是一个类型的基类时，这个操作的结果可以经由类型协变直接返回，所以我们可以据此编写一个 TypeSet：

template<typename... Ts>
struct TypeSet : TypeList<Ts>... {};
// 这里用 TypeList 包一下，是因为类似 int、double 的基本数据类型不允许被继承template<typename T, typename TpSet>
struct Exist;
template<typename T, typename... Ts>
struct Exist<T, TypeSet<Ts...>> : std::is_base_of<TypeList<T>, TypeSet<Ts...>> {};static_assert( Exist<char, TypeSet<double, char, float>>::value, "true" );
static_assert( !Exist<int, TypeSet<double, char, float>>::value, "false" );

C++ 不允许在多继承中重复继承多个相同的基类，所以如果 TypeSet 包含了重复元素就会直接触发一次编译硬错误。

不幸的是，这个硬错误无法被运用在 SFINAE 中，以检查多个类型列表是否包含重复元素。

在不涉及模板实例化的场景下使用一个明显包含重复元素的 TypeSet 并不会立即导致编译错误，

只有抵达了 std::is_base_of 之类需要展开继承关系的场景才会触发，

这种错误不能被 SFINAE 忽略，因为这个错误是由模板实例化尝试导致的。

而且因为不能使用 SFINAE 拒绝重复元素模板，所以如果想从 TypeList 构造一个 TypeSet，就需要提前检查前者是否包含重复元素。

一个朴素的查重实现可以由递归遍历操作得到：

template<typename TpList>
struct Duplicated;
template<>
struct Duplicated<TypeList<>> : std::false_type {};
template<typename Head, typename... Tail>
struct Duplicated<TypeList<Head, Tail...>>: std::conditional<Belong<Head, TypeList<Tail...>>::value, std::true_type, Duplicated<TypeList<Tail...>>>::type {};

这个实现过于朴素，以至于它的复杂度达到了 $O(n^2)$。

正常来说，如果想要有一个更优的复杂度实现，我们会首先排序待查找集合中的所有元素，然后线性查找重复的相邻元素，这能做到 $O(n\log n+n)$。

那么我们能否对 C++ 的类型进行排序？

1.指针标记

只要我们能给每一个类型赋予一个可比较的类型 ID，那么自然的，整个类型集合就是可以被排序的。

虽然在 C++ 里，只要是重载了比较运算符的类型都可以被比较，但因为我们要对类型进行运算，所以我们要把这个操作限定在编译期。

编译期可用的类型包括算术类型和指针类型，很容易想到的是，我们可以使用一个指向某个实例化模板的指针实现类型 ID：

using ID = typename std::add_pointer<void() noexcept>::type;template<typename T>
struct TypeID {
private:static constexpr void id() noexcept {}public:static constexpr ID value = &id;
};template<ID... Is>
struct IDList {};using IDs = IDList<TypeID<int>::value, TypeID<double>::value>;

很不幸的是，在尝试使用这种方法时，编译器（或者说标准）会抱怨：对指针的偏序比较操作不属于编译期常量表达式。

error: '(TypeID<int>::id < TypeID<double>::id)' is not a constant expression| constexpr bool value = TypeID<int>::value < TypeID<double>::value;|                        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

不过判等比较是没问题的。

出现这种错误的主要原因在于：执行比较时我们还处在编译期，代码生成没有完全结束，此时拿到的指针值纯粹是一个不可比较的类型标记，就和类型本身一样。

相同的，对指针做类似 reinterpret_cast 的转换也不属于一个编译期表达式。

指针这条路走不通，那么我们只能将目标转移到整数类型上了。

在下一节前，特别需要指出的是：

尽管 typeid() 产生的 std::type_info 类型提供了一个返回整数的 hash_code() 方法，

但 std::type_info 对象的生成会（被故意）延迟到运行期，所以 hash_code() 也不属于一个常量表达式。

2.整数标记

在 GCC、Clang 和 MSVC 中，编译器为我们提供了以下两个特殊的扩展宏：

// GCC、Clang：
__PRETTY_FUNCTION__// MSVC：
__FUNCSIG__

这两个宏的作用是以字符数组的形式返回当前函数的名称。

与 C++ 标准的 __func__ 变量不同，这两个宏带有更多与函数参数类型有关的信息，而我们可以借助它附带的类型信息将每一个类型映射为独一无二的整数值。

#include <iostream>template<typename T>
void foo()
{
#if defined( _MSC_VER )std::cout << __FUNCSIG__ << std::endl;
#elsestd::cout << __PRETTY_FUNCTION__ << std::endl;
#endif
}int main()
{foo<int>();foo<double>();foo<std::string>();
}

上述代码的输出为：

// gcc:
void foo() [with T = int]
void foo() [with T = double]
void foo() [with T = std::__cxx11::basic_string<char>]// clang:
void foo() [T = int]
void foo() [T = double]
void foo() [T = std::basic_string<char>]// msvc:
void __cdecl foo<int>(void)
void __cdecl foo<double>(void)
void __cdecl foo<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >>(void)

在 C++20 中，标准库引入了一个名为 std::source_location 的组件，这个组件可以在一定程度上获取当前源码上下文的信息。

特别是 std::source_location::function_name() 方法，标准称这个方法会返回一个由实现而异的、能表示当前函数名称的字符串，这个方法在 GCC、Clang 和 MSVC 上的实现与上述两个宏是相同的。

所以在 GCC、Clang、MSVC，亦或者 C++20 之后的 C++ 环境下，我们可以利用函数名字符串为每个类型计算得到一个独特 ID：

#include <cstdint>
#if defined( __cpp_lib_source_location )
# include <source_location>
#endif#if defined( __cpp_lib_source_location ) || defined( __GNUC__ ) || defined( __clang__ ) || defined( _MSC_VER )
using ID = std::uint64_t;template<typename T>
struct TypeID {
private:static constexpr ID avalanche( ID hash ) noexcept{ // 进行后处理是因为 fnv1a 对尾部字符差异不敏感，而 GCC 和 Clang 的函数字符串差异主要体现在尾部return ( ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull )^ ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull ) >> 33 ) )* 0xC4CEB9FE1A85EC53ull )^ ( ( ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull )^ ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull ) >> 33 ) )* 0xC4CEB9FE1A85EC53ull )>> 33 );}static constexpr ID fnv1a( const char* type_name, ID hash = 14695981039346656037ull ) noexcept{ // 因为函数签名是固定的，变动的只有模板参数名，所以这里也可以简单地累加 type_name 中的每个字符// 虽然累加得到的整数值会比较接近return *type_name == '\0'? avalanche( hash ): fnv1a( type_name + 1, ( hash ^ static_cast<ID>( *type_name ) ) * 1099511628211ull );}template<typename U>static constexpr ID id() noexcept{
# if defined( __cpp_lib_source_location )const auto location = std::source_location::current();return fnv1a( location.function_name() );
# elif defined( _MSC_VER )return fnv1a( __FUNCSIG__ );
# elsereturn fnv1a( __PRETTY_FUNCTION__ );
# endif}public:static constexpr ID value = id<typename std::remove_cv<typename std::remove_reference<T>::type>::type>();
};
#endif

现在我们拥有了将不同类型映射为一个唯一的整数 ID 的方法：

#include <iostream>int main()
{std::cout << TypeID<int>::value << std::endl<< TypeID<double>::value << std::endl<< TypeID<TypeID<int>>::value << std::endl<< TypeID<std::string>::value << std::endl<< TypeID<std::ostream>::value << std::endl;
}

以上代码的输出见此。

3.类型排序

因为类型是可以通过 std::is_same 直接判等的，所以我们可以直接排序一个 TypeList 而不需要单独创建 IDList。

排序算法可以随便选择一个，我用的是归并排序：

template<typename TpList>
struct Split;
template<typename TpList>
using Split_l = typename Split<TpList>::left;
template<typename TpList>
using Split_r = typename Split<TpList>::right;template<>
struct Split<TypeList<>> {using left  = TypeList<>;using right = TypeList<>;
};
template<typename T, typename... Ts>
struct Split<TypeList<T, Ts...>> {
private:static constexpr std::size_t N = 1 + sizeof...( Ts );static constexpr std::size_t H = N / 2;template<std::size_t... I>static constexpr TypeList<TypeAt_t<I, T, Ts...>...> make_first( std::index_sequence<I...> );template<std::size_t... I>static constexpr TypeList<TypeAt_t<I + H, T, Ts...>...> make_second( std::index_sequence<I...> );public:using left  = decltype( make_first( std::make_index_sequence<H> {} ) );using right = decltype( make_second( std::make_index_sequence<N - H> {} ) );
};template<typename TpList>
struct MergeSort;
template<typename TpList>
using MergeSort_t = typename MergeSort<TpList>::type;template<>
struct MergeSort<TypeList<>> {using type = TypeList<>;
};
template<typename T>
struct MergeSort<TypeList<T>> {using type = TypeList<T>;
};
template<typename... Ts>
struct MergeSort<TypeList<Ts...>> {
private:template<typename LeftList, typename RightList>struct Conquer;template<typename LeftList, typename RightList>using Conquer_t = typename Conquer<LeftList, RightList>::type;template<typename... Us>struct Conquer<TypeList<>, TypeList<Us...>> {using type = TypeList<Us...>;};template<typename... Us>struct Conquer<TypeList<Us...>, TypeList<>> {using type = TypeList<Us...>;};// 因为是按哈希 ID 排序，所以这里升降序没有意义，也就不提供模板谓词了template<typename U, typename... Us, typename V, typename... Vs>struct Conquer<TypeList<U, Us...>, TypeList<V, Vs...>>: std::conditional<( TypeID<U>::value < TypeID<V>::value ),PushFront<Conquer_t<TypeList<Us...>, TypeList<V, Vs...>>, U>,PushFront<Conquer_t<TypeList<U, Us...>, TypeList<Vs...>>, V>>::type {};public:using type =Conquer_t<MergeSort_t<Split_l<TypeList<Ts...>>>, MergeSort_t<Split_r<TypeList<Ts...>>>>;
};using List       = TypeList<char, unsigned char, double, int, float>;
using SortedList = MergeSort_t<TypeList<char, unsigned char, double, int, float>>;// 一般来说两个列表元素顺序是不同的，但这取决于具体的编译器实现
static_assert( !std::is_same<List, SortedList>::value, "false" );

4.类型查重

经过排序后的 TypeList 中，重复的元素（类型）会位于相邻的位置上，所以查重模板 Duplicated 可以简化为以下的线性查找实现：

template<typename TpList>
struct Duplicated;
template<>
struct Duplicated<TypeList<>> : std::false_type {};
template<typename TpList>
struct Duplicated {
private:template<typename Types>struct Helper;template<typename T>struct Helper<TypeList<T>> : std::false_type {};template<typename T1, typename T2, typename... Ts>struct Helper<TypeList<T1, T2, Ts...>>: std::conditional<std::is_same<T1, T2>::value, std::true_type, Helper<TypeList<T2, Ts...>>>::type {};public:static constexpr bool value = Helper<MergeSort_t<TpList>>::value;
};

现在可以用它检查一个 TypeList 是否包含重复元素，并且能否转换为一个 TypeSet 了。

static_assert( !Duplicated<TypeList<int, double, short, char>>::value, "false" );
static_assert( Duplicated<TypeList<int, double, int, float>>::value, "true" );

5.兼容性处理

由于 TypeID 基于特定的编译器宏、亦或者 C++20 的 std::srouce_location 实现了类型哈希，所以以上代码只适用于使用 GCC、Clang、MSVC 或者 C++20 的环境；在这些环境之外，只能提供一个朴素实现的 fallback。

实际上，如果能通过静态反射拿到一些可以排序的类型元数据的话，这里的实现可以更简单。

所以wo静态反射ne？

完整的类型查重实现代码为：

#include <cstdint>
#if defined( __cpp_lib_source_location )
# include <source_location>
#endif#if defined( __cpp_lib_source_location ) || defined( __GNUC__ ) || defined( __clang__ ) || defined( _MSC_VER )
using ID = std::uint64_t;template<typename T>
struct TypeID {
private:static constexpr ID avalanche( ID hash ) noexcept{return ( ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull )^ ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull ) >> 33 ) )* 0xC4CEB9FE1A85EC53ull )^ ( ( ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull )^ ( ( ( hash ^ ( hash >> 33 ) ) * 0xFF51AFD7ED558CCDull ) >> 33 ) )* 0xC4CEB9FE1A85EC53ull )>> 33 );}static constexpr ID fnv1a( const char* type_name, ID hash = 14695981039346656037ull ) noexcept{ // 因为函数签名是固定的，变动的只有模板参数名，所以这里也可以简单地累加 type_name 中的每个字符// 虽然累加得到的整数值会比较接近return *type_name == '\0'? avalanche( hash ): fnv1a( type_name + 1, ( hash ^ static_cast<ID>( *type_name ) ) * 1099511628211ull );}template<typename U>static constexpr ID id() noexcept{
# if defined( __cpp_lib_source_location )const auto location = std::source_location::current();return fnv1a( location.function_name() );
# elif defined( _MSC_VER )return fnv1a( __FUNCSIG__ );
# elsereturn fnv1a( __PRETTY_FUNCTION__ );
# endif}public:static constexpr ID value = id<typename std::remove_cv<typename std::remove_reference<T>::type>::type>();
};template<typename TpList>
struct Split;
template<typename TpList>
using Split_l = typename Split<TpList>::left;
template<typename TpList>
using Split_r = typename Split<TpList>::right;template<>
struct Split<TypeList<>> {using left  = TypeList<>;using right = TypeList<>;
};
template<typename T, typename... Ts>
struct Split<TypeList<T, Ts...>> {
private:static constexpr std::size_t N = 1 + sizeof...( Ts );static constexpr std::size_t H = N / 2;template<std::size_t... I>static constexpr TypeList<TypeAt_t<I, T, Ts...>...> make_first( std::index_sequence<I...> );template<std::size_t... I>static constexpr TypeList<TypeAt_t<I + H, T, Ts...>...> make_second( std::index_sequence<I...> );public:using left  = decltype( make_first( std::make_index_sequence<H> {} ) );using right = decltype( make_second( std::make_index_sequence<N - H> {} ) );
};template<typename TpList>
struct MergeSort;
template<typename TpList>
using MergeSort_t = typename MergeSort<TpList>::type;template<>
struct MergeSort<TypeList<>> {using type = TypeList<>;
};
template<typename T>
struct MergeSort<TypeList<T>> {using type = TypeList<T>;
};
template<typename... Ts>
struct MergeSort<TypeList<Ts...>> {
private:template<typename LeftList, typename RightList>struct Conquer;template<typename LeftList, typename RightList>using Conquer_t = typename Conquer<LeftList, RightList>::type;template<typename... Us>struct Conquer<TypeList<>, TypeList<Us...>> {using type = TypeList<Us...>;};template<typename... Us>struct Conquer<TypeList<Us...>, TypeList<>> {using type = TypeList<Us...>;};template<typename U, typename... Us, typename V, typename... Vs>struct Conquer<TypeList<U, Us...>, TypeList<V, Vs...>>: std::conditional<( TypeID<U>::value < TypeID<V>::value ),PushFront<Conquer_t<TypeList<Us...>, TypeList<V, Vs...>>, U>,PushFront<Conquer_t<TypeList<U, Us...>, TypeList<Vs...>>, V>>::type {};public:using type =Conquer_t<MergeSort_t<Split_l<TypeList<Ts...>>>, MergeSort_t<Split_r<TypeList<Ts...>>>>;
};template<typename TpList>
struct Duplicated;
template<>
struct Duplicated<TypeList<>> : std::false_type {};
template<typename TpList>
struct Duplicated {
private:template<typename Types>struct Helper;template<typename T>struct Helper<TypeList<T>> : std::false_type {};template<typename T1, typename T2, typename... Ts>struct Helper<TypeList<T1, T2, Ts...>>: std::conditional<std::is_same<T1, T2>::value, std::true_type, Helper<TypeList<T2, Ts...>>>::type {};public:static constexpr bool value = Helper<MergeSort_t<TpList>>::value;
};
#else
template<typename TpList>
struct Duplicated;
template<>
struct Duplicated<TypeList<>> : std::false_type {};
template<typename Head, typename... Tail>
struct Duplicated<TypeList<Head, Tail...>>: std::conditional<Belong<Head, TypeList<Tail...>>::value, std::true_type, Duplicated<TypeList<Tail...>>>::type {};
#endif

6.总结展望

实际上，由于我们已经实现了一个排序算法，所以只要有一个能够表示不同类型之间偏序关系的谓词，就可以将这个排序操作作用在任何概念上。

为此我们需要泛化一下先前的归并排序模板：

template<typename TpList, template<typename, typename> class Cmp>
struct MergeSort;
template<typename TpList, template<typename, typename> class Cmp>
using MergeSort_t = typename MergeSort<TpList, Cmp>::type;template<template<typename, typename> class Cmp>
struct MergeSort<TypeList<>, Cmp> {using type = TypeList<>;
};
template<typename T, template<typename, typename> class Cmp>
struct MergeSort<TypeList<T>, Cmp> {using type = TypeList<T>;
};
template<typename... Ts, template<typename, typename> class Cmp>
struct MergeSort<TypeList<Ts...>, Cmp> {
private:template<typename LeftList, typename RightList>struct Conquer;template<typename LeftList, typename RightList>using Conquer_t = typename Conquer<LeftList, RightList>::type;template<typename... Us>struct Conquer<TypeList<>, TypeList<Us...>> {using type = TypeList<Us...>;};template<typename... Us>struct Conquer<TypeList<Us...>, TypeList<>> {using type = TypeList<Us...>;};template<typename U, typename... Us, typename V, typename... Vs>struct Conquer<TypeList<U, Us...>, TypeList<V, Vs...>>: std::conditional<Cmp<U, V>::value,PushFront<Conquer_t<TypeList<Us...>, TypeList<V, Vs...>>, U>,PushFront<Conquer_t<TypeList<U, Us...>, TypeList<Vs...>>, V>>::type {};public:using type =Conquer_t<MergeSort_t<Split_l<TypeList<Ts...>>, Cmp>, MergeSort_t<Split_r<TypeList<Ts...>>, Cmp>>;
};

然后添加一个谓词模板：

// 按 ID 升序
template<typename A, typename B>
struct IDLess : std::integral_constant<bool, ( TypeID<A>::value < TypeID<B>::value )> {};

最后修改 Duplicated 的实现：

template<typename TpList>
struct Duplicated;
template<>
struct Duplicated<TypeList<>> : std::false_type {};
template<typename TpList>
struct Duplicated {
private:template<typename Types>struct Helper;template<typename T>struct Helper<TypeList<T>> : std::false_type {};template<typename T1, typename T2, typename... Ts>struct Helper<TypeList<T1, T2, Ts...>>: std::conditional<std::is_same<T1, T2>::value, std::true_type, Helper<TypeList<T2, Ts...>>>::type {};public:static constexpr bool value = Helper<MergeSort_t<TpList, IDLess>>::value;
};

我们已经将谓词模板暴露了出来，所以现在我们还能用这个排序算法实现一些更有意思的操作。

在 C++ 里，struct/class 的成员会受到不同的对齐字节要求，导致最终的 struct/class 类型的大小可能比实际成员大小之和略大；这在 std::tuple 中体现的极为明显：

#include <tuple>using tup = std::tuple<bool, void*, char, int>;
static_assert( sizeof( tup ) != ( sizeof( bool ) + sizeof( void* ) + sizeof( char ) + sizeof( int ) ),"false" );

如果我们定义一个基于类型大小降序的谓词模板，那么就可以利用排序算法重排列 std::tuple 的类型列表：

降序是因为在 std::tuple 的主流实现中，更靠左的类型参数会位于类型成员的“更高处”。

template<typename A, typename B>
struct SizeGreater : std::integral_constant<bool, ( sizeof( A ) > sizeof( B ) )> {};

为了协调 TypeList 和 std::tuple，还需要为它们编写一个类型转换模板：

// 不需要为 std::tuple -> TypeList 编写
// 因为这个类型转换可以利用模板特化匹配完成
template<typename TpList>
struct List2Tuple;
template<typename TpList>
using List2Tuple_t = typename List2Tuple<TpList>;template<typename... Ts>
struct List2Tuple<TypeList<Ts...>> {using type = std::tuple<Ts...>;
};

因为重排 std::tuple 会导致不同类型根据它们的实现大小被调换到不同的位置上，导致通过下标访问成员变得比较没什么意义。

这里可以用上之前的查重模板 Duplicated，确保传入和生成的 std::tuple 不存在重复类型，使得可以仅通过类型就查找到对应成员：

template<typename Tuple>
struct ReorderTuple;
template<typename Tuple>
using ReorderTuple_t = typename ReorderTuple<Tuple>::type;template<typename... Ts>
struct ReorderTuple<std::tuple<Ts...>> {static_assert( !Duplicated<TypeList<Ts...>>::value, "Duplicate types are not allowed" );using type = List2Tuple_t<MergeSort_t<TypeList<Ts...>, SizeGreater>>;
};

简单编写一个 std::tuple 就可以看到结果：

using Tup       = std::tuple<bool, void*, char, long long>;
using Reordered = ReorderTuple_t<Tup>;
static_assert( !std::is_same<Tup, Reordered>::value, "false" );
static_assert( sizeof( Tup ) > sizeof( Reordered ), "false" );

本文使用到的所有代码均可以在此找到。