51 单片机快速入门 [TOC] keil uVision5 第一步，点亮你的 LED 电源 晶振 复位电路 特殊功能寄存器 程序下载 第二步，硬件基础（Base）知识 电磁干扰 三极管 三八译码器 流水灯 定时器与数码管 中断与数码管动态显示 矩阵 LED 按键 步进电机与蜂鸣器 实例练习 UART串口通信 1602 液晶 1602 与 串口 i2c和e2prom ds1302 红外通信 模数转换和数模转换 RS-485 与 modbus协议 多功能电子钟 单片机开发常用工具 万用表 示波器 逻辑分析仪
C++ Template 进阶指南 [TOC] 0. 前言 0.1 C++另类简介：比你用的复杂，但比你想的简单 C++似乎从它为世人所知的那天开始便成为天然的话题性编程语言。在它在周围有着形形色色的赞美与贬低之词。当我在微博上透露欲写此文的意愿时，也收到了很多褒贬不一的评论。作为一门语言，能拥有这么多使用并恨着它、使用并畏惧它的用户，也算是语言丛林里的奇观了。 C++之所以变成一门层次丰富、结构多变、语法繁冗的语言，是有着多层次的原因的。Bjarne在《The Design and Evolution of C++》一书中，详细的解释了C++为什么会变成如今（C++98/03）的模样。这本书也是我和陈梓瀚一直对各位已经入门的新手强烈推荐的一本书。通过它你多少可以明白，C++的诸多语法要素之所以变成如今的模样，实属迫不得已。 模板作为C++中最有特色的语言特性，它堪称玄学的语法和语义，理所应当的成为初学者的梦魇。甚至很多工作多年的人也对C++的模板部分保有充分的敬畏。在多数的编码标准中，Template俨然和多重继承一样，成为了一般程序员（非程序库撰写者）的禁区。甚至运用模板较多的Boost，也成为了“众矢之的”。 但是实际上C++模板远没有想象的那么复杂。我们只需要换一个视角：在C++03的时候，模板本身就可以独立成为一门“语言”。它有“值”，有“函数”，有“表达式”和“语句”。除了语法比较蹩脚外，它既没有指针也没有数组，更没有C++里面复杂的继承和多态。可以说，它要比C语言要简单的多。如果我们把模板当做是一门语言来学习，那只需要花费学习OO零头的时间即可掌握。按照这样的思路，可以说在各种模板书籍中出现的多数技巧，都可以被轻松理解。 简单回顾一下模板的历史。87年的时候，泛型（Generic Programming）便被纳入了C++的考虑范畴，并直接导致了后来模板语法的产生。可以说模板语法一开始就是为了在C++中提供泛型机制。92年的时候，Alexander Stepanov开始研究利用模板语法制作程序库，后来这一程序库发展成STL，并在93年被接纳入标准中。 此时不少人以为STL已经是C++模板的集大成之作，C++模板技止于此。但是在95年的《C++ Report》上，John Barton和Lee Nackman提出了一个矩阵乘法的模板示例。可以说元编程在那个时候开始被很多人所关注。自此篇文章发表之后，很多大牛都开始对模板产生了浓厚的兴趣。其中对元编程技法贡献最大的当属Alexandrescu的《Modern C++ Design》及模板程序库Loki。这一2001年发表的图书间接地导致了模板元编程库的出现。书中所使用的Typelist等泛型组件，和Policy等设计方法令人耳目一新。但是因为全书用的是近乎Geek的手法来构造一切设施，因此使得此书阅读起来略有难度。 2002年出版的另一本书《C++ Templates》，可以说是在Template方面的集大成之作。它详细阐述了模板的语法、提供了和模板有关的语言细节信息，举了很多有代表性例子。但是对于模板新手来说，这本书细节如此丰富，让他们随随便便就打了退堂鼓缴械投降。 本文的写作初衷，就是通过“编程语言”的视角，介绍一个简单、清晰的“模板语言”。我会尽可能地将模板的诸多要素连串起来，用一些简单的例子帮助读者学习这门“语言”，让读者在编写、阅读模板代码的时候，能像 if(exp) { dosomething(); }一样的信手拈来，让“模板元编程”技术成为读者牢固掌握、可举一反三的有用技能。 0.2 适宜读者群 因为本文并不是用于C++入门，例子中也多少会牵涉一些其它知识，因此如果读者能够具备以下条件，会读起来更加轻松： 熟悉C++的基本语法； 使用过STL； 熟悉一些常用的算法，以及递归等程序设计方法。 此外，尽管第一章会介绍一些Template的基本语法，但是还是会略显单薄。因此也希望读者能对C++ Template最基本语法形式有所了解和掌握；如果会编写基本的模板函数和模板类那就更好了。 诚如上节所述，本文并不是《C++ Templates》的简单重复，与《Modern C++ Design》交叠更少。从知识结构上，我建议大家可以先读本文，再阅读《C++ Templates》获取更丰富的语法与实现细节，以更进一步；《Modern C++ Design》除了元编程之外，还有很多的泛型编程示例，原则上泛型编程的部分与我所述的内容交叉不大，读者在读完1-3章了解模板的基本规则之后便可阅读《MCD》的相应章节；元编程部分（如Typelist）建议在阅读完本文之后再行阅读，或许会更易理解。 0.3 版权 本文是随写随即同步到Github上，因此在行文中难免会遗漏引用（ref）。本文绝大部分内容应是直接承出我笔，但是也不定会有他山之石。所有指涉内容我会尽量以引号框记，或在上下文和边角注记中标示，如有遗漏烦请不吝指出。 全文所有为我所撰写的部分，作者均保留所有版权。如果有需要转帖或引用，还请注明出处并告知于我。 0.4 推荐编译（Compiler）环境 C++编译器众多，且对模板的支持可能存在细微差别。如果没有特别强调，本书行文过程中，使用了下列编译器来测试文中提供的代码和示例： Clang 3.7 (x86) Visual Studio 2015 Update 3 GCC 7 (x86, snapshot) 此外，部分复杂实例我们还在文中提供了在线的编译器预览以方便大家阅读和测试。在线编译器参见： gcc.godbolt.org。 一些示例中用到的特性所对应的C++标准： |特性|标准| |---|---| | std::decay_t | C++ 14 | 0.5 体例 0.5.1 示例代码 void SampleCode() { // 这是一段示例代码 } 0.5.2 引用 引用自C++标准： 1.1.2/1 这是一段引用或翻译自标准的文字 引用自其他图书： 《书名》 这是一段引用或翻译自其他图书的文字 0.6 意见、建议、喷、补遗、写作计划 需增加： 模板的使用动机。 增加“如何使用本文”一节。本节将说明全书的体例（强调字体、提示语、例子的组织），所有的描述、举例、引用在重审时将按照体例要求重新组织。 除了用于描述语法的例子外，其他例子将尽量赋予实际意义，以方便阐述意图。 在合适的章节完整叙述模板的类型推导规则。Parameter-Argument, auto variable, decltype, decltype(auto) 在函数模板重载和实例化的部分讲述ADL。 变参模板处应当按照标准（Argument Packing/Unpacking）来讲解。 建议： 比较模板和函数的差异性 蓝色：C++14 Return type deduction for normal functions 的分析 1. Template的基本语法 1.1 Template Class基本语法 1.1.1 Template Class的与成员变量定义 我们来回顾一下最基本的Template Class声明和定义形式： Template Class声明： template <typename T> class ClassA; Template Class定义： template <typename T> class ClassA { T member; }; template 是C++关键字，意味着我们接下来将定义一个模板。和函数一样，模板也有一系列参数（Parameter）。这些参数都被囊括在template之后的< >中。在上文的例子中， typename T便是模板参数。回顾一下与之相似的函数参数的声明形式： void foo(int a); T则可以类比为函数形参a，这里的“模板形参”T，也同函数形参一样取成任何你想要的名字；typename则类似于例子中函数参数类型int，它表示模板参数中的T将匹配一个类型。除了 typename 之外，我们在后面还要讲到，整型也可以作为模板的参数。 在定义完模板参数之后，便可以定义你所需要的类。不过在定义类的时候，除了一般类可以使用的类型外，你还可以使用在模板参数中使用的类型 T。可以说，这个 T是模板的精髓，因为你可以通过指定模板实参，将T替换成你所需要的类型。 例如我们用ClassA<int>来实例化模板类ClassA，那么ClassA<int>可以等同于以下的定义： // 注意：这并不是有效的C++语法，只是为了说明模板的作用 typedef class { int member; } ClassA<int>; 可以看出，通过模板参数替换类型，可以获得很多形式相同的新类型，有效减少了代码量。这种用法，我们称之为“泛型”（Generic Programming），它最常见的应用，即是STL中的容器（Container）模板类。 1.1.2 模板的使用 对于C++来说，类型最重要的作用之一就是用它去产生一个变量。例如我们定义了一个动态数组（列表）的模板类vector，它对于任意的元素类型都具有push_back和clear的操作，我们便可以如下定义这个类： template <typename T> class vector { public: void push_back(T const&); void clear(); private: T* elements; }; 此时我们的程序需要一个整型和一个浮点型的列表，那么便可以通过以下代码获得两个变量： vector<int> intArray; vector<float> floatArray; 此时我们就可以执行以下的操作，获得我们想要的结果： intArray.push_back(5); floatArray.push_back(3.0f); 变量定义的过程可以分成两步来看：第一步，vector<int>将int绑定到模板类vector上，获得了一个“普通的类vector<int>”；第二步通过“vector”定义了一个变量。 与“普通的类”不同，模板类是不能直接用来定义变量的。例如： vector unknownVector; // 错误示例 这样就是错误的。我们把通过类型绑定将模板类变成“普通的类”的过程，称之为模板实例化（Template Instantiate）。实例化的语法是： 模板名 < 模板实参1 [，模板实参2，...] > 看几个例子： vector<int> ClassA<double> template <typename T0, typename T1> class ClassB { // Class body ... }; ClassB<int, float> 当然，在实例化过程中，被绑定到模板参数上的类型（即模板实参）需要与模板形参正确匹配。 就如同函数一样，如果没有提供足够并匹配的参数，模板便不能正确的实例化。 1.1.3 模板类的成员函数定义 由于C++11正式废弃“模板导出”这一特性，因此在模板类的变量在调用成员函数的时候，需要看到完整的成员函数定义。因此现在的模板类中的成员函数，通常都是以内联的方式实现。 例如： template <typename T> class vector { public: void clear() { // Function body } private: T* elements; }; 当然，我们也可以将vector<T>::clear的定义部分放在类型之外，只不过这个时候的语法就显得蹩脚许多： template <typename T> class vector { public: void clear(); // 注意这里只有声明 private: T* elements; }; template <typename T> void vector<T>::clear() // 函数的实现放在这里 { // Function body } 函数的实现部分看起来略微拗口。我第一次学到的时候，觉得 void vector::clear() { // Function body } 这样不就行了吗？但是简单想就会知道，clear里面是找不到泛型类型T的符号的。 因此，在成员函数实现的时候，必须要提供模板参数。此外，为什么类型名不是vector而是vector<T>呢？ 如果你了解过模板的偏特化与特化的语法，应该能看出，这里的vector在语法上类似于特化/偏特化。实际上，这里的函数定义也确实是成员函数的偏特化。特化和偏特化的概念，本文会在第二部分详细介绍。 综上，正确的成员函数实现如下所示： template <typename T> // 模板参数 void vector<T> /*看起来像偏特化*/ ::clear() // 函数的实现放在这里 { // Function body } 1.2 Template Function的基本语法 1.2.1 Template Function的声明和定义 模板函数的语法与模板类基本相同，也是以关键字template和模板参数列表作为声明与定义的开始。模板参数列表中的类型，可以出现在参数、返回值以及函数体中。比方说下面几个例子 template <typename T> void foo(T const& v); template <typename T> T foo(); template <typename T, typename U> U foo(T const&); template <typename T> void foo() { T var; // ... } 无论是函数模板还是类模板，在实际代码中看起来都是“千变万化”的。这些“变化”，主要是因为类型被当做了参数，导致代码中可以变化的部分更多了。 归根结底，模板无外乎两点： 函数或者类里面，有一些类型我们希望它能变化一下，我们用标识符来代替它，这就是“模板参数”； 在需要这些类型的地方，写上相对应的标识符（“模板参数”）。 当然，这里的“可变”实际上在代码编译好后就固定下来了，可以称之为编译期的可变性。 这里多啰嗦一点，主要也是想告诉大家，模板其实是个很简单的东西。 下面这个例子，或许可以帮助大家解决以下两个问题： 什么样的需求会使用模板来解决？ 怎样把脑海中的“泛型”变成真正“泛型”的代码？ 举个例子：generic typed function ‘add’ 在我遇到的朋友中，即便如此对他解释了模板，即便他了解了模板，也仍然会对模板产生畏难情绪。毕竟从形式上来说，模板类和模板函数都要较非模板的版本更加复杂，阅读代码所需要理解的内容也有所增多。 如何才能克服这一问题，最终视模板如平坦代码呢？ 答案只有一个：无他，唯手熟尔。 在学习模板的时候，要反复做以下的思考和练习： 提出问题：我的需求能不能用模板来解决？ 怎么解决？ 把解决方案用代码写出来。 如果失败了，找到原因。是知识有盲点（例如不知道怎么将 T& 转化成 T），还是不可行（比如试图利用浮点常量特化模板类，但实际上这样做是不可行的）？ 通过重复以上的练习，应该可以对模板的语法和含义都有所掌握。如果提出问题本身有困难，或许下面这个经典案例可以作为你思考的开始： 写一个泛型的数据结构：例如，线性表，数组，链表，二叉树； 写一个可以在不同数据结构、不同的元素类型上工作的泛型函数，例如求和； 当然和“设计模式”一样，模板在实际应用中，也会有一些固定的需求和解决方案。比较常见的场景包括：泛型（最基本的用法）、通过类型获得相应的信息（型别萃取）、编译期间的计算、类型间的推导和变换（从一个类型变换成另外一个类型，比如boost::function）。这些本文在以后的章节中会陆续介绍。 1.2.2 模板函数的使用 我们先来看一个简单的函数模板，两个数相加： template <typename T> T Add(T a, T b) { return a + b; } 函数模板的调用格式是： 函数模板名 < 模板参数列表 > ( 参数 ) 例如，我们想对两个 int 求和，那么套用类的模板实例化方法，我们可以这么写： int a = 5; int b = 3; int result = Add<int>(a, b); 这时我们等于拥有了一个新函数： int Add<int>(int a, int b) { return a + b; } 这时在另外一个偏远的程序角落，你也需要求和。而此时你的参数类型是 float ，于是你写下： Add<float>(a, b); 一切看起来都很完美。但如果你具备程序员的最佳美德——懒惰——的话，你肯定会这样想，我在调用 Add<int>(a, b) 的时候， a 和 b 匹配的都是那个 T。编译器就应该知道那个 T 实际上是 int 呀？为什么还要我多此一举写 Add<int> 呢？ 唔，我想说的是，编译器的作者也是这么想的。所以实际上你在编译器里面写下以下片段： int a = 5; int b = 3; int result = Add(a, b); 编译器会心领神会地将 Add 变成 Add<int>。但是编译器不能面对模棱两可的答案。比如你这么写的话呢？ int a = 5; char b = 3; int result = Add(a, b); 第一个参数 a 告诉编译器，这个 T 是 int。编译器点点头说，好。但是第二个参数 b 不高兴了，告诉编译器说，你这个 T，其实是 char。 两个参数各自指导 T 的类型，编译器就不知道怎么做了。在Visual Studio 2012下，会有这样的提示： error C2782: 'T _1_2_2::Add(T,T)' : template parameter 'T' is ambiguous 好吧，"ambiguous"，这个提示再明确不过了。 不过，只要你别逼得编译器精神分裂的话，编译器其实是非常聪明的，它可以从很多的蛛丝马迹中，猜测到你真正的意图，有如下面的例子： template <typename T> class A {}; template <typename T> T foo( A<T> v ); A<int> v; foo(v); // 它能准确地猜到 T 是 int. 咦，编译器居然绕过了A这个外套，猜到了 T 匹配的是 int。编译器是怎么完成这一“魔法”的，我们暂且不表，2.2节时再和盘托出。 下面轮到你的练习时间了。你试着写了很多的例子，但是其中一个你还是犯了疑惑： float data[1024]; template <typename T> T GetValue(int i) { return static_cast<T>(data[i]); } float a = GetValue(0); // 出错了！ int b = GetValue(1); // 也出错了！ 为什么会出错呢？你仔细想了想，原来编译器是没办法去根据返回值推断类型的。函数调用的时候，返回值被谁接受还不知道呢。如下修改后，就一切正常了： float a = GetValue<float>(0); int b = GetValue<int>(1); 嗯，是不是so easy啊？嗯，你又信心满满的做了一个练习： 你要写一个模板函数叫 c_style_cast，顾名思义，执行的是C风格的转换。然后出于方便起见，你希望它能和 static_cast 这样的内置转换有同样的写法。于是你写了一个use case。 DstT dest = c_style_cast<DstT>(src); 根据调用形式你知道了，有 DstT 和 SrcT 两个模板参数。参数只有一个， src，所以函数的形参当然是这么写了： (SrcT src)。实现也很简单， (DstT)v。 我们把手上得到的信息来拼一拼，就可以编写自己的函数模板了： template <typename SrcT, typename DstT> DstT c_style_cast(SrcT v) { return (DstT)(v); } int v = 0; float i = c_style_cast<float>(v); 嗯，很Easy嘛！我们F6一下…咦！这是什么意思！ error C2783: 'DstT _1_2_2::c_style_cast(SrcT)' : could not deduce template argument for 'DstT' 然后你仔细的比较了一下，然后发现 … 模板参数有两个，而参数里面能得到的只有 SrcT 一个。结合出错信息看来关键在那个 DstT 上。这个时候，你死马当活马医，把模板参数写完整了： float i = c_style_cast<int, float>(v); 嗯，很顺利的通过了。难道C++不能支持让参数推导一部分模板参数吗？ 当然是可以的。只不过在部分推导、部分指定的情况下，编译器对模板参数的顺序是有限制的：先写需要指定的模板参数，再把能推导出来的模板参数放在后面。 在这个例子中，能推导出来的是 SrcT，需要指定的是 DstT。把函数模板写成下面这样就可以了： template <typename DstT, typename SrcT> DstT c_style_cast(SrcT v) // 模板参数 DstT 需要人肉指定，放前面。 { return (DstT)(v); } int v = 0; float i = c_style_cast<float>(v); // 形象地说，DstT会先把你指定的参数吃掉，剩下的就交给编译器从函数参数列表中推导啦。 1.3 整型也可是Template参数 模板参数除了类型外（包括基本类型、结构、类类型等），也可以是一个整型数（Integral Number）。这里的整型数比较宽泛，包括布尔型，不同位数、有无符号的整型，甚至包括指针。我们将整型的模板参数和类型作为模板参数来做一个对比： template <typename T> class TemplateWithType; template <int V> class TemplateWithValue; 我想这个时候你也更能理解 typename 的意思了：它相当于是模板参数的“类型”，告诉你 T 是一个 typename。 按照C++ Template最初的想法，模板不就是为了提供一个类型安全、易于调试的宏吗？有类型就够了，为什么要引入整型参数呢？考虑宏，它除了代码替换，还有一个作用是作为常数出现。所以整型模板参数最基本的用途，也是定义一个常数。例如这段代码的作用： template <typename T, int Size> struct Array { T data[Size]; }; Array<int, 16> arr; 便相当于下面这段代码： class IntArrayWithSize16 { int data[16]; // int 替换了 T, 16 替换了 Size }; IntArrayWithSize16 arr; 其中有一点需要注意，因为模板的匹配是在编译的时候完成的，所以实例化模板的时候所使用的参数，也必须要在编译期就能确定。例如以下的例子编译器就会报错： template <int i> class A {}; void foo() { int x = 3; A<5> a; // 正确！ A<x> b; // error C2971: '_1_3::A' : template parameter 'i' : 'x' : a local variable cannot be used as a non-type argument } 因为x不是一个编译期常量，所以 A<x> 就会告诉你，x是一个局部变量，不能作为一个模板参数出现。 嗯，这里我们再来写几个相对复杂的例子： template <int i> class A { public: void foo(int) { } }; template <uint8_t a, typename b, void* c> class B {}; template <bool, void (*a)()> class C {}; template <void (A<3>::*a)(int)> class D {}; template <int i> int Add(int a) // 当然也能用于函数模板 { return a + i; } void foo() { A<5> a; B<7, A<5>, nullptr> b; // 模板参数可以是一个无符号八位整数，可以是模板生成的类；可以是一个指针。 C<false, &foo> c; // 模板参数可以是一个bool类型的常量，甚至可以是一个函数指针。 D<&A<3>::foo> d; // 丧心病狂啊！它还能是一个成员函数指针！ int x = Add<3>(5); // x == 8。因为整型模板参数无法从函数参数获得，所以只能是手工指定啦。 } template <float a> class E {}; // ERROR: 别闹！早说过只能是整数类型的啦！ 当然，除了单纯的用作常数之外，整型参数还有一些其它的用途。这些“其它”用途最重要的一点是让类型也可以像整数一样运算。《Modern C++ Design》给我们展示了很多这方面的例子。不过你不用急着去阅读那本天书，我们会在做好足够的知识铺垫后，让你轻松学会这些招数。 1.4 模板形式与功能是统一的 第一章走马观花的带着大家复习了一下C++ Template的基本语法形式，也解释了包括 typename 在内，类/函数模板写法中各个语法元素的含义。形式是功能的外在体现，介绍它们也是为了让大家能理解到，模板之所以写成这种形式是有必要的，而不是语言的垃圾成分。 从下一章开始，我们便进入了更加复杂和丰富的世界：讨论模板的匹配规则。其中有令人望而生畏的特化与偏特化。但是，请相信我们在序言中所提到的：将模板作为一门语言来看待，它会变得有趣而简单。 2. 模板元编程基础（Base） 2.1 编程，元编程，模板元编程 技术的学习是一个登山的过程。第一章是最为平坦的山脚道路。而从这一章开始，则是正式的爬坡。无论是我写作还是你阅读，都需要付出比第一章更多的代价。那么问题就是，付出更多的精力学习模板是否值得？ 这个问题很功利，但是一针见血。因为技术的根本目的在于解决需求。那C++的模板能做什么？ 一个高（树）大（新）上（风）的回答是，C++里面的模板，犹如C中的宏、C#和Java中的自省（restropection）和反射（reflection），是一个改变语言内涵，拓展语言外延的存在。 程序最根本的目的是什么？复现真实世界或人所构想的规律，减少重复工作的成本，或通过提升规模完成人所不能及之事。但是世间之事万千，有限的程序如何重现复杂的世界呢？ 答案是“抽象”。论及具体手段，无外乎“求同”与“存异”：概括一般规律，处理特殊情况。这也是软件工程所追求的目标。一般规律概括的越好，我们所付出的劳动也就越少。 同样的，作为脑力劳动的产品，程序本身也是有规律性的。《Modern C++ Design》中的前言就抛出了一连串有代表性的问题： 如何撰写更高级的C++程式？ 如何应付即使在很干净的设计中仍然像雪崩一样的不相干细节？ 如何构建可复用组件，使得每次在不同程式中应用组件时无需大动干戈？ 我们以数据结构举例。在程序里，你需要一些堆栈。这个堆栈的元素可能是整数、浮点或者别的什么类型。一份整型堆栈的代码可能是： class StackInt { public: void push(int v); int pop(); int Find(int x) { for(int i = 0; i < size; ++i) { if(data[i] == x) { return i; } } } // ... 其他代码 ... }; 如果你要支持浮点了，那么你只能将代码再次拷贝出来，并作如下修改： class StackFloat { public: void push(float v); float pop(); int Find(float x) { for(int i = 0; i < size; ++i) { if(data[i] == x) { return i; } } } // ... 其他代码 ... }; 当然也许你觉得这样做能充分体会代码行数增长的成就感。但是有一天，你突然发现：呀，Find 函数实现有问题了。怎么办？这个时候也许你只有两份这样的代码，那好说，一一去修正就好了。如果你有十个呢？二十个？五十个？ 时间一长，你就厌倦了这样的生活。你觉得每个堆栈都差不多，但是又有点不一样。为了这一点点不一样，你付出了太多的时间。吃饭的时间，泡妞的时间，睡觉的时间，看岛国小电影顺便练习小臂力量的时间。 于是便诞生了新的技术，来消解我们的烦恼。 这个技术的名字，并不叫“模板”，而是叫“元编程”。 元（meta）无论在中文还是英文里，都是个很“抽象（abstract）”的词。因为它的本意就是“抽象”。元编程，也可以说就是“编程的抽象”。用更好理解的说法，元编程意味着你撰写一段程序A，程序A会运行后生成另外一个程序B，程序B才是真正实现功能的程序。那么这个时候程序A可以称作程序B的元程序，撰写程序A的过程，就称之为“元编程”。 回到我们的堆栈的例子。真正执行功能的，其实仍然是浮点的堆栈、整数的堆栈、各种你所需要的类型的堆栈。但是因为这些堆栈之间太相似了，仅仅有着些微的不同，我们为什么不能有一个将相似之处囊括起来，同时又能分别体现出不同之处的程序呢？很多语言都提供了这样的机会。C中的宏，C++中的模板，Python中的Duck Typing，广义上将都能够实现我们的思路。 我们的目的，是找出程序之间的相似性，进行“元编程”。而在C++中，元编程的手段，可以是宏，也可以是模板。 宏的例子姑且不论，我们来看一看模板： template <typename T> class Stack { public: void push(T v); T pop(); int Find(T x) { for(int i = 0; i < size; ++i) { if(data[i] == x) { return i; } } } // ... 其他代码 ... }; typedef Stack<int> StackInt; typedef Stack<float> StackFloat; 通过模板，我们可以将形形色色的堆栈代码分为两个部分，一个部分是不变的接口（Interface），以及近乎相同的实现；另外一部分是元素的类型，它们是需要变化的。因此同函数类似，需要变化的部分，由模板参数来反映；不变的部分，则是模板内的代码。可以看到，使用模板的代码，要比不使用模板的代码简洁许多。 如果元编程中所有变化的量（或者说元编程的参数），都是类型，那么这样的编程，我们有个特定的称呼，叫“泛型”。 但是你会问，模板的发明，仅仅是为了做和宏几乎一样的替换工作吗？可以说是，也可以说不是。一方面，很多时候模板就是为了替换类型，这个时候作用上其实和宏没什么区别。只是宏是基于文本的替换，被替换的文本本身没有任何语义。只有替换完成，编译器才能进行接下来的处理。而模板会在分析模板时以及实例化模板时时候都会进行检查，而且源代码中也能与调试符号一一对应，所以无论是编译时还是运行时，排错都相对简单。 但是模板和宏也有很大的不同，否则此文也就不能成立了。模板最大的不同在于它是“可以运算”的。我们来举一个例子，不过可能有点牵强。考虑我们要写一个向量逐分量乘法。只不过这个向量，它非常的大。所以为了保证速度，我们需要使用SIMD指令进行加速。假设我们有以下指令可以使用： Int8,16: N/A Int32 : VInt32Mul(int32x4, int32x4) Int64 : VInt64Mul(int64x4, int64x4) Float : VInt64Mul(floatx2, floatx2) 所以对于Int8和Int16，我们需要提升到Int32，而Int32和Int64，各自使用自己的指令。所以我们需要实现下的逻辑： for(v4a, v4b : vectorsA, vectorsB) { if type is Int8, Int16 VInt32Mul( ConvertToInt32(v4a), ConvertToInt32(v4b) ) elif type is Int32 VInt32Mul( v4a, v4b ) elif type is Float ... } 这里的问题就在于，如何根据 type 分别提供我们需要的实现？这里有两个难点。首先， if(type == xxx) {} 是不存在于C++中的。第二，即便存在根据 type 的分配方法，我们也不希望它在运行时branch，这样会变得很慢。我们希望它能按照类型直接就把代码编译好，就跟直接写的一样。 嗯，聪明你果然想到了，重载也可以解决这个问题。 GenericMul(int8x4, int8x4); GenericMul(int16x4, int16x4); GenericMul(int32x4, int32x4); GenericMul(int64x4, int64x4); // 其它 Generic Mul ... for(v4a, v4b : vectorsA, vectorsB) { GenericMul(v4a, v4b); } 这样不就可以了吗？ 唔，你赢了，是这样没错。但是问题是，我这个平台是你可没见过，它叫 Deep Thought， 特别缺心眼儿，不光有 int8，还有更奇怪的 int9, int11，以及可以代表世间万物的 int42。你总不能为之提供所有的重载吧？这简直就像你枚举了所有程序的输入，并为之提供了对应的输出一样。 好吧，我承认这个例子还是太牵强了。不过相信我，在你阅读完第二章和第三章之后，你会将这些特性自如地运用到你的程序之中。你的程序将会变成体现模板“可运算”威力的最好例子。 2.2 模板世界的If-Then-Else：类模板的特化与偏特化 2.2.1 根据类型执行代码 前一节的示例提出了一个要求：需要做出根据类型执行不同代码。要达成这一目的，模板并不是唯一的途径。比如之前我们所说的重载。如果把眼界放宽一些，虚函数也是根据类型执行代码的例子。此外，在C语言时代，也会有一些技法来达到这个目的，比如下面这个例子，我们需要对两个浮点做加法， 或者对两个整数做乘法： struct Variant { union { int x; float y; } data; uint32 typeId; }; Variant addFloatOrMulInt(Variant const* a, Variant const* b) { Variant ret; assert(a->typeId == b->typeId); if (a->typeId == TYPE_INT) { ret.x = a->x * b->x; } else { ret.y = a->y + b->y; } return ret; } 更常见的是 void*: #define BIN_OP(type, a, op, b, result) (*(type *)(result)) = (*(type const *)(a)) op (*(type const*)(b)) void doDiv(void* out, void const* data0, void const* data1, DATA_TYPE type) { if(type == TYPE_INT) { BIN_OP(int, data0, *, data1, out); } else { BIN_OP(float, data0, +, data1, out); } } 在C++中比如在 Boost.Any 的实现中，运用了 typeid 来查询类型信息。和 typeid 同属于RTTI机制的 dynamic_cast，也经常会用来做类型判别的工作。我想你应该写过类似于下面的代码： IAnimal* animal = GetAnimalFromSystem(); IDog* maybeDog = dynamic_cast<IDog*>(animal); if(maybeDog) { maybeDog->Wangwang(); } ICat* maybeCat = dynamic_cast<ICat*>(animal); if(maybeCat) { maybeCat->Moemoe(); } 当然，在实际的工作中，我们建议把需要 dynamic_cast 后执行的代码，尽量变成虚函数。不过这个已经是另外一个问题了。我们看到，不管是哪种方法都很难避免 if 的存在。而且因为输入数据的类型是模糊的，经常需要强制地、没有任何检查的转换成某个类型，因此很容易出错。 但是模板与这些方法最大的区别并不在这里。模板无论其参数或者是类型，它都是一个编译期分派的办法。编译期就能确定的东西既可以做类型检查，编译器也能进行优化，砍掉任何不必要的代码执行路径。例如在上例中， template <typename T> T addFloatOrMulInt(T a, T b); // 迷之代码1：用于T是float的情况 // 迷之代码2：用于T是int时的情况 如果你运用了模板来实现，那么当传入两个不同类型的变量，或者不是 int 和 float 变量，编译器就会提示错误。但是如果使用了我们前述的 Variant 来实现，编译器可就管不了那么多了。但是，成也编译期，败也编译期。最严重的“缺点”，就是你没办法根据用户输入或者别的什么在运行期间可能发生变化的量来决定它产生、或执行什么代码。比如下面的代码段，它是不成立的。 template <int i, int j> int foo() { return i + j; } int main() { cin >> x >> y; return foo<x, y>(); } 这点限制也粉碎了妄图用模板来包办工厂（Factory）甚至是反射的梦想。尽管在《Modern C++ Design》中（别问我为什么老举这本书，因为《C++ Templates》和《Generic Programming》我只是囫囵吞枣读过，基本不记得了)大量运用模板来简化工厂方法；同时C++11/14中的一些机制如Variadic Template更是让这一问题的解决更加彻底。但无论如何，直到C++11/14，光靠模板你就是写不出依靠类名或者ID变量产生类型实例的代码。 所以说，从能力上来看，模板能做的事情都是编译期完成的。编译期完成的意思就是，当你编译一个程序的时候，所有的量就都已经确定了。比如下面的这个例子： int a = 3, b = 5; Variant aVar, bVar; aVar.setInt(a); // 我们新加上的方法，怎么实现的无所谓，大家明白意思就行了。 bVar.setInt(b); Variant result = addFloatOrMulInt(aVar, bVar); 除非世界末日，否则这个例子里不管你怎么蹦跶，单看代码我们就能知道， aVar 和 bVar 都一定会是整数。所以如果有合适的机制，编译器就能知道此处的 addFloatOrMulInt 中只需要执行 Int 路径上的代码，而且编译器在此处也能单独为 Int 路径生成代码，从而去掉那个不必要的 if。 在模板代码中，这个“合适的机制”就是指“特化”和“部分特化（Partial Specialization）”，后者也叫“偏特化”。 2.2.2 特化 我的高中物理老师对我说过一句令我受用至今的话：把自己能做的事情做好。编写模板程序也是一样。当你试图用模板解决问题之前，先撇开那些复杂的语法要素，用最直观的方式表达你的需求： // 这里是伪代码，意思一下 int|float addFloatOrMulInt(a, b) { if(type is Int) { return a * b; } else if (type is Float) { return a + b; } } void foo() { float a, b, c; c = addFloatOrMulInt(a, b); // c = a + b; int x, y, z; z = addFloatOrMulInt(x, y); // z = x * y; } 因为这一节是讲类模板有关的特化和偏特化机制，所以我们不用普通的函数，而是用类的静态成员函数来做这个事情（这就是典型的没事找抽型）： // 这里仍然是伪代码，意思一下，too。 class AddFloatOrMulInt { static int|float Do(a, b) { if(type is Int) { return a * b; } else if (type is Float) { return a + b; } } }; void foo() { float a, b, c; c = AddFloatOrMulInt::Do(a, b); // c = a + b; int x, y, z; z = AddFloatOrMulInt::Do(x, y); // z = x * y; } 好，意思表达清楚了。我们先从调用方的角度，把这个形式改写一下： void foo() { float a, b, c; c = AddFloatOrMulInt<float>::Do(a, b); // c = a + b; int x, y, z; z = AddFloatOrMulInt<int>::Do(x, y); // z = x * y; } 也许你不明白为什么要改写成现在这个样子。看不懂不怪你，怪我讲得不好。但是你别急，先看看这样改写以后能不能跟我们的目标接近一点。如果我们把 AddFloatOrMulInt<float>::Do 看作一个普通的函数，那么我们可以写两个实现出来： float AddFloatOrMulInt<float>::Do(float a, float b) { return a + b; } int AddFloatOrMulInt<int>::Do(int a, int b) { return a * b; } void foo() { float a, b, c; c = AddFloatOrMulInt<float>::Do(a, b); // c = a + b; int x, y, z; z = AddFloatOrMulInt<int>::Do(x, y); // z = x * y; } 这样是不是就很开心了？我们更进一步，把 AddFloatOrMulInt<int>::Do 换成合法的类模板： // 这个是给float用的。 template <typename T> class AddFloatOrMulInt { T Do(T a, T b) { return a + b; } }; // 这个是给int用的。 template <typename T> class AddFloatOrMulInt { T Do(T a, T b) { return a * b; } }; void foo() { float a, b, c; // 嗯，我们需要 c = a + b; c = AddFloatOrMulInt<float>::Do(a, b); // ... 觉得哪里不对劲 ... // ... // ... // ... // 啊！有两个AddFloatOrMulInt，class看起来一模一样，要怎么区分呢！ } 好吧，问题来了！如何要让两个内容不同，但是模板参数形式相同的类进行区分呢？特化！特化（specialization）是根据一个或多个特殊的整数或类型，给出模板实例化时的一个指定内容。我们先来看特化是怎么应用到这个问题上的。 // 首先，要写出模板的一般形式（原型） template <typename T> class AddFloatOrMulInt { static T Do(T a, T b) { // 在这个例子里面一般形式里面是什么内容不重要，因为用不上 // 这里就随便给个0吧。 return T(0); } }; // 其次，我们要指定T是int时候的代码，这就是特化： template <> class AddFloatOrMulInt<int> { public: static int Do(int a, int b) // { return a * b; } }; // 再次，我们要指定T是float时候的代码： template <> class AddFloatOrMulInt<float> { public: static float Do(float a, float b) { return a + b; } }; void foo() { // 这里面就不写了 } 我们再把特化的形式拿出来一瞧：这货有点怪啊： template <> class AddFloatOrMulInt<int>。别急，我给你解释一下。 // 我们这个模板的基本形式是什么？ template <typename T> class AddFloatOrMulInt; // 但是这个类，是给T是Int的时候用的，于是我们写作 class AddFloatOrMulInt<int>; // 当然，这里编译是通不过的。 // 但是它又不是个普通类，而是类模板的一个特化（特例）。 // 所以前面要加模板关键字template， // 以及模板参数列表 template </* 这里要填什么？ */> class AddFloatOrMulInt<int>; // 最后，模板参数列表里面填什么？因为原型的T已经被int取代了。所以这里就不能也不需要放任何额外的参数了。 // 所以这里放空。 template <> class AddFloatOrMulInt<int> { // ... 针对Int的实现 ... }; // Bingo! 哈，这样就好了。我们来做一个练习。我们有一些类型，然后你要用模板做一个对照表，让类型对应上一个数字。我先来做一个示范： template <typename T> class TypeToID { public: static int const ID = -1; }; template <> class TypeToID<uint8_t> { public: static int const ID = 0; }; 然后呢，你的任务就是，要所有无符号的整数类型的特化（其实就是uint8_t到uint64_t啦），把所有的基本类型都赋予一个ID（当然是不一样的啦）。当你做完后呢，可以把类型所对应的ID打印出来，我仍然以 uint8_t 为例： void PrintID() { cout << "ID of uint8_t: " << TypeToID<uint8_t>::ID << endl; } 嗯，看起来挺简单的，是吧。但是这里透露出了一个非常重要的信号，我希望你已经能察觉出来了： TypeToID 如同是一个函数。这个函数只能在编译期间执行。它输入一个类型，输出一个ID。 如果你体味到了这一点，那么恭喜你，你的模板元编程已经开悟了。 2.2.3 特化：一些其它问题 在上一节结束之后，你一定做了许多的练习。我们再来做三个练习。第一，给float一个ID；第二，给void*一个ID；第三，给任意类型的指针一个ID。先来做第一个: // ... // TypeToID 的模板“原型” // ... template <> class TypeToID<float> { static int const ID = 0xF10A7; }; 嗯， 这个你已经了然于心了。那么void*呢？你想了想，这已经是一个复合类型了。不错你还是战战兢兢地写了下来： template <> class TypeToID<void*> { static int const ID = 0x401d; }; void PrintID() { cout << "ID of uint8_t: " << TypeToID<void*>::ID << endl; } 遍译运行一下，对了。模板不过如此嘛。然后你觉得自己已经完全掌握了，并试图将所有C++类型都放到模板里面，开始了自我折磨的过程： class ClassB {}; template <> class TypeToID<void ()>; // 函数的TypeID template <> class TypeToID<int[3]>; // 数组的TypeID template <> class TypeToID<int (int[3])>; // 这是以数组为参数的函数的TypeID template <> class TypeToID<int (ClassB::*[3])(void*, float[2])>; // 我也不知道这是什么了，自己看着办吧。 甚至连 const 和 volatile 都能装进去： template <> class TypeToID<int const * volatile * const volatile>; 此时就很明白了，只要 <> 内填进去的是一个C++能解析的合法类型，模板都能让你特化。不过这个时候如果你一点都没有写错的话， PrintID 中只打印了我们提供了特化的类型的ID。那如果我们没有为之提供特化的类型呢？比如说double？OK，实践出真知，我们来尝试着运行一下： void PrintID() { cout << "ID of double: " << TypeToID<double>::ID << endl; } 嗯，它输出的是-1。我们顺藤摸瓜会看到， TypeToID的类模板“原型”的ID是值就是-1。通过这个例子可以知道，当模板实例化时提供的模板参数不能匹配到任何的特化形式的时候，它就会去匹配类模板的“原型”形式。 不过这里有一个问题要理清一下。和继承不同，类模板的“原型”和它的特化类在实现上是没有关系的，并不是在类模板中写了 ID 这个Member，那所有的特化就必须要加入 ID 这个Member，或者特化就自动有了这个成员。完全没这回事。我们把类模板改成以下形式，或许能看的更清楚一点： template <typename T> class TypeToID { public: static int const NotID = -2; }; template <> class TypeToID<float> { public: static int const ID = 1; }; void PrintID() { cout << "ID of float: " << TypeToID<float>::ID << endl; // Print "1" cout << "NotID of float: " << TypeToID<float>::NotID << endl; // Error! TypeToID<float>使用的特化的类，这个类的实现没有NotID这个成员。 cout << "ID of double: " << TypeToID<double>::ID << endl; // Error! TypeToID<double>是由模板类实例化出来的，它只有NotID，没有ID这个成员。 } 这样就明白了。类模板和类模板的特化的作用，仅仅是指导编译器选择哪个编译，但是特化之间、特化和它原型的类模板之间，是分别独立实现的。所以如果多个特化、或者特化和对应的类模板有着类似的内容，很不好意思，你得写上若干遍了。 第三个问题，是写一个模板匹配任意类型的指针。对于C语言来说，因为没有泛型的概念，因此它提供了无类型的指针void*。它的优点是，所有指针都能转换成它。它的缺点是，一旦转换称它后，你就再也不知道这个指针到底是指向float或者是int或者是struct了。 比如说copy。 void copy(void* dst, void const* src, size_t elemSize, size_t elemCount, void (*copyElem)(void* dstElem, void const* srcElem)) { void const* reader = src; void const* writer = dst; for(size_t i = 0; i < elemCount; ++i) { copyElem(writer, reader); advancePointer(reader, elemSize); // 把Reader指针往后移动一些字节 advancePointer(writer, elemSize); } } 为什么要提供copyElem，是因为可能有些struct需要深拷贝，所以得用特殊的copy函数。这个在C++98/03里面就体现为拷贝构造和赋值函数。 但是不管怎么搞，因为这个函数的参数只是void*而已，当你使用了错误的elemSize，或者传入了错误的copyElem，就必须要到运行的时候才有可能看出来。注意，这还只是有可能而已。 那么C++有了模板后，能否既能匹配任意类型的指针，同时又保留了类型信息呢？答案是显然的。至于怎么写，那就得充分发挥你的直觉了： 首先，我们需要一个typename T来指代“任意类型”这四个字： template <typename T> 接下来，我们要写函数原型： void copy(?? dest, ?? src, size_t elemCount); 这里的 ?? 要怎么写呢？既然我们有了模板类型参数T，那我们不如就按照经验，写 T* 看看。 template <typename T> void copy(T* dst, T const* src, size_t elemCount); 编译一下，咦，居然通过了。看来这里的语法与我们以前学到的知识并没有什么不同。这也是语言设计最重要的一点原则：一致性。它可以让你辛辛苦苦体验到的规律不至于白费。 最后就是实现： template <typename T> void copy(T* dst, T const* src, size_t elemCount) { for(size_t i = 0; i < elemCount; ++i) { dst[i] = src[i]; } } 是不是简洁了许多？你不需要再传入size；只要你有正确的赋值函数，也不需要提供定制的copy；也不用担心dst和src的类型不匹配了。 最后，我们把函数模板学到的东西，也应用到类模板里面： template <typename T> // 嗯，需要一个T class TypeToID<T*> // 我要对所有的指针类型特化，所以这里就写T* { public: static int const ID = 0x80000000; // 用最高位表示它是一个指针 }; 最后写个例子来测试一下，看看我们的 T* 能不能搞定 float*： void PrintID() { cout << "ID of float*: " << TypeToID<float*>::ID << endl; } 哈哈，大功告成。嗯，别急着高兴。待我问一个问题：你知道 TypeToID<float*> 后，这里的T是什么吗？换句话说，你知道下面这段代码打印的是什么吗？ // ... // TypeToID 的其他代码，略过不表 // ... template <typename T> // 嗯，需要一个T class TypeToID<T*> // 我要对所有的指针类型特化，所以这里就写T* { public: typedef T SameAsT; static int const ID = 0x80000000; // 用最高位表示它是一个指针 }; void PrintID() { cout << "ID of float*: " << TypeToID< TypeToID<float*>::SameAsT >::ID << endl; } 别急着运行，你先猜。 ------------------------- 这里是给勤于思考的码猴的分割线 ------------------------------- OK，猜出来了吗，T是float。为什么呢？因为你用 float * 匹配了 T *，所以 T 就对应 float 了。没想清楚的自己再多体会一下。 嗯，所以实际上，我们可以利用这个特性做一件事情：把指针类型的那个指针给“干掉”： template <typename T> class RemovePointer { public: typedef T Result; // 如果放进来的不是一个指针，那么它就是我们要的结果。 }; template <typename T> class RemovePointer<T*> // 祖传牛皮藓，专治各类指针 { public: typedef T Result; // 正如我们刚刚讲的，去掉一层指针，把 T* 这里的 T 取出来。 }; void Foo() { RemovePointer<float*>::Result x = 5.0f; // 喏，用RemovePointer后，那个Result就是把float*的指针处理掉以后的结果：float啦。 std::cout << x << std::endl; } 当然啦，这里我们实现的不算是真正的 RemovePointer，因为我们只去掉了一层指针。而如果传进来的是类似 RemovePointer<int**> 这样的东西呢？是的没错，去掉一层之后还是一个指针。RemovePointer<int**>::Result 应该是一个 int*，要怎么才能实现我们想要的呢？聪明的你一定能想到：只要像剥洋葱一样，一层一层一层地剥开，不就好了吗！相应地我们应该怎么实现呢？可以把 RemovePointer 的特化版本改成这样（当然如果有一些不明白的地方你可以暂时跳过，接着往下看，很快就会明白的）： template <typename T> class RemovePointer<T*> { public: // 如果是传进来的是一个指针，我们就剥夺一层，直到指针形式不存在为止。 // 例如 RemovePointer<int**>，Result 是 RemovePointer<int*>::Result， // 而 RemovePointer<int*>::Result 又是 int，最终就变成了我们想要的 int，其它也是类似。 typedef typename RemovePointer<T>::Result Result; }; 是的没错，这便是我们想要的 RemovePointer 的样子。类似的你还可以试着实现 RemoveConst, AddPointer 之类的东西。 OK，回到我们之前的话题，如果这个时候，我需要给 int* 提供一个更加特殊的特化，那么我还得多提供一个： // ... // TypeToID 的其他代码，略过不表 // ... template <typename T> // 嗯，需要一个T class TypeToID<T*> // 我要对所有的指针类型特化，所以这里就写T* { public: typedef T SameAsT; static int const ID = 0x80000000; // 用最高位表示它是一个指针 }; template <> // 嗯，int* 已经是个具体的不能再具体的类型了，所以模板不需要额外的类型参数了 class TypeToID<int*> // 嗯，对int*的特化。在这里呢，要把int*整体看作一个类型 { public: static int const ID = 0x12345678; // 给一个缺心眼的ID }; void PrintID() { cout << "ID of int*: " << TypeToID<int*>::ID << endl; } 嗯，这个时候它会输出0x12345678的十进制（大概？）。 可能会有较真的人说，int* 去匹配 T 或者 T*，也是合法的。就和你说22岁以上能结婚，那24岁当然也能结婚一样。 那为什么 int* 就会找 int*，float *因为没有合适的特化就去找 T*，更一般的就去找 T 呢？废话，有专门为你准备的东西你不用，非要自己找事？这就是直觉。 但是呢，直觉对付更加复杂的问题还是没用的（也不是没用，主要是你没这个直觉了）。我们要把这个直觉，转换成合理的规则——即模板的匹配规则。 当然，这个匹配规则是对复杂问题用的，所以我们会到实在一眼看不出来的时候才会动用它。一开始我们只要把握：模板是从最特殊到最一般形式进行匹配的 就可以了。 2.3 即用即推导 2.3.1 视若无睹的语法错误 这一节我们将讲述模板一个非常重要的行为特点：那就是什么时候编译器会对模板进行推导，推导到什么程度。 这一知识，对于理解模板的编译期行为、以及修正模板编译错误都非常重要。 我们先来看一个例子： template <typename T> struct X {}; template <typename T> struct Y { typedef X<T> ReboundType; // 类型定义1 typedef typename X<T>::MemberType MemberType; // 类型定义2 typedef UnknownType MemberType3; // 类型定义3 void foo() { X<T> instance0; typename X<T>::MemberType instance1; WTF instance2 大王叫我来巡山 - + & } }; 把这段代码编译一下，类型定义3出错，其它的都没问题。不过到这里你应该会有几个问题： 不是struct X<T>的定义是空的吗？为什么在struct Y内的类型定义2使用了 X<T>::MemberType 编译器没有报错？ 类型定义2中的typename是什么鬼？为什么类型定义1就不需要？ 为什么类型定义3会导致编译错误？ 为什么void foo()在MSVC下什么错误都没报？ 这时我们就需要请出C++11标准 —— 中的某些概念了。这是我们到目前为止第一次参阅标准。我希望能尽量减少直接参阅标准的次数，因此即便是极为复杂的模板匹配决议我都暂时没有引入标准中的描述。 然而，Template引入的“双阶段名称查找（Two phase name lookup）”堪称是C++中最黑暗的角落 —— 这是LLVM的团队自己在博客上说的 —— 因此在这里，我们还是有必要去了解标准中是如何规定的。 2.3.2 名称查找：I am who I am 在C++标准中对于“名称查找（name lookup）”这个高大上的名词的诠释，主要集中出现在三处。第一处是3.4节，标题名就叫“Name Lookup”；第二处在10.2节，继承关系中的名称查找；第三处在14.6节，名称解析（name resolution）。 名称查找/名称解析，是编译器的基石。对编译原理稍有了解的人，都知道“符号表”的存在及重要意义。考虑一段最基本的C代码： int a = 0; int b; b = (a + 1) * 2; printf("Result: %d", b); 在这段代码中，所有出现的符号可以分为以下几类： int：类型标识符，代表整型； a, b, printf：变量名或函数名； =, +, *：运算符； ,, ;, (, )：分隔符； 那么，编译器怎么知道int就是整数类型，b=(a+1)*2中的a和b就是整型变量呢？这就是名称查找/名称解析的作用：它告诉编译器，这个标识符（identifer）是在哪里被声明或定义的，它究竟是什么意思。 也正因为这个机制非常基础，所以它才会面临各种可能的情况，编译器也要想尽办法让它在大部分场合都表现的合理。比如我们常见的作用域规则，就是为了对付名称在不同代码块中传播、并且遇到重名要如何处理的问题。下面是一个最简单的、大家在语言入门过程中都会碰到的一个例子： int a = 0; void f() { int a = 0; a += 2; printf("Inside : %d\n", a); } void g() { printf("Outside : %d\n", a); } int main() { f(); g(); } /* ------------ Console Output ----------------- Inside : 2 Outside : 0 --------------- Console Output -------------- */ 我想大家尽管不能处理所有名称查找中所遇到的问题，但是对一些常见的名称查找规则也有了充分的经验，可以解决一些常见的问题。 但是模板的引入，使得名称查找这一本来就不简单的基本问题变得更加复杂了。 考虑下面这个例子： struct A { int a; }; struct AB { int a, b; }; struct C { int c; }; template <typename T> foo(T& v0, C& v1){ v0.a = 1; v1.a = 2; v1.c = 3; } 简单分析上述代码很容易得到以下结论： 函数foo中的变量v1已经确定是struct C的实例，所以，v1.a = 2;会导致编译错误，v1.c = 3;是正确的代码； 对于变量v0来说，这个问题就变得很微妙。如果v0是struct A或者struct AB的实例，那么foo中的语句v0.a = 1;就是正确的。如果是struct C，那么这段代码就是错误的。 因此在模板定义的地方进行语义分析，并不能完全得出代码是正确或者错误的结论，只有到了实例化阶段，确定了模板参数的类型后，才知道这段代码正确与否。令人高兴的是，在这一问题上，我们和C++标准委员会的见地一致，说明我们的C++水平已经和Herb Sutter不分伯仲了。既然我们和Herb Sutter水平差不多，那凭什么人家就吃香喝辣？下面我们来选几条标准看看服不服： 14.6 名称解析（Name resolution） 1) 模板定义中能够出现以下三类名称： 模板名称、或模板实现中所定义的名称； 和模板参数有关的名称； 模板定义所在的定义域内能看到的名称。 … 9) … 如果名字查找和模板参数有关，那么查找会延期到模板参数全都确定的时候。 … 10) 如果（模板定义内出现的）名字和模板参数无关，那么在模板定义处，就应该找得到这个名字的声明。… 14.6.2 依赖（Dependencies）性名称（Dependent names） 1) …（模板定义中的）表达式和类型可能会依赖于模板参数，并且模板参数会影响到名称查找的作用域 … 如果表达式中有操作数依赖于模板参数，那么整个表达式都依赖于模板参数，名称查找延期到模板实例化时进行。并且定义时和实例化时的上下文都会参与名称查找。（依赖性）表达式可以分为类型依赖（类型指模板参数的类型）或值依赖。 14.6.2.2 类型依赖的表达式 2) 如果成员函数所属的类型是和模板参数有关的，那么这个成员函数中的this就认为是类型依赖的。 14.6.3 非依赖性名称（Non-dependent names） 1) 非依赖性名称在模板定义时使用通常的名称查找规则进行名称查找。 Working Draft: Standard of Programming Language C++, N3337 知道差距在哪了吗：人家会说黑话。什么时候咱们也会说黑话了，就是标准委员会成员了，反正懂得也不比他们少。不过黑话确实不太好懂 —— 怪我翻译不好的人，自己看原文，再说好懂了人家还靠什么吃饭 —— 我们来举一个例子： int a; struct B { int v; } template <typename T> struct X { B b; // B 是第三类名字，b 是第一类 T t; // T 是第二类 X* anthor; // X 这里代指 X<T>，第一类 typedef int Y; // int 是第三类 Y y; // Y 是第一类 C c; // C 什么都不是，编译错误。 void foo() { b.v += y; // b 是第一类，非依赖性名称 b.v *= T::s_mem; // T::s_mem 是第二类 // s_mem的作用域由T决定 // 依赖性名称，类型依赖 } }; 所以，按照标准的意思，名称查找会在模板定义和实例化时各做一次，分别处理非依赖性名称和依赖性名称的查找。这就是“两阶段名称查找”这一名词的由来。只不过这个术语我也不知道是谁发明的，它并没有出现的标准上，但是频繁出现在StackOverflow和Blog上。 接下来，我们就来解决2.3.1节中留下的几个问题。 先看第四个问题。为什么MSVC中，模板函数的定义内不管填什么编译器都不报错？因为MSVC在分析模板中成员函数定义时没有做任何事情。至于为啥连“大王叫我来巡山”都能过得去，这是C++语法/语义分析的特殊性导致的。 C++是个非常复杂的语言，以至于它的编译器，不可能通过词法-语法-语义多趟分析清晰分割，因为它的语义将会直接干扰到语法： void foo(){ A<T> b; } 在这段简短的代码中，就包含了两个歧义的可能，一是A是模板，于是A<T>是一个实例化的类型，b是变量，另外一种是比较表达式（Comparison Expression）的组合，((A < T) > b)。 甚至词法分析也会受到语义的干扰，C++11中才明确被修正的vector<vector<int>>，就因为>>被误解为右移或流操作符，而导致某些编译器上的错误。因此，在语义没有确定之前，连语法都没有分析的价值。 大约是基于如此考量，为了偷懒，MSVC将包括所有模板成员函数的语法/语义分析工作都挪到了第二个Phase，于是乎连带着语法分析都送进了第二个阶段。符合标准么？显然不符合。 但是这里值得一提的是，MSVC的做法和标准相比，虽然投机取巧，但并非有弊无利。我们来先说一说坏处。考虑以下例子： // ----------- X.h ------------ template <typename T> struct X { // 实现代码 }; // ---------- X.cpp ----------- // ... 一些代码 ... X<int> xi; // ... 一些代码 ... X<float> xf; // ... 一些代码 ... 此时如果X中有一些与模板参数无关的错误，如果名称查找/语义分析在两个阶段完成，那么这些错误会很早、且唯一的被提示出来；但是如果一切都在实例化时处理，那么可能会导致不同的实例化过程提示同样的错误。而模板在运用过程中，往往会产生很多实例，此时便会大量报告同样的错误。 当然，MSVC并不会真的这么做。根据推测，最终他们是合并（Merge）了相同的错误。因为即便对于模板参数相关的编译错误，也只能看到最后一次实例化的错误信息： template <typename T> struct X {}; template <typename T> struct Y { typedef X<T> ReboundType; // 类型定义1 void foo() { X<T> instance0; X<T>::MemberType instance1; WTF instance2 } }; void poo(){ Y<int>::foo(); Y<float>::foo(); } MSVC下和模板相关的错误只有一个： error C2039: 'MemberType': is not a member of 'X<T>' with [ T=float ] 然后是一些语法错误，比如MemberType不是一个合法的标识符之类的。这样甚至你会误以为int情况下模板的实例化是正确的。虽然在有了经验之后会发现这个问题挺荒唐的，但是仍然会让新手有困惑。 相比之下，更加遵守标准的Clang在错误提示上就要清晰许多： error: unknown type name 'WTF' WTF instance2 ^ error: expected ';' at end of declaration WTF instance2 ^ ; error: no type named 'MemberType' in 'X<int>' typename X<T>::MemberType instance1; ~~~~~~~~~~~~~~~^~~~~~~~~~ note: in instantiation of member function 'Y<int>::foo' requested here Y<int>::foo(); ^ error: no type named 'MemberType' in 'X<float>' typename X<T>::MemberType instance1; ~~~~~~~~~~~~~~~^~~~~~~~~~ note: in instantiation of member function 'Y<float>::foo' requested here Y<float>::foo(); ^ 4 errors generated. 可以看到，Clang的提示和标准更加契合。它很好地区分了模板在定义和实例化时分别产生的错误。 另一个缺点也与之类似。因为没有足够的检查，如果你写的模板没有被实例化，那么很可能缺陷会一直存在于代码之中。特别是模板代码多在头文件。虽然不如接口那么重要，但也是属于被公开的部分，别人很可能会踩到坑上。缺陷一旦传播开修复起来就没那么容易了。 但是正如我前面所述，这个违背了标准的特性，并不是一无是处。首先，它可以完美的兼容标准。符合标准的、能够被正确编译的代码，一定能够被MSVC的方案所兼容。其次，它带来了一个非常有趣的特性，看下面这个例子： struct A; template <typename T> struct X { int v; void convertTo(A& a) { a.v = v; // 这里需要A的实现 } }; struct A { int v; }; void main() { X<int> x; x.foo(5); } 这个例子在Clang中是错误的，因为： error: variable has incomplete type 'A' A a; ^ note: forward declaration of 'A' struct A; ^ 1 error generated. 符合标准的写法需要将模板类的定义，和模板函数的定义分离开： TODO 此处例子不够恰当，并且描述有歧义。需要在未来版本中修订。 struct A; template <typename T> struct X { int v; void convertTo(A& a); }; struct A { int v; }; template <typename T> void X<T>::convertTo(A& a) { a.v = v; } void main() { X<int> x; x.foo(5); } 但是其实我们知道，foo要到实例化之后，才需要真正的做语义分析。在MSVC上，因为函数实现就是到模板实例化时才处理的，所以这个例子是完全正常工作的。因此在上面这个例子中，MSVC的实现要比标准更加易于写和维护，是不是有点写Java/C#那种声明实现都在同一处的清爽感觉了呢！ 扩展阅读： The Dreaded Two-Phase Name Lookup 2.3.3 “多余的” typename 关键字 到了这里，2.3.1 中提到的四个问题，还有三个没有解决： template <typename T> struct X {}; template <typename T> struct Y { typedef X<T> ReboundType; // 这里为什么是正确的？ typedef typename X<T>::MemberType MemberType2; // 这里的typename是做什么的？ typedef UnknownType MemberType3; // 这里为什么会出错？ }; 我们运用我们2.3.2节中学习到的标准，来对Y内部做一下分析： template <typename T> struct Y { // X可以查找到原型； // X<T>是一个依赖性名称，模板定义阶段并不管X<T>是不是正确的。 typedef X<T> ReboundType; // X可以查找到原型； // X<T>是一个依赖性名称，X<T>::MemberType也是一个依赖性名称； // 所以模板声明时也不会管X模板里面有没有MemberType这回事。 typedef typename X<T>::MemberType MemberType2; // UnknownType 不是一个依赖性名称 // 而且这个名字在当前作用域中不存在，所以直接报错。 typedef UnknownType MemberType3; }; 下面，唯一的问题就是第二个：typename是做什么的？ 对于用户来说，这其实是一个语法噪音。也就是说，其实就算没有它，语法上也说得过去。事实上，某些情况下MSVC的确会在标准需要的时候，不用写typename。但是标准中还是规定了形如 T::MemberType 这样的qualified id 在默认情况下不是一个类型，而是解释为T的一个成员变量MemberType，只有当typename修饰之后才能作为类型出现。 事实上，标准对typename的使用规定极为复杂，也算是整个模板中的难点之一。如果想了解所有的标准，需要阅读标准14.6节下2-7条，以及14.6.2.1第一条中对于current instantiation的解释。 简单来说，如果编译器能在出现的时候知道它是一个类型，那么就不需要typename，如果必须要到实例化的时候才能知道它是不是合法，那么定义的时候就把这个名称作为变量而不是类型。 我们用一行代码来说明这个问题： a * b; 在没有模板的情况下，这个语句有两种可能的意思：如果a是一个类型，这就是定义了一个指针b，它拥有类型a*；如果a是一个对象或引用，这就是计算一个表达式a*b，虽然结果并没有保存下来。可是如果上面的a是模板参数的成员，会发生什么呢？ template <typename T> void meow() { T::a * b; // 这是指针定义还是表达式语句？ } 编译器对模板进行语法检查的时候，必须要知道上面那一行到底是个什么——这当然可以推迟到实例化的时候进行（比如VC，这也是上面说过VC可以不加typename的原因），不过那是另一个故事了——显然在模板定义的时候，编译器并不能妄断。因此，C++标准规定，在没有typename约束的情况下认为这里T::a不是类型，因此T::a * b; 会被当作表达式语句（例如乘法）；而为了告诉编译器这是一个指针的定义，我们必须在T::a之前加上typename关键字，告诉编译器T::a是一个类型，这样整个语句才能符合指针定义的语法。 在这里，我举几个例子帮助大家理解typename的用法，这几个例子已经足以涵盖日常使用（预览）： struct A; template <typename T> struct B; template <typename T> struct X { typedef X<T> _A; // 编译器当然知道 X<T> 是一个类型。 typedef X _B; // X 等价于 X<T> 的缩写 typedef T _C; // T 不是一个类型还玩毛 // ！！！注意我要变形了！！！ class Y { typedef X<T> _D; // X 的内部，既然外部高枕无忧，内部更不用说了 typedef X<T>::Y _E; // 嗯，这里也没问题，编译器知道Y就是当前的类型， // 这里在VS2015上会有错，需要添加 typename， // Clang 上顺利通过。 typedef typename X<T*>::Y _F; // 这个居然要加 typename！ // 因为，X<T*>和X<T>不一样哦， // 它可能会在实例化的时候被别的偏特化给抢过去实现了。 }; typedef A _G; // 嗯，没问题，A在外面声明啦 typedef B<T> _H; // B<T>也是一个类型 typedef typename B<T>::type _I; // 嗯，因为不知道B<T>::type的信息， // 所以需要typename typedef B<int>::type _J; // B<int> 不依赖模板参数， // 所以编译器直接就实例化（instantiate）了 // 但是这个时候，B并没有被实现，所以就出错了 }; 2.4 本章小结 这一章是写作中最艰难的一章，中间停滞了将近一年。因为要说清楚C++模板中一些语法噪音和设计决议并不是一件轻松的事情。不过通过这一章的学习，我们知道了下面这几件事情： 部分特化/偏特化 和 特化 相当于是模板实例化过程中的if-then-else。这使得我们根据不同类型，选择不同实现的需求得以实现； 在 2.3.3 一节我们插入了C++模板中最难理解的内容之一：名称查找。名称查找是语义分析的一个环节，模板内书写的 变量声明、typedef、类型名称 甚至 类模板中成员函数的实现 都要符合名称查找的规矩才不会出错； C++编译器对语义的分析的原则是“大胆假设，小心求证”：在能求证的地方尽量求证 —— 比如两段式名称查找的第一阶段；无法检查的地方假设你是正确的 —— 比如typedef typename A<T>::MemberType _X;在模板定义时因为T不明确不会轻易判定这个语句的死刑。 从下一章开始，我们将进入元编程环节。我们将使用大量的示例，一方面帮助巩固大家学到的模板知识，一方面也会引导大家使用函数式思维去解决常见的问题。 3 深入理解特化与偏特化 3.1 正确的理解偏特化 3.1.1 偏特化与函数重载的比较 在前面的章节中，我们介绍了偏特化的形式、也介绍了简单的用例。因为偏特化和函数重载存在着形式上的相似性，因此初学者便会借用重载的概念，来理解偏特化的行为。只是，重载和偏特化尽管相似但仍有差异。 我们来先看一个函数重载的例子： void doWork(int); void doWork(float); void doWork(int, int); void f() { doWork(0); doWork(0.5f); doWork(0, 0); } 在这个例子中，我们展现了函数重载可以在两种条件下工作：参数数量相同、类型不同；参数数量不同。 仿照重载的形式，我们通过特化机制，试图实现一个模板的“重载”： template <typename T> struct DoWork; // (0) 这是原型 template <> struct DoWork<int> {}; // (1) 这是 int 类型的"重载" template <> struct DoWork<float> {}; // (2) 这是 float 类型的"重载" template <> struct DoWork<int, int> {}; // (3) 这是 int, int 类型的“重载” void f(){ DoWork<int> i; DoWork<float> f; DoWork<int, int> ii; } 这个例子在字面上“看起来”并没有什么问题，可惜编译器在编译的时候仍然提示出错了goo.gl/zI42Zv： 5 : error: too many template arguments for class template 'DoWork' template <> struct DoWork<int, int> {}; // 这是 int, int 类型的“重载” ^ ~~~~ 1 : note: template is declared here template <typename T> struct DoWork {}; // 这是原型 ~~~~~~~~~~~~~~~~~~~~~ ^ 从编译出错的失望中冷静一下，在仔细看看函数特化/偏特化和一般模板的不同之处： template <typename T> class X {}; template <typename T> class X <T*> {}; // ^^^^ 注意这里 对，就是这个<T*>，跟在X后面的“小尾巴”，我们称作实参列表，决定了第二条语句是第一条语句的跟班。所以，第二条语句，即“偏特化”，必须要符合原型X的基本形式：那就是只有一个模板参数。这也是为什么DoWork尝试以template <> struct DoWork<int, int>的形式偏特化的时候，编译器会提示模板实参数量过多。 另外一方面，在类模板的实例化阶段，它并不会直接去寻找 template <> struct DoWork<int, int>这个小跟班，而是会先找到基本形式，template <typename T> struct DoWork;，然后再去寻找相应的特化。 我们以DoWork<int> i;为例，尝试复原一下编译器完成整个模板匹配过程的场景，帮助大家理解。看以下示例代码： template <typename T> struct DoWork; // (0) 这是原型 template <> struct DoWork<int> {}; // (1) 这是 int 类型的特化 template <> struct DoWork<float> {}; // (2) 这是 float 类型的特化 template <typename U> struct DoWork<U*> {}; // (3) 这是指针类型的偏特化 DoWork<int> i; // (4) DoWork<float*> pf; // (5) 首先，编译器分析(0), (1), (2)三句，得知(0)是模板的原型，(1)，(2)，(3)是模板(0)的特化或偏特化。我们假设有两个字典，第一个字典存储了模板原型，我们称之为TemplateDict。第二个字典TemplateSpecDict，存储了模板原型所对应的特化/偏特化形式。所以编译器在处理这几句时，可以视作 // 以下为伪代码 TemplateDict[DoWork<T>] = { DoWork<int>, DoWork<float>, DoWork<U*> }; 然后 (4) 试图以int实例化类模板DoWork。它会在TemplateDict中，找到DoWork，它有一个形式参数T接受类型，正好和我们实例化的要求相符合。并且此时T被推导为int。(5) 中的float*也是同理。 { // 以下为 DoWork<int> 查找对应匹配的伪代码 templateProtoInt = TemplateDict.find(DoWork, int); // 查找模板原型，查找到(0) template = templatePrototype.match(int); // 以 int 对应 int 匹配到 (1) } { // 以下为DoWork<float*> 查找对应匹配的伪代码 templateProtoIntPtr = TemplateDict.find(DoWork, float*) // 查找模板原型，查找到(0) template = templateProtoIntPtr.match(float*) // 以 float* 对应 U* 匹配到 (3)，此时U为float } 那么根据上面的步骤所展现的基本原理，我们随便来几个练习： template <typename T, typename U> struct X ; // 0 // 原型有两个类型参数 // 所以下面的这些偏特化的实参列表 // 也需要两个类型参数对应 template <typename T> struct X<T, T > {}; // 1 template <typename T> struct X<T*, T > {}; // 2 template <typename T> struct X<T, T* > {}; // 3 template <typename U> struct X<U, int> {}; // 4 template <typename U> struct X<U*, int> {}; // 5 template <typename U, typename T> struct X<U*, T* > {}; // 6 template <typename U, typename T> struct X<U, T* > {}; // 7 template <typename T> struct X<unique_ptr<T>, shared_ptr<T>>; // 8 // 以下特化，分别对应哪个偏特化的实例？ // 此时偏特化中的T或U分别是什么类型？ X<float*, int> v0; X<double*, int> v1; X<double, double> v2; X<float*, double*> v3; X<float*, float*> v4; X<double, float*> v5; X<int, double*> v6; X<int*, int> v7; X<double*, double> v8; 在上面这段例子中，有几个值得注意之处。首先，偏特化时的模板形参，和原型的模板形参没有任何关系。和原型不同，它的顺序完全不影响模式匹配的顺序，它只是偏特化模式，如<U, int>中U的声明，真正的模式，是由<U, int>体现出来的。 这也是为什么在特化的时候，当所有类型都已经确定，我们就可以抛弃全部的模板参数，写出template <> struct X<int, float>这样的形式：因为所有列表中所有参数都确定了，就不需要额外的形式参数了。 其次，作为一个模式匹配，偏特化的实参列表中展现出来的“样子”，就是它能被匹配的原因。比如，struct X<T, T>中，要求模板的两个参数必须是相同的类型。而struct X<T, T*>，则代表第二个模板类型参数必须是第一个模板类型参数的指针，比如X<float***, float****>就能匹配上。当然，除了简单的指针、const和volatile修饰符，其他的类模板也可以作为偏特化时的“模式”出现，例如示例8，它要求传入同一个类型的unique_ptr和shared_ptr。C++标准中指出下列模式都是可以被匹配的： N3337, 14.8.2.5/8 令T是模板类型实参或者类型列表（如 int, float, double 这样的，TT是template-template实参（参见6.2节），i是模板的非类型参数（整数、指针等），则以下形式的形参都会参与匹配： T, cv-list T, T*, template-name <T>, T&, T&& T [ integer-constant ] type (T), T(), T(T) T type ::*, type T::*, T T::* T (type ::*)(), type (T::*)(), type (type ::*)(T), type (T::*)(T), T (type ::*)(T), T (T::*)(), T (T::*)(T) type [i], template-name , TT<T>, TT, TT<> 对于某些实例化，偏特化的选择并不是唯一的。比如v4的参数是<float*, float*>，能够匹配的就有三条规则，1，6和7。很显然，6还是比7好一些，因为能多匹配一个指针。但是1和6，就很难说清楚谁更好了。一个说明了两者类型相同；另外一个则说明了两者都是指针。所以在这里，编译器也没办法决定使用那个，只好报出了编译器错误。 其他的示例可以先自己推测一下， 再去编译器上尝试一番：goo.gl/9UVzje。 3.1.2 不定长的模板参数 不过这个时候也许你还不死心。有没有一种办法能够让例子DoWork像重载一样，支持对长度不一的参数列表分别偏特化/特化呢？ 答案当然是肯定的。 首先，首先我们要让模板实例化时的模板参数统一到相同形式上。逆向思维一下，虽然两个类型参数我们很难缩成一个参数，但是我们可以通过添加额外的参数，把一个扩展成两个呀。比如这样： DoWork<int, void> i; DoWork<float, void> f; DoWork<int, int > ii; 这时，我们就能写出统一的模板原型： template <typename T0, typename T1> struct DoWork; 继而偏特化/特化问题也解决了： template <> struct DoWork<int, void> {}; // (1) 这是 int 类型的特化 template <> struct DoWork<float, void> {}; // (2) 这是 float 类型的特化 template <> struct DoWork<int, int> {}; // (3) 这是 int, int 类型的特化 显而易见这个解决方案并不那么完美。首先，不管是偏特化还是用户实例化模板的时候，都需要多撰写好几个void，而且最长的那个参数越长，需要写的就越多；其次，如果我们的DoWork在程序维护的过程中新加入了一个参数列表更长的实例，那么最悲惨的事情就会发生 —— 原型、每一个偏特化、每一个实例化都要追加上void以凑齐新出现的实例所需要的参数数量。 所幸模板参数也有一个和函数参数相同的特性：默认实参（Default Arguments）。只需要一个例子，你们就能看明白了goo.gl/TtmcY9： template <typename T0, typename T1 = void> struct DoWork; template <typename T> struct DoWork<T> {}; template <> struct DoWork<int> {}; template <> struct DoWork<float> {}; template <> struct DoWork<int, int> {}; DoWork<int> i; DoWork<float> f; DoWork<double> d; DoWork<int, int> ii; 所有参数不足，即原型中参数T1没有指定的地方，都由T1自己的默认参数void补齐了。 但是这个方案仍然有些美中不足之处。 比如，尽管我们默认了所有无效的类型都以void结尾，所以正确的类型列表应该是类似于<int, float, char, void, void>这样的形态。但你阻止不了你的用户写出类似于<void, int, void, float, char, void, void>这样不符合约定的类型参数列表。 其次，假设这段代码中有一个函数，它的参数使用了和类模板相同的参数列表类型，如下面这段代码： template <typename T0, typename T1 = void> struct X { static void call(T0 const& p0, T1 const& p1); // 0 }; template <typename T0> struct X<T0> { static void call(T0 const& p0); // 1 }; void foo(){ X<int>::call(5); // 调用函数 1 X<int, float>::call(5, 0.5f); // 调用函数 0 } 那么，每加一个参数就要多写一个偏特化的形式，甚至还要重复编写一些可以共享的实现。 不过不管怎么说，以长参数加默认参数的方式支持变长参数是可行的做法，这也是C++98/03时代的唯一选择。 例如，Boost.Tuple就使用了这个方法，支持了变长的Tuple： // Tuple 的声明，来自 boost struct null_type; template < class T0 = null_type, class T1 = null_type, class T2 = null_type, class T3 = null_type, class T4 = null_type, class T5 = null_type, class T6 = null_type, class T7 = null_type, class T8 = null_type, class T9 = null_type> class tuple; // Tuple的一些用例 tuple<int> a; tuple<double&, const double&, const double, double*, const double*> b; tuple<A, int(*)(char, int), B(A::*)(C&), C> c; tuple<std::string, std::pair<A, B> > d; tuple<A*, tuple<const A*, const B&, C>, bool, void*> e; 此外，Boost.MPL也使用了这个手法将boost::mpl::vector映射到boost::mpl::vector _n_上。但是我们也看到了，这个方案的缺陷很明显：代码臃肿和潜在的正确性问题。此外，过度使用模板偏特化、大量冗余的类型参数也给编译器带来了沉重的负担。 为了缓解这些问题，在C++11中，引入了变参模板（Variadic Template）。我们来看看支持了变参模板的C++11是如何实现tuple的： template <typename... Ts> class tuple; 是不是一下子简洁了很多！这里的typename... Ts相当于一个声明，是说Ts不是一个类型，而是一个不定常的类型列表。同C语言的不定长参数一样，它通常只能放在参数列表的最后。看下面的例子： template <typename... Ts, typename U> class X {}; // (1) error! template <typename... Ts> class Y {}; // (2) template <typename... Ts, typename U> class Y<U, Ts...> {}; // (3) template <typename... Ts, typename U> class Y<Ts..., U> {}; // (4) error! 为什么第(1)条语句会出错呢？(1)是模板原型，模板实例化时，要以它为基础和实例化时的类型实参相匹配。因为C++的模板是自左向右匹配的，所以不定长参数只能结尾。其他形式，无论写作Ts, U，或者是Ts, V, Us,，或者是V, Ts, Us都是不可取的。(4) 也存在同样的问题。 但是，为什么(3)中， 模板参数和(1)相同，都是typename... Ts, typename U，但是编译器却并没有报错呢？ 答案在这一节的早些时候。(3)和(1)不同，它并不是模板的原型，它只是Y的一个偏特化。回顾我们在之前所提到的，偏特化时，模板参数列表并不代表匹配顺序，它们只是为偏特化的模式提供的声明，也就是说，它们的匹配顺序，只是按照<U, Ts...>来，而之前的参数只是告诉你Ts是一个类型列表，而U是一个类型，排名不分先后。 在这里，我们只提到了变长模板参数的声明，如何使用我们将在第四章讲述。 3.1.3 模板的默认实参 在上一节中，我们介绍了模板对默认实参的支持。当时我们的例子很简单，默认模板实参是一个确定的类型void或者自定义的null_type： template < typename T0, typename T1 = void, typename T2 = void > class Tuple; 实际上，模板的默认参数不仅仅可以是一个确定的类型，它还能是以其他类型为参数的一个类型表达式。 考虑下面的例子：我们要执行两个同类型变量的除法，它对浮点、整数和其他类型分别采取不同的措施。 对于浮点，执行内置除法；对于整数，要处理除零保护，防止引发异常；对于其他类型，执行一个叫做CustomeDiv的函数。 第一步，我们先把浮点正确的写出来： #include <type_traits> template <typename T> T CustomDiv(T lhs, T rhs) { // Custom Div的实现 } template <typename T, bool IsFloat = std::is_floating_point<T>::value> struct SafeDivide { static T Do(T lhs, T rhs) { return CustomDiv(lhs, rhs); } }; template <typename T> struct SafeDivide<T, true>{ // 偏特化A static T Do(T lhs, T rhs){ return lhs/rhs; } }; template <typename T> struct SafeDivide<T, false>{ // 偏特化B static T Do(T lhs, T rhs){ return lhs; } }; void foo(){ SafeDivide<float>::Do(1.0f, 2.0f); // 调用偏特化A SafeDivide<int>::Do(1, 2); // 调用偏特化B } 在实例化的时候，尽管我们只为SafeDivide指定了参数T，但是它的另一个参数IsFloat在缺省的情况下，可以根据T，求出表达式std::is_floating_point<T>::value的值作为实参的值，带入到SafeDivide的匹配中。 嗯，这个时候我们要再把整型和其他类型纳入进来，无外乎就是加这么一个参数goo.gl/0Lqywt： #include <complex> #include <type_traits> template <typename T> T CustomDiv(T lhs, T rhs) { T v; // Custom Div的实现 return v; } template < typename T, bool IsFloat = std::is_floating_point<T>::value, bool IsIntegral = std::is_integral<T>::value > struct SafeDivide { static T Do(T lhs, T rhs) { return CustomDiv(lhs, rhs); } }; template <typename T> struct SafeDivide<T, true, false>{ // 偏特化A static T Do(T lhs, T rhs){ return lhs/rhs; } }; template <typename T> struct SafeDivide<T, false, true>{ // 偏特化B static T Do(T lhs, T rhs){ return rhs == 0 ? 0 : lhs/rhs; } }; void foo(){ SafeDivide<float>::Do(1.0f, 2.0f); // 调用偏特化A SafeDivide<int>::Do(1, 2); // 调用偏特化B SafeDivide<std::complex<float>>::Do({1.f, 2.f}, {1.f, -2.f}); // 调用一般形式 } 当然，这时也许你会注意到，is_integral，is_floating_point和其他类类型三者是互斥的，那能不能只使用一个条件量来进行分派呢？答案当然是可以的：goo.gl/jYp5J2： #include <complex> #include <type_traits> template <typename T> T CustomDiv(T lhs, T rhs) { T v; // Custom Div的实现 return v; } template <typename T, typename Enabled = std::true_type> struct SafeDivide { static T Do(T lhs, T rhs) { return CustomDiv(lhs, rhs); } }; template <typename T> struct SafeDivide< T, typename std::is_floating_point<T>::type>{ // 偏特化A static T Do(T lhs, T rhs){ return lhs/rhs; } }; template <typename T> struct SafeDivide< T, typename std::is_integral<T>::type>{ // 偏特化B static T Do(T lhs, T rhs){ return rhs == 0 ? 0 : lhs/rhs; } }; void foo(){ SafeDivide<float>::Do(1.0f, 2.0f); // 调用偏特化A SafeDivide<int>::Do(1, 2); // 调用偏特化B SafeDivide<std::complex<float>>::Do({1.f, 2.f}, {1.f, -2.f}); } 我们借助这个例子，帮助大家理解一下这个结构是怎么工作的： 对SafeDivide<int> 通过匹配类模板的泛化形式，计算默认实参，可以知道我们要匹配的模板实参是SafeDivide<int, true_type> 计算两个偏特化的形式的匹配：A得到<int, false_type>,和B得到 <int, true_type> 最后偏特化B的匹配结果和模板实参一致，使用它。 针对SafeDivide<complex<float>> 通过匹配类模板的泛化形式，可以知道我们要匹配的模板实参是SafeDivide<complex<float>, true_type> 计算两个偏特化形式的匹配：A和B均得到SafeDivide<complex<float>, false_type> A和B都与模板实参无法匹配，所以使用原型，调用CustomDiv 3.2 后悔药：SFINAE 考虑下面这个函数模板： template <typename T, typename U> void foo(T t, typename U::type u) { // ... } 到本节为止，我们所有的例子都保证了一旦咱们敲定了模板参数中 T 和 U，函数参变量 t 和 u 的类型都是成立的，比如下面这样： struct X { typedef float type; }; template <typename T, typename U> void foo(T t, typename U::type u) { // ... } void callFoo() { foo<int, X>(5, 5.0); // T == int, typename U::type == X::type == float } 那么这里有一个可能都不算是问题的问题 —— 对于下面的代码，你认为它会提示怎么样的错误： struct X { typedef float type; }; struct Y { typedef float type2; }; template <typename T, typename U> void foo(T t, typename U::type u) { // ... } void callFoo() { foo<int, X>(5, 5.0); // T == int, typename U::type == X::type == float foo<int, Y>(5, 5.0); // ??? } 这个时候你也许会说：啊，这个简单，Y 没有 type 这个成员自然会出错啦！嗯，这个时候咱们来看看Clang给出的结果： error: no matching function for call to 'foo' foo<int, Y>(5, 5.0); // ??? ^~~~~~~~~~~ note: candidate template ignored: substitution failure [with T = int, U = Y]: no type named 'type' in 'Y' void foo(T t, typename U::type u) { 完整翻译过来就是，直接的出错原因是没有匹配的 foo 函数，间接原因是尝试用 [T = int, U = y] 做类型替换的时候失败了，所以这个函数模板就被忽略了。等等，不是出错，而是被忽略了？那么也就是说，只要有别的能匹配的类型兜着，编译器就无视这里的失败了？ 银河火箭队的阿喵说，就是这样。不信邪的朋友可以试试下面的代码： struct X { typedef float type; }; struct Y { typedef float type2; }; template <typename T, typename U> void foo(T t, typename U::type u) { // ... } template <typename T, typename U> void foo(T t, typename U::type2 u) { // ... } void callFoo() { foo<int, X>(5, 5.0); // T == int, typename U::type == X::type == float foo<int, Y>( 1, 1.0 ); // ??? } 这下相信编译器真的是不关心替换失败了吧。我们管这种只要有正确的候选，就无视替换失败的做法为SFINAE。 我们不用纠结这个词的发音，它来自于 Substitution failure is not an error 的首字母缩写。这一句之乎者也般难懂的话，由之乎者 —— 啊，不，Substitution，Failure和Error三个词构成。 我们从最简单的词“Error”开始理解。Error就是一般意义上的编译错误。一旦出现编译错误，大家都知道，编译器就会中止编译，并且停止接下来的代码生成和链接等后续活动。 其次，我们再说“Failure”。很多时候光看字面意思，很多人会把 Failure 和 Error 等同起来。但是实际上Failure很多场合下只是一个中性词。比如我们看下面这个虚构的例子就知道这两者的区别了。 假设我们有一个语法分析器，其中某一个规则需要匹配一个token，它可以是标识符，字面量或者是字符串，那么我们会有下面的代码： switch(token) { case IDENTIFIER: // do something break; case LITERAL_NUMBER: // do something break; case LITERAL_STRING: // do something break; default: throw WrongToken(token); } 假如我们当前的token是 LITERAL_STRING 的时候，那么第一步它在匹配 IDENTIFIER 时，我们可以认为它失败（failure）了，但是它在第三步就会匹配上，所以它并不是一个错误。 但是如果这个token既不是标识符、也不是数字字面量、也不是字符串字面量，而且我们的语法规定除了这三类值以外其他统统都是非法的时，我们才认为它是一个error。 大家所熟知的函数重载也是如此。比如说下面这个例子： struct A {}; struct B: public A {}; struct C {}; void foo(A const&) {} void foo(B const&) {} void callFoo() { foo( A() ); foo( B() ); foo( C() ); } 那么 foo( A() ) 虽然匹配 foo(B const&) 会失败，但是它起码能匹配 foo(A const&)，所以它是正确的；foo( B() ) 能同时匹配两个函数原型，但是 foo(B const&) 要更好一些，因此它选择了这个原型。而 foo( C() ); 因为两个函数都匹配失败（Failure）了，所以它找不到相应的原型，这时才会报出一个编译器错误（Error）。 所以到这里我们就明白了，在很多情况下，Failure is not an error。编译器在遇到Failure的时候，往往还需要尝试其他的可能性。 好，现在我们把最后一个词，Substitution，加入到我们的字典中。现在这句话的意思就是说，我们要把 Failure is not an error 的概念，推广到Substitution阶段。 所谓substitution，就是将函数模板中的形参，替换成实参的过程。概念很简洁但是实现却颇多细节，所以C++标准中对这一概念的解释比较拗口。它分别指出了以下几点： 什么时候函数模板会发生实参 替代（Substitute） 形参的行为； 什么样的行为被称作 Substitution； 什么样的行为不可以被称作 Substitution Failure —— 他们叫SFINAE error。 我们在此不再详述，有兴趣的同学可以参照这里，这是标准的一个精炼版本。这里我们简单的解释一下。 考虑我们有这么个函数签名： template < typename T0, // 一大坨其他模板参数 typename U = /* 和前面T有关的一大坨 */ > RType /* 和模板参数有关的一大坨 */ functionName ( PType0 /* PType0 是和模板参数有关的一大坨 */, PType1 /* PType1 是和模板参数有关的一大坨 */, // ... 其他参数 ) { // 实现，和模板参数有关的一大坨 } 那么，在这个函数模板被实例化的时候，所有函数签名上的“和模板参数有关的一大坨”被推导出具体类型的过程，就是替换。一个更具体的例子来解释上面的“一大坨”： template < typename T, typename U = typename vector<T>::iterator // 1 > typename vector<T>::value_type // 1 foo( T*, // 1 T&, // 1 typename T::internal_type, // 1 typename add_reference<T>::type, // 1 int // 这里都不需要 substitution ) { // 整个实现部分，都没有 substitution。这个很关键。 } 所有标记为 1 的部分，都是需要替换的部分，而它们在替换过程中的失败（failure），就称之为替换失败（substitution failure）。 下面的代码是提供了一些替换成功和替换失败的示例： struct X { typedef int type; }; struct Y { typedef int type2; }; template <typename T> void foo(typename T::type); // Foo0 template <typename T> void foo(typename T::type2); // Foo1 template <typename T> void foo(T); // Foo2 void callFoo() { foo<X>(5); // Foo0: Succeed, Foo1: Failed, Foo2: Failed foo<Y>(10); // Foo0: Failed, Foo1: Succeed, Foo2: Failed foo<int>(15); // Foo0: Failed, Foo1: Failed, Foo2: Succeed } 在这个例子中，当我们指定 foo<Y> 的时候，substitution就开始工作了，而且会同时工作在三个不同的 foo 签名上。如果我们仅仅因为 Y 没有 type，匹配 Foo0 失败了，就宣布代码有错，中止编译，那显然是武断的。因为 Foo1 是可以被正确替换的，我们也希望 Foo1 成为 foo<Y> 的原型。 std/boost库中的 enable_if 是 SFINAE 最直接也是最主要的应用。所以我们通过下面 enable_if 的例子，来深入理解一下 SFINAE 在模板编程中的作用。 假设我们有两个不同类型的计数器（counter），一种是普通的整数类型，另外一种是一个复杂对象，它从接口 ICounter 继承，这个接口有一个成员叫做increase实现计数功能。现在，我们想把这两种类型的counter封装一个统一的调用：inc_counter。那么，我们直觉会简单粗暴的写出下面的代码： struct ICounter { virtual void increase() = 0; virtual ~ICounter() {} }; struct Counter: public ICounter { void increase() override { // Implements } }; template <typename T> void inc_counter(T& counterObj) { counterObj.increase(); } template <typename T> void inc_counter(T& intTypeCounter){ ++intTypeCounter; } void doSomething() { Counter cntObj; uint32_t cntUI32; // blah blah blah inc_counter(cntObj); inc_counter(cntUI32); } 我们非常希望它展现出预期的行为。因为其实我们是知道对于任何一个调用，两个 inc_counter 只有一个是能够编译正确的。“有且唯一”，我们理应当期望编译器能够挑出那个唯一来。 可惜编译器做不到这一点。首先，它就告诉我们，这两个签名 template <typename T> void inc_counter(T& counterObj); template <typename T> void inc_counter(T& intTypeCounter); 其实是一模一样的。我们遇到了 redefinition。 我们看看 enable_if 是怎么解决这个问题的。我们通过 enable_if 这个 T 对于不同的实例做个限定： template <typename T> void inc_counter( T& counterObj, typename std::enable_if< std::is_base_of<ICounter, T>::value >::type* = nullptr ); template <typename T> void inc_counter( T& counterInt, typename std::enable_if< std::is_integral<T>::value >::type* = nullptr ); 然后我们解释一下，这个 enable_if 是怎么工作的，语法为什么这么丑： 首先，替换（substitution）只有在推断函数类型的时候，才会起作用。推断函数类型需要参数的类型，所以， typename std::enable_if<std::is_integral<T>::value>::type 这么一长串代码，就是为了让 enable_if 参与到函数类型中； 其次， is_integral<T>::value 返回一个布尔类型的编译器常数，告诉我们它是或者不是一个 integral type，enable_if<C> 的作用就是，如果这个 C 值为 True，那么 enable_if<C>::type 就会被推断成一个 void 或者是别的什么类型，让整个函数匹配后的类型变成 void inc_counter<int>(int & counterInt, void* dummy = nullptr); 如果这个值为 False ，那么 enable_if<false> 这个特化形式中，压根就没有这个 ::type，于是替换就失败了。和我们之前的例子中一样，这个函数原型就不会被产生出来。 所以我们能保证，无论对于 int 还是 counter 类型的实例，我们都只有一个函数原型通过了substitution —— 这样就保证了它的“有且唯一”，编译器也不会因为你某个替换失败而无视成功的那个实例。 这个例子说到了这里，熟悉C++的你，一定会站出来说我们只要把第一个签名改成： void inc_counter(ICounter& counterObj); 就能完美解决这个问题了，根本不需要这么复杂的编译器机制。 嗯，你说的没错，在这里这个特性一点都没用。 这也提醒我们，当你觉得需要写 enable_if 的时候，首先要考虑到以下可能性： 重载（对模板函数） 偏特化（对模板类而言） 虚函数 但是问题到了这里并没有结束。因为 increase 毕竟是个虚函数。假如 Counter 需要调用的地方实在是太多了，这个时候我们会非常期望 increase 不再是个虚函数以提高性能。此时我们会调整继承层级： struct ICounter {}; struct Counter: public ICounter { void increase() { // impl } }; 那么原有的 void inc_counter(ICounter& counterObj) 就无法再执行下去了。这个时候你可能会考虑一些变通的办法： template <typename T> void inc_counter(ICounter& c) {}; template <typename T> void inc_counter(T& c) { ++c; }; void doSomething() { Counter cntObj; uint32_t cntUI32; // blah blah blah inc_counter(cntObj); // 1 inc_counter(static_cast<ICounter&>(cntObj)); // 2 inc_counter(cntUI32); // 3 } 对于调用 1，因为 cntObj 到 ICounter 是需要类型转换的，所以比 void inc_counter(T&) [T = Counter] 要更差一些。然后它会直接实例化后者，结果实现变成了 ++cntObj，BOOM！ 那么我们做 2 试试看？嗯，工作的很好。但是等等，我们的初衷是什么来着？不就是让 inc_counter 对不同的计数器类型透明吗？这不是又一夜回到解放前了？ 所以这个时候，就能看到 enable_if 是如何通过 SFINAE 发挥威力的了： #include <type_traits> #include <utility> #include <cstdint> struct ICounter {}; struct Counter: public ICounter { void increase() { // impl } }; template <typename T> void inc_counter( T& counterObj, typename std::enable_if< std::is_base_of<ICounter, T>::value >::type* = nullptr ){ counterObj.increase(); } template <typename T> void inc_counter( T& counterInt, typename std::enable_if< std::is_integral<T>::value >::type* = nullptr ){ ++counterInt; } void doSomething() { Counter cntObj; uint32_t cntUI32; // blah blah blah inc_counter(cntObj); // OK! inc_counter(cntUI32); // OK! } 这个代码是不是看起来有点脏脏的。眼尖的你定睛一瞧，咦， ICounter 不是已经空了吗，为什么我们还要用它作为基类呢？ 这是个好问题。在本例中，我们用它来区分一个counter是不是继承自ICounter。最终目的，是希望知道 counter 有没有 increase 这个函数。 所以 ICounter 只是相当于一个标签（Tag）。而于情于理这个标签都是个累赘。但是在C++11之前，我们并没有办法去写类似于： template <typename T> void foo(T& c, decltype(c.increase())* = nullptr); 这样的函数签名，因为假如 T 是 int，那么 c.increase() 这个函数调用就不存在。但它又不属于Type Failure，而是一个Expression Failure，在C++11之前它会直接导致编译器出错，这并不是我们所期望的。所以我们才退而求其次，用一个类似于标签的形式来提供我们所需要的类型信息。以后的章节，后面我们会说到，这种和类型有关的信息我们可以称之为 type traits。 到了C++11，它正式提供了 Expression SFINAE，这时我们就能抛开 ICounter 这个无用的Tag，直接写出我们要写的东西： struct Counter { void increase() { // Implements } }; template <typename T> void inc_counter(T& intTypeCounter, std::decay_t<decltype(++intTypeCounter)>* = nullptr) { ++intTypeCounter; } template <typename T> void inc_counter(T& counterObj, std::decay_t<decltype(counterObj.increase())>* = nullptr) { counterObj.increase(); } void doSomething() { Counter cntObj; uint32_t cntUI32; // blah blah blah inc_counter(cntObj); inc_counter(cntUI32); } 此外，还有一种情况只能使用 SFINAE，而无法使用包括继承、重载在内的任何方法，这就是Universal Reference。比如， // 这里的a是个通用引用，可以准确的处理左右值引用的问题。 template <typename ArgT> void foo(ArgT&& a); 假如我们要限定ArgT只能是 float 的衍生类型，那么写成下面这个样子是不对的，它实际上只能接受 float 的右值引用。 void foo(float&& a); 此时的唯一选择，就是使用Universal Reference，并增加 enable_if 限定类型，如下面这样： template <typename ArgT> void foo( ArgT&& a, typename std::enabled_if< std::is_same<std::decay_t<ArgT>, float>::value >::type* = nullptr ); 从上面这些例子可以看到，SFINAE最主要的作用，是保证编译器在泛型函数、偏特化、及一般重载函数中遴选函数原型的候选列表时不被打断。除此之外，它还有一个很重要的元编程作用就是实现部分的编译期自省和反射。 虽然它写起来并不直观，但是对于既没有编译器自省、也没有Concept的C++11来说，已经是最好的选择了。 （补充例子：构造函数上的enable_if） !!! 以下章节未完成 !!! 4 元编程下的数据结构与算法 4.1 表达式与数值计算 4.1 获得类型的属性——类型萃取（Type Traits） 4.2 列表与数组 4.3 字典结构 4.4 “快速”排序 4.5 其它常用的“轮子” 5 模板的进阶技巧 5.1 嵌入类 5.2 Template-Template Class 5.3 高阶函数 5.4 闭包：模板的“基于对象” stl allocator? mpl::apply 5.5 占位符(placeholder)：在C++中实现方言的基石 5.6 编译期“多态” 6 模板的威力：从foreach, transform到Linq 6.1 Foreach与Transform 6.2 Boost中的模板 Any Spirit Hana TypeErasure 6.3 Reactor、Linq与C++中的实践 6.4 更高更快更强：从Linq到FP 7 结语：讨论有益，争端无用 7.1 更好的编译器，更友善的出错信息 7.2 模板的症结：易于实现，难于完美 7.3 一些期望 alexandrescu 关于 min max 的讨论：《再谈Min和Max》 std::experimental::any / boost.any 对于 reference 的处理
tuple 模板是 pair 模板的泛化，但允许定义 tuple 模板的实例，可以封装不同类型的任意数量的对象，因此 tuple 实例可以有任意数量的模板类型参数（Parameter）。tuple 模板定义在 tuple 头文件中。 tuple 这个术语也适用于很多其他的场景，例如数据库，这里一个 tuple 就是由一些类型的不同数据项组成的，这和 tuple 的概念相似。tuple 对象有很多用途。当需要将多个对象当作一个对象传给函数时，tuple 类型是很有用的。 tuple 的操作 生成 tuple 对象的最简单方式是使用定义在 tuple 头文件中的辅助函数 make_tuple()。这个函数可以接受不同类型的任意个数的参数，返回的 tuple 的类型由参数的类型决定。例如： auto my_tuple = std::make_tuple ( Name{"Peter"，"Piper"}, 42, std::string{"914 626 7890"} ); my_tuple 对象是 tuple<Name，int，string> 类型，因为模板类型参数是由 make_tuple() 函数的参数推导出来的。如果提供给 make_tuple() 的第三个参数是一个字符串常量，my_tuple 的类型将是 tuple<Name,int,const*>，这和之前的不同。 tuple 对象的构造函数提供了可能会用到的每一种选择。例如： std::tuple<std::string, size_t> my_tl;//Default initialization std:: tuple<Name, std::string> my_t2 {Name {"Andy", "Capp"},std::string{“Programmer”}}; std::tuple<Name,std::string> copy_my_t2{my_t2}; // Copy constructor std::tuple<std::string, std::string> my_t3 {"this", "that"}; // Implicit conversion tuple 中的对象由默认构造函数用默认值初始化。为 my_t2 调用的构造函数将参数移到 tuple 的元素中。下一条语句会调用拷贝构造函数来生成 tuple，在最后一个构造函数调用中，将参数隐式转换为 string 类型并生成了一个 tuple 元素。 也可以用 pair 对象构造 tuple 对象，pair 可以是左值，也可以是右值。显然，tuple 只能有两个元素。下面有两个示例： auto the_pair = std::make_pair("these","those"); std::tuple<std::string, std::string> my_t4 {the_pair}; std::tuple<std::string, std::string> my_t5 {std::pair <std::string, std::string > { "this", "that"} }; 第二条语句从 the_pair 生成了一个 tuple，它是一个左值。the_pair 的成员变量 first 和 second 可以隐式转换为这个 tuple 中的元素的类型。最后一条语句从右值 pair 对象生成了一个 tuple。 可以用任何比较运算符来比较相同类型的 tuple 对象。tuple 对象中的元素是按照字典顺序比较的。例如： std::cout << std::boolalpha << (my_t4 < my_t5) << std::endl; tuple 对象中的元素是依次比较的，第一个不同的元素决定了比较结果。my_t4 的第一个元素小于 my_t5 的第一个元素，因此比较结果为 true。如果是相等比较，任何一对不相等的对应元素都会使比较结果为 false。 tuple 对象的成员函数 swap() 可以将它的元素和参数交换。参数的类型必须和 tuple 对象的类型一致。例如： my_t4.swap (my_t5); 通过调用成员函数 swap() 来交换 my_t4 和 my_t5 对应的元素。显然，tuple 中所有元素的类型都必须是可交换的，tuple 头文件中定义了一个全局的 swap() 函数，它能够以相同的方式交换两个 tuple 对象的元素。 因为 tuple 是 pair 的泛化，所以它的工作方式不同。pair 的对象个数是固定的，因此它们有成员名。tuple 中的对象数目是不固定的，所以访问它们的机制必须能够满足这种情况。函数模板 get() 可以返回 tuple 中的一个元素。第一个模板类型参数是 size_t 类型值，它 是 tuple 中元素的索引（Index），因此 0 会选择 tuple 中的第一个元素，1 会选择第二个元素，以此类推。get() 模板剩下的类型参数是和 tuple 的参数同样推导的。下面是一个使用 get() 和索引来获取元素的示例： auto my_tuple = std::make_tuple (Name {"Peter","Piper"}, 42, std::string{"914 626 7890"}); std::cout << std::get<0>(my_tuple) << "age = " << std::get<1>(my_tuple) << " tel: " << std::get<2>(my_tuple) << std::endl; 在输出语句中第一次调用 get() 时返回了 my_tuple 中第一个元素的引用（ref），它是一个 Name 对象，第二次调用 get() 时返回了下一个元素的引用，它是一个整数；第三次调用 get() 时返回了第三个元素的引用，它是一个 string 对象。因此输出结果是： Peter Piper age = 42 tel: 914 626 7890 也可以用基于类型的 get() 从 tuple 获取元素，但要求 tuple 中只有一个这种类型的元素。例如： auto my_tuple = std::make_tuple(Name{"Peter", "Piper"}, 42, std::string {"914 626 7890"}); std::cout << std::get<Name>(my_tuple) <<" age = " << std::get<int> (my_tuple) << " tel: " << std::get<std::string>(my_tuple) << std::endl; 如果 tuple 中包含的 get() 类型参数值的元素不止一个，代码就无法编译（Compiler）通过。这里 tuple 的全部 3 个成员为不同类型，所以可以正常使用。 全局的 tie() 函数模板定义在 tuple 头文件中，它提供了另一种访问 tuple 元素的方式。这个函数可以把 tuple 中的元素值转换为可以绑定到 tie() 的左值集合。tie() 的模板类型参数是从函数参数中推导的。例如： auto my_tuple = std::make_tuple (Name{"Peter","Piper"}, 42, std::string{"914 626 7890"}); Name name {}; size_t age {}; std::string phone {}; std::tie (name, age, phone) = my_tuple; 在最后一条语句中，赋值运算符的左操作数表达式会返回一个参数的 tuple 引用。因此，赋值运算符左右的操作数都是 tuple 对象，并且用 my_tuple 中的元素值来对 tie() 参数中的变量赋值。我们可能并不想存储每一个元素的值。下面展示了如何只保存 my_tuple 中 name 和 phone 的值： std::tie(name, std::ignore,phone) = my_tuple; ignore 定义在 tuple 中，它被用来标记 tie() 函数中要被忽略的值。tuple 中被忽略的元素的值将不会被记录下来。在这个示例中只复制了第一个和第三个元素。 也可以用 tie() 函数来实现对类的数据成员的字典比较。例如，可以在 Name 类中实现 operator<() 函数： bool Name::operator<(const Name& name) const { return std::tie(second, first) < std::tie(name.second, name.first); } 在这个函数体中，调用 tie() 得到的 tuple 对象的元素是按顺序比较的。用 < 运算符来比较连续的元素对，出现的第一对不同值会决定比较的结果；这个表达式的比较结果就是不同元素的比较结果。如果全部元素都相等或等价，那么结果为 false。
《C++ Primer》5th 读书笔记 虽然说是这本书的笔记，但是还是会引入一些书外面的概念和新版标准的部分内容 对于不属于这本书的特殊的地方我会额外加以标注 [TOC] 第 1 章 开始 C++ 超级基础（Base）， 可以看我之前写的关于c++的必知必会的文章 UB(Undefined-Behaviors) 未定义行为 char 是 signed char 还是 unsigned char 是未定义的 int 是大于等于 short 小于等于 long 的 流 流可以作为 condition，用于判断是否到了流末尾，当到达流末尾时为 false，所以我们经常可以看到如下的写法 int n; while (std::cin >> n) { // do somthing... } 此时调用了 std::cin 类的 >> 函数，往 n 中输入数据，返回的是 std::cin 类的 istream 对象，到达流末尾时（通常这个标记为 EOF(End-Of-File)），在windows上可通过 Ctrl-z 和 Ctrl-d 输入 EOF 符号，标志流结束。 >> 作为一个函数，同理 std::cout << "Hello World" << std::endl; 的 << 也是一个函数，但是你会发现，其中存在多次调用，因为 std::cout<< 的返回值是一个 ostream 对象，即 std::cout 本身，所以实现了上面这样子的连续调用，但实际上，这个操作可以像下面这样分解， std::cout << "Hello World"; std::cout << std::endl; 这两种写法是完全等价的，于是就引出了一个问题，线程安全，因为，这个操作可以被等价分成两份，所以它的操作是不原子的，就可能在别的线程中，被插入，造成输出顺序混乱，比如输出了 Hello World123123\n 但是你想要输出的是 Hello World\n123123 其中，上面的\n的是转义字符，让换行看起来更加明显。解决办法也是有的，使用原子锁，但是这个内容是在后面学习多线程时才会讲到的，所以这里不加以赘述。 字面量 字面量大致可以分为两种，一种是语言提供的字面量，一种是库提供的字面量 语言提供的字面量，例如（其实我也没有仔细研究过具体哪些属于哪些，反正把自己知道的都列出来了） // 指针字面量 nullptr; // 布尔字面量 true;false; // 整数字面量 auto a = 1; // int a auto b = 0x1; // int b auto c = 01; // int c // 二进制字面量在 c++14 中引入 auto d = 0b1; // int d auto e = 1u; // unsigned int e auto f = 1ll; // long long f auto uf= 1ull; // unsigned long long f auto g = 1l; // long g // 其实这些后缀大小写都是可以的，为了方便书写，这里都写小写 // 浮点数字面量 auto h = 1.0l; // long double h auto i = 1e-1; // double i auto j = 1.0f; // float j auto k = 1e-1f; // float k // 字符(串)字面量 auto l = "Hello"; // const char *l auto m = u"World"; // const char16_t *m auto n = U"你好"; // const char32_t *n auto o = u8"世界"; // const char8_t *o auto p = L'！'; // wchar_t p auto q = '!'; // char q 但实际上，部分字面量会根据自己的数据大小自动变更数据类型，如果数据超过了long所能承载的范围，就会自动变为 long long，类型都是所能承受的最小类型，当然，char和short不在此列； 用户自定义字面量 使用运算符重载的方式 auto operator"" end(something) { } 就可以弄一个 somethingend 的一个字面量，something 作为参数（Parameter）传入 函数，处理后返回 第 I 部分 C++ 基础 第 2 章 变量和基本类型 初始化与赋值 其实这个是老生常谈的问题了，因为总是有非常多的事情，在这个上面纠结 int a = 10; // mov DWORD PTR [rbp-4], 10 int b; // int d = a; // mov eax, DWORD PTR [rbp-4] // mov DWORD PTR [rbp-8], eax int c = b; // mov eax, DWORD PTR [rbp-12] // mov DWORD PTR [rbp-16], eax b = 10; // mov DWORD PTR [rbp-12], 10 左侧为 c++ 代码，右侧为生成的汇编。这就很神奇了，你发现第二行定义变量 b 的时候，没有生成任何代码。在你尝试书写 int a = 10; // mov DWORD PTR [rbp-4], 10 int b; // b = 10; // mov DWORD PTR [rbp-12], 10 如上的代码的时候，生成的汇编也只有两行，就算你开 -O0 也一样，因为这个定义的语句，的确，什么事情也没有干，只是告诉编译（Compiler）器，「这个位置我占掉了，虽然里面的东西我没有明确给它，但是我占了，你得让接下来的变量都往后挪挪，而且不能说我不在」的这种状态。 类型、限定符、修饰符 int, char, short, long, long long, float, double, long double 等被称为基础数据类型，一切的一切基于此而产生 分析一个变量的具体类型，应该从右王座看，看到 & 就是引用（ref）类型，看到 [] 就是数组类型，看到 *就是指针类型，然后看 顶层const还是底层const 人们喜欢讨论 * 这个字符用于限定变量的时候的位置，就会产生下面三种结果 int *p1; // *p1 的类型为 int int * p1; // 两边各退一步 int* p1; // p1 的类型为 int* 我个人倾向于使用 int* 的方式，将其作为一整个类型，因为 c++ 的类型系统过于复杂，比如 int x = 20; int* px = &x; decltype(x) px2 = px; 如果说是 *p 的类型为 type 的话，应当如何解释 decltype(x) 所推断出来的类型？所以，我倾向于使用 type* name，auto px3 = px;也是如此，如果不是类型，何来「类型推断」？ 同理，引用类型也是这样 // 指针 type* name1; // 引用 (type*)& name2 = name1; // 上面这个是对于指针类型的引用，引用必须要初始化 下面讲讲关于 const 和 constexpr 在此之前，真正的 constant 实际上是使用 #define 来定义的，但是 c++11 出现了 constexpr，终于可以用正经的方式定义一个真正的 constant 了。 constexpr 要求变量或者表达式的值能够在编译器得到计算，于是乎，用 constexpr 修饰的变量，是一个定值 const 所代表的是，不变量，与变量相对，只是在使用的过程中不会发生变化，但不代表它是一个固定的值 int a; std::cin >> a; const int b = a; 合法么，合法，但是 b 的值会随着我们的输入而发生变化，但是在接下来试图改变b的值，都会造成编译器错误。 但其实也不一定的，虽然说不能直接通过b修改b所对应的对象值，但是我们可以通过间接的方式，访问到b，并修改，而且不会引发编译器错误。 这个我们可以拿 nim 中类似的语句进行对比 const str = "Hello World" # Mutable variables var c: int c = 20 # Immutable variables let e = c nim 中 const 是常量，var 是变量，let 是不可变量 c++ 中 constexpr 是常量，没有限定符的各种类型 是变量，const 是不可变量 这样一比其实也不难发现 c++ 在发展上的滞后性了 const int i = 20; // 不能修改的 int 类型变量（不变量也是不会变的变量） const int* const pi = &i; // 首先，a 是 const，a 本身的值不能改动 // 其次，是 const int* 类型，代表是 cosnt int 类型的指针 // 说明 a 所指向的对象是 int 且不能修改 const int*& const rpi = pi; // 一个 const int* 类型的引用，且本身也不能修改，（虽然说引用本来就不能改，不知道加上有没有 我们再加上一个数组类型，数组类型就非常有趣了，因为其中的矛盾点实在太多了，比如可以弱化成指针，这一点就很折磨人，所以和别人解释，但是这个内容再在下一章解释 自动类型推断 auto decltype(statment) decltype(auto) //c++17 引进 自定义数据结构，使用 struct 将各种数据归为一类， 但是好像没有看到 union 这个数据结构在这本书中被介绍 虽然说用的少，但其实，还是很有用的，比如用作动态类型的数据结构 第 3 章 字符串、向量和数组 其实这一章前面部分没有什么特别重要的事情，只不过介绍了 std::string 和 std::vector 两个标准库「容器（Container）」 我想这个内容可能看 C++ 标准库 可能更加适合一些 但有一点可以注意的就是 std::vector<std::string> a(10, "20"); std::vector<std::string> b{10, "20"}; 的效果是一样的 迭代器 std::string::itrator; std::vector<int>::itrator; 数组 int a[10]; using int10 = int[10]; int10 b; 第 4 章 表达式 提升，转换，重载，左右值 赋值，取址，解引用和下标…… 都必须要使用左值， decltype 对左值，取到的是一个引用，但对于右值，取到的是本来的类型 这个在之前的例子中有出现过 int i = 10; int* pi = &i; decltype (*pi) d = i; // 实际上这是 int& 类型 decltype (pi) e = pi; // 这个是 int* 类型 sizeof int sizeof (1+1) int a = f1() + f2(); 像上面这两个函数返回值相加，但是你没有办法知道先执行的是哪一个函数，这个是不确定的，一定程度上也是线程不安全的 T operator+(const T &a, const T2 &b); 同理，因为加号会图上面这样子重载，对于某一个类型的重载，你也可以把int类型的+重载成*，这个以后再讲。f1和f2就成为了 operator+ 的两个参数，这样同样表明，函数作为函数参数时，其运行顺序也是不确定的 取余的运算比较复杂，日后重新罗列 第 5 章 语句 if if-else for for while do-while switch break continue goto throw try catch 第 6 章 函数 const 的故事到这里，才算真正地开始…… 整个 c++11 就是一个类型斗争史，auto，decltype，template，using，透露出两个字，类型，类型，还是类型，函数重载、尾置返回、左值引用、右值引用也涉及到类型推断， 尾置返回类型 auto func (int i) -> int(*)[10]; 函数参数中的顶层 const 会被忽略掉 void func (const int i); void func (int i); 上面两个声明其实都是一个函数，会报错 void print (const int* i); void print (const int i[]); void print (const int i[10]); 上面三种声明，也是一样的，所以，在作为函数参数的时候，数组会弱化为指针 const int& i = 41; void func (int& ar[]); // 引用的数组 void func (int (&ar)[]); // 数组的引用 函数返回数组指针 int (*function(void))[10]; // 一个返回指向 int[10] 的指针的函数 // 使用尾置返回 auto function(void) -> int(*)[10]; using pi10 = int(*)[10]; pi10 function (void); 函数返回函数指针 int (*function (void)) (int*, int); auto function(void) -> int(*)(int*,int); using ifpii = int(*)(int*, int); ifpii function (void); 关于如何向数组传入长度参数，其实还有别的小妙招 template <typename T> void func (int& ar[T]) { } type (*function(parameters))[dimension] { } 可以定义一个返回 数组的指针 的函数 折叠表达式(C++17 起) template<typename... Args> bool all(Args... args) { return (... && args); } template<typename... Args> bool any(Args... args) { return (... || args); } template<typename... Args> bool sum(Args... args) { return (... + args); } bool b = all(true, true, true, false); // 在 all() 中，一元左折叠展开成 // return ((true && true) && true) && false; // b 为 false // 将一元折叠用于零长包展开时，仅允许下列运算符： // 1) 逻辑与（&&）。空包的值为 true // 2) 逻辑或（||）。空包的值为 false // 3) 逗号运算符（,）。空包的值为 void() // 注解 // 若用作 初值 或 形参包 的表达式在顶层具有优先级低于转型的运算符，则它可以加括号： template<typename ...Args> int sum(Args&&... args) { // return (args + ... + 1 * 2); // 错误：优先级低于转型的运算符 return (args + ... + (1 * 2)); // OK } 函数重载匹配其实也是一个很复杂的问题， 但是拒绝认识它也是可以的，就是不要写出具有歧义的重载函数 第 7 章 类 访问控制 public private protect 友元 friend 类成员 作用域和名字查找 构造函数初始化列表 委托构造函数 默认构造函数 =default =delete 隐式类类型转换 explicit 第 II 部分 C++ 标准库 第 8 章 IO 库 |头文件|类型|描述| |-|-|-| |iostream|istream, wistream|从流读入数据 ||ostream, wostream|向流写入数据 ||iostream, wiostream|读写流 |fstream|ifstream, wifstream|从文件流读入数据 ||ofstream, wofstream|向文件流写入数据 ||fstream, wfstream|文件读写流 |sstream|istringstream, wistringstream|从 string 读入数据 ||ostringstream, wostringstream|向 string 写入数据 ||stringstream, wstringstream|读写 string c++ 定义了上面这些流操作的类型，提供了最基础的流抽象功能，其他功能也可以基于此进行更深的抽象 但是，C++ 的流可能是一个非常失败的设计，因为输入输出的符号大家都不是很喜欢，而且在前期缺少合适的文本格式化工具，直到 c++20 引入了 format 库，才有所改观，但实际上现在没有任何一家的编译器是支持 format 库的再者是自带的 STL 库都没有提供对于标准化输入输出流的支持，只能自己手动输入输出。 但是我们也可以通过这个设计实现一个统一的输入输出操作 可以通过若干种标志判断当前流的状态处于失败、结尾、正常或者是异常 也可以通过对应的函数设置当前的状态 unitbuf, nounitbuf, flush, endl 立即刷新，不立即刷新，强制刷新，强制刷新并换行 我们可以使用 fstream 完成对文件流的读写操作，其具体操作与输入输出流并没有特别多的区别，唯一的是需要指明文件的路径和打开方式 需要注意的是，文件的写操作默认是附带 std::ios::trunc 的，这个意味着打开一个文件的时候，如果原先存在文件，则会将原先的文件删除 使用 stringstream 则可以对流进行细分，在实际使用中出现频率还是很高的 第 9 章 顺序容器 顺序容器主要有 |类型|介绍| |-:|:-| |vector|动态数组，即长度可变，支持快速随机（Random）访问，数据连续存储，所以插入数据可能很慢| |deque|双向队列，长度可变，支持快速随机访问，头尾插入删除很快，数据连续存储的同时分块存储| |list|双向链表，长度可变，随机访问并不快速，任意一个元素的插入删除都很快，就链表的存储方式| |forward_list|单向链表，长度可变，随机访问也不快速，但是相比双向链表少了一个方向，所以在插入和删除时比自己手写的链表快不了多少| |array|静态数组，长度不可变，可以看作是原生数组的高级版本| |string|和vector类似，但是专门用于保存字符，同时提供大量字符串处理相关的函数| |queue|单向队列，由双向队列继承而来| |priority_queue|| |stack|栈，由双向队列继承而来| 其实这里有一个很巧妙的点，为什么说是快速随机访问呢，确实，链表因为数据结构的问题，其实不支持随机访问，但是可以通过遍历的方式，实现一个非常慢速的随机访问，但也其实，可以通过一个vector存储链表的迭代器，再对vector随机访问，就可以实现对链表的随机访问了，这个适用于大规模的对于链表的随机访问 同时，这些容器库之所以要叫容器库，是因为它们提供了对任意类型的「容」，这个得益于 c++ 复杂的模板，在编译器对各种类型进行展开，同时，由于模板的存在，很多本来看上去很正常的名字，就变得极为不正常了，这也导致使用了模板的报错变得异常难读，学会从模板报错中找到正确的错误，也是一个非常重要的技巧 这些容器库，STL，都包含着若干统一的操作函数，但这里就不一一列举了，这不应该成为学习 c++ 的负担。诸如比较，构造，复制，交换，添加删除，以及各类迭代器（c++11 引入了一种新的反迭代器，还有各种容器的构造，赋值，交换，追加，插入，删除，移动，拷贝，这里也不加以细说。 往容器中添加元素又变得非常有复杂，但也没有那么复杂 push_back, push_front, emplace_back, emplace_front, insert，其中 emplace 系列函数于 c++11 引入，究其原因还是因为 c++11 带来的右值引用，push 系列函数在插入一个值的时候，会先对值进行拷贝，但是 emplcae 函数借用右值引用直接将值写入对应位置，减少了一次拷贝，一定程度上提升了性能（右值引用牛逼！） https://zhuanlan.zhihu.com/p/213853588 pop_back, pop_front, erase 用于删除元素 各个迭代器的使用，forward_list独树一帜的特殊操作 对于容器的插入删除可能导致迭代器失效，因为移动了容器中实际内容的位置，vector在内容将要填满预先分配的空间时，会将当前空间扩大为两倍，使用capacity可以查看已分配的空间，size查看已使用的空间 对字符串的各种操作函数在这里也不加以赘述了，实际上字符串库应当搭配c++11引入的regex正则匹配库和c++20引入的format格式化库使用更加顺手，正则匹配是一个好东西，就是看起来效率非常差，但也没有那么差了 第 10 章 泛型算法 泛型，何为泛型，即通用的，对于任何类型都可以使用，类型无关 这些泛型函数主要通过迭代器和传入的函数进行使用 其中大多数函数定义在 algorithm 算法库中，c++11 提供了超过一百种的内置算法，为开发提供了非常有用的帮助，尤其是 sort 函数我使用的次数不可谓不多 find, find_if... （我会在将来的某天详细地介标准库的内容，但不会是在这本书上 泛型算法主要分为只读算法，写算法和排序算法 查找算法，判断算法等算法为只读算法 写算法，插入算法（使用插入迭代器），拷贝算法（利用迭代器）， 排序算法，sort不稳定排序，stable_sort稳定排序，性能上各有千秋 之后，这本书在这个地方介绍了一个非常重量的 c++11 更新，lambda 函数，同时，这也更一步的让c++拥有了函数式编程的风范，一个较为简单的方式声明并使用一个函数，其中的详细内容我会另开一个文章进行介绍，但书中没有在这里引入function函数用来存储lambda函数我感觉还是有些欠妥当，不过也介绍了bind函数关于绑定函数参数的内容，同时介绍了find_if 函数和for_each 函数。值捕获，引用捕获，隐式捕获，等等等等，设置返回值，自动推断返回值，这里甚至还产生了闭包，但是在这本书里貌似没有介绍到。在lua中，闭包是一个非常重要的概念，而且在介绍lua的书中大书特书了 这里详细介绍了插入迭代器和反迭代器 第 11 章 关联容器 1）set or map 2）可否重复 3）有无顺序 因此产生了八种不同的数据类型，分别是：set map multiset multimap unordered_map unordered_set unordered_multimap unordered_multiset 因为map存储了两个信息，这里还引入了一个新的对象 pair，用于构成一对的数据结构，分别存储 map的key和value。关联容器同样拥有普通容器的大部分操作。之所以叫做关联，是因为key之间是相互影响的。比如在map和set中，是不允许出现相同的key的，这叫关联。 关联容器可以使用任意类型当作key和value，总之非常有用，但是具体的操作并不在这里赘述。一个非常有用的地方，就是统计单词的数量和有多少种单词，map的key为单数，value为数量，即可进行统计。set的key为单词，即可统计单词的种类，因为set在数学上与集合的含义相类似，所以在这里其实对于set还有非常多的集合操作，这本书上也没有讲。 然后我也没什么好讲的了，毕竟关于标准库的介绍不应该成为负担 第 12 章 动态内存 从程序支持手动申请内存开始，人类就陷入了无限的与指针的抗争之中。人们为了正确处理这些内存，掉了数不清的头发。所有分配的对象，需要一个能够指向它们的指针才能调用。手动分配的对象不受作用域或者生命周期影响。但是用来存储这个指针的对象，存在作用域和生命周期，当语句块结束后，这个指针变量则会消失，也许指针变成返回值传到另一个变量之中，也许没有。如果没有的话，那么这个内存中的对象就彻底变得无主了，于是这个内存中的对象就无法已正常地形式进行清除了。 这就形成了垃圾，于是我们引入了垃圾回收的概念，这个在相当多的语言中都有直接的体会，但是，这么方便为什么c++不用呢？因为垃圾回收，浪费空间，也浪费性能，所以这个功能不会在c++中提供，诸如python和lua，会对一些垃圾自动「标记-清理」。如果尝试写python，循环地进行一些事项，你有可能发现自己的内存占用，忽高忽低，这个就是python垃圾回收的效果了。 智能指针 但是c++难道没有办法高效地实现垃圾回收了么？当然是有的。答案就是使用智能指针，智能指针是在C++11中引入的。既然问题出现在指针上，那么解决这个指针，那么所有的问题就迎刃而解了。借助 c++ 类所带来的 RAII 功能，我们可以轻松实现，创建时如何，销毁时如何的功能。这也为智能指针的出现，奠定了基础。 智能指针分为三类 shared_ptr unique_ptr weak_ptr 其中，shared_ptr可以被赋值，拷贝，即可以存在多份，每次赋值拷贝会调用对应的构造函数，返回这样一个指针也会产生拷贝。每一次执行上述的操作时，其内部的计数器，会让自己的值增加一，只要内部计数器的值达到零，就会自动销毁内存中的对象。当然，这个时候，智能指针对象也肯定不会存在的。其中，weak_ptr是不会增长这个计数器，但是，当目标对象被销毁后，使用 weak_ptr 又成了一个未定义行为。unique_ptr不允许拷贝、赋值等操作，只能单一存在 std::shared_ptr<std::string> sps(new std::string); std::shared_ptr<std::string> sps2(sps); std::shared_ptr<int> spi(new int[100]) std::unique_ptr<std::string> ups(new std::string) 手动分配、管理内存 使用 new 和 delete 关键字，即可完成对象的申请和销毁。但是这里有一个小小的问题，与我们之前所讲的东西有所不同的是，new 所返回的并不是如我们所想的 数组的指针，它直接返回的只是一个指针，我们在这个过程失去了数组的大小，而且你甚至不能判断它就是数组。 int* i = new int; // 创建一个 int 对象 int* is= new int[10]; // 创建一个 int[10] 对象 delete i; // 销毁一个 int 对象 delete [] is; // 销毁一个 int[10] 对象 int* pi = new int[0]; // 创建一个空对象 // 实际上这句话什么事情也没有做，pi 所指向的值是未定义的 先分配内存空间，再进行初始化赋值 std::allocator 如果之前已经尝试过大量代码的同学，可能早就发现在使用STL的过程中，有一些报错的模板展开后，就有std::allocator类， 第 III 部分 类设计者的工具 第 13 章 拷贝控制 拷贝构造函数 Foo (); // 默认构造函数 Foo (const Foo&) // 拷贝构造函数 合成拷贝构造函数，即默认的拷贝构造函数，会将源对象的所有内容拷贝到目标对象 std::string dots(10, '.'); // 直接初始化 std::string s(dots); // 直接初始化 std::string s2 = dots; // 拷贝初始化 std::string null_book = "9" // 拷贝初始化 std::string nines = std::string(100, '9') // 拷贝初始化 拷贝赋值函数 Foo& operator= (const Foo&); // 拷贝赋值 同样的，拷贝复制也有合成拷贝赋值运算 移动构造函数 移动赋值运算符 析构函数 析构函数作为一种在对象生命周期结束的时候调用的一个函数，等同于给对象擦屁股的作用。于是，C++也提供了 RAII 等一系列功能。 生命周期如何结束：变量离开作用域，父级对象被销毁，容器被销毁，delete主动销毁，临时变量创建完整的表达式之后 C++ 三/五法则 当定义一个类时，我们显式地或隐式地指定了此类型的对象在拷贝、赋值和销毁时做什么。一个类通过定义三种特殊的成员函数来控制这些操作：拷贝构造函数、拷贝赋值运算符和析构函数。 拷贝构造函数定义了当用同类型的另一个对象初始化新对象时做什么，拷贝赋值运算符定义了将一个对象赋予同类型的另一个对象时做什么，析构函数定义了此类型的对象销毁时做什么。我们将这些操作称为拷贝控制操作。 由于拷贝控制操作是由三个特殊的成员函数来完成的，所以我们称此为“C++三法则”。在较新的 C++11 标准中，为了支持移动语义， 又增加了移动构造函数和移动赋值运算符，这样共有五个特殊的成员函数，所以又称为“C++五法则”。 也就是说，“三法则”是针对较旧的 C++89 标准说的，“五法则”是针对较新的 C++11 标准说的。 为了统一称呼，后来人们把它叫做“C++ 三/五法则”。 “需要析构函数的类也需要拷贝和赋值操作” 从“需要析构函数”可知，类中必然出现了指针类型的成员（否则不需要我们写析构函数，默认的析构函数就够了），所以，我们需要自己写析构函数来释放给指针所分配的内存来防止内存泄漏。 那么为什么说“也需要拷贝构造函数和赋值操作”呢？原因是：类中出现了指针类型的成员，必须防止浅拷贝问题。所以需要自己书写拷贝构造函数和拷贝赋值运算符，而不能使用默认的拷贝构造函数和默认的拷贝赋值运算符。 “需要拷贝操作的类也需要赋值操作，反之亦然” “析构函数不能是删除的成员” 如果析构函数是删除的，那么无法销毁此类型的对象。对于一个删除了析构函数的类型，编译器不允许定义该类型的变量或创建该类的临时对象。而且，如果一个类有某个成员的类型删除了析构函数，我们也不能定义该类的变量或临时对象。 让编译器使用合成 class Foo { public: Foo () = default; Foo (const Foo&) = default; Foo& operator= (const Foo&); ~Foo () = default; }; Foo& Foo::operator= (const Foo&) = default; 阻止拷贝 如果要阻止拷贝，就把上面对应的default换成delete删除即可，但是delete必须出现在成员第一次声明的地方，即 class Foo { public: Foo () = default; Foo (const Foo&) = default; Foo& operator= (const Foo&) = delete; ~Foo () = default; }; 其中，析构函数若被删除，我们就无法释放这些对象 如果一个类有数据成员不能默认构造、拷贝、复制或者销毁，则类对应的成员函数将被定义为删除。其原因是为了避免所创造的对象无法被销毁 但是这个功能是在c++11中引入的，在此之前，我们可以通过把对应的成员函数定义为private，外部的环境则无法访问对应的成员函数，实现了删除。声明但不定义是合法的，但是当使用这个函数时，会报链接错误，即找不到对应的函数定义，通过private声明，则可以阻止用户（我们）调用private函数，实现控制。 试着联系之前出现过的 std::unique_ptr 的禁止拷贝 尝试书写自己的资源管理类 值一样的类和指针一样的类，对应了之前的string类型和智能指针 动态内存管理类（std::allocator 续） 教你怎么实现 vector 类 申请一块内存区域，然后使用 allocator 复制内存区域到新申请的区域 对象移动和移动语义 为了避免在前面管理内存的时候，出现无意义的拷贝赋值，所以在c++11引入了右值引用，减少了对数据的拷贝，提升了效率 int i = 42; int& ri = i; // 左值引用 int&& rri = i; // 编译错误，左值不能绑定到右值引用上 int& ri2 = 42 * i; // 编译错误，右值不能绑定到左值引用上 const int& cri = 42 * i; // 右值可以绑定到常量左值引用上 int&& rri2 = 42 * i; // 右值引用 右值是临时的，而左值是永久的（在作用域内是永久的） 右值引用的好处是可以延长临时变量的生命周期。其基础上也实现了移动语言std::move和完美转发std::forward 能出现在等号左边的就是左值，右值只能出现在等号右边 使用移动操作时，要标明函数是不抛出异常的，否则会为此做一些额外的工作 class StrVec { public: StrVec (StrVec&&) noexcept; }; StrVec::StrVec (StrVec&& s) noexcept : { // ... } 引用限定符 class Foo { public: Foo& operator= (const Foo&) &; // 只能向可修改的左值赋值 }; Foo& Foo::operator= (const Foo& rhs) &; 第 14 章 重载运算与类型转换 不可重载的运算符 大多数运算符都是可以重载的,但是有5个运算符C++语言规定是不可以重载的. .(点运算符),通常用于去对象的成员,但是->(箭头运算符),是可以重载的 ::(域运算符),即类名+域运算符,取成员,不可以重载 .*(点星运算符,)不可以重载,成员指针运算符".*,即成员是指针类型 ?:(条件运算符),不可以重载 sizeof,不可以重载 C++ 只允许使用原本存在的运算符，而不支持自定义运算符，但是如果实现了这个功能，c++ 马上又起飞了 c++11 还引入了用户自定义字面量，似乎这个功能并没有在这本书中得以体现 long double operator"" pi(long double x) { return x*3.14159265357; } long double operator"" pi(unsigned long long x) { return static_cast<long double>(x)*3.14159265357; } 通过如上的代码我们可以实现自定义字面量，实现了xpi的数学写法，当然也可以给自然底数加上这样的功能 auto rad = 3pi; auto rad2 = 4.0pi; c++20 其实还引入了一个新的运算符<=>三向比较运算符，俗称，飞碟运算符，这个就是后话了，这里也不赘述 重载运算符的使用 之前在一个群里听到有人吐槽 std::string 没有重载与部分类型的 + 运算，然后我就丢给了他这样子的代码 std::string operator+ (std::string str, int x) { return str+std::to_string(x); } auto str = std::string ("H") + 123; // "H123" 实现了 std::string 与 int 类型的直接相加 当然，上面相加的一行，也等价为 auto str = operator+ (std::string("H"), 123); // 同理 auto i = operator+ (123, 321); // 也是成立的，但是 operator 只能同时有两个参数，而且写起来也格外麻烦 要注意的是，尽量不要使重载后的运算符的含义偏经离义，那会让使用者困惑。 又往下看了一些，发现 std::string 并没有把 + 作为自己的成员函数，而是当成了普通的非成员函数，所以也实现了 const char + std::string 的功能，如果是成员函数的话，const char 是不能放在前面的 输入输出运算符也是如此，应当作为非成员函数存在才能正常使用，不然以 ostream.>>(Foo) 的调用形式，是不能正确实现期望的功能的 ostream& operator<< (ostream& os, T t) { // ... } 运算符介绍 算术运算符 无非就是加减乘除余和各种二元运算符 逻辑运算符 逻辑运算符和算术运算符使用方法基本一致 赋值运算符 普通的赋值运算符没有什么特别的，但是复合赋值运算符就有一些不同了，只传入一个参数，其中，左侧的被赋值对象的 this 指针会被传入 下标运算符 通常是返回访问元素的引用为好，此时可以多重下标运算 递增递减运算符 这里又有点小不同了，递增递减分为前置和后置，但是运算符重载总是以 operatorOPR的形式存在的，应当如何区分前置和后置呢？ int& operator++ (); // 前置 int& operator++ (int); // 后置 后置递增运算符中，虽然出现了一个额外的参数，但是这个参数是不应当被使用到的，编译器为默认往里面传入0。此行为只是为了区分前后置 显式调用递增运算符 Foo p; p.operator++(0); // 后置 p.operator++(); // 前置 成员访问运算符 虽然我们不可以重载点成员访问运算符，但是我们可以重载箭头成员访问运算符 函数调用运算符 重载这个运算符，可以让我们的类对象表现得像函数一样 Foo foo; foo(123); // 此处已然不是构造函数 类型转换运算符 书中把这个内容放在了 lambda 的下面，但是我把它提了上来，放在了一起。类型转换函数一般形式如下： operator type() const; // 显式类型转换运算符 我们再一次联系之前所学到的内容，explicit explicit type() const; 只有当我们尝试使用显式类型转换时，才会调用这个函数 static_cast<type> a; 书看到这里，也差不多能够解决我的一个疑问了，我当初就想，为什么一个流对象在循环中可以被当作条件使用，现在发现因为有隐式类型转换运算符重载的出现，所以在条件中，流被转换成一个bool类型的值返回，使循环可以正常运行 记得避免二义性转换 lambda 表达式再续前缘 cppreference 上面写道：lambda 就是创建一个闭包并返回，但是可能闭包这个概念解释起来也是过于复杂，所以 C++ primer 真的也只是做了一个 primer，从而不介绍具体的编程范式，这个大概可以在别的书中看到具体的操作方式。当然，网上也有很多类似的教程 c++ 是一个多范式编程语言，虽然在 lambda 出现之前就已经实现了函数式编程的功能，但是，lambda 表达式的存在，第一次让书写函数变得如此简练，写函数写起来真的是非常的爽快 于是乎，c++ 标准库为了符合的上自己的多范式编程语言的称号，也在 functional 中定义了一系列的函数式范式的类，用于生成对应的函数对象提供进一步的操作 |算术|关系|逻辑| |-|-|-| |plus<T>|equal_to<T>|logical_and<T>| |minus<T>|not_equal_to<T>|logical_or<T>| |multiplies<T>|greater<T>|logical_not<T>| |divides<T>|greater_euql<T>|| |modulus<T>|less<T>|| |negate<T>|less_equal<T>|| 可调用对象与function 今天下午，巨佬刚好怼着 std::function 喷了一堆，但是我也看不懂，他反驳的是 c++ 标准库中存在的那些糟粕，嫌弃 std::function 的性能之差，说 noexcept swap allocator 等东西满天飞，到 2021 年还没有解决，自己写的 ystdex::function 直接性能上都能把 libstdc++ 摁在地上锤 除了实现难度比较大，而且吐槽了新议程中的试图把信号槽系统搬进标准c++的事情 当我们尝试做一个复杂的计算器时，会运用到非常多的计算功能，这些计算功能就是通过函数实现的，所以如何保存一个函数，就显得非常重要了，c++是一个静态语言，也不支持反射，所以不可能通过生成代码的方式生成一个函数，如果尝试诸如 lua、python 等语言的话，可以尝试一下这种方式 函数表 int add(int i, int j) { return i + j; } auto mod = [] (int i, int j) -> int { return i + j; } struct divide { int operator() (int denominator, int divisor) { return denominator / divisor; } } std::map<std::string, int(*)(int,int)> binops; binops.insert ({"+", add}); // 将 add 函数和 + 绑定在一起 但是我们不能将 mod 和 divide 存入 binops，其中 lambda 有自己的类类型，与函数指针类型不匹配。解决办法是……std::function std::function<int(int, int)> f1 = add; std::function<int(int, int)> f2 = divide(); std::function<int(int, int)> f3 = [] (int i, int j) -> int { return i * j; }; 但是，std::function 会面临重载函数二义性的问题，因为赋值的时候只提供了一个关于函数的名字，但是没有任何参数，编译器无法推断此时应当使用哪一个函数存入 std::function 第 15 章 面向对象程序设计 面向对象的介绍 这个地方其实我自己也不知道应当如何介绍，只能抄一点书上的内容了 P525-576 面向对象的核心是数据抽象、继承和动态绑定 基类，派生（Fork）类（也称为父类，子类） 派生类需要通过在类派生列表中明确指出它是从哪（些）个基类派生而得到的 虚函数使得派生类可以修改继承得到的那些标记为虚函数的函数，使之表现出不同的行为 动态绑定，运行时绑定，这个概念很奇怪，总之就是在代码运行的时候对不同的对象使用不同的成员函数 面向对象的使用 定义基类 virtual override 定义派生类 阻止继承 final 虚函数 抽象基类：只含有纯虚函数的基类 访问控制 在之前第六章的时候我们讨论过一些访问控制，这里更加深入地去了解他们 public protected private friend 其他类的操作 拷贝，赋值，移动，构造，析构……与先前的语法一致，但是可能会有一些不同 第 16 章 模板与泛型编程 定义一个模板 函数模板 template <typename T> int compare (const T& v1, const T& v2) { return v1<v2?-1:v2<v1?1:0; } 其实上面的代码实现了一个三相比较符，这个在c++20中以及被引入 我感觉如果接住了重载运算符的功能，就是用户自己添加运算符应当成为一个符合标准的事情才对 模板的特殊操作 template <unsigned N, unsigned M> int compare (const char (&p1)[N], const char (&p2)[M]) { return strcmp (p1, p2); } 往函数中传入了一个数组！！！ 这都归功于模板的实例化，编译器在编译器就将数据的大小用我们看不到的方式传入了函数之中，让函数也直接得到了数组的大小 我们也可以使用 constexpr 对函数修饰要求能够在编译期返回一个常量结果 模板的保存总是又臭又长，因为其实例化展开的过程非常**，经常会让保存变得难以看懂，尤其是标准库那互相依赖（Dependencies）一报上百个的报错 类模板 template <typename T> class Foo { }; 类模板其实和函数模板没有太大的区别，但是类模板需要手动指定类型实现实例化。类模板也存在偏特化和全特化，对视直接在类中写入对于什么样的类型执行什么样的操作。 比如 vector 和 map 创建一个对象的时候 在类外使用类模板名 template <typename T> Foo<T> Foo<T>::operator+ (T a, T b) { // ... } 一对一友元类， 通用和特定友好关系 令模板中的类型为自己的友元 模板类型别名 using strFoo = Foo<std::string>; static 成员 每一个实例化的类都有自己对应的静态成员 模板参数的作用域 使用类的类型成员 这里可以看看之前我们是如何声明容器的迭代器的，那样子我们对于模板类的类型成员也会有所感觉了 模板类的默认模板形参 template <class T = int> class Foo { // ... } 类成员函数模板 其实本质上和函数模板并无区别，无非就是身在类中 实例化与成员函数 实例化 控制实例化 extern template class Blob<string>; template int compare (const int&, const int&); 运行时绑定删除器 编译时绑定删除器 模板类型实参推断 类型转换与类型模板参数 template <typename T1, typename T2, typename T3> T1 sum (T2, T3); auto val3 = sum<long long>(i, lng); // long long sum (int, long) 尾置返回类型 标准库中的类型转换模板 函数指针和实参推断 模板实参推断和引用 主要是关于引用折叠和右值引用的参数相关的内容 理解 std::move std::move 的定义 template <typename T> typename remove_reference<T>::type&& move (T&& t) { return static_cast<typename remove_reference<T>::type&&> (t); } std::string s1("hi"), s2; s2 = std::move (std::string ("HELLO")); s2 = std::move (s1); 从一个左值 static_cast 到一个右值是允许的 转发 std::forward 重载与模板 可变参数模板 模板参数包，函数参数包 我们使用一个省略号表示一个包，但是这个省略号实际上是由三个句号构成的，不是中文的省略号 使用 sizeof... 可以获取包的长度 template <typename T, typename... Args> void foo (const T &t, const Args&... rest); 编写可变参数函数模板 包扩展 c++11 中引入的包，使得解包可以较为方便地通过递归的方式实现 template <typename T, typename... Args> ostream& print (ostream& os, const T& t, const Args&... rest) { os << t << ","; return print (os, rest...); } 转发参数包 模板特例化 第 IV 部分 高级主题 第 17 章 标准库特殊设施 认识 std::tuple tuple 类似于 pairs，但是与 pairs 想不不同的是，pairs 只能存有两个（一对）类型，但是 tuple 可以存储若干个类型，所以这个类，在很多情况下也被用作函数返回值（与 struct 非常相近是不是？） 再会 std::bitset 其实 bitset 类，在这本书的开头我们就已经看到过了，现在是郑重其事地介绍一遍 可以理解为二进制数组，类似于java的bitmap吧，可以用来存储而静止图像 一个无限长度的整数类，也有支持的对应的运算符 初遇正则表达式 正则表达式才是真正的大头，这个功能真的是非常非常有用 头文件 regex 组件们 |名称|介绍| |-|-| |regex|表示正则表达式的类| |regex_match|进行正则匹配| |regex_search|寻找第一个与表达式匹配的子序列| |regex_replace|使用给定正则替换目标序列| |sregex_iterator|调用regex_match匹配string中的所有匹配子序列| |smatch|容器类，保存搜索结果| |ssub_match|string中匹配子表达式的结果| 我们将在之后的时间里，详细地补充 regex 的使用方法，对于如何书写一个正则表达式，也会在届时详细补充 子表达式 随机数 在出现专门的随机数库之前，我们使用 cstdlib 提供的 rand 和 srand 生成随机数，但是 rand 返回的随机数结果是有范围，而且属于平均的随机，而且生成随机数的质量并不是很高，但是胜在速度足够快 随机数引擎 使用随机数引擎，我们甚至可以生成符合正态分布的随机数 再探 IO 库 我们讲了很多关于流的操作，但是我们没有将如何控制一个流。 但实际上，这个部分可以放弃了，在实际使用中，真的用的非常少，大家宁愿使用 printf， sprintf，也不会去使用 ostream 或者 stringstream 的格式化，因为真的是又臭又长，但是好处是处理效率很快，但是相比需要关心这个狗屁格式，显然是使用 c++20 引入的 format 库更加实用有效。 单字节操作 is.get, os.put, is.putback, is.unget, is.peek 多字节操作 is.get, is.getline, is.read, is.gcount, os.write, is.ignore 流随机访问 seek 和 tell 函数 第 18 章 用于大型程序的工具 异常处理 抛出异常 如何抛出一个异常其实还是一个非常富有技术含量的活 terminate 函数用于终止程序的运行， 如果代码写的足够多了，你经常可以发现自己的程序被杀死了，输出一条结果 xxx terminate: xxxx，大多数情况下是因为指针的问题，这个致命的异常要是一直没有被捕获，就会返回到最外层，然后调用 terminate 函数，终止程序的运行 捕获异常 noexcept 这个是不抛出异常，在我们之前使用 function 的时候也见到过 命名空间 命名空间的定义，使用，嵌套定义，分块定义，内联，无名，模板特例化， 调用命名空间内的成员 using 的使用 类、命名空间和作用域 多重继承和虚继承 第 19 章 特殊工具与技术 控制内存分配 当当，new 和 delete 相关的重载在这里出现了，我之前完全没有发现重载运算符那里没有讲new 和 delete，对了，delete 操作也是需要添加 noexcept 的修饰符的 c 中使用 malloc free 来分配释放内存，C++ 也继承了这部分功能 运行时类型识别（RTTI） dynamic_cast typeid 运算符，可以获取类型并返回 type_info 但是，其实 typeid 是一个非常慢的操作，我之前用这个玩意儿，还被大佬吐槽了一番， 枚举类型 C++11 引入了限定作用域的枚举类型，也让枚举拥有了更多的类型 枚举类型、联合体、结构体，这个在 c 中是作为一个基础的数据结构，在很早的时候就会被介绍到的，但是这里为了防止我们书写不那么 c++ 风格的代码，从而延后了。 限定枚举的作用域，在c中，枚举是在整个作用域可见的，导致枚举的名字不能重复，或者重复的意义可能出现不同，从而导致问题 使用 class 和 struct 表明枚举的范围 enum T { Tname1, Tname2, Tname3, Tname4 }; enum class CT { a, b, c, d }; Tname1 // ok a // not ok CT::a // ok 我们还可以限定枚举中元素的类型，默认为 int， enum class intValues : unsigned long long { charTyp = 255, shortTyp = 65535, intTyp = 65535, // 这里出现了一个非常有趣的事情，int 的上限居然和 short 一样 // 这个是因为标准没有明确规定int的具体长度，只规定了一个范围 longType = 4294967295UL, long_longType = 18446744073709551615ULL }; 枚举类型的前置声明 enum class intValues : unsigned long long; 枚举的形参匹配 只能是枚举，就算值和枚举一样，对应的还是枚举，而非这个值 类成员指针 数据成员指针 const std::string CLASS::* pdata; // 指向 CLASS 对象的 std::string 成员 的 指针 成员函数指针 char (CLASS::* pmf2) (CLASS::X, CLASS::y) const; // 指针叫 pmf2，指向来自 CLASS 的函数 // 函数返回值为 char， 不能再函数内部修改变量的值 // 传入参数为 CLASS::X 和 CLASS::Y using c = char (CLASS::*)(CLASS::X,CLASS::Y) const; // 使用别名 c pmf3; 成员指针函数表 将成员函数作为可调用对象 嵌套类 只是如此嵌套而已，似乎并没有什么可以多讲的 局部类 和嵌套类也很相似，但是没有什么特别的不同，我把它提前放置在这里 联合体：union 特殊的类，将多种数据结构在一个空间上存储，实现类型的动态变化 union 用于实现了 lua的动态类型 c++11更新之后，它就变成一种特殊的类，拥有了权限控制，默认都是 public union UT{ char cval; int ival; long long llval; double dval; std::string sval; }; std::map <std::string, UT> valueStack; 同枚举，类，结构体一样，联合体是可以匿名的 我们可以使用枚举存储当前联合体中存储的类型，在进行操作时加以判断 C++ 的固有不可移植性 因为 c++ 为了高效，需要编译到机器码，机器码则与对应的硬件设施相关，而其调用的库则是平台相关，导致c++的移植总是需要重新编译一串代码 位域 volatile volatile 要求编译器不要对这个变量以及相关的进行优化，因为在多线程下，如果某一段代码被优化了，另一个线程对其的修改其实就不能生效了，这就会导致一定的问题，具体的可以看到 https://www.zhihu.com/question/31459750/answer/52061391 。书中对其描写非常之少 extern "C" 让链接器使用其他语言的编译器编译其中的代码，但是得让这个代码和c++能够一起运行 附录 A 标准库 A.1 标准库名字和头文件 A.2 算法概览 find (beg, end, val) find_if (beg, end, unaryPred) find_if_not (beg, end, unaryPred) count (beg, end, val) count_if (beg, end, unaryPred) all_of (beg, end, unaryPred) any_of (beg, end, unaryPred) none_of (beg, end, unaryPred) A.3 随机数 索引（Index）
【leetcode-292】Nim 游戏——博弈论初步 Nim 游戏 看到这标题，我还是觉得有趣的，因为 Nim 是一门十岁半的语言，满有趣的 但是我看到题目我还是很奇怪的，看上去好像很简单诶，做起来感觉又很奇怪，然后翻了评论，看到了这么一个博弈论的东西 CPP class Solution { public: bool canWinNim(int n) { return n%4>0; } }; C bool canWinNim(int n){ return n%4>0; } Lua function canWinNim (n) return n%4>0 end 巴什博奕 巴什博奕： 两个顶尖聪明的人在玩游戏，有n 个石子，每人可以随便拿1−m 个石子，不能拿的人为败者，问谁会胜利 巴什博奕是博弈论问题中基础（Base）的问题 它是最简单的一种情形对应一种状态的博弈 回到顶部 博弈分析 我们从最简单的情景开始分析 当石子有1−m 个时，毫无疑问，先手必胜 当石子有m+1 个时，先手无论拿几个，后手都可以拿干净，先手必败 当石子有m+2−2m 时，先手可以拿走几个，剩下m+1 个，先手必胜 我们不难发现，面临m+1 个石子的人一定失败。 这样的话两个人的最优策略一定是通过拿走石子，使得对方拿石子时还有m+1 个 我们考虑往一般情况推广 设当前的石子数为n=k∗(m+1)+r 先手会首先拿走r 个，接下来假设后手拿走x 个，先手会拿走m+1−x 个，这样博弈下去后手最终一定失败 设当前的石子数为n=k∗(m+1) 假设先手拿x 个，后手一定会拿m+1−x 个，这样下去先手一定失败 巴什博奕 (Bash Game) 首先我们来玩一个比较古老的报数游戏。A 和 B 一起报数，每个人每次最少报一个，最多报 4 个。轮流报数，看谁先报到 30. 如果不知道巴什博弈的可能会觉得这个是个有运气成分的问题，但是如果知道的人一定知道怎样一定可以赢。 我们先看下一个一眼就能看出答案的例子 比如说我们报到 5 (4+1), 每次报最多报 4 个，最少报 1 个。那么是不是后者一定可以赢呢？答案是肯定的。好了到这巴什博弈的精髓基本就 OK 了。 那么如果我们要报到 n+1, 每次最多报 n 个，最少报 1 个的话，后者一定能够赢。 现在我们需要报数到 n, 而每次最多报数 m 个，最少报数 1 个。我们可以化成这样 n = k*(1+m)+r (0 <= r <= m）这样的话如果 r 不等于 0 那么先手一定会赢，为什么呢？首先先手报 r 个，那么剩下 k 倍 (1+m) 个数，那么我们每次报数 1+m-k (B) 个数就一定能保证最后剩下 1+m 个，那么就到了上面我们说的那个了，先手就一定会赢，如果 r=0 那么后手一定会赢，道理一样的。 (r 为任意自然数，s≤m), 即 n%(m+1) != 0, 则先取者肯定获胜 代码： import java.util.Scanner; /** Created by YYL on 2017/2/24. */ //先报数到n者胜，每次最少报m1,最大报m2，且1<=m1<m2<n; public class BashGame { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m1=scanner.nextInt(); int m2=scanner.nextInt(); if(m1<1||m2>=n); else { if(n%(m1+m2)!=0) System.out.println("第一个人获胜"); else System.out.println("第二个人获胜"); } } } 运行结果： 30 2 6 第一个人获胜 其他实例： 大学英语四级考试就要来临了， Kiki 和 Cici 在紧张的复习之余喜欢打牌放松。“升级”？“斗地主”？那多俗啊！作为计算机学院的学生，Kiki 和 Cici 打牌的时候可没忘记专业，她们打牌的规则是这样的： 1、 总共 n 张牌； 2、 双方轮流抓牌； 3、 每人每次抓牌的个数只能是 2 的幂次（即：1，2，4，8，16…） 4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者； 假设 Kiki 和 Cici 都是足够聪明并且每次都是 Kiki 先抓牌，请问谁能赢呢？ Input 输入数据包含多个测试用例，每个测试用例占一行，包含一个整数 n（1<=n<=1000）。 Output 若 Kiki 能赢的话输出 “Kiki”，否则输出 “Cici”，每个实例的输出占一行。 Sample Input 1 3 Sample Output Kiki Cici 分析： 如果你是先手，考虑你的必胜态。注意，因为任何正整数都能写成若干个 2 的整数次方幂之和 (相当于十进制转二进制)。由于规定只能取 2 的某个整数次方幂，只要你留给对手的牌数为 3 的倍数时，那么你就必赢，因为留下 3 的倍数时，对手有两种情况： 1：如果轮到对方抓牌时只剩 3 张牌，对方要么取 1 张，要么取 2 张，剩下的你全取走，必赢！ 2：如果轮到对方抓牌时还剩 3k 张牌，对手不管取多少，剩下的牌数是 3x+1 或者 3x+2。轮到你时，你又可以构造一个 3 的倍数。 所以无论哪种情况，当你留给对手为 3k 的时候，你是必胜的。 题目说 Kiki 先抓牌，那么当牌数为 3 的倍数时，Kiki 就输了。否则 Kiki 就能利用先手优势将留给对方的牌数变成 3 的倍数，就必胜。 代码如下： #include <iostream> using namespace std; int main () { int num; while (cin>>num ) { if(num%3!=0) cout<<"Kiki"<<endl; else cout<<"Cici"<<endl; } return 0; } 土地拍卖 Problem Description 小鸡同学和鹏程同学始终没有逃过退学的命运，因为他们没有在程序设计竞赛中获奖，还为了争抢莎莎大打出手。现在等待他们的只能回家种田。要种田得有田才行，小鸡听说街上正在举行一场拍卖会，拍卖的物品正好就是一块田地。于是，小鸡带上他的全部积蓄，冲往拍卖会。后来发现，整个拍卖会只有小鸡和他的死对头鹏程。通过打听，小鸡知道这场拍卖的规则是这样的：刚开始底价为 0，两个人轮流开始加价，不过每次加价的幅度要在 1～N 之间，当价格大于或等于田地的成本价 M 时，就把这块田地卖给这次叫价的人。小鸡和鹏程虽然比赛不行，但是对拍卖却十分精通，而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。由于抽签决定，所以每次都是由小鸡先开始加价，请问，第一次加价的时候，小鸡要出多少才能保证自己买得到这块地呢？ Input 本题目包含多组测试，请处理到文件结束 (EOF)。每组测试占一行。每组测试包含两个整数 M 和 N (含义见题目描述，0 # include<stdio.h> int main() { int n,m; while(scanf("%d %d",&m,&n)!=EOF) { if(m%(n+1)==0) { printf("none\\n"); continue; } if(m<=n) { printf("%d",m); for(int i=m+1; i<=n; i++) printf(" %d",i); printf("\\n"); continue; } printf("%d\\n",m%(n+1)); } return 0; } 威佐夫博奕（Wythoff Game） 这种博弈比前面一种要稍微复杂一点。我们来看下下面这个游戏。 有两堆火柴棍，每次可以从某一堆取至少 1 根火柴棍 (无上限)，或者从两堆取相同的火柴棍数。最后取完的是胜利者。好了，如果你不知道这个博弈定理，对于小数目的火柴棍数，可能还能推出来，但是如果火柴棍数一多，就不行了。看了下面的这个介绍，你也会有一种被骗的感觉。 首先我们知道两堆火柴是没有差别的，也就是说第一堆有 a 根，第二堆有 b 根和第一堆有 b 根，第二堆有 a 根是一样的结果。 我们用一个二维的状态（a,b) 来记录当前剩下的火柴数，表示第一堆剩下 a 根火柴，第二堆剩下 b 根火柴。同样我们假设两个人的编号是 A 和 B，且 A 先取。 那么如果某个人遇到了这样的状态 (0,0) 那么也就是说这个人输了。这样的状态我们叫做奇异状态 , 也可以叫做失败态。 那么接下来的几个失败态为 (1,2),(3,5),(4,7),(6,10),(8,13)…… 我们用 a [i] 表示失败态中的第一个，b [i] 表示失败态中的第二个.(i 从 0 开始). 那么我们可以看到 b [i] = a [i]+i;（i >= 0）,a [i] 是前面的失败态中没有出现过的最小的整数 下面我们可以得到三个基本的结论。 每个数仅包含在一个失败态中 首先我们知道 a [k] 是不可能和前面的失败态中的 a [i],b [i] 重复的 (这点由 a [i] 的得到可以知道) b [k] = a [k]+k > a [k-1]+k>a [k-1]+k-1+1>a [k-1]+(k-1) = b [k-1]>a [k-1] 这样我们知道每个数仅在一个失败态中。 每个失败态可以转到非失败态。 加入当前的失败态为 (a,b)，那么如果我们只在一堆中取的话，肯定会变成非失败态 (这点由第一点可以保证), 如果从两堆同时取的话，由于每个失败态的差是不一样的，所以也不可能得到一个失败态。也就是说一个失败态不管你怎么取，都会得到一个非失败态。 每个非失败态都可以转到一个失败态 对于这个结论，首先我们要知到每个状态 (a,b) 要么 a = a [i], 要么 b = b [i].(每个数都出现在一个失败态中), 下面我们分两种情况来讨论 I.a = a [i]. 如果 b = a 的话那么一次取完就变成了 (0,0). 如果 b > b [i] 的话，那么我们从第二堆中取走 b-b [i] 就变成了一个失败态。如果 b < b [i]. 那么我们从两堆中同时取走 a-a [b-a [i]] 这样得到失败态 (a [b-a [i]],a [b-a [i]]+b-a [i])(a [i] = a) II.b = b [i]. 如果 a > a [i] 那么我们从第一堆中取走 a-a [i] 根火柴. 如果 a <a [i]. 这里又分两种情况。第一是 a = a [k](k < i) 那么我们从第二堆取走 b - b [k] 就行了。 第二是 a = b [k] 这样的话由于两堆火柴是没有区别的，所以我们把 b 变成 a [k] 就行了，也即是从第二堆火柴中取走 b - a [k] 就变成了失败态 至于怎么判断一个状态是否是失败态。我们可以用下面的方法来判断 (本人暂时还不会证明) a[i] = i*(1+√5)/2 b[i] = a[i]+i; 那么这就是一个失败态 找规律分析 第一个（0 ， 0），先手输，当游戏某一方面对（ 0 ， 0）时，他没有办法取了，那么肯定是先手在上一局取完了，那么输。 第二个 （ 1 ， 2 ），先手输，先手只有四种取法， 1）取 1 中的一个，那么后手取第二堆中两个。 2）取 2 中一个，那么后手在两堆中各取一个。 3）在 2 中取两个，那么后手在第一堆中取一个。 4）两堆中各取一个，那么后手在第二堆中取一个。 可以看出，不论先手怎么取，后说总是能赢。所以先手必输！ 第三个 （ 3 ， 5 ），先手必输。首先先手必定不能把任意一堆取完，如果取完了很明显后手取完另一堆先手必输，那么 假如看取一堆的情况，假设先手先在第一堆中取。 取 1 个，后手第二堆中取 4 个，变成（1 ，2）了，上面分析了是先手的必输局。 取 2 个，后手第二堆中取 3 个，也变成（ 1 ， 2）局面了。 假设先手在第二堆中取，取 1 个，那么后手在两堆中各取 2 个，也变成 (1 , 2) 局面了。 取 2 个 ，那么后手可以两堆中都去三个， 变成 （ 0 ， 0）局面，上面分析其必输。 取 3 个，后手两堆各取 1 个 ，变成（ 1 ， 2）局面了。 取 4 个，后手在第一堆中取一个，变成（ 1 ， 2）局面了。 可见不论先手怎么取，其必输！ 第四个（4 ， 7），先手必输。 自己推理可以发现不论第一次先手如何取，那么后手总是会变成前面分析过的先手的必输局面。 那么到底有什么规律没有呢，我们继续往下写。 第四个 （ 6 ，10 ） 第五个 （ 8 ，13） 第六个 （ 9 ， 15） 第七个 （ 11 ，18） 会发现他们的差值是递增的，为 0 ， 1 ， 2， 3， 4 ， 5 ， 6， 7…..n 而用数学方法分析发现局面中第一个值为前面局面中没有出现过的第一个值，比如第三个局面，前面出现了 0 1 2，那么第三个局面的第一个值为 3 ，比如第五个局面，前 面出现了 0 1 2 3 4 5 , 那么第五个局面第一个值为 6。 再找规律的话我们会发现，第一个值 = 差值 * 1.618 而 1.618 = （sqrt（5）+ 1） / 2 。 大家都知道 0.618 是黄金分割率。而威佐夫博弈正好是 1.618，这就是博弈的奇妙之处！ 下面来看看威佐夫博弈常见的三类问题： 1）给你一个局面，让你求是先手输赢。 有了上面的分析，那么这个问题应该不难解决。首先求出差值，差值 * 1.618 == 最小值 的话后手赢，否则先手赢。（注意这里的 1.618 最好是用上面式子计算出来的，否则精 度要求高的题目会错） 2）给你一个局面，让你求先手输赢，假设先手赢的话输出他第一次的取法。 首先讨论在两边同时取的情况，很明显两边同时取的话，不论怎样取他的差值是不会变的，那么我们可以根据差值计算出其中的小的值，然后加上差值就是大的一个值，当 然能取的条件是求出的最小的值不能大于其中小的一堆的石子数目。 加入在一堆中取的话，可以取任意一堆，那么其差值也是不定的，但是我们可以枚举差值，差值范围是 0 — 大的石子数目，然后根据上面的理论判断满足条件的话就是一种合理的取法。 尼姆博奕（Nimm Game） 指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下： 1) 每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子； 2) 如果谁取到最后一枚石子就胜。 也就是尼姆博弈（Nimm Game）。 必败局面：也叫奇异局势。无论做出何出操作，最终结果都是输的局面。必败局面经过 2 次操作后，可以达到另一个必败局面。 必胜局面：经过 1 次操作后可以达到必败局面。 即当前局面不是必败局面就是必胜局面，而必胜局面可以一步转变成必败局面。 最终状态： （1）最后剩下一堆石子；（必胜局面） （2）剩下两堆，每堆一个；（必败局面） （3）当石子剩下两堆，其中一堆只剩下 1 颗，另一堆剩下多于 n 颗石子时，当前取的人只需将多于 1 颗的那一堆取出 n-1 颗，则局面变为刚才提到的必败局面。（必胜局面） 判断当前局势是否为必胜（必败）局势： 1）把所有堆的石子数目用二进制数表示出来，当全部这些数按位异或结果为 0 时当前局面为必败局面，否则为必胜局面； 2）在必胜局面下，因为所有数按位异或的结果是大于零的，那么通过一次取，将这个（大于其它所有数按位异或的结果的）数下降到其它所有数按位异或的结果，这时局面就变为必败局面了。 我们用 (a，b，c) 表示某种局势 首先 (0，0，0) 显然是奇异局势，无论谁面对奇异局势，都必然失败。 第二种奇异局势是 (0，n，n)，只要与对手拿走一样多的物品，最后都将导致 (0，0，0)。仔细分析一下，(1，2，3) 也是奇异局势，无论对手如何拿，接下来都可以变为 (0，n，n) 的情形。 对于以上两种情况，均有三个数疑惑后为零。其实，只要取完数后使得剩下局面为三数异或结果为零，则胜。 例如 (14，21，39)，14 (+) 21=27，39-27=12，所以从 39 中拿走 12 个物体即可达到奇异局势 (14，21，27)。 我们来实际进行一盘比赛看看: 甲：(7,8,9)->(1,8,9) 奇异局势 乙：(1,8,9)->(1,8,4) 甲：(1,8,4)->(1,5,4) 奇异局势 乙：(1,5,4)->(1,4,4) 甲：(1,4,4)->(0,4,4) 奇异局势 乙：(0,4,4)->(0,4,2) 甲：(0.4,2)->(0,2,2) 奇异局势 乙：(0,2,2)->(0,2,1) 甲：(0,2,1)->(0,1,1) 奇异局势 乙：(0,1,1)->(0,1,0) 甲：(0,1,0)->(0,0,0) 奇异局势 甲胜。 代码： import java.util.Scanner; /** * Created by YYL on 2017/2/24. */ //A先取，若A面对奇艺局面，则失败 public class NimmGame { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt();//堆数 int [] temp=new int[n]; for (int i = 0; i <n ; i++) { temp[i]=scanner.nextInt();//初始化每堆的个数 } int result=temp[0]; for (int i = 1; i <n ; i++) { result^=temp[i]; } if(result==0) System.out.println("B胜"); else System.out.println("A胜"); } } 运行结果 3 7 8 9 A 胜 ———————————————— 理论： 博弈 2： 巴什博奕（Bash Game） 巴什博奕基础情形 只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜。 如果 n = m + 1； 我们假设第一个人拿走了 k 个， 还剩下 m + 1 - k。 因为 1<=（m + 1 - k）<= m, 所以， 剩下的部分一定可以被第二个人一次性取走。 现在我们将上述规律加一推广： 如果 n=（m+1）r+s（r∈ N，s<= m)； 那么先取者要拿走 s 个物品，如果后取者拿走 k（k<= m) 个，那么 先取者再拿走 m+1-k 个，结果剩下（m+1）（r-1）个， 以后保持这样的取法，那么先取者肯定获胜 那么在我方取最优解的情况下： 现在我们就发现了巴什博弈的一个必败态： （m + 1）* r （r∈ N）； 那么巴什博弈的必胜态也就可以反推出来： （m + 1）* r + k （1<=k<= m, r ∈N）; 现在我们换一个角度来考虑这个问题： 如果物品数量随机（Random），那么先手一方胜利的概率是 m/(m+1)，后手方胜利的概率是 1/(m+1) 对于上述的问题， 我们可以用 mod 的方法快速的求出答案（其实三种博弈的最优美之处就是能用 %^& 这三个符号完美解答） ` 巴什博弈演变 硬币问题 1 Alice 和 Bob 在玩这样的一个游戏， 给定 k 个数组 a1,a2,a3,……ak。 一开始， 有 x 枚硬币， Alice 和 Bob 轮流取硬币， 每次所取硬币的枚数硬顶要在 a1,a2,a3,……ak 之中。 Alice 先取， 取走最后一枚硬币的一方获胜。 当双方都采取最优策略的时候， 谁会获胜？ 题目假定 a1,a2,a3,……ak 之中一定有 1。 下面我们来分情况讨论到达自己时， 还有 j 枚硬币的胜负情况： 题目规定， 取光所有的硬币就获胜， 这等价于轮到自己时如果没有硬币就失败， 因此 j = 0 时是必败态。 如果对于某个 i（i<=i<= k）, 就 j - ai 是必败态， 那么 j 就是必胜态（如果当前有 j 枚硬币， 只要取走 ai 枚对手就必败→自己必胜）； 如果对于任意的 i（1 <= i <= k）， j - ai 都是必败态的话， j 就是必败态（无论对手这么走， 对手都必胜， 自己必败） 根据这些规则， 我们都能利用动态规划算法按照 j 从小到大的顺序计算必胜态。， 只要看 x 是必胜态还是必败态， 我们就知道谁会取胜； 通常来说， 通过考虑每个小状态的取胜条件， 判断必胜条件和必胜态， 是有胜负的游戏的基础； 上代码 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int x，k; bool win[100000]; int a[100000]; void Bash() {//轮到自己没有硬币则必败； win[0] = false; for (int i = 1; i <= x; i++) { //如果可以让对手达到必败态， 则自己必胜； win[i] = false; for (int j = 0; j < k; i++) win[i] |= (a[j] <= i && !win[i - a[j]]); // |= 真真为真 真假为真 假假为假 } } int main(void) { while (scanf("%d %d", &x, &k) != EOF) { for (int i = 0; i < k; i++) scanf("%d", &a[i]); sort(a, a + k); memset(win, 0, sizeof(a)); Bash(); if (win[x]) printf("Alicce!\\n"); else printf("Bob!\\n"); } return 0; } 硬币问题 2 n 枚硬币排成一个圈。Alice 和 Bob 轮流从中取一枚或者两枚硬币， 不过， 取两枚时这两枚必须是连续的。硬币取走之后留下空位，想个空位的硬币被认为是不连续。 A 开始先取， 取走最后一枚硬币的一方获胜。双方都采取最优策略的时候谁会取胜？ 按照上面问题的想法， 我们来拆分一下问题； 首先我们是想一下如下的情况。 将所有的剩余硬币分成完全相同的组别， 这个是必胜状态还是必败状态？ 事实上这是必败态， 无论采取什么策略， 对手只要在另一组中使用相同的策略， 就有回到了相同分组的状态， 而最终的相同分组状态就是（0，0）； 接下来， 我们回归正题。A 在第一取走一枚或者两枚硬币之后，称圈的硬币就变成了长度为 n - 1 或者是 n - 2 的。 Bob 只要在中间位置根据链的奇偶性， 在链的中间位置取走 1 或者 2 枚， 就可以把所有的硬币分成长度相同的两个链。 正如我们所说的，这是必败态， 也就是说， Alice 必败， Bob 必胜，只不过， 当 n <= 2， Alice 可以一步取光， 所以胜利的是 Alice， 除此之外， 在都进行最优解的情况下， Alice 必败。 int k; if(k <= 2) printf("Alice!\\n"); else printf("Bob\\n"); Euclid’s Game(poj 2348) poj 传送门 题目大意： 给定两个整数 a, b。Alice 和 Bob 轮流用较大的数减去较小的数的整数倍， 并且相减之后的值不小于 0。 如果在自己的回合之内， 相减之后的结果为零， 那么获胜。Alice 先手。 根据上述两个问题我们有两个规律可以用上：1. 将大问题划分为小问题在进行解决 2. 寻找开始（或结束）位置的必败态（或必胜态）在加以正推（或倒推）； 划分： 我们按照后续处理的差别， 将其分为 3 类： 1.b < a, 我们将 a b 进行交换， 使得 b 恒大于 a； 2.a > (b - a)； 3.a < (b - a) ; 对于第一种情况， 为了便于后续处理， 我们将其认为是默认情况； 对于第二种情况， 我么可以选择在 b 的基础上减去 a， 或者减去 2a 和以上；（这一种是有余地的方案） 对于第三种情况， 我们仅仅只有减去 a 这一种方法； 对于第一种情况：默认的调整方式， 我们用来调整 a，b 代表的值， 在这里不用讨论（这里实际指的就是 swap 函数的调用过程） 对于第三种情况， 仅仅只有一种方案： 继续向下迭代， 直到出现最终结局； 对于第二种情况： 假设 x 是使 b - ax b) swap(&a, &b); if(b % a == 0) break; if(b - a > a) break; b -= a; flag = !flag; } if(flag) printf("Alice!\\n"); else printf("Bob!\\n"); 博弈论基础知识：巴什博奕 + 威佐夫博奕 + 尼姆博弈 (及 Staircase) 【嵌牛导读】：介绍一些博弈，因为算法有时候就是应用在博弈问题上。 【嵌牛鼻子】：巴什博奕 (Bash Game)。威佐夫博奕 (Wythoff Game)。尼姆博奕 (Nimm Game)。Nim Staircase 博奕。 【嵌牛提问】：什么是巴什博奕 (Bash Game)。威佐夫博奕 (Wythoff Game)。尼姆博奕 (Nimm Game)。Nim Staircase 博奕？ 【嵌牛正文】： (一) 巴什博奕 (Bash Game): 只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜. 若 (m+1) | n，则先手必败，否则先手必胜。 显然，如果 n=m+1, 那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发 现了如何取胜的法则：如果 n=(m+1) r+s,(r 为任意自然数，s≤m), 那么先取者要拿走 s 个物品，如果后取者拿走 k (≤m) 个，那么先取者再拿 走 m+1-k 个，结果剩下 (m+1)(r-1) 个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下 (m+1) 的倍数，就能最后获胜. (二) 威佐夫博奕 (Wythoff Game): 有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜. 奇异局势下先手必败，非奇异局势下先手必胜。 这种情况下是颇为复杂的。我们用 (ak,bk)(ak ≤bk ,k=0,1,2,...,n) 表示两堆物品的数量并称其为局势，如果甲面对 (0,0), 那么甲已经 输了，这种局势我们称为奇异局势。前几个奇异局势是：(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20). 可以看出，a0=b0=0,ak 是未在前面出现过的最小自然数，而 bk= ak + k, 奇异局势有如下三条性质： 1、任何自然数都包含在一个且仅有一个奇异局势中. 由于 ak 是未在前面出现过的最小自然数，所以有 ak > ak-1 , 而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 . 所以性质 1. 成立. 2、任意操作都可将奇异局势变为非奇异局势. 事实上，若只改变奇异局势 (ak,bk) 的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使 (ak,bk) 的两 个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势. 3、采用适当的方法，可以将非奇异局势变为奇异局势. 假设面对的局势是 (a,b), 若 b = a, 则同时从两堆中取走 a 个物体，就变为了奇异局势 (0,0)；如果 a = ak ,b > bk, 那么，取走 b - bk 个物 体，即变为奇异局势；如果 a = ak , b <bk , 则同时从两堆中拿走 ak - ab - ak 个物体，变为奇异局势 ( ab - ak , ab - ak+ b - ak) ；如果 a > ak ,b= ak + k, 则从第一堆中拿走多余的数量 a - ak 即可；如果 a <ak ,b= ak + k, 分两种情况，第一种，a=aj (j < k), 从 第二堆里面拿走 b - bj 即可；第二种，a=bj (j < k), 从第二堆里面拿走 b - aj 即可. 从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜. 那么任给一个局势 (a,b), 怎样判断它是不是奇异局势呢？我们有如下公式： ak =k (1+√5)/2, bk= ak + k (k∈N) 奇妙的是其中出现了有关黄金分割数的式子：$\frac{1+\sqrt{5}}{2} = 1.618...$, 若两堆物品个数分别为 x,y (x<y)，则 k=y-x，再判断 x 是否等于 $y-x\times \frac{1+\sqrt{5}}{2}$ 即可得知是否是奇异局势。 参考例题：POJ1067 取石子游戏 参考代码： var a,b:longint;begin repeat readln(a,b); if a>b then begin a:=a xor b; b:=a xor b; a:=a xor b; end; if a=trunc((b-a)*(sqrt(5)+1)/2) then writeln(0) else writeln(1); until seekeof;end. (三) 尼姆博奕 (Nimm Game): 有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜. 这种情况最有意思，它与二进制有密切关系，我们用 (a,b,c) 表示某种局势，首先 (0,0,0) 显然是奇异局势，无论谁面对奇异局势，都必然失 败。第二种奇异局势是 (0,n,n), 只要与对手拿走一样多的物品，最后都将导致 (0,0,0). 仔细分析一下，(1,2,3) 也是奇异局势，无论对手如 何拿，接下来都可以变为 (0,n,n) 的情形. 计算机算法里面有一种叫做按位模 2 加，也叫做异或的运算，我们用符号 xor 表示这种运算。这种运算和一般加法不同的一点是 1+1=0. 先看 (1,2,3) 的按位模 2 加的结果： 1 = 二进制 01 Xor 2 = 二进制 10 Xor 3 = 二进制 11 ——————— 0 = 二进制 00 对于奇异局势 (0,n,n) 也一样，结果也是 0. 任何奇异局势 (a,b,c) 都有 a xor b xor c =0。该结论可以推广至若干堆，都是成立的。 如果我们面对的是一个非奇异局势 (a,b,c), 要如何变为奇异局势呢？假设 a < b< c, 我们只要将 c 变为 a xor b, 即可，因为有如下的运算 结果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=0 xor 0=0. 要将 c 变为 a xor b, 只要从 c 中减去 c-(a xor b) 即可. (四) Nim Staircase 博奕: 这个问题是尼姆博弈的拓展：游戏开始时有许多硬币任意分布在楼梯上，共 n 阶楼梯从地面由下向上编号为 0 到 n。游戏者在每次操作时 可以将楼梯 j (1<=j<=n) 上的任意多但至少一个硬币移动到楼梯 j-1 上。游戏者轮流操作，将最后一枚硬币移至地上（0 号）的人获胜。 算法：将奇数楼层的状态异或，和为 0 则先手必败，否则先手必胜。证明略。 例题：Poj1704 这道题可以把两个棋子中间间隔的空格子个数作为一堆石子，则原题转化为每次可以把左边的一堆石子移到相邻的右边的一堆中。也就 是阶梯尼姆博弈，注意对输入数据先排序，然后倒着往前数（a [n]-a [n-1]-1 为第一个），奇数个数到的就做一下 xor，其中最前面的看 做 a 1-0-1，参考程序： var t,n,b,i,j:longint; a:array [0..1000] of longint;begin readln (t); repeat dec (t); readln (n); for i:=1 to n do read (a [i]); qsort (1,n);// 快排略 j:=0; b:=0; for i:=n downto 1 do begin inc (j); if odd (j) then b:=b xor (a [i]-a [i-1]-1); end; if b=0 then writeln ('Bob will win') else writeln ('Georgia will win'); until t=0;end. 其他题目 【hdu-1846】Brave Game 【hdu-4764】Stone https://www.cnblogs.com/zwfymqz/p/8460192.html 版权声明：本文为CSDN博主「yyl424525」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/yyl424525/article/details/56840182 版权声明：本文为CSDN博主「sun897949163」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/sun897949163/article/details/50609070 https://www.jianshu.com/p/0b84d77a3bfd