C++20新版本特性—编译时多态

第二章 编译时多态

本章介绍如何使用C++进行编译时多态机制，编译时多态相比于运行时多态，会节省运行时的开销。

2.1 函数重载机制

在C语言中除了static函数以外，不支持同名函数，再加上没有名称空间的概念，因此程序员将多个编译单元链接在一起的时候，若出现同名函数将导致链接重定义错误。通常解决办法是在函数名字前面加上模块的名字作为前缀，来避免名称冲突。在C++中，支持函数重载和命名空间，使得多个同名函数称为可能。

运用这种方式可以使得程序员在编写例如加法函数的时候，操作数可以是字符串，可以使整形，也可以是两个类。但同时，这种方式带来的缺点是引入很复杂的决策机制，用户使用同一个名字，那也就是需要编译器根据上下文来决策需要使用哪一个函数，即编译时多态。若决策失败，将导致名字冲突等编译错误。

考虑如下代码，使用哪个重载版本的feed?

namespace animal
{
	struct Cat {};
	void feed(Cat* foo, int);
};

struct CatLike { CatLike(animal::Cat*); };
void feed(CatLike);

template<typename T>
void feed(T* obj, double);

template<>
void feed(animal::Cat* obj, double d);

int main()
{
	animal::Cat cat;
	feed(&cat, 1); // 使用哪个重载版本？
}

2.1.1 名称查找

决策的第一阶段是进行名称查找，编译器需要在feed(&cat,1);这个点找出所有与feed同名的函数声明和函数模板，通常来说名称查找分三类：

• 成员函数名查找，当使用.或者->进行成员函数调用时，名称查找位于该成员类中的同名函数。
• 限定名称查找，当显式使用限定符::进行函数调用时，例如std::sort，查找std命名空间下的sort函数。
• 未限定名称查找，除了以上两种方式，编译器还可以根据参数依赖查找规则。

上面这个例子就是未限定名称查找，由于实参类型Cat属于animal命名空间，其命名空间的同名函数也会纳入考虑范围，因此编译器会找到三个候选函数。

void feed(Cat* foo, int);
void feed(CatLike);
template<typename T>
void feed(T* obj, double);

相对于另两个候选函数，第一个很容易被程序员忽视，因为我们并没有打开animal的命名空间，但是编译器却将它纳入考虑，这是因为ADL规则发挥了作用。这个规则大大简化了函数调用过程，在操作符重载的场景中，程序员无需显式指定操作符所在的命名空间即可限定调用。

std::cout << "Hello World!" << "n";
std::operator<<(std::operator<<(std::cout,"Hello World!"),"n");

如果不想采用这种规则，可以在函数调用时，将函数名括起来，例如：(feed)(&cat,1)。

我们需要注意的时我们模板特化函数并没有出现在候选集，这是因为名称查找阶段仅考虑普通函数和主模板函数的情况，不会考虑所有特化版本。

2.1.2 模板函数处理

模板函数无法直接调用，需要实例化，这一阶段编译器会进行处理，从而进行推导，将会替换推导后的类型。

template<typename T>
void feed(T* obj, double);

这个模板函数仅一个T，而feed的调用没有显示指明实际的模板参数，因此编译器会根据实参&cat进行推导，得到模板参数T为animal::Cat，接下来进行模板参数替换，得到可调用的模板实例化函数：

void feed<animal::Cat>(animal::Cat*, double);

如果模板参数推导与参数替换的过程失败，则编译器会将该模板函数从候选集中删除。那么，什么情况下模板参数会替换失败呢？考虑如下模板函数：

template<typename T>
void feed(T *obj, typename T::value_type v);

该模板参数的第二个形参类型为typename T::value_type，因为编译器不知道T::value_type是一个静态变量还是一个类型别名，因此需要加上typename来明确告诉编译器这是一个类型。如果写成T::value_type的话，编译器可能认为这是一个成员变量。从C++20起，放松了这方面的要求，但是还是建议加上typename来修饰。

首先，编译器会根据实际调用的情况来进行模板参数替换，如下：

void feed<animal::Cat>(animal::Cat *obj, typename animal::Cat::value_type v);

根据Cat的定义，不存在value_type的成员类型别名，因此该替换失败，但是不会导致编译错误，只是会将该模板函数从候选集中删除。

2.1.3 重载决议

最后一个阶段是重载决议，这个阶段得到的是一系列的模板函数与非模板函数的候选集，回顾一下当前的候选集。

void animal::feed(Cat *foo,int); // #1
void feed(CatLike);              // #2
void feed<animal::Cat>(animal::Cat*, double); // #3

这个阶段可分为两步：规定可行函数集与挑选最佳可行函数。

首先，是从候选集中得到可行函数，根据函数调用的实参与候选函数的形参的数量进行规约得到可行函数集，一个可行函数必须符合如下规则。

1. 如果调用函数有M个实参，那么可行函数必须得有M个形参。
2. 如果候选函数少于M个形参，但最后一个参数是可变形参，则为可行函数。
3. 如果候选函数多于M个形参，但是从第M+1到最后的形参都拥有默认参数，则为可行函数。
4. 从C++20起，如果函数有约束，必须满足约束条件。
5. 可行需要保证每个形参类型即使通过隐式转换后也能与实参类型对的上。

对于第一个候选函数来说，形参和实参类型数量都为两个，并且两个类型完全匹配，那么该候选函数可行。

对于第二个候选函数来说，Cat*需要隐式转换为CatLike，但是该候选函数的参数个数不匹配，因此，该候选函数不可行。

对于第三个候选函数来说，模板实例化后，第一个参数与第一个候选函数一致，第二个参数为double，中间做了一次隐式转换，因此，该候选函数可行。

最后，我们发现，上面的第一个和第三个候选函数都为可行，那么，我们要从中选出最佳可行函数。接下来进入第二步。

// 目前可行函数集
void animal::feed(Cat *foo,int); 
void feed<animal::Cat>(animal::Cat*, double); 

编译器依据每条规则逐条进行两两比较，从而决策出最佳可行函数，否则进入下一条规则。如果所有规则都不满足，那么，会引发编译错误。现如何以下几条比较重要的规则。

1. 形参与实参类型最匹配、转换最少的为最佳可行函数。
2. 非模板函数优于模板函数。
3. 若多于两个模板实例，那么最具体的模板实例最佳。
4. C++20起，若函数拥有约束，则选择约束最强的哪个。

根据第一条规则，我们就可以决策出第一个函数为最佳可行函数，因此选择该函数。

2.1.4 注意事项

根据C++标准，函数重载机制并不将函数的返回类型考虑在内，这是因为，返回类型上的差异无法决定重载决策。尽管函数（操作符）重载机制可以实现编译时多态，但并非所有重载都是为了多态而存在的。大多数情况下是为了提升表达力。

// 让复数可以进行a+b形式的操作
Complex operator+(const Complex& lhs,const Complex& rhs);

// 使vector可以实现vector[5]的操作
template<typename T>
T& vector<T>::operator[](size_t index);

2.1.5 再谈SFINAE

曾经，我们实现过一个declval模板函数，用于在非求值上下文构造对象，从而能够获取类对象的一些特征。

template<typename T>
struct declval_protector
{
	static constexpr bool value = false;
};

template<typename T>
T&& declval()
{
	static_assert( declval_protector<T>::value,
					"declval应该decltype/sizeof等非求值上下文中使用！" );	
}

这个实现没有考虑到注入void等不可引用的类型，从而导致编译错误，而根据C++标准，对于不可引用的类型应该返回其本身。为此，我们希望通过SFINAE机制来补充这个场景。考虑提供declval函数的重载。若类型会引用，则返回类型为该类型的右值引用形式，否则为原类型。

template<typename T>
T declval();
template<typename T,typename U = T&&>
U declval();

根据两个版本，构造出两个用例：

• decltype(declval<void>())的结果为void
• decltype(declval<Point>())的结果为Point&&

首先对于第一个用例，在名称查找阶段，上述两个模板函数的重载都可以成为候选集，那么接下来就是模板函数处理阶段，将模板替换成void，如何获得以下两个模板实例。

void declval<void>();
void&& declval<void,void&&>();

第二个模板实例化之后，存在非法语句void&&，因此，该替换失败，从候选集中删除。

再来看看第二个用例，同样地。先在名称查找阶段，这两个函数都被称为候选集，而在模板函数处理阶段，会产生如下两个模板实例。

Point declval<Point>();
Point&& declval<Point,Point&&>();

这两个实例都合法，因此这个阶段候选集没变化，接下来到了重载决议过程将发生歧义，因为这两个函数只有返回类型上的差异从而无法决策最佳版本，需要为这两个函数添加形参以进行区分，进而得到如下实现。

template<typename T>
T declval(long);
template<typename T,typename U = T&&>
U declval(int);

但是这样要求程序员使用的时候传递一个实参去调用，提供传递int类型的0来调用，那么，在进行决策的时候，因为第二个函数不需要进行隐式转换，从而作为最优。但是，这样有个麻烦时，我们必须再传入一个参数，所有我们对此进行封装。

template<typename T>
T declval_(long);
template<typename T,typename U = T&&>
U declval_(int);

template<typename T>
auto declval() -> decltype(declval_<T>(0))
{
    static_assert( declval_protector<T>::value,
					"declval应该decltype/sizeof等非求值上下文中使用！" );
    return declval_<T>(0); // 避免编译警告
}

2.2 类型特征（Type traits）

C++通过模板来实现泛型变参，从而减轻运行时绑定开销，初看起来效率并不是最高的，因为同样的算法不会在每个数据结构上最优，比如排序链表的算法不同于排序数组的算法，有序的结构要比无序结构搜索的更快。

C++11标准库提供了<type_traits>来解决这类问题，它定义了一些编译时基于模板类的接口用于查询、修改类型的特征：输入的是类型，输出与该类型相关的特征（属性）。

考虑这么一个场景，给定任意类型T，可能是bool类型，也可能是int类型或者自定义得到类型，通过type_traits可以回答一系列问题？这个类型是否是数值类型？是否是函数对象？是不是指针？有没有构造函数？能不能拷贝构造？等待。

除此之外，还能对类型进行转换，比如给定任意类型T，为这个类型添加const修饰符、引用、指针等待。并且都是发生编译时，不会造成运行时的开销。

2.2.1 Type traits谓词与变量模板

标准库提供的type traits谓词命名时is_为前缀，通过访问静态成员常量value得到输出结果。

static_assert(is_integral<int>::value); // true
static_assert(!is_integral<float>::value); // false
static_assert(is_floating_point<double>::value); // true
static_assert(is_class<struct Point>::value); // true
static_assert(!is_same<int,double>::value); // false

根据名字就可以猜测其含义，C++17提供了更简洁的方式来表达is_integral<int>::value，只需要使用is_integral_v<int>。

template <typename _Tp>
inline constexpr bool is_integral_v = is_integral<_Tp>::value;
template <typename _Tp>
inline constexpr bool is_floating_point_v = is_floating_point<_Tp>::value;

使用变量模板的一个好处是提供了更简短的访问方式，这点和类型别名很相似。定义变量模板与定义普通变量很类似，唯一不同的是定义变量模板可以带上模板参数。变量模板可以进行编译时的表达式计算，考虑如下代码。

template<char c>
constexpr bool is_digit = (c >= '0' && c <= '9');

static_assert(!is_digit<'x'>);
static_assert(is_digit<'0'>);

那么，我们如何使用这种方式来实现斐波那契函数，参考如下代码。

template<size_t N>
inline constexpr size_t fibonacci = fibonacci<N - 1> + fibonacci<N - 2>;

template<>
inline constexpr size_t fibonacci<0> = 0;

template<>
inline constexpr size_t fibonacci<1> = 1;


cout << fibonacci<100> << endl;

首先，定义一个基本变量模板fibonacci，并且，创建两个特化版本，当N为1和为0的时候，结果分别为1和0。

2.2.2 类型转换

标准库<type_traits>拥有修改类型的能力，基于已有类型应用修改得到新的类型，输出类型可以通过访问type类型成员得到结果。值得注意的是，不会修改原有输入的类型，而是产生新的类型。

int main()
{
    static_assert(is_same_v<typename remove_const<const int>::type,int>);
    static_assert(is_same_v<typename remove_const<int>::type,int>);
    static_assert(is_same_v<typename add_const<int>::type,const int>);
    static_assert(is_same_v<typename add_pointer<int *>::type,int**>);
    static_assert(is_same_v<typename decay<int[5][6]>::type,int(*)[6]>);
}

像remove_const 和add_const这些，从字面上都能很好理解其作用，但是最后一个decay稍微复杂写，其语义是类型退化，通过模拟函数或值语义传递时，会使所有应用到的函数参数类型退化，由于decay是值语义，因此，引用类型会退化成普通类型。

数组类型之所以能够传递给一个接受指针类型的函数，是因为在这个过程中数组类型发生了退化，变成了指针类型。

数组退化成指针意味着长度信息的丢失，换来的是可以接受任意长度数组的灵活性，而这也导致后续对指针的内存操作存在风险。好在C++20标准库提供了区间类型std::span来同时传递指针与长度信息，考虑如下代码。

void passArrayLike(span<int> container)
{
	cout << "container.size():" << container.size() << endl;
	for (auto elem : container)
		cout << elem << " ";
	cout << endl;
}

int main()
{
	int arr[]{ 1,2,3,4 };
	vector vec{ 1,2,3,4,5 };
	array arr2{ 1,2,3,4,5,6 };

	passArrayLike(arr); // 4
	passArrayLike(vec); // 5
	passArrayLike(arr2); // 6
}

在C++11之后，也对类型变化相关的函数做了简洁处理，typename decay<int[5][6]>::type可以写成decay_t<int[5][6]>即可。

2.2.3 辅助类

标准库<type_traits>预定义了一些常用的辅助类，方便实现其他的type traits。辅助类integral_constant将值与对应的类型包裹起来，从而能够将值转换成类型，也能从类型转换回值，实现值与类型的一一映射关系。

using Two = integral_constant<int, 2>;
using Four = integral_constant<int, 4>;
static_assert(Two::value * Two::value == Four::value);

Two和Four为两个类型，分别对应数值2和4，并且转换之后，可以通过静态成员常量value来获取对应的值。

其实，标准库有很多谓词，其结果都是一个布尔类型，因此标准库也提供了布尔类型的辅助类bool_constant。实现如下。

template<bool v>
using bool_constant = integral_constant<bool,v>;

using true_type = integral_constant<bool,true>;
using false_type = integral_constant<bool,false>;

那么最为基础的integral_constant是如何实现的呢？若输出一个类型与对应的值，根据标准库的约定，用静态成员value来存储。

template<typename T, T v>
struct integral_constant
{
	using type = integral_constant;
	using value_type = T; // 存储值的类型
	static constexpr T value = v; // 对应的值
}

2.2.4 空基类优化

标准库中大量使用继承技术来复用代码而不是表达IsA的关系，并且不使用虚函数来避免运行时的多态开销，这也是STL高效的一个原因。就复用代码而言，与成员组合方式相比，后者只能通过大量委托转调来实现。

C++有些类可能是空的，而这些类实际上它们的大小占用一个字节。

struct Base {};
static_assert(sizeof(Base) == 1);

那么，我们考虑一个场景，通过组合的方式定义Children，那么如下的Children将占用多少内存？

struct Children
{
	Base base; // 1
	int other; // 4
};
static_assert(sizeof(Children) == 8);

这里需要考虑内存对齐的缘故，因此Children的大小为8。但如果对空类采用继承，那么就允许空类基类占用0字节，即空基类优化。故考虑以下代码，最终空类的字节占用为0。

struct Children : Base
{
	int other; // 4
};
static_assert(sizeof(Children) == 4);

那么，空类既然什么都没有，我们为何要考虑呢，我们要知道，像typedef/using这种定义的类型成员和静态数据成员，并不占用内存空间，这些数据是有用的。继承它们的子类将复用这些数据，无需委托。

考虑一下标准库的<vector>容器实现，它的第二个模板参数用于内存分配器，默认std::allocator<T>，可以对::new和::delete进行封装，允许用户自己提供内存分配器，只需要将参数传递给vector的第二参数即可。

由于大多数情况下使用标准库提供的默认内存分配器是无状态的空类，如果使用成员变量的方式存储，至少浪费一个字节，而用户传递的分配器可能是有状态的非空类。如果统一派生自分配器，那么将会享受到空基类优化的效果。

当然也可以使用C++20提供的属性[[no_unique_addree]]来避免这个问题，可以使空类作为成员变量的时候，也能享受空基类优化。

2.2.5 实现Type traits

其实type traits，简单来说就是，它们是一种模板类，使用<>的方式将参数传入进去，再通过其成员来输出结果，我们称这种为元函数。

is_floating_point判断给定的类型是否是浮点类型，我们首先定义一个基本的模板类，然后默认返回为假，只有遇到浮点数时，返回为真，我们采用模板特化来解决这个情况。

template<typename T>
struct is_floating_point : false_type {};

template<>
struct is_floating_point<float> : true_type {};

template<>
struct is_floating_point<double> : true_type {};

template<>
struct is_floating_point<long double> : true_type {};

is_same时判断给定的两个类型是否相同，还是同样的方式，先考虑统一的模板来继承false_type，再考虑其特化版本，那么如果两个类型相同，说明模板参数只有一个，那么我们可以把模板参数为一个作为特化版本继承true_type。

template<typename T,typename U>
struct is_same : false_type {};

template<typename T>
struct is_same<T,T> : true_type {};

那么，以上是实现对错，那么如何实现通过元函数进行输入类型和输出类型呢？

remove_const是将输入的类型去掉const修饰符，首先先考虑一个主模板，接受任意的类型，那么这个类型就是T。我们通过using一个成员来进行输出该类型，那么再考虑特化版本，特化版本其实就是接受带有const的类型，因为只需要对带有const的类型进行处理即可，下面是具体实现。

template<typename T>
struct remove_const {
    using type = T;
};

template<typename T>
struct remove_const<const T> {
    using type = T;
};

那么，在考虑一个复杂一点的，std::conditional类似三元条件操作符，它接受三个模板参数，第一个模板参数为bool类型，是当第一个值为true时，就输出第二个类型，否则输出第三个类型。那么，主模板很简单，就是接受三个类型，默认将第二个参数作为输出类型。然后，其特化版本就是，特化第一个参数为false，然后输出类型为第三个参数。

template<bool v, typename Then, typename Else>
struct conditional {
	using type = Then;
};
	
template<typename Then, typename Else>
struct conditional<false, Then, Else> {
	using type = Else;
};

有了conditional元函数之后，就能实现稍微复杂的type traits了，考虑decay元函数实现使类型退化，那么，我们要考虑什么类型需要做退化：

1. 类型为数组类型，退化成一维指针。
2. 否则，类型为函数类型，退化为函数指针类型。
3. 否则，去除类型的cv修饰符。

实现如下：

template<typename T>
class decay
{
    using U = std::remove_reference_t<T>; // 去除引用类型
    using type = conditional_t<is_array_v<U>,
    	remove_extent_t<U>* , // 去除掉[],变成指针
    	conditional_t<is_function_v<U>, // 如果是函数类型
    		add_pointer_t<U>,   // 退化成函数指针
   			remove_cv_t<U>      // 否则去除cv修饰符
        	>
    	>;
};

标准库还有一些元函数，是无法通过C++语法来实现的，例如是否是一个抽象类is_abstract。

2.2.6 类型内省

内省指的是程序运行时检查对象的类型或属性的一种能力，在C++中类型萃取的过程也可以视作内省，不过这个过程实在编译时查询与类型相关的特征。

通过使用模板类与特化方式，可以解构一个类型的各个组成部分。考虑最基本的一个一维数组类型，如何获得其长度？

template<typename T> struct array_size;
template<typename E,size_t N>
struct array_size<E[N]>
{
using value_type = E;
static constexpr size_t len = N;
};

static_assert(is_same_v<array_size<int[5]>::value_type,int>);
static_assert(array_size<int[5]>::len == 5);

首先，声明一个模板类array_size，其接收一个数组类型作为输入，并在偏特化中实现。里面有两个，一个是成员类型参数value_type来记录这个模板类的类型，另一个静态成员来记录数组的大小。

再考虑一个更为复杂的场景，如何获得函数类型的各个组成部分？函数类型是由一个返回类型与多个输入类型组成。

 template<typename F> struct function_trait;
 template<typename Ret,typename ...Args> // 偏特化
 struct function_trait<Ret(Args...)>
 {
     using result_type = Ret;
     using args_type = tuple<Args...>; // 使用tuple来存储，tuple是可以存储多个类型的
     static constexpr size_t num_of_args = sizeof...(Args);
     // 再通过传入的参数来获取第几个类型
     template<size_t Index>
     using arg = tuple_element_t<Index,args_type>; // 下标也是从0开始
 };

首先，先生们一个模板类function_trait，他接受返回值(形参列表)这种形式的函数类型，使用可变模板参数来获取传入形参的类型，使用标准库的元组来存储传入的形参类型，并且使用一个静态编译常量来存储参数的个数，最后，也可以通过下标访问来访问第几个参数。

2.2.7 enable_if 元函数

C++11起标准库提供了enable_if元函数。可以理解为就是一个针对于元函数的if语句。

enable_if接受两个模板参数，第一个参数为bool类型的值，当条件为真时，使用成员type的结果作为第二个模板参数，否则没有类型成员type。实现如下：

template<bool,typename = void> // 第二个默认为void
struct enable_if {};

template<typename T>
struct enable_if<true,T> { using type = T; };

考虑对数值进行判等操作的场景。如果是整数类型，则使用==进行判断，如果是浮点型类型，则考虑精度的问题。

template<typename T, enable_if_t<is_integral_v<T>>* = nullptr>
bool numEq(T lhs, T rhs) { return lhs == rhs; }

template<typename T, enable_if_t<is_floating_point_v<T>>* = nullptr>
bool numEq(T lhs, T rhs) { return fabs(lhs-rhs) < numeric_limits<T>::epsilon(); }

第一个参数是T，但第二个参数是非类型模板参数void*，因为，enable_if的第二个参数默认为void，如果is_integral满足时，那么得到类型void，同时默认值设置为nullptr。我们要记住，如果为假的时候，type是没有定义的，所以，从候选函数集中删去，替换失败。

2.2.8 标签分发

除了enable_if之外的编译时多态手段还有标签分发，这也是C++社区著名的惯用方法。标签通常是一个空类，例如前面介绍的true_type和false_type的辅助类作为标签。关键在于将标签作用于重载函数，根据不同的标签决议出不同的函数模板，可以重新实现numEq。

template<typename T>
bool numEqImpl(T lhs,T rhs,true_type) // 针对于浮点类型
{ return fabs(lhs-rhs) < numeric_limits<T>::epsilon(); }

template<typename T>
bool numEqImpl(T lhs,T rhs,false_type) // 其他算术类型
{ return lhs == rhs; }

template<typename T>
auto numEq(T lhs,T rhs) -> enable_if_t<is_arithmetic_v<T>,bool>
{ return numEqImpl(lhs,rhs,is_floating_point<T>{}); }

标签分发技术可以实现enable_if难以实现的功能：当条件存在包含关系时，用标签分发可以很自然的表达这种关系。

标准库的迭代器概念是容器和算法之间的桥梁，各种算法通过迭代器解耦具体的容器。迭代器可以作为广义的指针，行为与指针也很类似。下面有几种迭代器标签。

1. 输入迭代器input_iterator_tag仅支持单向遍历，只能遍历一轮。
2. 前向迭代器forward_iterator_tag和输入迭代器类似，但它可以支持多轮遍历。
3. 双向迭代器bidirectional_iterator_tag与前向迭代器不同的时，它支持前后遍历。
4. 随机访问迭代器random_access_iterator_tag，它支持随机访问，与原生指针类似。

仔细观察这几种标签，其实隐含了一种包含关系，input_iterator_tag功能最小，在最里面，而random_access_iterator_tag功能最大，在最外面，一层一层包含，因此可以衍生出以下的继承关系。

struct input_iterator_tag { };

struct forward_iterator_tag : public input_iterator_tag { };

struct bidirectional_iterator_tag : public forward_iterator_tag { };

struct random_access_iterator_tag : public bidirectional_iterator_tag { };

同时迭代器元函数iterator_traits，通过输入迭代器，如何其成员类型iterator_category存储的就是迭代器的标签类型，value_type时解引用后的类型，difference_type时迭代器做差后的类型ptrdiff_t。

考虑给定迭代器和偏移量实现，对迭代器偏移的算法advance。偏移量为正的时候向前移动，为负的时候向后移动。

使用标签分发来实现该算法，实现如下：

// 输入时单向迭代器或者向前迭代器
template<typename InputIter>
void advanceImpl(InputIter& iter,
                    typename iterator_traits<InputIter>::difference_type n,
                    input_iterator_tag) {
    for (; n > 0; --n) ++iter;
}
// 输入是双向迭代器
template<typename BiDirIter>
void advanceImpl(BiDirIter& iter,
                    typename iterator_traits<BiDirIter>::difference_type n,
                    bidirectional_iterator_tag) {
    if(n >= 0) for (; n > 0; --n) ++iter;
    else for(;n < 0;++n) --iter;
}
// 输入是随机访问迭代器
template<typename RandIter>
void advanceImpl(RandIter& iter,
                    typename iterator_traits<RandIter>::difference_type n,
                    random_access_iterator_tag) {
	iter += n;
}
// 采用标签分发机制
template<typename Iterator>
void advance(Iterator &iter,
				typename iterator_traits<Iterator>::difference_type n){
	advanceImpl(iter,n,typename iterator_traits<Iterator>::iterator_category{});
}

2.2.9 if constexpr

if constexpr是C++17引入的特性，与普通的if语句相比，他会在编译时对布尔类型常量表达式进行评估，并生成对应分支的代码。可以更加的清晰处理编译时分支的问题。

我们重新对之前的numEq模板函数实现对数值类型的判等操作。

template<typename T>
auto numEq(T lhs,T rhs) -> enable_if_t<is_arithmetic_v<T>,bool>
{
    if constexpr (is_integral_v<T>)
    	return lhs == rhs;
    else 
    	return fabs(lhs-rhs) < numeric_limits<T>::epsilon();
}

同样也可以对迭代器偏移函数advance进行替换。

template<typename InputIter>
void advance(InputIter &iter,
                typename iterator_traits<InputIter>::difference_type n) {
    using Category = typename iterator_traits<InputIter>::iterator_category;
    if constexpr (is_base_of_v<random_access_iterator_tag, Category>) { // 如果该标签时继承于random标签
        iter += n;
     } else if constexpr (is_base_of_v<bidirectional_iterator_tag, Category>) { // 针对于双向迭代器
          if (n >= 0) for (; n > 0; --n) ++iter;
          else for (; n < 0; ++n) --iter;
     }else { // 针对于输入和单向迭代器
          for(;n > 0;--n) ++iter;
     }
}

2.2.10 void_t 元函数

在C++17标准库中，引入元函数void_t用于检测一个给定的类型是否良构，进一步根据良构选择不同分支的代码，一般用于模板类于其特化版本之间的选择。void_t可以简单使用类型别名的方式实现。

template<typename...>
using void_t = void;

该元函数输入的是一系列类型模板参数，如果这些类型良构，那么输出的类型将为void。考虑编写一个谓词元函数，判断输入的类型是否存在成员类型::type。

template<typename T,typename = void>
struct HasTypeMember : false_type {};

template<typename T>
struct HasTypeMember<T, void_t<typename T::type>> : true_type {};

static_assert(!HasTypeMember<int>::value);
static_assert(HasTypeMember<true_type>::value);

首先，主模板声明要求输入两个类型参数，用户只需要提供一个，另一个默认为假。同时提供一个偏特化版本，当输入的类型具有::type时，即类型良构，那么void_t的结果为void，从而输出真。利用主模板第二个参数为void，即默认选择偏特化版本，只有当类型良构时，偏特化版本才会成立，否则使用主模板。

除了根据类型是否良构，还可以配合decltype用于检测成员变量、成员函数是否存在。考虑实现一个HasInit

来判断给定的类型是否拥有成员函数OnInit。

template<typename T,typename = void> // 主模板
struct HasInit : false_type {};

template<typename T> // 偏特化版本 
struct HasInit<T, void_t<decltype(declval<T>().OnInit())>> : true_type {};

struct Foo
{
	void OnInit() {}
};

static_assert(HasInit<Foo>::value);
static_assert(!HasInit<int>::value);

declval模板函数用于在非求值上下文decltype中构造函数，进一步调用其成员函数OnInit()，通过偏特化的方式，如果满足有该成员函数，故使用偏特化版本，否则使用主模板。

2.3 奇异模板递归

**奇异递归模板模式（CRTP）**是C++模板编程的一种惯用法：把派生类作为基类的模板参数，从而让基类可以使用派生类提供的方法。这种方式初看和它的名字一样奇怪，但在一定场景下相当有用。

• 代码复用：由于子类派生于模板基类，因此可以复用基类的方法。
• 编译时多态：由于基类是一个模板类，能够获得传递进来的派生类，进而可以调用派生类的方法，达到多态的效果。并且没有虚表的开销。

2.3.1 代码复用

访问者模式是面向对象编程的一个经典的设计模式，虽然现代C++使用std::variant和std::visit来代替访问者模式，但作为代码复用的例子值得一提。

这个模式的基本想法如下：假设我们拥有一个由不同种类的对象构成的对象结构，这些对象的类都有一个accept方法用于接受访问者对象；访问者是一个接口，它拥有一个visit方法，这个方法可以对访问到的对象结构中的不同类型的元素做出不同的反应。

在对象结构的一次访问过程中，我们遍历整个对象结构，对每一个元素都调用accept方法，在每一个元素的accept方法中回调访问者的visit方法，从而使访问者得以处理对象结构的每一个元素。

考虑位文件目录树结构设计接口，用户可以通过访问者接口对文件目录进行遍历以完成一些动作。访问者和元素的接口如下。

struct Visitor
{
	virtual void visit(VideoFile&) = 0;
	virtual void visit(TextFile&) = 0;
	virtual ~Visitor() = default;
};

struct Elem {
	virtual void accpet(Visitor& visitor) = 0;
	virtual ~Elem() = default;
};

这里涉及到两个多态结构的派发，即双重派发。

• 元素Elem接口通过运行时接受一个Visitor对象，通过虚函数动态派发到双方具体类的实现上。
• 元素Elem通过函数重载机制对visit接口进行静态派发。

struct VideoFile : Elem
{
	void accpet(Visitor& visitor) override
	{
		visitor.visit(*this);
	}
};

struct TextFile : Elem
{
	void accpet(Visitor& visitor) override
	{
		visitor.visit(*this);
	}
};

随着系统的演进，会发现有越来越多的重复的accept方法实现。而它们也只是简单的进行静态绑定。那么，可否考虑将accpet的实现都放到基类Elem中，从而减少这种重复的代码。

答案是否定的，因为this类型实际上是该类的指针类型，如果放到基类中，那么this指针，将为基类的指针，丢失类型信息后无法静态绑定。

我们可以通过采用奇异模板递归模式，基类的模板类型将会参数化派生类的类型，便能在静态分发的同时又能服用代码，重构之后的代码如下。

template<typename Derived>
struct AutoDispatchElem : Elem
{
	void accept(Visitor& visitor) override
	{
		visitor.visit(static_assert<Derived&>(*this));
	}
};

struct VideoFile : AutoDispatchElem<VideoFile> {};
struct TextFile : AutoDispatchElem<TextFile> {};

由于模板基类AutoDispatchElem能够获得派生类的类型，通过将this类型静态转换到派生类型的过程是安全的，进而能够重载到合适的visit函数上。而派生类继承自模板基类，也能够获得基类accpet的实现，从而满足代码复用。

为一个类实现大小比较、判等操作时常见的行为，标准库的一些容器诸如map、set等要求被存储的类型能够进行大小比较。如果要位一个类实现可比较的操作，则要实现六种比较操作符的重载，而真正要实现的只有两种，<和=，其余都是可以通过组合这两个来完成。

struct Point
{
	int x;
	int y;
	friend bool operator==(const Point& lhs, const Point& rhs)
	{
		return std::tie(lhs.x, lhs.y) == std::tie(rhs.x, rhs.y);  // 是将类型参数打包成元组
	}
	friend bool operator<(const Point& lhs, const Point& rhs)
	{
		return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y);
	}
	friend bool operator!=(const Point& lhs, const Point& rhs)
	{
		return !(lhs == rhs);  // 是将类型参数打包成元组
	}
	friend bool operator>(const Point& lhs, const Point& rhs)
	{
		return rhs < lhs;
	}
	friend bool operator<=(const Point& lhs, const Point& rhs)
	{
		return !(lhs > rhs);
	}
	friend bool operator>=(const Point& lhs, const Point& rhs)
	{
		return !(lhs < rhs);
	}
};

这里实现了一个Point类，它们之间的大小关系可以通过字典方式比较，首先比较第一个字段，若第一个字段相等，则比较第二个字段。我们使用了标准库的tie来将字段打包成元组tuple。元组是一个带有可变参数的模板类型，可以包含多个不同类型的参数。并且tuple还实现了重载比较操作符。

这里可以通过奇异模板递归的方式来实现，我们定义一个Comparable比较类，是一个模板参数为子类的基类。这个基类里面实现六种比较操作。但是子类必须拥有函数tie()来将成员打包为元组进行比较。

template<typename Derived>
struct Comparable
{
	friend bool operator==(const Derived& lhs, const Derived& rhs)
	{
		return std::tie(lhs.x, lhs.y) == std::tie(rhs.x, rhs.y);  // 是将类型参数打包成元组
	}
	friend bool operator<(const Derived& lhs, const Derived& rhs)
	{
		return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y);
	}
	friend bool operator!=(const Derived& lhs, const Derived& rhs)
	{
		return !(lhs == rhs);  // 是将类型参数打包成元组
	}
	friend bool operator>(const Derived& lhs, const Derived& rhs)
	{
		return rhs < lhs;
	}
	friend bool operator<=(const Derived& lhs, const Derived& rhs)
	{
		return !(lhs > rhs);
	}
	friend bool operator>=(const Derived& lhs, const Derived& rhs)
	{
		return !(lhs < rhs);
	}
};

struct Point : Comparable<Point>
{
	int x;
	int y;
	auto tie() const { return std::tie(x, y); }
};

C++20引入了三路比较操作符<=>以替代这种奇异递归模板模式来复用比较操作符，只需要实现一个<=>操作符重载即可。这个操作符由于长的很像**“飞船”，又被称为飞船操作符**。

<=>也是一个二元关系运算符，但它返回的并不是布尔类型，而是根据用户指明的三种类型之一：partial_ordering、weak_ordering、strong_ordering，定义于标准库头文件<compare>中，默认是string_ordering类型。

下面重点介绍一下这三种类型：

• 偏序partial_ordering表达了比较关系中的偏序关系，即给定的任意两个对象不一定可比较。例如，给定一个对象树，假设父节点比子节点大，<=>得到的是greater，但不是任意两个节点都可以比较，此时它们的关系是unordered。对于偏序关系的排序，使用拓扑排序算法将获得正确的结果。
• 弱序weak_ordering表达了比较关系中的全序关系，即给定的任意两个对象都可以比较，即不大于也不小于的关系被称为等价。假设长方形的类按照面积进行比较就是弱序关系，长宽分别为2和6的矩形与长宽分别为3和4的矩形比较，它们的面积相同，因此是等价的。但不相等是因为可以通过长宽区分出来并不一样。
• 强序string_ordering与弱序一样，考虑正方形按照面积比较的关系就是强序关系，因为面积相同的正方形，即边长也相同。

此外，<=>的结果与字符串比较函数strcmp类似，如果大于0表示大于关系，等于0表示等价、等于关系，小于0表示小于关系。

struct Point {
	int x; int y;
	friend auto operator<=>(const Point& lhs,const Point& rhs) = default;
};

2.3.2 静态多态

奇异递归模板模式的另一个作用是实现编译时多态，避免虚函数的开销。由于基类能够在编译时获得派生类的类型，因此也能在编译时对派生类的函数进行派发。考虑该模式实现动物类的多态，设计如下接口并实现。

template<typename Derived>
struct Animal
{
	void bark() { static_cast<Derived&>(*this).barkImpl(); }
};

class Cat : public Animal<Cat>
{
	friend Animal; // 让基类访问
	void barkImpl() { cout << "Miaowing!" << endl; }
};

class Dog : public Animal<Dog>
{
	friend Animal; // 让基类访问
	void barkImpl() { cout << "Bow wow!" << endl; }
};

template<typename T>
void play(Animal<T>& animal)
{
	animal.bark();
}

int main()
{
	Cat cat;
	play(cat);
	Dog dog;
	play(dog);
}

2.3.3 enable_shared_from_this 模板类

现代C++常用智能指针来管理对象的生命周期和所有权，标准库提供了非侵入式的智能指针shared_ptr和unique_ptr，分别用于共享对象的所有权或者独占对象的所有权。

shared_ptr，除了管理对象的内存之外，还使用引用计数控制，当计数大于0时，表示当前对象仍然被其他对象所管理者。当引用计数为0时，则释放内存，从而避免手动管理内存。

异步编程有一个场景，需要在类中将该类的对象注册到某个回调类或函数中，不能简单的将this指针传给回调类，很可能因为回调时该对象不存在而导致野指针访问的问题。标准库提供了enable_shared_from_this模板基类，通过奇异模板递归模式在父类中存储子类的指针信息与引用计数信息，并提供shared_from_this和weak_from_this接口获得智能指针。

智能指针在最初构造的时候，通过编译时多态的手段来判断被构造的类是否派生于enable_shared_from_this。若派送则将相关信息存储至基类中供后续使用，否则什么也不做。