OOP课程笔记：第八章 模板与泛型编程

第八章 模板与泛型编程

1.简介

函数模板提供了一种描述通用算法的机制

将算法处理的 数据类型参数化 ，从而既可以保留函数定义和函数调用的语义，又不必绕过 C++ 的类型检查

程序员 将函数接口（参数表和返回类型）中的全部或者部分类型参数化 ，而函数体保持不变 。

如果一个 函数的实现对一组实例都是相同的 ，区别仅在于每个实例处理不同的数据类型 ，那么该函数就可以定义为函数
模板

模板的定义方式

template <typename T>

2.应用

用函数模板实现通用算法

将具体算法实现中的 数据类型参数化 ，用 模板类型参数 代替，保留函数中与类型无关的代码，就可以得到函数模板的定义

// 模板函数定义（修正原图中的语法错误）
template <class Type>
Type min(Type array[], int size) {
    Type min_val = array[0];          // 初始化最小值为首元素
    for (int ix = 1; ix < size; ++ix) // 从第二个元素开始遍历
        if (array[ix] < min_val) 
            min_val = array[ix];      // 发现更小值时更新
    return min_val;                   // 返回最小值
}

使用模板非类型参数的算法实现

模板类型参数 Type 在模板定义中作为类型标识符使用，表示数组的类型
模板非类型参数 size 作为常量使用，表示数组的大小

// 函数模板：返回定长数组的最小值（通过const引用传递数组）
template <class Type, int size>
Type min2(const Type (&array)[size]) {  // 想传递数组的const引用
    Type min_val = array[0];            // 初始化最小值为首元素
    for (int ix = 1; ix < size; ++ix)  // 遍历数组
        if (array[ix] < min_val) 
            min_val = array[ix];        // 更新最小值
    return min_val;
}

3.函数模板的实例化

函数模板本身并不是真正的函数定义，因为其中的类型信息不完整

函数模板被调用时编译器首先对其进行实例化 ，生成真正整的函数定义实例，然后再 实施对函数实例的调用

根据每次调用模板函数的不同实参，一个函数模板可以实例化得到多个不同的函数定义

当调用一个函数模板时，编译器用 函数实参 推演 模板实参

模板实例化在函数模板被调用或取地址时隐式发生

// 版本1：接收数组指针和大小参数
template<class Type>
Type min(Type array[], int size) {
    Type min_val = array[0];
    for (int i = 1; i < size; ++i)
        if (array[i] < min_val) min_val = array[i];
    return min_val;
}

// 版本2：接收数组的常量引用（编译期确定大小）
template<class Type, int size>
Type min2(const Type (&array)[size]) {
    Type min_val = array[0];
    for (int i = 1; i < size; ++i)
        if (array[i] < min_val) min_val = array[i];
    return min_val;
}

例如，当调用模板 min 时，编译器会用一个具体类型替换 Type

调用模板 min2 时会用一个 具体类型 和一个 常量值 分别替换 Type 和 size

在使用函数模板时，必须能够通过上下文为每一个模板实参确定 一个唯一的类型或值 ，否则会产生编译错误

// 三类型参数的函数模板
template <class T1, class T2, class T3>
T1 funcion(T2 arg1, T3 arg2) { /*...*/ }

// 单类型参数的函数模板
template <class T>
void goo(T a, T b) { /*...*/ }

int main() {
    int x, y;
    double d;
    
    x = funcion(y, d);  // 正确用法：x = funcion<int>(y, d);
    goo(x, d);           // 正确用法：goo<double>(x, d);
}

---

显式指定模板实参

在函数模板实例化时，函数名后面用尖括号<>指定模板实参

函数实参可以应用隐式类型转换，转换成相应的函数参数

显式模板实参应该只用在解决二义性时，或用在模板实参不能被推演出来的情况下

// 三元模板函数定义
template <class T1, class T2, class T3>
T1 function(T2 arg1, T3 arg2) { /*...*/ }

int main() {
    int x, y;
    double d;
    
    // 三种调用方式示例
    x = function(y, d);           // 调用1：缺少T1信息（无法推导）
    x = function<int, int, double>(y, d);  // 调用2：显式指定全部类型
    x = function<int>(y, d);      // 调用3：显式指定T1，推导T2和T3
}

4.重载函数模板

用函数模板重载另一个函数模板，函数参数的个数不同，而不是参数类型

也可以用一个非模板函数重载一个同名的函数模板

// 两个同类型参数的min模板
template<class Type>
Type min(Type a, Type b) {
    return a < b ? a : b;
}

// 三个同类型参数的min模板
template<class Type>
Type min(Type a, Type b, Type c) {
    Type t = a < b ? a : b;
    return t < c ? t : c;
}

// const char*特化版本（字符串比较）
const char* min(const char* a, const char* b) {
    return strcmp(a, b) < 0 ? a : b;
}

具体运行逻辑如下：

1.寻找一个参数完全匹配的非模板函数，若找到，则调用该函数

2.寻找一个函数模板，能将其实例化为一个完全匹配的函数，若找到，则调用；

3.只考虑重载函数集中的普通函数（会尝试进行隐式类型转换），按照重载函数解析过程选择可调用的函数，若找到，则调用。

如果都没有找到匹配的函数，则出现“无可调用的函数”错误；

如果某一步内出现多个匹配的函数，则引起二义性错误。

5.类模板

类模板用来实现通用数据类型,vector 就是 C++ 标准模板库中定义的一个类模板

类模板定义的一般语法形式为：

template <模板参数表>

下例中的栈模板可以实现元素为不同类型的栈

// 栈模板类实现（修正版）
template<class Type>
class Stack {
public:
    Stack(int cap) : size(cap), top(bottom) {  // 构造函数
        ele = new Type[size];                  // 动态分配内存
    }
    
    ~Stack() { delete[] ele; }                 // 析构函数释放内存
    
    Type pop() {                               // 弹出栈顶元素
        if (empty()) throw "Stack Underflow";  // 空栈检查
        return ele[top--];                     // 返回并移动栈顶指针
    }
    
    void push(Type e) {                        // 压入元素
        if (full()) throw "Stack Overflow";    // 栈满检查
        ele[++top] = e;                        // 移动指针后存储
    }
    
    bool empty() { return top == bottom; }     // 栈空判断（bottom=-1）
    bool full()  { return top == size - 1; }   // 栈满判断

private:
    Type* ele;      // 元素存储数组
    int top;        // 栈顶指针（初始为-1）
    int size;       // 栈容量
    const static int bottom = -1;  // 栈底标记
};

---

类模板的实例化

从类模板定义中生成类的过程称为模板实例化

类模板本身并不定义任何类型，而只是指定了怎样根据一个或多个实际的类型或值构造单独的类

不同于函数模板，类模板在 实例化时 必须显式指定 模板实参

类模板的每个实例都是一个独立的类型

Stack<int> is(20)
Stack<string> ss(10)

---

类模板的成员函数与非类型参数

成员函数也可以在类模板之外定义，定义前面必须加关键字 template 以及模板参数表

模板的非类型参数代表一个常量值（大多数情况下都是整型）

template <class Type, int cap>
class Stack {
public:
    Stack();
    ~Stack() { delete []ele; }
    void push(Type e) { ele[++top] = e; }
    Type pop() { return ele[top--]; }
    bool empty() { return top == bottom; }
    bool full() { return top == size-1; }

private:
    Type* ele;
    int top;
    int size;
    const static int bottom = -1;
};

// 类外定义
template<class Type, int cap> 
Stack<Type, cap>::Stack()
{
    assert(cap > 0);
    size = cap;
    ele = new Type[size];
    top = bottom;
}

int main()
{
    Stack<int, 10> is;
    for(int i = 0; i < 10; i++)
        is.push(i);
    while(!is.empty())
        cout << is.pop() << "\t";
}

---

类模板的静态数据成员

类模板中可以声明 static 数据成员， static 数据成员的定义必须出现在类模板的定义之外

类模板的每个实例都有自己的一组 static 数据成员

每个 static 数据成员实例都与一个类模板实例相对应

因此，一个 static 数据成员的实例总是通过一个特定的类模板实例被引用

---

类模板的友元

1.非模板友元类或友元函数

不使用模板参数的友元类或友元函数是类模板的所有实例的友元

2.绑定的友元类模板或函数模板

使用模板类的模板参数的友元类和友元函数与实例化后的模板类实例之间是一一对应的关系

下面程序中的 Queue 就是 QueueItem 的友元类模板，通过模板类型参数绑定。

template <class Type> class Queue; // 向前引用声明Queue

template <class T> 
class QueueItem {
public:
    QueueItem(const T& data) : item(data), next(0) {}
    friend class Queue<T>;//友元声明，使用模板类型参数 T 绑定实例
private:
    T item;
    QueueItem* next;
};

template <class Type> 
class Queue {
public:
    Queue() : front(0), back(0) {}
    ~Queue();
    Type remove();
    void add(const Type&);
    bool is_empty() const { return front == 0; }

private:
    QueueItem<Type>* front;
    QueueItem<Type>* back;
};

template <class Type> void Queue<Type>::add(const Type& val) {
    // 实现代码
}

template <class Type> Type Queue<Type>::remove() {
    // 实现代码
}

3.非绑定的友元类模板或函数模板

友元类模板或函数模板有自己的模板参数，和模板类实例之间形成一对多的映射关系

对任一个模板类的实例，友元类模板或函数模板的所有实例都是它的友元

template <class T> 
class MTC {
public:
    friend void foo();    
    // 友元函数与模板类实例之间是一对多关系
    // foo是所有MTC模板的实例的友元
    
    friend void goo<T>(vector<T>);
    // 友元函数实例与模板类实例之间是一对一关系
    // 每个实例化的MTC类都有一个相应的goo友元实例
    
    template <class Type> 
    friend void hoo(MTC<Type>);
    // 友元函数实例与单个模板类实例之间是多对一关系
    // 对MTC的每个实例，hoo的每个实例都是它的友元
};

模板的代码组织

为了避免模板定义被同一文件多次包含而引起编译错误，在模板定义的头文件中应该使用包含

#ifndef FLAG
#define FLAG
//模板定义
#endif

// 模板定义头文件 templatemin.h
#ifndef TEMPLATE_MIN_H
#define TEMPLATE_MIN_H

template <class Type>
Type min(Type array[], int size) {
    Type min_val = array[0];
    for (int ix = 1; ix < size; ++ix)
        if (array[ix] < min_val) min_val = array[ix];
    return min_val;
}

#endif /* TEMPLATE_MIN_H */

// 使用模板定义的源文件 test.cpp
#include <iostream>
#include "templatemin.h"
using namespace std;

int main() {
    int a[] = {2, 5, 3, 4, 1, 7};
    cout << "min(a,6) = " << min(a, 6) << endl;

    double da[] = {1.2, 3.5, 7.2};
    cout << "min(da,3) = " << min(da, 3) << endl;
}