OOP 朋辈辅学 Lec5 模板与 STL¶

1 模板¶

1. 1 泛型编程¶

C++ 模板（Template）是泛型编程（Generic Programming）的核心。它允许程序员编写与类型无关的代码，把类型参数化，从而复用同一份逻辑。

如果没有泛型，想实现“返回两个对象中的较大者”，就需要为不同类型重复写函数。

没有泛型时的重复重载

int max(int x, int y) { return x < y ? y : x; }
float max(float x, float y) { return x < y ? y : x; }
double max(double x, double y) { return x < y ? y : x; }

// 还要继续支持更多类型...

这些函数的逻辑完全相同，区别只是参数类型不同。

C 语言中也可以用 void* 写出“看起来通用”的接口，但会丢失类型信息。

void* 版本

const void* my_max(
    const void* x_ptr,
    const void* y_ptr,
    int (*cmp)(const void*, const void*)
) {
    if (cmp(x_ptr, y_ptr) < 0) {
        return y_ptr;
    } else {
        return x_ptr;
    }
}

宏也能做代码替换，但并不安全。

宏定义版本

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

宏和 void* 的问题

宏在预处理阶段直接替换文本，容易导致程序员看到的代码和编译器真正看到的代码不一致
宏缺少类型检查，表达式副作用和优先级问题都很常见
void* 完全丢失类型信息，相当于放弃了强类型语言的编译期保护

有了模板之后，可以只写一份逻辑。

函数模板

template <typename T>
T max(T x, T y)
{
    return x < y ? y : x;
}

int max_int = max(1, 2);
double max_double = max(2.5, -3.0);

模板能工作的前提

模板只是把类型参数化，具体类型仍然必须支持模板内部使用的操作。上面的 max 依赖 < 运算符，因此传入的类型必须能比较大小。

1. 2 函数模板和类模板¶

函数模板适用于“逻辑相同，但参数类型不同”的函数。

函数模板

template <class T>
T add(T a, T b)
{
    return a + b;
}

int i = add(10, 20);        // 实例化为 add<int>
double d = add(1.5, 2.5);   // 实例化为 add<double>

类模板允许成员变量和成员函数的类型也参数化。

类模板

template <typename T>
class Box {
private:
    T data;

public:
    Box(T d): data(d) {}

    T getData()
    {
        return data;
    }
};

Box<int> intBox(100);
Box<string> strBox("Hello");

1. 3 实现机制¶

模板本身不是普通函数或普通类的机器码实现。只有当模板被使用时，编译器才会根据具体类型进行实例化。

模板实例化的特点

编译期生成：编译器根据实参推导 T，并生成对应类型的代码
实现通常放在头文件：编译器实例化模板时必须能看到完整定义，因此模板一般不能只把实现放到 .cpp 文件中
可能导致代码膨胀：每种实际用到的类型都可能生成一份机器代码，源码减少了，但二进制体积可能变大

1. 4 多个类型参数¶

模板可以同时拥有多个类型参数。

键值对类模板

template <typename T, typename U>
class KeyValuePair {
private:
    T key;
    U value;

public:
    KeyValuePair(T k, U v): key(k), value(v) {}

    T getKey() const { return key; }
    U getValue() const { return value; }
};

1. 5 非类型模板参数¶

模板参数不一定是类型，也可以是编译期可确定的常量值，常见的是整数。

泛型定长数组

template <typename T, int Size>
class GenericArray {
public:
    T& operator[](int idx)
    {
        return arr[idx];
    }

private:
    T arr[Size];
};

GenericArray<int, 10> int_arr;  // 长度固定为 10 的整型数组

1. 6 模板特化¶

当通用模板不适用于某些特定类型时，可以为这些类型写专门实现，这称为模板特化。

模板特化主要分为：

全特化：为所有模板参数都指定具体类型
偏特化：只固定一部分模板参数，规则更复杂

课件重点讨论的是全特化。

函数模板全特化

template <typename T>
T f(const T& a)
{
    cout << "template" << endl;
    return a;
}

template <>
int f(const int& a)
{
    cout << "specialization" << endl;
    return a;
}

实践建议

函数模板全特化在实际代码中不如函数重载直观。遇到函数行为需要针对某个类型特殊处理时，通常优先考虑普通函数重载。

类模板全特化

template <typename T>
class Storage {
public:
    void print()
    {
        cout << "General" << endl;
    }
};

template <>
class Storage<bool> {
public:
    void print()
    {
        cout << "Specialized for bool" << endl;
    }
};

1. 7 匹配优先级¶

假设存在以下重载和模板：

f(1.0f) 会调用哪个函数

void f(int x)
{
    cout << "int" << endl;
}

void f(double x)
{
    cout << "double" << endl;
}

template <typename T>
void f(T x)
{
    cout << "template" << endl;
}

答案

调用模板函数，输出 template。

解析

f(int)：需要 float -> int 的转换
f(double)：需要 float -> double 的浮点提升
template<T> f(T)：可实例化为 f<float>，是精确匹配
精确匹配优先级更高，因此选择模板版本

重载决议的核心顺序

完全匹配的普通函数
完全匹配的模板函数
需要类型转换的普通函数

如果多个候选都能匹配且无法判断谁更优，就会产生二义性错误；如果没有任何候选能匹配，就会报“找不到匹配函数”。

2 STL¶

2. 1 介绍¶

STL（Standard Template Library，标准模板库）是 C++ 标准库的核心部分。它通过泛型编程把数据结构和算法分离，提高代码复用和开发效率。

STL 的核心思想是：

容器负责保存数据
迭代器负责抽象访问方式
算法通过迭代器操作数据，而不是直接依赖具体容器

2. 2 序列容器¶

2. 2. 1 `vector`¶

vector 是动态数组，底层连续存储，支持随机访问，尾部插入效率高。

vector 常用操作

vector<int> vec1 = {1, 2, 3, 4, 5};  // 列表初始化

vector<int> vec2(5, 0);              // 长度为 5，初始值为 0

vec1.pop_back();                     // 尾部弹出一个元素
vec1.push_back(6);                   // 尾部插入一个元素
vec1[2] = -vec2[1];                  // 支持下标随机访问

下标访问是否检查越界

vec[i] 不进行边界检查，越界是未定义行为。若需要越界时抛出异常，应使用 vec.at(i)。

大小、判空与二维 vector

int size = vec1.size();
bool is_empty = vec1.empty();

vector<vector<int>> vec3(10, vector<int>(5, 0));  // 10 行 5 列

vector 没有 Python 那样的切片语法，但可以用迭代器范围构造出类似效果。

用迭代器拷贝一段范围

vector<int> vec1 = {1, 2, 3, 4, 5};
vector<int> vec2(vec1.begin() + 1, vec1.end() - 1);  // {2, 3, 4}

2. 2. 2 `deque` 和 `list`¶

deque 是双端队列，两端都可以高效插入和删除
list 是双向链表，任意位置插入删除效率高，但不支持随机访问

list 的特点

list 是较特殊的容器，有一些定制操作，例如拼接 splice。算法题中链表一般会手写结构体结点，但力扣 146 LRU 缓存这类题可以借助 list 实现。

2. 3 关联容器¶

关联容器按照键组织数据，常见容器包括：

set / unordered_set：集合，元素唯一，常用于去重和判断元素是否存在
map / unordered_map：键值对映射，常用于计数和根据键查值

set 和 unordered_set 的区别

set 底层通常是红黑树，元素按键自动排序，查找复杂度为 O(log n)
unordered_set 底层通常是哈希表，不保证顺序，平均查找复杂度为 O(1)
哈希表要求键类型可哈希

unordered_set 使用示例

vector<int> vec = {1, 2, 2, 3, 4, 5, 5};
unordered_set<int> v_set;

for (auto v : vec) {
    v_set.insert(v);
}

v_set.erase(4);

int target = 4;
if (v_set.find(target) == v_set.end()) {
    cout << target << " not in vec" << endl;
} else {
    cout << target << " in vec" << endl;
}

unordered_map 使用示例

vector<int> vec = {1, 2, 3, 5, 4, 3, 6, 4, 3};
unordered_map<int, int> count;

for (auto v : vec) {
    count[v]++;
}

count.erase(1);

for (auto i : count) {
    cout << i.first << ":" << i.second << endl;
}

for (auto it = count.begin(); it != count.end(); ++it) {
    cout << it->first << ":" << it->second << endl;
}

map[key] 的行为

对 unordered_map 或 map 使用 count[v]++ 时，如果键 v 不存在，会自动创建该键对应的元素，并把值初始化为默认值。对 int 来说默认值是 0。

2. 4 `pair` 与 `tuple`¶

pair 用于存储两个值，tuple 可以存储任意多个值。它们常用于函数返回多个结果，或作为容器元素类型。

pair

pair<string, int> p = {"Alice", 90};
cout << p.first << ": " << p.second << endl;

auto p2 = make_pair("Bob", 85);

tuple

tuple<string, int, double> t = {"Alice", 90, 3.9};

cout << get<0>(t) << endl;
cout << get<1>(t) << endl;

auto [name, score, gpa] = t;  // C++17 结构化绑定
cout << name << " " << score << " " << gpa << endl;

2. 5 容器适配器¶

容器适配器是在已有底层容器上包装出新的接口。

名称	默认底层容器	特性
`stack`	`deque`	后进先出
`queue`	`deque`	先进先出
`priority_queue`	`vector`	默认大顶堆

stack

stack<int> s;

s.push(10);
s.push(20);
s.push(30);

cout << "栈顶元素：" << s.top() << endl;
s.pop();   // 出栈，注意 pop 不返回栈顶元素

queue

queue<int> q;

q.push(10);
q.push(20);
q.push(30);

cout << "队首元素：" << q.front() << endl;
cout << "队尾元素：" << q.back() << endl;
q.pop();

priority_queue

priority_queue<int> maxHeap;

maxHeap.push(5);
maxHeap.push(10);
maxHeap.push(7);
maxHeap.push(-4);

maxHeap.pop();
cout << "最大元素是：" << maxHeap.top() << endl;

priority_queue 默认是大顶堆，接口上更接近“带优先级的栈顶访问”。

如果需要小顶堆，可以指定比较器。

小顶堆

priority_queue<int, vector<int>, greater<int>> minHeap;

比较器的方向

priority_queue 默认使用 <，形成大顶堆。对基本类型，如果想要小顶堆，可以使用 greater<int>。自定义类型也可以通过自定义比较函数或函数对象改变优先级规则。

2. 6 常用算法¶

STL 提供了大量标准算法，涵盖排序、查找、修改、计数等。算法通常不直接操作容器，而是通过迭代器操作一段范围。

排序与反转

vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

sort(vec.begin(), vec.end());                    // 升序
sort(vec.begin(), vec.end(), greater<int>());    // 降序

sort(vec.begin(), vec.end(), [](int a, int b) {
    return abs(a) < abs(b);                      // 按绝对值升序
});

reverse(vec.begin(), vec.end());                 // 原地反转

查找与统计

vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

auto it = find(vec.begin(), vec.end(), 5);
if (it != vec.end()) {
    cout << "找到，位置：" << (it - vec.begin()) << endl;
}

cout << *max_element(vec.begin(), vec.end()) << endl;
cout << *min_element(vec.begin(), vec.end()) << endl;

int cnt = count_if(vec.begin(), vec.end(), [](int x) {
    return x > 3;
});

3 断言¶

3. 1 简介¶

断言（Assertion）用于验证程序在运行时或编译时是否满足某个条件。

条件为真：程序继续执行
条件为假：程序停止并报错

断言和异常的区别

断言用于发现程序逻辑错误，通常只在开发环境启用
异常用于处理运行中可能遇到的问题
断言触发后程序通常直接停止
异常可以被上层代码捕获并恢复

例如，数组越界这种“理论上绝不应该发生”的问题适合用断言尽早暴露；HTTP 发送失败、文件不存在等外部问题更适合用异常或错误返回处理。

3. 2 运行时断言¶

运行时断言 assert 定义在 <cassert> 中。它只在未定义 NDEBUG 宏时有效。

检查指针

#include <cassert>

int* arr = new int[5];
assert(arr != nullptr);

检查函数结果

int add(int x, int y)
{
    return x + y;
}

int add_res = add(1, 2);
assert(add_res == 3);