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：调用对应的析构函数，然后释放内存

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

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

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

智能指针&垃圾回收

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

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

1. 引用计数（C++ 中可以用智能指针实现，weak_ptr, shared_ptr, unique_ptr)
   记录一下当前有多少个活跃的指针指向一块动态分配的内存 当这个计数变为 0 时，释放这块内存。
2. 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
• 可以通过模板来实现一些编译期计算(有个名词叫做“模板元编程”）

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

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

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