信息学竞赛 CPP 进阶篇

宏

软件的发展历史，是不断追求重用的历史。

c++ 如何实现重用？

• 函数：通过参数变化，暴露接口，隐藏实现
• 宏： 模板代码，编译时替换展开
• 类：更复杂的抽象，暴露接口，隐藏内部结构、状态、实现细节
• 模板泛型：把算法和类型分离开

宏的常见用法

三种格式

• define XXX

  只是定义了一个符号，常用于条件编译

  可用#undef XXX 取消该定义

• define PI 3.14

  定义一个常量，避免魔法数字，新标准建议用 const

• define ADD(x,y) x+y

  有参的宏定义

  表面看像个函数，实际上是代码的硬替换

  有建议，用内联函数代替有参宏定义

宏在编译前进行宏替换处理，也叫：宏展开

这种替换是硬性的替换，与类型、语法无关，使用不当，容易引发诡异的错误。

例如：#define PI 3.14;

其后的源码：a = PI r r;

在编译前，被替换为：a = 3.14; r r;

原因仅仅是：#define 语句后边多了个分号。

宏的常见应用场景

• 避免魔法数字，增加程序可读性，可维护性。

  #define M 100
  ....
  char x[M];
  x[M-1]='\0';

  注意陷阱：

  #define M 100+5
  ... 
  int x[2*M];  // 想开两倍空间，实际展开：int x[2*100+5];

• 预定义宏

  __FILE__   // 两个下划线，当前文件
  __LINE__  // 当前行号
  __DATE__  // 当前日期
  __TIME__  // 当前时间

• 防止头文件多次包含

  传统方案是用宏配合条件编译：

  #ifndef _MY_H_
  #define _MY_H_
  // 文件内容
  #endif

  另一个方案，文件开始处：#pragma once

  以此表明：此文件只编译一次

  但，有些编译器可能不支持

• 管理调试信息

  开发中，经常会在程序的中间步骤上输出调试信息，开发结束后则不需要这些输出

  //#define LOG(x) cout << (x) << endl;
  #define LOG(x)
  int main()
  {
      cout << "normal" << endl;
      LOG("only for debug...")
    return 0;
  }

• 不调函数，提高效率

  比如，经常交换两个变量，不想用函数开销，则可以用有参宏替换：

  #define SWAP(a,b) {int t=a; a=b; b=t; }
  int main()
  {
      int a=5,b=8;
      SWAP(a,b)
      cout << a << "," << b << endl;
      return 0;
  }

  这有个小缺点：当类型不是整数，岂不悲哀？

  我们心里希望，那个临时变量类型与 a, b 是一样的。不一定是整数！

  也有办法：

  #define SWAP(a,b) {typeof(a) t=a; a=b; b=t;}

  typeof 与 sizeof 类似，它在编译阶段来确定参数的类型，所以并非真正的“动态”。

另一个有参宏的例子：

求最大值

#define MAX(a,b) \
    ({ typeof(a) _a = (a); \
       typeof(b) _b = (b); \
     _a > _b ? _a : _b; })
int main()
{
    cout << MAX(2+3,4*5) << endl;
    return 0;
}

实时效果反馈

1. 关于c++宏, 说法正确的是：__

• A 宏的展开在程序运行时进行

• B 在宏定义的末尾不能出现分号

• C 宏定义只能写在同一行

• D 为了避免魔法数字，也可以使用const定义常量

2. 下列x平方的宏，哪个更恰当？__

• A #define PF(x) x*x

• B #define PF(x) (x*x)

• C #define PF(x) ((x)*(x))

• D #define PF (x) ((x)*(x))

答案

1=>D 2=>C

宏(2)

宏在编译前执行，可以很简单，也可以超级复杂。

因为宏可以嵌套展开。

#define V1 "27.3.6"
#define V2 "1.4"
#define VER(pre,v) pre "." #v
#define PR(x) cout << (x) << endl;
int main()
{
    PR(VER(V1,25))
    PR(VER(V2,25))
    return 0;
}

运行结果：

更多的宏特性

宏的展开规则：类似于函数调用，有参宏展开时，先对其参数宏展开

有例外：如果宏定义中有#或##则其参数不展开

我们可以利用这个特性，观察宏展开的结果：

#define TO_STR(x) TO_S(x)
#define TO_S(x) #x
....
    PR(TO_STR(VER(V1,25)))

如果x是参数，则#x 是把x加双引号包围

## 则是拼接的意思，可以造出一个标识符来

#define ODD(x,y) int y##x ()
ODD(in,ma)
{
    cout << "haha" << endl;
    return 0;
}

这个功能太强大了，如果精心设计，我们可以改变c++的语法！

但，程序的可读性会严重下降。

宏的优势

宏的优势在于，可以在编译前对源码进行变换。

这种变换不占用运行时，使用得好，可以减少模板代码，可以提高效率。

c++还有很多关于宏的很细致的规定和约束，

并非一开始就设计成那样，这是长期实践，积累，修补的结果。

一般认为，适量使用宏可以获得效率、代码可读性、兼容性、可维护性等方面的益处。

但，过于复杂的宏很可能是隐患。

宏注意

• 有参宏的括号重要性

#define AREA(r) 3.14*r*r

有参宏，定义了圆面积的计算方法。

如果使用：

    double a = AREA(1+1) ;
    cout << a << endl;

不会得到期望的结果，以内，硬性替换后，相当于：

double a = 3.14*1+1*1+1;

较好的方法是：

#define AREA(r) (3.14*(r)*(r))

• 宏替换的第一个位置必须为合法的标识符

  #define 0x ABC

• 宏替换的后边内容也不能随意写，引号必须配对

  #define P1 at"

• 双引号内的内容不会被替换

  #define S(a) "a"

• 一个标识符整体被替换，它的一部分不会替换

宏：只负责文字上的替换，不管语法的事情，也不会计算表达式。

常量，可以用 const 代替

有参宏，一般可以用 inline 函数代替

很多情况也可以使用 函数模板、类模板来解决。

总结

就像 goto 语句一样，宏在有些场合用，很容易，很恰当；但，滥用，会导致灾难。

理论上，宏足以强大到用 c 构建出另一种高级语言来。

实践上，复杂的宏，常常让我们涌起砸碎显示屏的冲动。

实时效果反馈

1. 关于宏的弱点, 说法==不正确==的是：__

• A 逻辑稍复杂后，可读性差

• B 难于调试

• C 没有名字空间，污染全局域

• D 拖慢运行速度

2. c中的有参宏，c++中建议用什么代替？__

• A const

• B inline function

• C function template

• D function pointer

答案

1=>D 2=>B

内联函数

为什么要定义如下宏？

#define MIN(x,y) ((x)<(y)?(x):(y))

更好一点的版本：

#define MIN(a,b) \
    ({ typeof(a) _a = (a); \
       typeof(b) _b = (b); \
     _a < _b ? _a : _b; })

既然，这么简单的功能，如此繁冗的代码，使用函数不好吗？

函数调用的弱点

因为，如果用一个函数，调用函数会耗费运行时。

函数调用过程：

1. 保存当前的执行断点（执行上下文）
2. 分配形参变量空间
3. 用实参来初始化形参
4. 跳转到被调函数代码执行
5. 释放形参变量（可能有必要的清理工作，比如析构函数）
6. 恢复原来的执行断点，继续主调函数的工作

如果频繁地切换小函数，只执行很短的代码，则切换环境会相对浪费时间。

如果，直接写 ?: 表达式，又太麻烦，可读性不好。

宏呢？虽然简单如此，也要一堆括号，防止参数中含有表达式。

使用宏的弱点

• 比起函数来，宏的可读性差，宏不容易调试，不容易维护

• 宏没有类型，编译器没办法做更多的介入和检查

• 宏不能访问类的私有成员，但使用函数，可以声明友元函数

inline function

有没有什么办法，既有函数的形式，又不真的调用函数呢？

内联函数是个解决方案

inline int min(int a, int b)
{
    return a < b ? a : b;
}
int main()
{
    cout << min(5, 6) << endl;
    cout << min(6+8, 5+4) << endl;
    return 0;
}

这段代码，

编译时，会把对 min 的调用直接展开为代码，

这样，虽然最终生成的代码变长了，也包含了重复，但执行效率提高了。

注意事项

• inline 关键字并非函数签名的一部分，它并非是接口，它是控制实现方式的。

inline 只有与函数的定义（而非声明）放在一起才有效。

• 定义在 class 内的成员函数自动变为内联函数

class MyA{
public:
　　int add() { return i+j;}
　　inline int dec() { return i-j;}
　　int getNum();
private:
    int i,j;
}
inline int MyA::getNum(){
    return i;
}

• 小的函数用内联（建议小于10行），大函数得不偿失

带来的问题

宏是不管类型的，仅仅是文字上的替换。

函数是有类型的，编译器可以介入检查，虽然安全，但带来了类型限制。

比如，min 函数怎么指定其参数是：字符串，或其它更复杂的类型呢？

这方面，宏的类型无关反而成了优点。

但，c++的函数模板，类模板可以解决这个问题。

实时效果反馈

1. 关于inline, 说法==不正确==的是：__

• A inline 写在.h文件中，则该函数编译为内联函数

• B inline 与实现写在一起才有效，以便于编译时展开。

• C 直接定义在 class 中的函数，自动编译为内联函数

• D 一般建议小函数用 inline，函数太庞大，用内联得不偿失

2. 内联函数与宏的关系是：__

• A 内联函数可以完全代替宏的功能

• B 使用内联比使用宏执行效率更高

• C 一般情况下，与内联函数相比，使用宏的代码可读性更好一些

• D 与宏相比，内联函数的可读性，可维护性更好些。

答案

1=>A 2=>D

函数模板

c++中有泛型编程的概念。

即，编程时，类型是不确定的，在调用处，替换为真正的具体类型。

c++的指针泛化，在一定程度上解决了泛型编程的问题，但指针泛化是在运行时发生的，对泛型指针的调用，比普通的成员函数调用，更耗费处理器时间。

而这里所说的泛型编程，力求在编译阶段解决问题，不能降低执行效率。

c++使用函数模板，类模板来解决这个问题。

函数模板定义

以 template 来开启泛型函数声明

告诉编译器， T是个待定的类型，在具体调用时编译为实际的类型。

template <typename T>
void swap1(T& a, T& b)
{
    T t = a;
    a = b;
    b = t;
}
int main()
{
    int a=5,b=8;
    swap1<int>(a,b);
    //swap1(a,b);
    cout << a << "," << b << endl;
    return 0;
}

标准库中已经有了 std::swap，所以改了名字

调用的时候，用来指定 T 的具体类型，

这里，不指定也可以，因为，编译器能推断出 T 的类型是 int

可以把 T 换成其它类型，甚至是用户自己定义的类型来试试。

使用注意

• 编译器会对函数模板进行两次编译，第一次编译模板函数本身，第二次替换类型后，当作普通函数编译
• 函数模板不能隐式转换，类型需要严格匹配
• 函数模板可以有多个模板类型参数
• 无法自动推断返回值类型，需要自己指定

template<typename T1, typename T2>
T1 f(T2 x, T2, y) { ... }
....
auto t1 = f<int>(a, b);  // 指定了返回值类型

类型名需要从左到右依次指定（可以部分指定），所以返回值应该定义为 T1，

否则，比如在最后一个typename, 为了指定返回值，就需要把所有名字都指定了。

与函数重载关系

可以共存。

函数重载，在有限的类型种类中，分别定制如何处理，而模板类型可以没有限定。

当发生二义时，首先选普通函数，其次才考虑模板

如果模板可以更精确匹配，选择模板

我们可以使用空尖括号，限定只能使用模板

与 inline 联合使用

这样用可以代替一些有参宏，并且是类型安全的。

比如，经典的求最大值

template <class T>
inline T max1(const T& a, const T& b)  // 标准库中已有max
{
    return a > b? a : b;
}

这样，兼具了宏的类型无关，和内联函数编译监督两个好处。

实时效果反馈

1. 关于函数模板, 说法正确的是：__

• A 与宏一样，函数模板在编译前展开

• B 函数模板比普通函数执行更有效率

• C 函数模板在编译时，把泛定类型确定为具体类型

• D 函数模板，在运行时把泛定类型替换为普通类型

2. 如果有 template<class T> T f(T a, Tb){....}，以下错误的是：__

• A f(1,2);

• B f(1,2);

• C f(1.2, 3.4);

• D f(1.2, 3);

答案

1=>C 2=>D

函数模板特化

语法固然重要，但更重要的是最佳实践。

宏可以带来效率，可以类型无关；函数可以有可预料的行为和安全的类型。

内联的函数模板可以兼具两者优势。

常见的用法举例：

// 删除堆指针的时候，一般的行为
template <typename T>
inline void SafeDelete(T*& p)
{ 
    if(p){delete p; p=NULL;} 
}
// 返回数组变量的元素个数
template <typename T>
inline int CountOf(const T& array)
{  
    return sizeof(array) / sizeof(array[0]);
}
// 判断一个类型是否为 unsigned 类型
template <typename T>
inline bool IsUnsigned(T)
{  
    return (T)-1 > 0;
}

对特殊情形的单独处理

• 可以定义一个重载的普通函数
• 可以定义一个特化的函数模板

特化的例子

template <class T>
bool eq(const T& a, const T& b)
{
    return a==b;
}
template<>
bool eq<char*>(char* const & p1, char* const & p2)
{
    cout << "eq...<>" << endl;
    return strcmp(p1,p2)==0;
}

调用处：

    int a = 10;
    cout << eq(a,5+5) << endl;
    char* p1 = "abc";
    char* p2 = "abc";
    char p3[] = "abc";
    cout << eq(p1, p2) << endl;
    //cout << eq(p1, p3) << endl;

注意：p1,p3 比较会报编译错误，因为：类型不一致。模板函数类型严格。

p1 类型：char*

p3 类型：char[4]

其实，我们也可以直接用重载，它会进行一些必要的类型转换，不会要求那么严格匹配。

bool eq(char* p1, char* p2)
{
    cout << "eq...normal" << endl;
    return strcmp(p1,p2)==0;
}
int main()
{
    int a = 10;
    cout << eq(a,5+5) << endl;
    char* p1 = "abc";
    char* p2 = "abc";
    char p3[] = "abc";
    cout << eq<>(p1, p2) << endl;  // 强制使用模板
    cout << eq(p1, p3) << endl;
    return 0;
}

实时效果反馈

1. 关于函数模板与重载函数的关系, 说法正确的是：__

• A 重载函数不可以和函数模板同名

• B 模板与重载函数都匹配时，优先使用具体函数版本

• C 函数模板匹配参数很宽松，可以自动进行必要的类型转换

• D 函数模板不可以实现为内联函数

2. 为解决函数模板对有些类型不通用的问题，哪个解决方案最==不推荐==？：__

• A 定义函数模板的特化版本

• B 定义针对具体类型的普通函数重载版本

• C 在函数模板实现中用 if 语句断定类型，分别处理

• D 设计复杂的宏来取代模板

答案

1=>B 2=>D

函数模板与数组引用

当数组作为参数传递时，会退化为指针。

也就是说，数组的元素个数信息会丢失。我们可以通过typeid来检查验证。

void g(int x[3])
{
    cout << typeid(x).name() << endl;
    // [3] 是徒劳，因为退化问题，与 int x[], 或者 int* x 是一样的
}

注意，别忘了：#include

调用处：

    int* p;
    int q[] = {1,2,3};
    int a = 16;
    g(q);
    cout << typeid(p).name() << endl;
    cout << typeid(q).name() << endl;

但是，当数组作为引用传递时，就不一样：

void g(int (&x)[3])
{
    cout << typeid(x).name() << endl;
}

注意，括号的使用，

若不然，表示x是数组，元素是 int&

如果希望元素个数==泛定==怎么办呢？

我们可以这样考虑，在编译的时候，肯定是知道元素个数的，可不可以先写N，在编译时，再替换为具体的数字呢？这不恰恰是模板的特征吗？

确实可以！

template <int N>
void f(int (&x)[N])
{
    cout << typeid(x).name() << endl;
}

在试试传入数组吧。

最佳实践

经常，我们希望 cout 在输出数组类型时，能输出有所得元素，并不想打印指针

能不能写一个通用得函数模板，对所有的数组都打印它的所有元素呢？

template <class T, int N>
void print_array(T (&x)[N])
{
    for(int i=0; i<N; i++) cout << x[i] << " ";
    cout << endl;
}
int main()
{
    int a[] = {1,2,3,4,5};
    char* b[] = {"abc", "hah..", "123"};
    print_array(a);
    print_array(b);
    return 0;
}

实时效果反馈

1. 关于数组和指向它第一个元素的指针, 说法正确的是：__

• A 该数组与指针是同一个类型

• B 这是两个完全不同的类型，不能自动转换

• C 指针类型可以自动转为数组类型

• D 数组类型可以自动转为指针类型

2. template <类型列表>，语法==错误==的是：__

• A template <>

• B template <typename T>

• C template <typename T, int 3>

• D template <typename T1, int N>

答案

1=>D 2=>C

类模板

我们在前边定义过 Point 类型，包含 x，y 坐标

struct Point{
    int x;
    int y;
};

但，x, y 类型有几种可能： int, double, long long 甚至 char 都是选择。

我们不希望对类似的代码定义许多次，仅仅是 x y 类型上有差异，其它都一样或类似。

类模板就是用来解决这个问题的。

语法上，与函数模板类似，以 template 来开启模板的定义：

template <typename T>
struct Point{
    Point(T& a, T& b):x(a),y(b){ }
    friend ostream& operator<< (ostream& out, Point<T>& obj){
            out << "(" << obj.x << "," << obj.y << ") ";
            return out;
    }
    T x;
    T y;
};

调用方式：

Point<int> a(1,2);
Point<double> b(2.3, 4);
cout << a << endl;
cout << b << endl;

注意，这里的 operator<< 并非是成员函数，它是模板函数，

而且，它一般是定义在类外的。

但此处，如果挪到类外：

template <typename T>
ostream& operator<< (ostream& out, Point<T>& obj){
    out << "(" << obj.x << "," << obj.y << ") ";
    return out;
}

会导致编译不通过。

这是由于模板的二次编译造成的。

解决的方案，是明确告知编译器， operator<< 是个函数模板，并在类内具化。

即，增加前置声明

template <typename T> class Point;
template <typename T>
ostream& operator<< (ostream& out, Point<T>& obj);
template <typename T>
struct Point{
    Point(T a, T b):x(a),y(b){}
    friend ostream& operator<< <T> (ostream& out, Point<T>& obj);
    T x;
    T y;
};
template <typename T>
ostream& operator<< (ostream& out, Point<T>& obj){
    out << "(" << obj.x << "," << obj.y << ") ";
    return out;
}

一般工程规范情况下，要划分 .h 文件和 .cpp 文件。

划分职责如下：

头文件主体内容：

///////// .h
template <typename T> class Point;
template <typename T>
ostream& operator<< (ostream& out, Point<T>& obj);
template <typename T>
struct Point{
    Point(T a, T b):x(a),y(b){}
    friend ostream& operator<< <T> (ostream& out, Point<T>& obj);
    double distance(Point<T>& that);
    T x;
    T y;
};

.cpp 主体内容：

////////// .cpp
template <typename T>
ostream& operator<< (ostream& out, Point<T>& obj){
    out << "(" << obj.x << "," << obj.y << ") ";
    return out;
}
template <typename T>
inline SQ(T x) { return x * x; }
template <typename T>
double Point<T>::distance(Point<T>& t)
{
    return sqrt(SQ(t.x-x) + SQ(t.x-x));
}

使用场景

int main()
{
    Point<int> a(1,2);
    Point<int> b(3,4);
    Point<double> c(2.3, 4);
    cout << a << b << c<< endl;
    cout << a.distance(b) << endl;
    return 0;
}

实时效果反馈

1. 关于类模板, 说法正确的是：__

• A 类模板在实例化时，可以根据参数自动推断泛定类型

• B 类模板实例化时，需要用<>中指定具化类型

• C 与宏类似，类模板在编译之前进行替换展开

• D 类模板只能有1个模板参数

2. 当在类模板内声明友元函数，类外去定义，说法错误的是：__

• A 类模板和友元函数模板都要前置声明

• B 类内声明要对友元函数模板具化

• C 该友元函数一定实现为函数模板形式

• D 该友元函数不能重载

答案

1=>B 2=>D

栈的数组实现

前边的课程中，我们实现过简单栈，但元素的类型是定死的。

现在有了模板，我们可以类型灵活起来，顺带也让数组大小灵活起来

还记得我们之前实现的支持任意类型的栈吗？

那个任意是有代价的。

• 通过 IObj* 访问 User 对象的成员是多态访问，不是直接编译为确定函数的调用

• MyStack 与 User 数据间是聚合关系，不是组合。

  栈的数组中只保存对象指针，而不是对象本身，内存多次 new，效率不高

• 如果用户的数据，有些是局部的，有些在堆中，管理将十分麻烦。

有了类模板，我们可以在不损失性能的前提下，实现类型无关。

template <typename T>
struct IStack{
    virtual ~IStack() {}
    virtual IStack& push(const T&) = 0;
    virtual T pop() = 0;
    virtual bool empty() = 0;
};

c++中，接口并不特殊，当然可以是模板类型

其它类可以继承这个模板，可以普通类，也可以是类模板。

但，无论如何，在继承时，都需要对 IStack进行具化处理。

template <typename T>
class MyStack:public IStack<T>{
public:
    MyStack() { n = 0; }
    virtual MyStack& push(const T& x) override{
        if(n>=100) throw "stack overflow";
        data[n++] = x;
        return *this;
    }
    virtual T pop() override{
        if(n==0) throw "empty pop!";
        return data[--n];
    }
    virtual bool empty() override{
        return n == 0;
    }
private:
    T data[100];
    int n;
};

这个类模板还有点小缺陷，数组的大小顶死了，其实可以当模板参数的。

在用户创建实例的时候指定这个参数：

template <typename T, int N>
class MyStack:public IStack<T>{
public:
    MyStack() { n = 0; }
    virtual MyStack& push(const T& x) override{
        if(n>=N) throw "stack overflow";
        data[n++] = x;
        return *this;
    }
    virtual T pop() override{
        if(n==0) throw "empty pop!";
        return data[--n];
    }
    virtual bool empty() override{
        return n == 0;
    }
private:
    T data[N];
    int n;
};

当然，调用处要多指定一个具化参数：

MyStack<Point,200> a;

实时效果反馈

1. 关于类模板, 说法正确的是：__

• A 含有虚函数的类不能做成类模板

• B 接口不能是类模板

• C 类模板无法被普通的类继承

• D 类模板可以指定多个泛型参数

2. 关于类模板的继承，==错误==的说法是：__

• A 继承的类不一定是类模板，也可以是普通类

• B 使用类模板继承时，子类的模板参数个数必须与父类模板相同

• C 继承时，需要对父类模板具化处理。

• D 类模板的成员函数，如果定义在类外，一定是函数模板

答案

1=>D 2=>C

类模板特化

与函数模板的情况类似，类模板有时也不能完全兼容所有泛定类型的处理。

这时，可以固定全部或部分的类型，来实现一个特殊的版本。

template <typename T1, typename T2>
class MyA{
public:
    MyA(const T1& a, const T2& b){
        cout << "MyA(T1, T2)" << endl;
    }
    void f1() { cout << "f1" << endl; }
    void f2() { cout << "f2" << endl; }
};
// MyA 模板的特化版，如需要，必须重新定义所有函数，或添加新函数
template<>
class MyA<int, int>{
public:
    MyA(const int& a, const int& b){
        cout << "MyA(int, int)" << endl;
    }
    ...
};

调用：

    MyA<int, double> a(1, 1.0);
    MyA<int, int> b(1, 1);
    b.f1(); // 错误，特化版中没有这个函数

如果我们的特化版本仅仅是某个局部有不同处理，大部分都相同，那不如用继承：

// 可以重用 MyA 模板的内容
struct MyB: public MyA<double,double>{
    MyB(int x, int y):MyA(x,y){}
};

调用：

    MyB c(2.0,2.0);
    c.f1();

特化的花样

特化能做出很多花样来，前边的例子是全特化

• 全特化

  template <>
  class MyA<int, int> {  // 这里所有参数都固定下来
      ....
  }

• 部分特化

  template <typename T>  // 列出剩余没有固定的类型
  class MyA<T, int> {  // 只固定部分类型
      ...
  }

• 偏特化

  对类型施加某些限制

  template <typename T1, typename T2>
  class MyA<T1*, T2*>{ // 限定了泛型必须为指针类型
      ...
  }

  再比如：

  template <typename T>
  class MyA<T, T>{  // 限定了两个泛型必须是相同的类型
      ...
  }

  如果某个调用同时匹配多个特化，就会产生二义性。

  可以针对特殊情况定义相应的全特化版。

与函数模板特化的比较

• 函数模板只能全特化

• 函数可以重载，类无法重载，同名的类会冲突

  namespace my{
  template <typename T1, typename T2>
  bool eq(const T1& a, const T2& b){
      return a == b;
  }
  template <typename T>
  bool eq(double a, const T& b){
      return fabs(a-b) < 0.0001;
  }
  template <typename T>
  bool eq(const T& a, double b){
      return fabs(a-b) < 0.0001;
  }
  }
  int main()
  {
      cout << my::eq(1.000001, 1) << endl;
      cout << my::eq(1, 0.999999) << endl;
      //cout << my::eq(1.000001, 1.0001) << endl;
      return 0;
  }

• 工程实践中，建议尽量优先使用函数模板特化、类模板特化，

  无法满足要求时，才使用函数重载、定义新的类

实时效果反馈

1. 关于模板特化, 说法正确的是：__

• A 函数模板支持全特化和部分特化

• B 类模板支持全特化和部分特化

• C 函数模板只能部分特化

• D 类模板只能部分特化

2. 当类模板对某个泛型的参数需要轻微修正函数行为，一般怎么处理？：__

• A 考虑继承类模板，重载其中不满足要求的函数

• B 写一个普通类，重载类模板

• C 写一个全新的类

• D 使用条件编译，分别处理

答案

1=>B 2=>A

队列模板

前边的学习中，实现过循环队列，是用数组实现的。

并且，也可以通过指针泛化来支持任意的用户定义类型。

但泛型版本更有效率上的优势。

本节利用模板知识，实现一个单链表的队列，其中的元素类型是泛定的。

队列容量没有限制。

原理

Que 含有两个节点指针，front 指向队头，back 指向队尾。

节点 Node 是实现机制，可以对外隐藏，实现为内部类。

Node 包装了用户类型 T data

实现

template <typename T>
class Que{
public:
    Que() { front = back = NULL; }
    ~Que() {
        while(!empty()){ cout << "debug: " << remove() << endl; }
    }
    Que& add(const T& x);
    T remove();
    bool empty() { return front==NULL; }
private:
    class Node{
    public:
        Node(const T& x){ data = x; next=NULL; }
        T data;
        Node* next;
    };
private:
    Node* front;
    Node* back;
};

节点类是队列内部使用的，不需要暴露给用户，所以是private

需要注意的是， class Node 并没有定义为模板类，是因为Que在具化的时候，就会一并具化 class Node，因而就消除了不确定的类型。

类外的实现：

template <typename T>
Que<T>& Que<T>::add(const T& x)
{
    Node* p = new Node(x);
    if(empty())
        front = p;
    else
        back->next = p;
    back = p;
    return *this;
}
template <typename T>
T Que<T>::remove()
{
    if(empty()) throw -1;
    Node* p = front;
    front = front->next;
    if(front==NULL) back = NULL;
    T rt = p->data;
    delete p;
    return rt;
}

这些都需要实现为函数模板，并且其中引用类的时候，要具化。

注意：析构的重要性，否则会产生内存泄漏

调用处：

    Que<int> a;
    a.add(1).add(2).add(3);
    while(!a.empty()) cout << a.remove() << endl;
    a.add(4).add(5);

模板对宏的比较优势

模板泛型体系是c++较晚才引入的特性。

此前，通过有参宏替换来实现。

其问题是：

• 宏展开的时候，无法语法追踪，写法太灵活。
• 宏替换在编译时，已经确定为具体的类型，无法让两个泛型实例并存。

实时效果反馈

1. 关于队列, 说法正确的是：__

• A 队列是后进先出的线性结构

• B 队列的实现可以是链表，数组，动态数组，块链或者更复杂的结构

• C 泛型队列模板与指针泛化的方案比起来，主要优势是适用更多类型

• D 两个不同用户类型的 Que 无法并存

2. 对于本节Que的实现，当物理内存耗尽，表现是：__

• A 程序行为不确定，与内存随机数据有关

• B 栈溢出错误

• C 会抛出异常，程序终止

• D add新数据没有效果

答案

1=>B 2=>C

traits 技术

我们在适用函数模板，类模板编程的时候，很快就会发现，一个模板代码很难尽善尽美，

经常会出现特殊情况。即，对某个类型，或某种类型要特殊处理。

• 使用类模板的特化如何？

  只修改一点点，大部分都要抄下来，违背了 don’t repeat 原则

• if ( T 是某某类型) 则： 。。。。

  这个如果是动态判断，消耗运行时处理器时间，有时，效率很敏感。

其实，我们可能也希望写 if( T 是某种类型 ) 。。。。 但，我们希望这个 if 能在编译时确定好，不用运行时现场断定类型，也就是所说的：静态反射机制

traits, 翻译为：特性，或特质，按c++之父的说法：

Think of a trait as a ==small object== whose main purpose is to ==carry information== used by another object or algorithm to determine “policy” or “implementation details”.

可以看到，关键字就是：携带类型信息，服务于其它类或函数。

而，这个类型信息是编译时的，不是运行时的。

示例

template <typename T, bool isPointer>
class Test{
public:
    void f() {
        if(isPointer) cout<< "POINTER "; // 类型不同特殊处理
        cout << "do somthing..." << endl;
    }
};
int main()
{
    Test<int,false>().f();
    Test<int*, true>().f();
    return 0;
}

当类型 T 为指针时，处理逻辑上轻微调整。

如果，用 if 实现分支处理，则需要传入一个 bool信息

客户会奇怪，因为这本应该与他无关。

实际上，这个bool信息显然可以在编译过程中，从T提取，方法：

template <typename T>
struct TestHelper{
    static const bool isPointer = false;
};
template <typename T>
struct TestHelper<T*>{
    static const bool isPointer = true;
};
template <typename T>
class Test{
public:
    void f() {
        if(TestHelper<T>::isPointer) cout<< "POINTER ";
        cout << "do somthing..." << endl;
    }
};
int main()
{
    Test<int>().f();
    Test<int*>().f();
    return 0;
}

经过这样处理，isPointer 这个逻辑就被封装在Test中

示例2

比如，我们开始有这样的类模板，

template <typename T>
class Test{
public:
    T f(T x);
private:
    T data;
};

后来，需求变更了，要求：

• 当 T 为指针时，传入为 int, 传出为 int*
• 当 T 为 int 时，传入为 int, 传出为 double

这时，就可以用trait技术了，

我们可以用trait辅助类封装原来的输入值和输出值的类型：

template <typename T>
struct mytrait{
    typedef T ret_t;
    typedef T par_t;
};
template <typename T>
struct mytrait<T*>{
    typedef int* ret_t;
    typedef int par_t;
};
template <>
struct mytrait<int>{
    typedef double ret_t;
    typedef int par_t;
};
template <typename T>
class Test{
public:
    typename mytrait<T>::ret_t f(typename mytrait<T>::par_t x);
private:
    T data;
};

注意： mytrait::ret_t 之前的 typename，这是因为，c++编译器默认::限定的东西是个value，而非type。

为了避免冗长，可以把这个长长的类型再次typedef

template <typename T>
class Test{
public:
    typedef typename mytrait<T>::ret_t ret_t;
    typedef typename mytrait<T>::par_t par_t;
    ret_t f(par_t x);
private:
    T data;
};

这种技巧很实用，因为 ret_t 很可能在程序中多处被引用。

实时效果反馈

1. 关于traits, 说法正确的是：__

• A traits 是一个复杂的函数模板，负责分发请求

• B traits 一般是一个很小的类模板，封装与泛定类型相关的类型信息

• C traits 是一个个独立的接口，普通类可以继承多个trait

• D traits 是一些重载函数

2. 使用traits封装后，间接地使用类型，其好处是：__

• A 隔离不同类型间的差异，使得调用有统一的形式

• B 对冗长的类型重定义，使得表达更短小

• C 对特殊的类型更友好，使得其操作快速

• D 对指针类型重定义，区别对待

答案

1=>B 2=>A

迭代器

迭代器是重要的抽象，它提供遍历容器中元素的方法，却要求与容器的物理实现无关。

首先考虑一个简单的数组 int [N]，我们如何遍历？

显然，最容易想到的方法，一个 int* 指针，指向第一个元素，

一直往后走，直到数组尾部。

int a[N] = ....;
int* p = a;
int* end = a + N;
while(p != end) cout << *p << endl;

那么，如果容器并非数组，而是链表呢？块链呢？

能统一地、无差别地对待吗？

这时，我们需要一个智能指针类型，表面上，感觉就是一个指针，支持：

p++, *p, p != end 这些操作。

我们只需要重载这些运算符就好。

示例

使用动态数组时：

class MyArray{
public:
    MyArray(){ size=10; data = new int[size]; n=0; }
    ~MyArray() { delete [] data; }
    void add(int x){
        if(n==size){
            int* old = data;
            data = new int[size * 2];
            memcpy(data, old, size * sizeof(int));
            delete [] old;
            size *= 2;
        }
        data[n++] = x;
    }
private:
    int size; // 初始大小
    int n;  // 已有元素个数
    int* data;
};

使用块链结构时：

class MyBlock{
public:
    MyBlock() { tail = head = new Node(); }
    ~MyBlock() {
        while(head){
            Node* p = head;
            delete [] p;
            head = head->next;
        }
    }
    void add(int x){
        if(tail->n == BLOCK_SIZE) {
            Node* p = new Node();
            tail->next = p;
            tail = p;
        }
        tail->data[tail->n++] = x;
    }
private:
    static const int BLOCK_SIZE = 10;
    struct Node{
        Node() { n=0; next=NULL; }
        int data[BLOCK_SIZE];
        int n;
        Node* next;
    };
private:
    Node* head;
    Node* tail;
};

统一的显示操作：

分别为这两个类增加一个内部 Iter 类型，可以理解为智能指针。

class MyArray{
public:
    MyArray(){ size=10; data = new int[size]; n=0; }
    ~MyArray() { delete [] data; }
    void add(int x){ .... }
public:
    typedef int* Iter;   // 迭代器就是 int* 本身
    Iter begin() { return data; }
    Iter end() { return data + n; }
private:
    int size; // 初始大小
    int n;  // 已有元素个数
    int* data;
};

MyBlock 的Iter就要复杂了：

class MyBlock{
public:
    MyBlock() { tail = head = new Node(); }
    ~MyBlock() { .... }
    void add(int x){ ....  }
public:
    struct Node;
    class Iter{
    public:
        Iter(Node* it, int n){
            this->it = it;
            this->p = it->data + n;
        }
        int operator* () { return *p; }
        void operator++(int) {
            p++;
            if(p==it->data + it->n && it->next){
                it = it->next;
                p = it->data;
            }
        }
        bool operator!= (const Iter& that){
            if(this->it != that.it) return true;
            if(this->p != that.p) return true;
            return false;
        }
    private:
        Node* it;  //当前块
        int* p; // 当前位置
    };
    Iter begin() { return Iter(head, 0); }
    Iter end() { return Iter(tail, tail->n); }
public:
    static const int BLOCK_SIZE = 10;
    struct Node{
        Node() { n=0; next=NULL; }
        int data[BLOCK_SIZE];
        int n;
        Node* next;
    };
private:
    Node* head;
    Node* tail;
};

使用：

    MyArray a;
    MyBlock b;
    for(int i=0; i<50; i++){
        a.add(i);
        b.add(i);
    }
    for(MyArray::Iter i=a.begin(); i!=a.end(); i++)
        cout << "a: " << *i << endl;
    for(MyBlock::Iter i=b.begin(); i!=b.end(); i++)
        cout << "b: " << *i << endl;

使用函数模板统一：

template <typename T>
void display(T& x){
    for(auto i=x.begin(); i!=x.end(); i++)
        cout << *i << " ";
    cout << endl;
}
int main()
{
    MyArray a;
    MyBlock b;
    for(int i=0; i<50; i++){
        a.add(i);
        b.add(i);
    }
    display(a);
    display(b);
    return 0;
}

实时效果反馈

1. 关于迭代器, 说法正确的是：__

• A 迭代器就是指向容器中元素的指针

• B 迭代器的目的是能更方便地访问容器中的元素

• C 迭代器的目的是能更高效地访问容器中的元素

• D 迭代器的目的是能更统一地访问容器中的元素，与容器类型无关

2. 当迭代器p不是原生指针，要重载运算符，一般哪个==不==需要重载？__

• A p++

• B *p

• C p != q

• D p[5]

答案

1=>D 2=>D

STL的迭代器

STL中提供了丰富的容器类型。

为了用统一的方式，访问这些容器中的元素，使得算法与类型隔离，与容器的物理结构隔离，广泛使用了迭代器的概念。

最常见的表现形式：

for(auto i=容器.begin(); i!=容器.end(); ++i){
    // 对 *i 进行操作
}

常见的迭代器有以下几种类型：

这个图画的不是继承关系，只是表达越往后边的迭代器功能越多。

比如， p 是forward迭代器，则支持： ++p, 但不支持 —p，而双向迭代器就可以。

迭代器功能

p，p1 是迭代器对象，则：

• 所有迭代器：

  | 运算 | 含义 | | —— | —————————— | | p++ | 自增迭代，返回增前值 | | ++p | 自增迭代，返回之后值 |

• 输入迭代器

  | 运算 | 含义 | | ———- | ——————————— | | xx = *p | 读取迭代器位置的元素值 | | p = p1 | 迭代器赋值 | | p == p1 | 迭代器比较 | | p != p1 | 迭代器比较 |

• 输出迭代器

  | 运算 | 含义 | | ———— | ———————— | | *p = xxx | 向迭代器位置写入 | | p = p1 | 迭代器赋值 |

• 正向迭代器 = 提供所有输入、输出迭代器的功能

• 双向迭代器（提供正向所有功能）

• 随机迭代器

  | 运算符 | 含义 | | ———- | ————————————— | | p += i | 连续前进 i 步 | | p -= i | 连续后退 i 步 | | p + i | 相对 p 位置前进 i 位置 | | p - i | 相对 p 位置后退 i 位置 | | p[i] | 相对 p 偏移 i 位置的元素值 | | p < p1 | p 在 p1 之前 | | p <= p1 | p 在 p1 之前，或相等 | | p > p1 | p 在 p1 之后 | | p >= p1 | p 在 p1 之后，或相等 |

可以看出，迭代器是对指针的概念的升华。

与指针的区别

迭代器是“假”指针，表面上装作指针的样子，指针的行为，但毕竟是个对象。

比如：容器.end() 返回的是最后一个元素后边那个位置，称为：尾后迭代器，它并非一个真正的“位置”，而 *p 也是引用一个并不存在的元素。

还有，p++ 是广义的 + ，移动方向未必是指针增量方向。比如反向遍历时，用的也是++

我们对 string 使用迭代器概念：

string s = "1234567";
for(auto i = s.rbegin(); i != s.rend(); ++i){
    cout << *i << endl;
}

看到，反向的输出效果，但 ++i, 不是 —i

iterator 的编译类型

从编译器的角度看，迭代器有 4 种：

• 容器::iterator 正向迭代器

• 容器::const_iterator 常量正向迭代器

• 容器::reverse_iterator 反向迭代器
• 容器::const_reverse_iterator 常量反向迭代器

我们应该使用尽量具体的类型，以提供更多的编译保护。

比如，上边的反向遍历串种元素，如果只是显示，不需要更改，则：

string s = "1234567";
for(string::const_reverse_iterator i = s.crbegin(); 
i != s.crend(); ++i){
    cout << *i << endl;
}

STL各种容器类型种的迭代器

这里列举主要的STL容器特点：

实时效果反馈

1. 如果我们定义单链表，则它的迭代器应该是：__

• A 前向迭代器

• B 双向迭代器

• C 随机迭代器

• D 输入迭代器

2. set类型容器为什么不提供随机迭代器？：__

• A set 是哈希表实现的，随机没有线性的概念

• B 为了快速判断元素是否存在，元素不是按某种顺序规律存储，随机访问会很慢

• C set 是链表，不方便提供随机访问

• D 为了安全性不提供

答案

1=>A 2=>B

函数对象

一个对象可以伪装为函数。

• 对象(参数，…) 表面上看好像函数调用
• 一个需要函数指针的地方，可以传入与之类型匹配的函数对象
• 可以通过重载 operator() 运算符来实现

struct MyF{
    int operator() (int a, int b) { return a * 10 + b; }
};

调用方法：

    MyF a;
    cout << a(2,3) << endl;

明明可以用普通的函数，现在搬出个对象来有什么用？

答曰：对象可以持有状态

比如，我们要多次调用一个 add(int x)，最后获得累加值，该如何处理呢？

如果用普通函数，就必须借助 static 或全局变量：

int g_a = 0;
void add(int x)
{
    g_a += x;
}

调用：

    g_a = 0;
    for(int i=0; i<10; i++) add(i);
    cout << g_a << endl;

这个方案的弱点是：

• 引入全局变量，终究是个隐患
• 多个线程中执行add过程，将引发灾难

如果改用函数对象，对象可以持有自己的状态，就能避免全局变量与线程竞争问题。

函数对象实现add

class MyF{
public:
    MyF():sum(0){}
    void operator() (int x) { sum += x; }
    int get_sum() { return sum; }
private:
    int sum;
};

调用：

    MyF a;
    for(int i=0; i<10; i++) a(i);
    cout << a.get_sum() << endl;

让一个函数持有状态，计算过程与状态有关，这是现代高级语言中的函数闭包

c++的函数对象与函数闭包比较，有更强大的能力和可塑性。

与STL协作

STL的核心思想是算法与容器类型分离

有些算法，需要传入用户自己定义的处理过程，即函数指针，此时如果需要持有状态，就可以用函数对象来代替之。

比如：for_each，它需要传入2个迭代器，以及一个函数

    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    MyF a = for_each(v.begin(), v.end(), MyF());
    cout << a.get_sum() << endl;

注意，需要 include

#include <algorithm>
#include <vector>

实时效果反馈

1. 怎样的类，才能生成函数对象：__

• A 类中重载了 operator() 运算符

• B 类中定义了函数指针

• C 类中定义了函数模板

• D 类中定义了特殊函数

2. 函数对象，与普通函数比，有何优势？__

• A 能够支持任意多的参数

• B 能够指定默认值

• C 能够更好地重载

• D 能使用局部变量来持有状态

答案

1=>A 2=>D

STL中的函数对象

根据函数输入参数数目的不同，STL中常用到的函数对象：

• 发生器

  没有任何参数，返回值为某个类型。比如：随机数产生器

• 一元函数

  一个输入参数，返回值类型可能与输入参数不同

• 二元函数

  两个输入参数，返回值可能与输入参数不同

• 一元判定函数（一元谓词）

  返回值是 bool 的一元函数

• 二元判定函数（二元谓词）

  返回值是 bool 的二元函数

STL算法的通用性

STL算法希望能够通用，它采用：

• 模板定义，与具体的类型隔离开，同时又不损失运行期效率。
• 函数对象，与具体的行为细节隔离开，可以接受函数对象或者函数指针

int add(int a, int b){ return a + b; }
struct MyF{
    int operator() (int a, int b){ return a*b; }
};
int main()
{
    int a[] = {1,2,3,4,5,6,7,8,9};
    const int N = sizeof(a)/sizeof(int);
    cout << accumulate(a, a+N, 0, add) << endl;
    cout << accumulate(a, a+N, 1, MyF()) << endl;
    return 0;
}