C++梳理

引言

这一节课面向已经有一些 C++ 基础的同学(一个快速判断标准:是否知道构造函数和析构函数是什么，并自己写过构造函数和析构函数)，复习串讲一些 OOP 中的知识点，以及介绍一些有趣的在面试中或者在写程序时用得到的 C++ 知识。

关于算协

2016年：清华大学计算机系学生算法与竞赛协会
- 举办过的活动：清华校赛（THUPC）
2022年：清华大学学生算法协会
- 成为校级社团希望开展更广泛的活动

暑期培训：拓展业务的尝试，希望你在奋斗的路上少一些孤单。

初衷：帮助大三升大四的同学复习编程和算法知识
形式：多次相对独立的授课，提供回放
建议：分析自身需求，有选择性地听课和完成作业

授课定位

C++ 相当庞大不仅语言名字的字符数是 C 语言的三倍标准的长度也相当于C语言的三倍多。
C++20 标准页数 1853 页
ISO - ISO/IEC 14882:2020 - Programming languages — C++
C11 标准页数 520 页
ISO - ISO/IEC 9899:2018 - Information technology — Programming languages — C
段子：21 天才能精通 C++
本次课理想受众：至少上过一门 C++ 的课程/读过一本 C++ 的入门书籍

尝试带大家梳理一些语言特性，帮助大家“融会贯通”
最终希望大家能够尝试自己梳理更多的 C++ 语言特性、或用同样的思路学习其他语言。
第一次做这种尝试，请大家在课后问卷中多多反馈
You can’t just look at C++ as a collection of features; some features make no sense in isolation. You can only use the sum of the parts if you are thinking about design, not simply coding. And to understand C++ this way, you must understand the problems with C and with programming in general.
– Bruce Eckel，Thinking in C++
The C++ Programming Language 里，大量的交叉引用反映了语言特性之间的互动和联系

内存

内存是什么？

我们可以认为，程序处理的数据存储在内存（RAM）（忽略缓存和硬盘的使用）
现在常用的内存条，包含若干内存颗粒(半导体集成电路)
物理上，通过一些微小的元器件来表示 “0” “1” 状态
能存储的比特数取决于集成电路里的元器件数目
可以想象成一条非常非常长的纸带每个格子可以填写 0-255 的一个状态（8 个 0/1 比特，一个字节）
例如 16G 的内存，一共能填写 16x1024x1024x1024 个字节
然后这根纸带卷啊卷，卷到了一根内存条这么大
这就是操作系统所拥有的内存资源，操作系统会将内存分配给正在执行的程序

内存分配

（分配内存的细节，和编译器、操作系统、运行时环境等等有关，具体细节需具体学习）
计算机上有多个程序同时运行，操作系统也预留了一部分内存，而内存是有限的
因此程序只能在操作系统分配给它的范围内使用内存
操作系统一开始就分配给程序一些内存，用来存储全局变量、局部变量、函数参数返回值、程序代码等数据。其中，全局变量、程序代码分配在static内存区域（从程序开始执行到结束，这些内存都被占用）。局部变量、函数参数返回值等，被分配在栈内存区域（函数调用栈）
函数每一次被调用时，在函数调用栈中分配一个大小合适的栈帧，存储这一次的局部变量、参数和返回值。从函数中返回时，释放栈帧的内存。（操作系统角度，整个函数调用栈还是在程序那里）
递归过深程序崩溃，是因为大量的栈帧未释放，占满了函数调用栈的内存。(stack overflow)
另外，程序在运行时，可以向操作系统动态地申请和释放一些内存（堆内存）

变量/指针/引用

变量：一块具有类型的内存（类型：数据的存储表示方式以及你可以对它进行的操作）
指针：一块内存的地址，指针的类型可能说明这个指针指向特定类型的变量。（void*）
引用：可以理解为指针的一种“语法糖”（左值引用/右值引用）
数组：内存中连续排列的多个同类型变量。数组名称可以用作指向第一个元素的指针
自定义的类型 (class/struct):一组成员变量在内存里的排列方式以及可以对它进行的操作
一个对象：按照特定排列方式存储在内存里的一组成员变量
+（课后练习：查阅资料，复习/学习 struct 中各个成员变量的 layout 规则）

一些类的示例

Model2 中一目了然的设计缺陷：

struct Point {
    double x;
    double y;
    double z;
};

struct Triangle {
    Point A;
    Point B;
    Point C;
};

struct Model {
    Triangle many_triangles[100];
};

struct Model2 {
    Triangle* triangles;
    Model2(int n) {
        triangles = new Triangle[n];
    }
    ~Model2() {
        delete[] triangles;
    }
};

struct Model3 {
    std::vector<Triangle> triangles;
};

Model2 需要加一个成员变量表示拥有多少个三角形面片。

构造函数/析构函数，new/delete

C++ 中两个运算符替代了C语言的 malloc/dealloc 库函数
通过 new/delete 动态分配或释放一个对象时会发生:
new：分配内存，然后调用对应的构造函数(递归调用各个成员变量的构造函数)
delete：调用对应的析构函数，然后释放内存

动态内存管理的两种风格(不代表只有这两种风格）

RAII （C++ 语言中可通过恰当实现构造/析构函数、恰当调用 new/delete 实现）
垃圾回收（C++ 语言中可通过智能指针实现）

将动态分配的资源的生命周期绑定到某个局部变量上，随着作用域的创建和消失完成分配和释放。
当希望创建一个动态数组时，不是在主函数里直接 new/delete
而是使用一个“包含动态数组的类”，作为局部变量定义，构造函数里 new，析构函数里 delete。
阅读 The C++ programming language 13.3 Resource Managerment，RAII 和异常处理。

智能指针&垃圾回收

如果计算机能够更加智能，意识到某块动态分配的内存目前没有任何一个活跃的指针会用到，就自动回收这一块内存，会怎么样？

这里介绍两种垃圾回收思路（并不止两种）：

引用计数（C++ 中可以用智能指针实现，weak_ptr, shared_ptr, unique_ptr)
记录一下当前有多少个活跃的指针指向一块动态分配的内存当这个计数变为 0 时，释放这块内存。
Mark & sweep （最早的垃圾回收方法，在Lisp中被使用）
每隔一段时间标记所有从当前程序执行到的位置出发，能够访问到的变量
然后将所有未标记的变量释放

时间所限，这里不细讲智能指针的具体语法。

有空可以看一下 “leak freedom in C++… by default by Herb Sutter”，CppCon的演讲

思考：

引用计数和 Mark&Sweep 带来的额外开销有什么区别？注重实时性的系统能否用垃圾回收？
C++ 中的智能指针常常会重载哪个运算符？(-> 和 *)
尝试用智能指针实现一个双向链表，要求做到首尾节点释放后，中间的所有节点自动释放
使用 STL 的容器可以大大方便 C++ 中的一些内存管理，非必要不造轮子

函数

减少函数调用：内联函数 vs 预处理宏

调用函数时，处理传参/返回值/栈帧的产生和销毁，会带来一定的开销。
对于简单的函数，将调用函数改为直接嵌入一段代码，可以节约一些计算开销。
C 语言：采用宏定义， #define min(a, b) ((a<b)?a:b)
C++：使用 inline 关键字建议编译器进行内联（但并不代表编译器一定会这么做）
C++ 中，建议非必要不使用宏，如果一定要用，起一堆大写字母的丑陋名字
课后：查询如何用 C++11 中引入的 constexpr 关键字标识函数

传值/传引用

定义函数

f(Type x){
    ...
}

函数 g 内有 Type 类型的局部变量 b，并调用了 f(b)
在函数 f 内修改 x，会不会导致 f 返回后，函数 g 中 b 的数值发生对应的改变？（传值/传引用）
f(int x), f(int &x), f(int *x), f(int x[]), f(int &&x)

思考题：举出一种实际应用情况，我们选择让函数返回一个引用（提示：从The C++ programming language 7.7.1 page 192中查找答案）

深浅拷贝

拷贝有两种情况可能发生：

拷贝构造函数
重载赋值符号(A = B）
当一个类中包含动态分配的资源时，浅拷贝将不会分配第二份资源，使得拷贝后的对象和之前的对象指向相同的一份资源（如数组）。这很多时候是一个 bug，或者可以用 CoW/Move 来替代
默认的拷贝行为对所有成员函数逐个拷贝
合理的拷贝行为应当满足：等价性，独立性

拷贝/移动

有时并不需要进行拷贝，因为完成拷贝之后，旧的元素失去了使用的价值。

例如常见的交换函数：

void swap(Type a, Type b){
    Type tmp = a;
    a = b;
    b = tmp;
}

可以通过 move 来避免不必要的拷贝。（右值引用表示一个可以被销毁的临时值）

swap函数

template<class T>
void swap(Type& A, Type& B) {
    T tmp = std::move(a);
    a = std::move(b);
    b = std::move(tmp);
}

函数指针

通过函数指针，实现“以函数为参数”的函数, 或者说，传入一个“谓词”(predicate)
实质上是函数的代码所在的地址
例如可以定义遍历函数 iterate(数组A，函数B)，对数组中每个元素执行函数B (如都翻倍)
另一个常见例子：给排序函数传入一个比较函数的函数指针作为参数

bool cmp_func(const int &a, const int &b){ return abs(a) < abs(b); }
std::sort(array_A, array_A+n, cmp_func);

另一个用途: 设置回调函数, “发生某事件时调用该函数”

函数对象

函数对象是重载了函数调用运算符()的对象
在 C++ 中，应当倾向于使用函数对象 /lambda 表达式而非函数指针

struct cmp {
    bool operator()(int a, int b) const { return a < b; }
};

Lambda表达式

C++11 标准中引入的匿名函数，用于方便地定义一个匿名的函数对象
可以在 lambda 中“捕获”当前作用域的变量，定义参数列表，也可以有返回值
也可以将 lambda 表达式赋值给一个变量

auto cmp = (const int &x, const int &y){return x<y;}; //这里没有捕获列表。

+ 尝试分别用函数指针/函数对象/lambda表达式结合 std::sort( ) 写一个“按照绝对值排序整数的程序” + 查阅文档：如何表示“捕获”一个变量时，捕获它的值/引用？

多态

继承

两类典型的继承：“实现继承”/ “接口继承”
如果没有继承语法，我们如何表示继承关系？
可以将基类作为子类的一个成员
如果一开始理解继承机制的时候有困难，可以认为基类就是子类的一种特殊成员变量
public/private 控制外部对成员变量的访问权限
通过 protected，特殊控制子类对基类的访问权限

列个表：

public/private/protected 继承，子类分别能否访问基类的public/private/protected成员变量？

虚函数

在成员函数前标注 virtual，允许子类重新实现这个函数，编译器和运行时环境通过虚表，保证调用正确版本的函数
纯虚函数要求子类必须重新实现这个函数
虚表可以认为是子类隐藏的一个成员数组，数组中标注每个虚函数具体指向哪一个实现版本（通常是继承关系上，“最近”的一个类所实现的版本，例如如果这个子类自身有实现，就调用自身实现的版本）（虚表中可能会保存指向一些函数实现的函数指针）
查阅文档: 用 final 或 override 关键字标注一个虚函数，分别会对子类提出什么样的要求？

运行时多态(runtime polymorphism)

多态: 通过继承和虚函数，可以实现这样的行为: 某个变量的类型为基类的指针，它可以指向某个子类的对象，并正确调用子类对虚函数的具体实现。
（也可以通过引用来实现多态行为）
如果不用指针/引用而直接使用一个对象，可能会导致意外的切片(slicing), 从子类转换为基类，丢失了子类的数据。
尝试写一个会导致切片行为的简单程序
不同语言会用不同的方式来实现多态。查询文档：Java 中如何用 interface 实现多态？(rust 如何用 trait 实现多态？）

多态的应用：Visitor pattern

这是一种在编译器中应用广泛的设计模式
在编译器中，常常需要多次遍历一个语法树的所有结点，第一轮遍历的时候进行符号收集，第二轮遍历的时候进行代码生成……
不同类型的节点有着不同的内部结构，但都对外提供构造函数、visit() 等接口
Visit() 可以接收一个函数对象作为参数，表示对节点进行的操作
这个函数对象我们称为 visitor，语法树节点的 visit() 接口接收一个基类 visitor 的函数对象作为参数
实际调用时，传入一个具体的继承 visitor（的指针/引用），对语法树中的节点进行遍历
如果大家去做一些编译原理课程的作业，看一下实验框架(通常是 toy compiler），或者看一些用 C++ 实现的开源编译器，常常会找到类似的结构。

模板的简介

函数：对于两段只有参数数值不同的代码，不用重复编写
模板：对于两个只有参数类型不同的函数，不用重复编写，编译器自动生成程序中用到的不同类型的函数。模板较多的代码往往编译起来非常慢
C++ 的 STL 容器中大量使用了模板，如我们可以定义保存任意类型的 std::vector，定义任意两个类型组成的 std::pair
可以通过模板来实现一些编译期计算(有个名词叫做“模板元编程”）

为什么模板类的函数声明和定义要放在一起？

考虑模板代码生成的过程：

从编译器的角度，模板函数本身并不是一个能直接拿来链接的函数，而是需要用它来生成一些其他的函数
将函数声明和定义拆开编写，其实是在链接阶段再去处理函数名称和函数实现的绑定
链接器通常没有办法在链接阶段再去处理模板参数的替换