Skip to content

CS106L

约 7715 个字 502 行代码 9 张图片 预计阅读时间 37 分钟

Info

速通 CS106L 2024 Autumn 之后记录的粗略的笔记，主要来自于课程的 slides，一定程度上也是对我的 C++笔记 的补充。

CS106L 的 slides 和 assignments 解答可以在我的仓库 CS106L-2024-Autumn 中找到。

类型与结构体

类型

C++ 是静态类型语言，在编译时就需要确定每个实体（变量、函数等）的类型，并且它们的类型从被定义之后就不能改变。

动态类型语言（如 Python）在运行时才会确定类型，并且在运行过程中会不断根据它们当前的值来确定类型。

结构体

结构体（struct）是一种用户自定义的，由多个成员变量组成的数据结构。它可以作为函数的参数、返回值，也可以作为容器的元素，从而实现一次传递多个数据。

结构体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
struct StanfordID {
string name;    // These are called fields
int idNumber;
};

// Initialize struct
StanfordID id1;                  
id.name = "Xestray";    // Access field with ‘.’
id.idNumber = 114514;

// List Initialization
StanfordID id2 = {"Xestray", 114513};

std::pair

std::pair 在 头文件中定义，是一个模板类，用于存储两个的对象（不一定是相同类型）。可以通过 first 和 second 来访问其中的元素。

1
2
3
std::pair<double, double> point { 1.0, 2.0 };

std::cout << point.first << " " << point.second

我们可以直接使用 std::make_pair 来创建一个 pair 对象，并使用 auto 来自动推断类型。

1
auto point = std::make_pair(1.0, 2.0);

初始化与引用

初始化

C++ 有三种初始化方式：

  • 直接初始化（direct initialization）
  • 统一初始化（uniform initialization）
  • 结构化绑定（structured binding）

直接初始化

直接初始化有两种形式

1
2
int num1 = 12.0;
int num2(12.0);

C++在直接赋值时不会进行类型检查，这里直接把 double 类型的 12.0 赋值给了 int 类型的变量，会发生窄化转换（narrowing conversion），可能会导致精度的丢失。

统一初始化

统一初始化使用花括号 {} 来初始化变量，它可以防止隐式类型转换，也可以避免窄化转换。

1
2
int num1 {12.0};
float num2 {12.0};

12.0 是 double 类型的，因此这里对 num1 的初始化会出现编译错误，阻止窄化转换；虽然 num2 是 float 类型的，但是因为它们都是浮点类型的数据，double 到 float 的转换是安全的，因此这里不会报错。

统一初始化的优点在于

  • 安全性：统一初始化禁止了窄化转换，从而避免出现意料之外的情况
  • 一致性：统一初始化可以用于所有类型的初始化场景，包括变量、数组、结构体、类等

结构化绑定

结构化绑定是 C++17 中引入的新特性，允许我们通过结构体、函数的返回值等方式，一次性对多个变量进行初始化。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
#include <tuple>

std::tuple<std::string, std::string, std::string> getClassInfo()
{
    std::string className = "CS106L";
    std::string buildingName = "Thornton 110";
    std::string language = "C++";
    return {className, buildingName, language};
}

int main() {
    auto [className, buildingName, language] = getClassInfo();
    std::cout << "Come to " << buildingName << " and join us for " << className
              << " to learn " << language << "!" << std::endl;

    return 0;
}
  • 结构化绑定允许我们使用在编译时大小确定的数据结构（如 tuple、pair、array、struct）来一次性初始化多个变量
  • 在使用结构化绑定时，我们只能使用 auto 关键字来自动推断变量的类型

引用

引用是某个已经存在的变量的别名，使用 & 符号来定义。对某个变量的引用和这个变量的标识符指向的是内存中的同一个地址，因此对引用的操作会直接影响到原变量。

1
2
3
4
5
int num = 5;
int& ref = num;
ref = 10; // Assigning a new value through the
reference
std::cout << num << std::endl; // Output: 10
  • 按值传递（pass by value）：函数的参数是一个变量的拷贝，对参数的修改不会影响原变量
  • 按引用传递（pass by reference）：函数的参数是原变量的引用，对参数的修改会直接影响原变量

Example

1
2
3
4
void square(int& n)
{
    n = std::pow(n, 2);
}

左值与右值

从字面意思来看，左值就是可以放在赋值运算符左边的值，右值就是只能放在赋值运算符右边的值。但具体来说

  • 左值：是一个具有持久身份、可以取地址的实体，通常对应一个具名对象（变量或引用等）

    • 可以放在赋值运算符左侧（e.g. int x = 5;）
    • 有明确的内存地址（可通过 & 取地址）
    • 生命周期超过当前表达式

  • 右值：是一个临时的表达式，通常无法取地址，通常对应一个匿名对象或表达式的结果

    • 只能放在赋值运算符右侧（e.g. 10 = a 非法）
    • 通常是字面量、临时对象或表达式计算结果等
    • 生命周期仅限于当前表达式

流（stream）

基本概念

流（stream）：一种通用的 C++ I/O 抽象，用于读取和写入数据。

  • cin：标准输入流，用于读取用户输入
  • cout：标准输出流，用于输出信息（无缓冲）
  • cerr：标准错误流，用于输出错误信息（无缓冲）
  • clog：标准日志流，用于记录非关键事件的日志（有缓冲）

cout

std::cout 流是 std::ostream 的一个实例，能将数据输出到控制台上，基本运算符为 <<（插入符）。

1
std::cout << "Hello, World" << std::endl;

cin

std::cin 流是 std::istream 的一个实例，能从控制台读取数据,基本运算符为 >>（提取符）。

1
std::cin >> num;

字符串流

字符串流（stringstream）可用于处理混合数据类型的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    std::string initial_quote = "Bjarne Stroustrup C makes it easy to shoot yourself in the foot";

    // 两种字符串流初始化方式
    // 1. 字符串构造函数
    std::stringstream ss(initial_quote);

    // 2. 插入字符串
    // std::stringstream ss;
    // ss << initial_quote;

    std::string first;
    std::string last;
    std::string language, extracted_quote;

    // >> 提取符按数据流顺序读取字符串的内容，
    // 以空白字符分隔（' ', '\n', '\t'）
    ss >> first >> last >> language >> extracted_quote;

    // 输出
    std::cout << first << "" << last << " said this: " << language << " " << extracted_quote << std::endl; 
}

Warning

使用字符串流时 extracted_quote 不能一次性把剩余的字符串全部提取出来，因为每一次提取都会按照空白符（包括空格、缩进、换行）进行分割，因此一次只能读取一个单词。

为了一次性读取一行输入中剩余的内容，应该使用 getline() 函数。

getline()

函数接口为 istream& getline(istream& is, string& str, char delim)

  • getline()读取一串输入流is，直到读取字符delim时停止，将读到的数据存入缓冲区str中
  • delim 默认为 \n
  • getline() 读取的数据是会把字符 delim “消耗（consumes）” 掉，也会读取这个字符

上面的代码中提取字符的部分修改为以下语句，就可以让extracted_quote提取出剩余的字符串：

1
2
ss >> first >> last >> language;
std::getline(ss, extracted_quote);

输出流

输出流：一种向目标/外部源写入数据的方法

  • 使用 << 运算符“发送”输出流

输出流的字符在被释放（flush）到目的地之前会被存储在一个中间缓冲区内，std::endl 除了换行之外，还会立即执行一次 flush 操作

  • 一般而言，更建议使用 \n 而非 std::endl——一定程度上减少 flush 次数以提高性能。

输出文件流

输出文件流（output file streams）的类型为 std::ofstream，同样采用 << 插入符将数据送入文件内。

std::ofstream 常用的几种方法有

  • is_open()
  • open()
  • close()
  • fail()

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int main()
{
    // 在文件 hello.txt 中创建一个新的输出文件流
    std::ofstream ofs("hello.txt");

    // 检查文件是否打开，若是则将一段字符串写进文件内
    if (ofs.is_open())
    {
        ofs << "Hello CS106L!" << '\n';
    }

    // 关闭文件
    ofs.close();

    // 由于文件已关闭，以下内容不会被写入 hello.txt 中
    ofs << "this will not get written";

    // 重新打开文件
    ofs.open("hello.txt");

    // 下面的字符串又可以被写入文件内，但是会覆盖文件原来的内容
    ofs << "this will though! It's open again";

    return 0;
}

输入流

输入流 std::cin 也同样有缓冲区，它会把输入流数据逐个读入缓冲区内，直到遇到空白字符为止。

考虑下面的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int main()
{
    double pi;
    double tao;
    std::string name;

    std::cin >> pi;
    std::cin >> name;
    std::cin >> tao;

    std::cout << "my name is: " << " tao is: " << tao << " pi is: " << pi << '\n';

    return 0;
}

std::cin 的缓冲区的内容为：

我们很容易知道 pi 的值为 3.14，name 的值为字符串 "Fabio"，但类型为 double 的 tao 由于接收到了类型不匹配的数据 "Ibanez"，因此它的值被设置为 0，并抛出了错误信息。事实上我们希望 name 的值为完整的字符串 "Faibio Ibanez"。

我们不难想到使用 getline() 来提取这个完整的字符串。但此时我们只会读取到紧接在 3.14 后面的 \n，然后就会因为遇到了换行符而停止向 name 读入数据，从而使得在这个 \n 后的数据被抛弃掉。

解决办法是连续使用两次 getline()：先读取掉第一个换行符，在通过第二次 getline() 获取正确的数据

1
2
3
4
std::cin >> pi;
std::getline(std::cin, name);
std::getline(std::cin, name);
std::cin >> tao;

这提醒我们在将 std::cin 和 getline() 混合使用时，我们需要格外注意由于读取规则不同而导致的读取错误，如果可以，应尽量避免将它们混合使用。

输入文件流

输入文件流（input file streams）的类型为 std::ifstream，使用 >> 提取符从文件中读取数据。它的各种方法输出文件流非常类似：

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
int inputFileStreamExample()
{
    std::ifstream ifs("append.txt");

    if (ifs.is_open())
    {
        std::string line;
        std::getline(ifs, line);
        std::out << "Read from the file: " << line << '\n';
    }

    if (ifs.is_open())
    {
        std::string lineTwo;
        std::getline(ifs, lineTwo);
        std::out << "Read from the file: " << lineTwo << '\n';
    }    

    return 0; 
}

容器

Info

CS106L 默认学生已经修读（或同时正在修读 CS106B/X），因此它对于各种容器的使用方法没有介绍得很详细，只讲解了少数几个容器的内容，如果希望了解更多关于容器的知识，可以从 cppreference 或其他网络资源了解。

几个常见容器及其方法

C++ 许多容器处于 C++ Standard Template Library (STL) 中，所有的 STL 容器都是模板，包括

  • std::vector
  • std::set
  • std::stack
  • std::queue
  • std::map
  • std::unordered_map
  • std::unordered_set
  • std::priority_queue
  • std::deque
  • std::array

vector

  • std::vector<int> vec;：创建新的空向量
  • std::vector<int> vec(n);：创建一个包含 n 个 0 的向量
  • std::vector<int> vec(n, k);：创建一个包含 n 个值 k 的向量
  • vec.push_back(k);：将 k 加在向量的末端
  • vec.clear();：移除向量内所有元素
  • int k = vec[i];：获取索引为 i 的元素（不检查是否索引越界）
  • int k = v.at(i);：获取索引为 i 的元素（检查是否出现索引越界）
  • vec.size();：查看向量大小（当前元素个数）
  • vec.capacity()：查看当前向量容量（当前占据的内存空间可以容纳多少个元素，而不需进行动态内存分配）

deque

deque（读音为 deck）是双端队列（double-ended queue），除了额外的 push_front() 和 pop_front() 方法外，它具有与 std::vector 几乎完全相同的接口。

map

映射（map）中包含多个键值对，方法包括

  • std:::map<int, char> m;：创建空映射
  • m.insert({k, v}); 或 m[k] = v;：将键 k 和对应值 v 加入映射内
  • m.erase(k);：将键 k 从映射中移除
  • m.count(k)：检查键 k 是否在映射内，返回布尔值
  • m.empty()：检查映射是否为空
  • char c = m.at(k); m.at(k) = v;：检索并覆写键 k 对应的值（若键不存在则报错）
  • char c = m[k]; m[k] = v;：检索并覆写键 k 对应的值（若键不存在则自动插入）

std::map<K, V> 实际上是一个存储着多个 std::pair<const K, V> 的集合。例如，我们可以像下面这样使用：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
std::map<std::string, int> map;

// 方法1
for (auto kv : map) {
    // kv 类型为 std::pair<const std::string, int>
    std::string key = kv.first;
    int value = kv.second;
}

//方法2
for (const auto& [key, value] : map) {
    // key 的类型为 const std::string&
    // value 的类型为 const int&
}

map 的实现

std::map 在具体的实现上是通过二叉树（技术上是红黑树）来做到的。

由于二叉树在搜索时需要对键值 K 进行比较，因此 K 需要具有比较运算符 operator<

1
2
3
4
5
// OKAY - int has operator<
std::map<int, int> map1; 

// ERROR - std::ifstream has no operator<
std::map<std::ifstream, int> map2;

set

std::set 存储着一系列不同的元素，它相当于一个特殊的、只存储 key 而不保存 value 的 std::map。

std::set 同样也是通过红黑树实现的，因此它保存的元素也必须能够进行比较，具有 operator<

  • std::set<int> s;：创建空集合
  • s.insert(k)：将值 k 加入集合内
  • s.erase(k)：从集合中移除值 k

  • if (s.count(k))：检查值 k 是否在集合内

    • 从 C++20 开始也可使用 if (s.contains(k))

  • if (s.empty())：检查集合是否为空

unordered_map 与 unordered_set

unordered_map 是 map 的一个优化版本，它具有和 map 相同的接口，但是它的实现方式是通过哈希表（hash table）来实现的，因此它的插入、查找、删除等操作的时间复杂度是 O(1)。

Tip

unordered_map 不再要求 key 必须具有 operator<，而是要求 key 必须具有 operator== 和 std::hash（可以通过 std::hash 来计算 key 的哈希值，hashable）。

1
2
3
4
5
// OKAY - int is hashable
std::unordered_map<int, int> map1; 

// ERROR - std::ifstream is not hashable
std::unordered_map<std::ifstream, int> map2;
  • 荷载因子（load factor）：哈希表中元素的数量与桶的数量之比，当荷载因子超过某个阈值时，哈希表会自动扩容，以保证查询效率。

  • 默认的 load factor 为 1，我们也可以通过 max_load_factor() 来设置荷载因子的阈值。

    1
2
3
4
    std::unordered_map<std::string, int> map;

double lf = map.load_factor(); // Get current load factor
map.max_load_factor(2.0);      // Set the max load factor

而 std::unordered_set 就相当于一个不含有 values 的 std::unordered_map，它的元素也必须是 hashable 的。

unordered_map vs. map

  • unordered_map 通常比 map 更快，但会占据更多的内存空间
  • 如果需要保存的类型没有 operator<，则应该使用 unordered_map
  • 相对而言，unordered_map 更加安全

Abstract

ith element search insertion erase
std::vector 很快 慢 慢 慢
std::deque 快 慢 慢 慢
std::set 慢 快 快 快
std::map 慢 快 快 快
std::unordered_set N/A 很快 很快 很快
std::unordered_map N/A 很快 很快 很快

容器的分类

序列容器

序列容器是元素的线性序列，可以通过按顺序访问容器内的元素。

上面介绍过的容器中，std::vector 和 std::deque 就是序列容器。

vector 的内部实现

无论何时，std::vector 都会分配一块连续的内存空间来存储元素，并且在需要额外的空间时会被分配到一个更大的内存空间，然后将原来的元素复制到新的内存空间中（并释放旧的元素）。

需要注意的是，vector 所拥有的元素个数（size）和它所分配的内存空间（capacity）是两个不同的概念。

  • 当目前的 capacity 不足以容纳新的元素时（e.g. 在 v.size()==v.capacity() 插入一个新元素），vector 会重新分配一块更大的内存空间，并将原来的元素复制到新的内存空间中。

    • 新分配的内存空间的大小取决于编译器，但一般来说会是原来的两倍。

  • 当 capacity 足够时，对 vector 的元素进行增删不会改变 capacity。

    • e.g. 若当前的 capacity 为 8，而 size 为 5，这时删去一个元素，size 变为 4，但 capacity 仍为 8。这样做是为了避免频繁的内存分配和释放。

deque 的内部实现

std::deque 是双端队列（double-ended queue），底层通常由多个固定大小的内存块（chunks）组成，这些块在逻辑上是连续的，但在物理内存中不要求连续。每个块的大小由实现定义，例如 GCC 的 libstdc++ 中每个块的大小为 512 字节 / sizeof(element)。

在更上一层的逻辑上，deque 用一个动态数组（称为 map 或 control block）来保存指向各个内存块的指针。这个数组负责管理所有块的地址，类似“索引”的作用。

  • 动态分块分配：当在头部或尾部插入元素时，如果当前块已满，deque 会分配得到一个新的内存块，并将其地址添加到 map 中。这一过程避免了整体元素的移动，使得两端插入/删除的时间复杂度为 \(O(1)\)。
  • map 的扩容：如果 map 的空间不足以存储新块的指针，map 会重新分配得到一个更大的内存（类似 std::vector 的扩容策略），并将旧指针复制到新位置。此操作的时间复杂度较高（O(n)），但发生频率极低。

std::deque 的迭代器

std::deque 的迭代器需要记录以下信息：

  • 当前元素所在的块指针
  • 当前元素在块内的位置
  • 必要时跳转到相邻块

关联容器

特点：

  • 容器不必是有序的
  • 具有更快的检索速度

map 与 set 的内部实现

  • 映射（map）是由配对（pair）实现的，其中每一个元素都是：std::pair<const key, value>
  • 集合（set）相当于只有键、没有值的映射，因此它的元素都是 const key

有序的 map 和 set 的内部是通过红黑树实现的，因此都要求元素的键值具有 operator<，以此来进行元素的比较与检索。

无序的 unordered_map 和 unordered_set 的内部是通过哈希表实现的，因此要求元素的具有运算符 std::hash 和 operator==，即可哈希化且可比较。

迭代器

迭代器基本概念

迭代器（iterator）是一种对象，它允许我们按照某种特定的顺序在容器中遍历元素，而不需要关心容器的具体实现。

  • c.begin()：返回指向容器 c 中第一个元素的迭代器
  • c.end()：返回指向容器 c 中最后一个元素的下一个位置的迭代器（并不是指向最后一个元素）

所有的迭代器都有以下几个基本操作：

  • auto it = c.begin(); 拷贝初始化
  • ++it：迭代器自增
  • *it：解引用迭代器，获取迭代器指向的元素
  • it == c.end()：比较操作

但大部分迭代器还会提供一下几种操作：

  • --it：迭代器自减（反向移动）
  • *it = elem;：修改迭代器指向的元素
  • it += n;：迭代器移动 n 个位置
  • it1 < it2：比较两个迭代器的位置（某个迭代器是否在另一个迭代器之前）

迭代器的类型

迭代器的类型决定了它们的功能和行为，C++ 中的迭代器类型大致可以这么划分：

  • 输入迭代器（Input Iterators）：绝大部分迭代器的基本类型，允许我们通过迭代器读取元素
  • 输出迭代器（Output Iterator）：允许我们通过迭代器写入（修改）元素
  • 前向迭代器（Forward Iterator）：允许我们在容器中向前遍历元素的输入迭代器
  • 双向迭代器（Bidirectional Iterator）：允许我们在容器中向前和向后遍历元素的输入迭代器

  • 随机访问迭代器（Random Access Iterator）：允许我们在容器中随机访问元素的输入迭代器（可以指定偏移量，而不按顺序迭代）

    • std::vector 和 std::deque 的迭代器就是随机访问迭代器

for-each loop 与迭代器

for-each loop 本质上在使用迭代器来遍历容器，因此它只能用于支持输入迭代器的容器。

下面这段代码使用 for-each loop 来遍历一个 vector：

1
2
3
4
5
std::vector<int> vec = {1, 2, 3, 4, 5};

for (int elem : vec) {
    std::cout << elem << " ";
}

它的实现方式类似于下面的代码：

1
2
3
4
5
6
7
auto b = vec.begin();
auto e = vec.end();

for (auto it = b; it != e; ++it) {
    int elem = *it;
    std::cout << elem << " ";
}

类

我的 C++ 笔记中已经对关于类的内容有了很多介绍了，这里就只稍微记一些补充的内容。

基本概念

结构体和类的区别

classes containing a sequence of objects of various typs, a set of functions for manipulating these objects, and a set of restriction on the access of these objects and function;

structrues which are classes without access restriction;

-- Bjarne Stroustrup

在 CS106L 建议我们把类分别定义在 .h 和 .cpp 文件中，这样可以更好地区分类的声明和实现。

  • 头文件（.h）：
    • 定义类的接口
    • 包括：类的声明、成员变量、成员函数的原型、类型定义（alias 和 enum 等）、常量等
  • 源文件（.cpp）：
    • 定义类的实现
    • 包括：成员函数的具体实现、静态成员变量的初始化、可执行代码等

继承

继承具有以下特点：

  • 动态多态性（dynamic polymorphism）：不同类型的对象
  • 拓展性（extensibility）：继承允许我们通过创建具有特定属性的子类来扩展现有类

三种继承方式

继承类型 public protected private
派生类中 public 成员的属性 public protected 不可访问
派生类中 protected 成员的属性 protected protected 不可访问
派生类中 private 成员的属性 private private 不可访问

菱形继承问题（diamond problem）

菱形继承问题是指在多重继承中，派生类继承了两个基类，而这两个基类又继承自同一个基类，从而导致派生类中包含了两份相同的基类。

我们需要使用虚继承（virtual inheritance）来解决这个问题。

1
2
3
4
class A {};
class B : public A {};
class C : public A {};
class D : public B, public C {};

在这个例子中，D 继承了 B 和 C，而 B 和 C 都继承了 A，因此 D 中包含了两份 A。

为了解决这个问题，我们可以使用虚继承：

1
2
3
4
class A {};
class B : virtual public A {};
class C : virtual public A {};
class D : public B, public C {};

这样 D 中就只包含了一份 A，并且 D 要负责调用 A 的构造函数（负责初始化基类 A）。

模板类

类模板与模板类

虽然类模板和模板类在名称上非常相似，但它们的含义是不同的：

  • 类模板（class template）：是一个模板，用于生成类的定义，编译器会使用它来实例化各种具体的类，类似于函数模板用于生成函数定义
  • 模板类（template class）：是类模板实例化后的具体类。当使用类模板定义对象时，需要指定实际的类型参数，从而生成模板类。
1
2
3
4
5
6
7
8
// 类模板
template <typename T>
class MyClass {
    T data;
};

// 模板类
MyClass<int> myInt;

由于编译器需要知道模板类中所有成员的定义（包括成员函数的完整定义和实现），因此类模板的声明和实现都需要包含在头文件中，然后在需要使用这个类模板的地方 #include 这个头文件。

直接在头文件中定义类模板的两种方法

myclass.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#ifndef MYCLASS_H
#define MYCLASS_H

template <typename T>
class MyClass {
public:
    void myFunction();
};

void MyClass<T>::myFunction() {
    // Implementation
}

#endif
myclass.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#ifndef MYCLASS_H
#define MYCLASS_H

template <typename T>
class MyClass {
public:
    void myFunction() {
        // Implementation
    }
};

#endif
main.cpp
1
2
3
4
5
6
7
8
9
#include "myclass.h"

int main()
{
    MyClass<int> myInt;
    myInt.myFunction();

    return 0;
}

Info

CS106L 给出的观点是，仍然在 .h 文件中定义类模板，在 .cpp 文件中实现类模板的成员函数，但是要在 .h 文件的末尾#include 这个 .cpp 文件。然后在需要使用这个类模板的地方 #include 这个 .h 文件即可。

按照 CS106L 的观点，一个普通的类一般是这么编写的：

myclass.h
1
2
3
4
5
6
7
#ifndef MYCLASS_H
#define MYCLASS_H

class MyClass {
public:
    void myFunction();
};
myclass.cpp
1
2
3
4
5
#include "myclass.h"

void MyClass::myFunction() {
    // Implementation
}

而当我们使用类模板时，我们就要：

mytemplate.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#ifndef MYTEMPLATE_H
#define MYTEMPLATE_H

template <typename T>
class MyTemplate {
public:
    T& myFunction();
};

#include "mytemplate.cpp"
mytemplate.cpp
1
2
3
4
template <typename T>
T& MyTemplate<T>::myFunction() {
    // Implementation
}

至于到底是使用哪种方式定义类模板，就见仁见智了。

typename 与 class

在模板中，typename 和 class 是等价的，例如下面四种写法都是等价的；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 写法一
template <typename K, typename V>
struct pair;

// 写法二
template <class K, class V>
struct pair;

// 写法三
template <typename K, class V>
struct pair;

// 写法四
template <class K, typename V>
struct pair;

模板函数

模板函数是一种将数据类型进行参数化的函数，它允许我们在编写函数时不指定具体的数据类型，而是在调用函数时显式或隐式地指定数据类型。

一个简单的例子

例如下面这个简单的模板函数：

1
2
3
4
template <typename T>
T min(T a, T b) {
    return a < b ? a : b;
}

我们可以在第一行设置一个默认的类型参数：

1
template <typename Type=int>

可以显式地指定模板函数的类型参数：

1
min<int>(3, 4)

也可以隐式地指定模板函数的类型参数（让编译器自行推导参数类型）：

1
min(1.1, 2.2)

Warning

当我们使用字符串作为模板函数的类型参数时，编译器自行推断得到的类型将是 const char*，而不是 std::string。

1
2
3
// 以下两者是一致的
min("Jacob", "Fabio");
min<const char*>("Jacob", "Fabio");

在这个函数中，被比较的两个参数将是两个指针的值，即这两个字符串的地址，而不是字符串本身的值。如果我们希望比较字符串的值，我们需要显式使用 std::string 类型。

1
min<std::string>("Jacob", "Fabio");

concept

在使用模板函数时，我们通常要求模板函数的类型参数具有某些特定的属性，例如上面的 min 函数要求参数类型具有 < 运算符，这些限制被称为约束（constraints）。这些约束的被命名的集合被称为概念（concept）。

我们可以使用 concept 来限制模板函数的类型参数，从而避免一些不合法的类型参数。对于上面的例子，我们要求传入的参数是“可比较的”（comparable）：

1
2
3
4
template <typename T>
concept Comparable = requires(const T a, const T b) {
{ a < b } -> std::convertible_to<bool>;
};
  • 这个 concept 的名字是 Comparable
  • requires 子句后面是对于这个约束的要求，这里表示接受两个 const T 类型的参数 a 和 b
  • { a < b } 表示我们需要检查 a < b 这个表达式是否有效，即我们希望类型 T 具有 < 运算符
  • -> std::convertible_to<bool> 表示我们希望 a < b 的结果可以转换为 bool 类型

把这个 concept 用在我们的 min 函数中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// 写法一
template <Comparable T> requires Comparable<T>
T min(T a, T b) {
    return a < b ? a : b;
}

// 写法二
template <Comparable T>
T min(T a, T b) {
    return a < b ? a : b;
}

让我们的 min 函数能接受任意多个参数

1
2
3
4
5
template <Comparable T, Comparable... Ts>
T min(T a, Ts... args) {
    auto m = min(args...);
    return a < m ? a : m;
}
这里的 Comparable... Ts 表示我们可以接受任意多个参数，而这些参数都必须满足 Comparable 的要求。例如我们调用 min<int, int, int>(1, 2, 3)，这里的 int 满足 Comparable 的要求。

1
2
T = int
Ts = {int, int}

这个函数的实现方式是递归的，它先对除了第一个参数外的其他参数调用 min 函数，用第一个参数和返回值进行比较，然后返回较小的那个。我们需要定义一个 base case，即当只有一个参数时，直接返回这个参数。

1
2
3
4
template <Comparable T>
T min(T a) {
    return a;
}

模板元编程

我们可以利用函数模板的特性来进行一些编译期的计算，这被称为模板元编程（template metaprogramming）。

例如，我们可以使用模板元编程来计算阶乘：

1
2
3
4
5
6
7
8
9
template <>
struct Factorial<0> {
enum { value = 1 };
};
template <size_t N>
struct Factorial {
enum { value = N * Factorial<N - 1>::value };
};
std::cout << Factorial<7>::value << std::endl;

Tip

  • 模板元编程是图灵完备的，因此我们可以使用这项技术来在编译期间执行任意代码（但是这样做的语法很复杂，而且容易出错）。
  • 要使代码在编译期间执行，我们也可以使用 constexpr/consteval 函数。

函数与 Lambdas

谓词函数

我们称返回值是布尔类型的函数为谓词函数，它用于判断某个条件是否成立，可以接受一个或多个参数。

1
2
3
bool isEven(int n) {
    return n % 2 == 0;
}

谓词函数可以是一个普通的函数，也可以是一个 lambda 函数。

考虑一个简单的函数 find_if，它接受两个迭代器和一个谓词（predicate）函数，返回容器中第一个满足谓词的元素：

1
2
3
4
5
6
7
template <typename It, typename Pred>
It find(It first, It last, Pred pred) {
    for (auto it = first; it != last; ++it) {
        if (pred(*it)) return it;
    }
    return last;
}

我们可以像下面这样使用这个函数：

1
2
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = find(vec.begin(), vec.end(), isEven);

我们传入的 isEven 是实际上是一个函数指针，它指向了 isEven 函数的地址。我们也可以使用 lambda 函数来代替这个函数指针：

1
auto it = find(vec.begin(), vec.end(), [](int n) { return n % 2 == 0; });

lambda 表达式

lambda 表达式的基本格式为

1
2
3
4
auto var = [capture-clause] (auto param) -> bool
{
    // ...
}
  • capture-clause：捕获列表，用于捕获外部变量
  • param：参数列表
  • -> bool：返回值类型
  • {}：函数体

关于捕获子句：

  • []：不捕获任何外部变量
  • [=]：捕获所有函数体中使用到的外部变量（值捕获）
  • [&]：捕获所有函数体中使用到的外部变量（引用捕获）
  • [var]：捕获 var 变量（值捕获）
  • [&var]：捕获 var 变量（引用捕获）
  • [&, var]：引用捕获函数体中使用到的所有外部变量，但 var 为值捕获
  • [=, &var]：值捕获函数体中使用到的所有外部变量，但 var 为引用捕获

当我们使用一个 lambda 表达式时，编译器会生成一个匿名的函数对象（或称函子，functor），这个函数对象的类型是由编译器自动推导的。

例如这段简单的代码

1
2
3
int n = 10;
auto lessThanN = [n](int x) { return x < n; };
find_if(begin, end, lessThanN);

实际上相当于

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class __lambda_6_18 // 由编译器随机生成的类名
{
public:
    bool operator()(int x) const { return x < n; } // 重载了函数调用运算符()
    __lambda_6_18(int& _n) : n{_n} {} // 构造函数
private:
    int n; // 捕获的外部变量
};

int n = 10;
auto lessThanN = __lambda_6_18{ n }; // 利用 n 创建一个匿名对象
find_if(begin, end, lessThanN);

运算符重载

不可重载的运算符

  • ::：作用域解析运算符
  • .* .：成员指针运算符
  • ?:：三目条件运算符
  • sizeof()：长度运算符
  • typeid()：类型信息运算符
  • cast()：类型转换运算符

可重载的运算符

通常有两种重载运算符的方法：

  • 成员函数：重载运算符作为类的成员函数

    • 要求这个运算符的左操作数是这个类的对象
    • 需要在类的作用域内声明，可以在类的内部或外部定义

  • 非成员函数：重载运算符作为类的友元函数

    • 不要求这个运算符的左操作数是这个类的对象，允许左操作数是其他类型，如基本类型 int、double 等
    • 可以在类的外部定义，但是需要在类的作用域内使用 friend 关键字声明

运算符重载的使用哲学

  • 重载后的运算符会保持原有的优先级和结合性
  • 重载后的运算符应意义明确
  • 重载后的运算符应该遵循常规的语义，例如不要把 + 重载成减法

特殊成员函数

每个类都拥有六个特殊的成员函数（special member functions，SMF），它们是：

  • 默认构造函数（default constructor）：不接受任何参数的构造函数
  • 析构函数（destructor）：当对象离开作用域时被调用
  • 拷贝构造函数（copy constructor）：通过按成员拷贝一个现有对象，创建一个新对象
  • 拷贝赋值运算符（copy assignment operator）：将一个对象的值赋给另一个对象
  • 移动构造函数（move constructor）：通过移动现有对象的资源，创建一个新对象
  • 移动赋值运算符（move assignment operator）：将一个对象的资源移动给另一个对象

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Widget
{
    public:
        Widget();                             // default construtor
        Widget (const Widget& w);             // copy constuctor
        Widget& operator = (const Widget& w); // copy assignment operator
        ~Widget();                            // destrutor
        Widget (Widget&& rhs);                // move constructor
        Widget& operator = (Widget&& rhs);    // move assignment operator
}

拷贝构造与拷贝赋值

当我们使用一个对象初始化另一个对象时，拷贝构造函数会被调用；当我们使用一个对象赋值给另一个对象时，拷贝赋值运算符会被调用。

当这两个函数/运算符没有被显式定义时，编译器会自动生成默认的版本，它们会一一对应地拷贝对象的每一个成员变量的值。但当我们的类中包含了指针或其他资源时，直接使用默认的拷贝构造函数和拷贝赋值运算符会导致新的对象和原对象共享资源（例如两个对象中的指针都指向同一块内存）。

当其中一个对象对这块资源进行操作（例如通过指针修改这块内存存储的值）是，另一个对象并不知情，当另一个对象再次访问这块资源时，可能会因为这块资源的值已经被修改而出现错误。

上述的拷贝被称为浅拷贝。如果我们希望做到深拷贝，即新创建的对象拥有一份独立的资源，我们就需要显式地自行定义拷贝构造函数和拷贝赋值运算符。

Example

1
2
3
4
5
6
Vector<T>::Vector(const Vector<T>& other)
    : _size(other._size), _capacity(other._capacity), _data(newT[other._capacity]) {
        for (size_t i = 0; i < _size; ++i) {
            _data[i] = other._data[i];
    }
}

下面这些表达式调用的函数是什么？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
vector<int> func(vector<int> vec0) {
    vector<int> vec1;
    vector<int> vec2(3);
    vector<int> vec3{3};
    vector<int> vec4();
    vector<int> vec5(vec2);
    vector<int> vec6{};
    vector<int> vec7{static_cast<int>(vec2.size() + vec6.size())};
    vector<int> vec8 = vec2;
    vec8 = vec2;
    return vec8;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// 暂时不考虑移动语义
vector<int> func(vector<int> vec0) { // 按值传递参数，也会调用拷贝构造函数
    vector<int> vec1;       // 默认构造函数
    vector<int> vec2(3);    // 自定义的含参数构造函数，不是 SMF，表示创建一个大小为 3 的 vector
    vector<int> vec3{3};    // 一致初始化，不是 SMF
    vector<int> vec4();     // 函数声明，不是 SMF
    vector<int> vec5(vec2); // 拷贝构造函数
    vector<int> vec6{};     // 默认初始化
    vector<int> vec7{static_cast<int>(vec2.size() + vec6.size())}; //列表初始化
    vector<int> vec8 = vec2;// 拷贝构造函数
    vec8 = vec2;            // 拷贝赋值运算符
    return vec8;            // 会调用拷贝构造函数
}

移动语义

移动语义允许我们直接将资源的所有权从一个对象转移到另一个对象，以避免不必要的资源拷贝，提高程序的性能。

我们可以使用 && 来表示右值引用，它是一个新的引用类型，用于绑定到临时对象（右值）。我们可以在实现移动语义的函数的参数列表中使用右值引用，以表示我们希望这个函数接受一个右值。当我们向函数调用传入一个右值，或是一个临时对象时，编译器会知道此时应该调用移动构造函数或移动赋值运算符。

除非真的有必要这么做，我们最好不要对一个左值使用 std::move，因为这样会使得它的资源被转移，假如不经过重新赋值而再次使用这个对象，可能会导致程序出错。

Note

Rule of Zero：

  • 如果编译器默认生成的特殊成员函数能够满足需求，那么就不要显式地定义这些函数

Rule of Three：

  • 如果我们需要显式定义析构函数、拷贝构造函数或拷贝赋值运算符其中任意一个，那么通常这三者都需要我们自行定义

Rule of Five：

  • 如果我们显式定义了析构函数、拷贝构造函数或拷贝赋值运算符，那么我们也需要定义移动构造函数和移动赋值运算符

Optional 与类型安全

类型安全

类型安全是指编程语言能够防止程序出现类型错误的能力。

考虑下面这段简单的代码：

1
2
3
4
5
void removeOddsFromEnd(vector<int>& vec){
    while(vec.back() % 2 == 1){
        vec.pop_back();
    }
}

我们不难发现当 vector 为空时，调用这个函数将导致未定义行为，因为 vec.back() 和 vec.pop_back() 都会访问一个不存在的元素。

对于上面的问题，我们可以想到两种解决方案：

  • 修改 while 语句的判断条件为 !vec.empty() && vec.back() % 2 == 1，即先判断 vector 是否为空，不为空时再判断最后一个元素是否为奇数
  • 修改 vec.back() 函数，使其能应对各种情况，防止出现未定义行为

对于后一种方法，假设我们原本的 vec.back() 函数是这样的：

1
2
3
valueType& vector<valueType>::back() {
    return *(begin() + size() - 1);
}

我们可以让这个函数在发现 vector 为空时抛出一个 std::out_of_range 异常：

1
2
3
4
valueType& vector<valueType>::back(){
    if(empty()) throw std::out_of_range;
    return *(begin() + size() - 1);
}

我们还可以有另一种思路：让函数的返回值能够表示这个函数是否成功执行，例如

1
2
3
4
5
6
7
std::pair<bool, valueType&> vector<valueType>::back()
{
    if (empty())
        // 默认 valueType 存在构造函数，但调用构造函数的成本较高
        return {false, valueType()};
    return {true, *(begin() + size() - 1)};
}

std::optional

std::optional 是 C++17 中引入的一个新的标准库类型，它是一个模板类，用于表示一个可能为空的值：它要么保存着一个值，要么不保存任何值（即 std::nullopt）。

nullopt 不是 nullptr

  • nullptr 是一个空指针常量，用于表示指针不指向任何对象
  • nullopt 是一个空值常量，用于表示 std::optional 不保存任何值

利用 std::optional，我们可以重写上面的 vector::back() 函数：

1
2
3
4
5
std::optional<valueType> vector<valueType>::back() {
    if (empty())
        return {};
    return *(begin() + size() - 1);
}

但是这样又会产生一个问题 —— std::optional 类型不能直接参与算术运算，需要使用 * 解引用操作符来获取它的值。为了解决这个问题，我们可以使用 value() 函数来获取 std::optional 的值：

1
2
3
4
5
6
void removeOddsFromEnd(vector<int>& vec) {
    while(vec.back().has_value() && vec.back().value() % 2 == 1)
    {
        vec.pop_back();
    }
}

std::optional 的接口

  • .value()：返回 std::optional 中保存的值，或抛出一个 std::bad_optional_access 异常
  • .value_or(valueType val)：返回 std::optional 中保存的值，或返回参数 val 的值（默认值）
  • .has_value()：如果 std::optional 保存了值，返回 true，否则返回 false
  • .reset()：清空 std::optional 中保存的值
  • .and_then(function f)：如果 std::optional 中保存了值，返回调用 f(value) 函数的结果；否则返回 std::nullopt（函数 f 的返回值必须也是 std::optional）
  • .transform(function f)：如果 std::optional 中保存了值，返回调用 f(value) 函数的结果；否则返回 std::nullopt（函数 f 的返回值必须是 std::optional<valueType>）
  • .or_else(function f)：如果 std::optional 中保存了值，返回这个值；否则返回调用 f() 函数的结果

使用 std::optional 作为函数返回类型的优劣：

  • 优：
    • 能够使函数返回更有意义的内容
    • 类函数调用行为的正确性、安全性得到保证
  • 劣：
    • 会增加代码的复杂性，比如到处使用 .value() 方法
    • 可能会遇见 bad_optional_access 错误
    • 使用这个类型本身也可能遇见未定义行为（例如使用 .value() 时没有进行错误检查）

Info

由于 std::optional 较为笨重，使用时的代码运行效率较低，因此 C++ STL 数据结构通常不会用到它。

RAII 与智能指针

RAII

当我们在程序中获取（acquire）资源后，需要在不再使用时释放（release）这个资源，这种资源管理方式被称为资源获取即初始化（Resource Acquisition Is Initialization，RAII）。

RAII 的基本思想

  • 类（对象）所使用的所有资源都应该在构造函数中被获取
  • 类（对象）所使用的所有资源都应该在析构函数中被释放

我们可以用一句话来概括 RAII 的基本思想：

资源的获取和释放应该是一体的，资源的释放应该在对象的生命周期结束时自动进行。即资源的有效期 = 持有资源的对象的生命周期。

Acquire Release search
Heap memory new delete
Files open close
Locks try_lock unlock
Sockets socket close

智能指针

  • std::unique_ptr：独占资源所有权的智能指针，只能有一个指针指向这个对象，无法被复制
  • std::shared_ptr：共享资源所有权的智能指针，可以有多个指针指向这个对象，使用引用计数来管理资源的生命周期
  • std::weak_ptr：弱引用智能指针，不会增加引用计数，用于解决 std::shared_ptr 的循环引用（循环依赖）问题

std::unique_ptr

当我们使用一个 std::unique_ptr 去初始化另一个 std::unique_ptr 时，资源的所有权会被转移，即原来的 std::unique_ptr 不再拥有这个资源。

1
2
3
4
5
auto ptr1 = std::make_unique<int>(42);
auto ptr2 = std::move(ptr1);// 移动了资源的所有权，ptr1 不再拥有这个资源

std::cout << *ptr1 << '\n'; // 未定义行为
std::cout << *ptr2 << '\n'; // 42

std::shared_ptr

若要让多个指针共享一个资源，我们可以使用 std::shared_ptr。std::shared_ptr 主要有两个部分组成：一个指向资源的指针和一指向控制块。每当一个新的 std::shared_ptr 指向这个资源时（需要使用现有的 std::shared_ptr 来初始化新的 std::shared_ptr），控制块中的引用计数会增加 1，当 std::shared_ptr 被销毁时，引用计数会减少 1，仅当引用计数为 0 时，资源才会被释放。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
auto ptr1 = std::make_shared<int>(42);
auto ptr2 = ptr1; // 引用计数加 1

std::cout << *ptr1 << *ptr2 << '\n'; // 42

ptr1.reset(); // 引用计数减 1

std::cout << *ptr2 << '\n'; // 42

ptr2.reset(); // 引用计数减 1，资源被释放

std::weak_ptr

std::shared_ptr 存在一个致命的问题：循环依赖问题。当两个对象各自掌握指向对方的 std::shared_ptr 时，它们在被销毁时会因为循环依赖问题而导致资源无法被正确释放。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <memory>

class B; // 前向声明 B，使得类 A 内部可以创建一个指向 B 类的智能指针

class A
{
public:
    std::shared_ptr<B> ptr_to_b;
    ~A()
    {
        std::cout << "All of A's resources deallocated" << std::endl;
    }
};

class B
{
public:
    std::shared_ptr<A> ptr_to_a;
    ~B()
    {
        std::cout << "All of B's resources deallocated" << std::endl;
    }
};

int main()
{
    std::shared_ptr<A> a = std::make_shared<A>();
    std::shared_ptr<B> b = std::make_shared<B>();
    a->ptr_to_b = b;
    b->ptr_to_a = a;
    return 0;
}

这个例子中，类 A 的实例和类 B 的实例互相保存了指向对方的共享指针，这就构成了一个简单的循环。

  • 由于 b 的定义出现在 a 后面，后创建的变量先被销毁，因此当 main 函数结束时 b 会首先被销毁。
  • 销毁 b
    • 尝试销毁共享指针 b 时，他会首先检查是否还有别的 shared_ptr 指向这个 B 类对象，答案是有（a->ptr_to_b），因此 b 被销毁时只是将 B 的引用计数减至 1（B 仍存活）
    • 此时 A 的引用计数为 2，B 的引用计数为 1
  • 接着销毁共享指针 a，
    • a 被销毁时，由于此时 B 仍然有一个指针指向着 A，因此 a 被销毁只会导致 A 的引用计数减至 1（A 仍存活）
    • 此时 A、B 的引用计数均为 1
  • 现在 a 和 b 都被销毁了，但是仍然有两个实例 A 和 B 相互引用对方（并且我们现在无法用任何方式来访问这两个指针），因此直到整个程序彻底结束，它们都不会被销毁，都不会有任何析构函数被调用！

为了解决这个问题，我们可以使用 std::weak_ptr 来避免循环依赖问题：

std::weak_ptr 指向一个已经由 std::shared_ptr 保管的资源时不会增加控制块中的引用计数，因此我们可以对上面的程序稍作修改：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <memory>

class B; // 前向声明 B，使得类 A 内部可以创建一个指向 B 类的智能指针

class A
{
public:
    std::shared_ptr<B> ptr_to_b;
    ~A()
    {
        std::cout << "All of A's resources deallocated" << std::endl;
    }
};

class B
{
public:
    std::weak_ptr<A> ptr_to_a;
    ~B()
    {
        std::cout << "All of B's resources deallocated" << std::endl;
    }
};

int main()
{
    std::shared_ptr<A> a = std::make_shared<A>();
    std::shared_ptr<B> b = std::make_shared<B>();
    a->ptr_to_b = b;
    b->ptr_to_a = a;
    return 0;
}

现在我们的程序就可以正确地释放资源了，程序运行的输出结果为：

1
2
All of A's resources deallocated
All of B's resources deallocated
  • a 和 b 分别指向新创建的 A 和 B 对象，初始引用计数均为 1。
  • a->ptr_to_b = b 使 B 的引用计数从 1 → 2。
  • b->ptr_to_a = a 仅建立弱引用，A 的引用计数仍为 1。
  • 由于 b 后创建，因此它先于 a 被销毁
    • b 被销毁后，B 的引用计数从 2 → 1，因此 B 的析构函数不会被调用

  • 接着销毁 a，

    • a 的引用计数从 1 → 0，触发 A 的析构函数，输出
    1
    All of A's resources deallocated
    • A 被销毁后，其成员 ptr_to_b（指向 B 的 shared_ptr）也被销毁，导致 B 的引用计数从 1 → 0。
    • 最终触发 B 的析构函数，输出：
    1
    All of A's resources deallocated

Comments