CS106L 学习笔记

§1 类型与结构体 Types & Structs

1.1 结构体 Structs

结构体将命名变量捆绑到一个新类型中。

struct Order {
    string item;
    int quantity;
};
Order dozen = {"Eggs", 12};

上述例子可以使用 std::pair 代替：

std::pair<std::string, int> dozen {"Eggs", 12};
std::string item = dozen.first;
int quantity = dozen.second;

1.2 std标准库

std是C++的标准库。C++ 标准库提供了大量预定义的类型、函数及相关组件。在使用标准库中的特定组件之前，需要通过 #include 预处理指令引入相应的头文件。

• #include <utility> 提供 std::pair

我们需要在标准库中的语言名称前加上 std:: 前缀。如果我们使用 using namespace std; ，我们就不必这么做，但这被认为是不良的习惯，因为这会污染命名空间。比如，如果我们自定义了一个sort函数，编译器就难以区分标准库里的sort函数和我们自己的sort函数。

1.3 using 和 auto 用于简化代码

当类型名较长时，反复完整书写会降低代码的可读性与编写效率。可以使用 using 关键字为已有类型定义别名，从而简化复杂类型的表达。

//不使用using关键字
std::pair<bool, std::pair<double, double>> solveQuadratic(double a, double b, double c);
//使用using关键字
using Zeros = std::pair<double, double>;
using Solutions = std::pair<bool, Zeros>;
Solutions solveQuadratic(double a, double b, double c);

同时，auto 关键字让编译器根据数据自己选择合适的数据类型。需要注意，auto只在定义初始决定好数据类型，后续无法更改。

//延续上述例子
auto result = solveQuadratic(double a, double b, double c);

§2 初始化与引用 Initialization & References

2.1 初始化 Initialization

直接初始化（direct initialization）：初始化的值如果不符合定义的类型，则强制转换。

int numOne = 12.0;
int numTwo(12.0);   //12.0不符合int数据类型，编译器转化为12

统一初始化（uniform initialization）：初始化的值必须符合定义的类型。

int numOne = {12};
int numTwo{12.0};   //12.0不符合int数据类型，编译器报错

结构化绑定（Structured Binding）：从固定大小的数据结构中初始化多个变量。常用于访问函数返回的多个值。该数据结构的大小必须在编译时已知。

std::tuple<std::string, std::string, std::string> getClassInfo() {
    std::string className = "CS106L";
    std::string buildingName = "Thornron 101";
    std::string language = "C++";
    return {className, buildingName, language}; //统一初始化
}
auto [className, buildingName, language] = getClassInfo(); //结构化绑定

2.2 引用 References

引用就是给已经存在的对象或函数起一个别名，内存地址和引用对象完全相同，通过引用可以原地改变实参的值。引用可用于函数传参等。

void shift(std::vector<std::pair<int, int>> &nums) {
    for (auto& [nums1, nums2] : nums) {  //运用了引用和结构化绑定
        nums1++;
        nums2++;
    }
    return;
}

2.3 使用命令行进行.cpp文件的编译（compile)

使用g++编译器按照C++23的标准将main.cpp编译成程序：

g++ -std=c++23 main.cpp -o main

如果是多文件程序，要把所有.cpp文件写在main.cpp的位置。

在Linux或macOS中，运行编译好的文件指令为：

./main

在Windows上运行，则指令为：

.\main.exe

§3 流 Stream

3.1 流的定义

流（stream）是C++的一种通用的输入输出抽象模式，提供了一种统一的处理外部数据的方式。

cout & cin输出：（略）

fout & fin输出：

//create a file called "data.txt"
std::ofstream fout("data.txt");
fout << "I'm writing to this file";

std::ifstream fin("data.txt");
std::string first_word;
//store the first word from the file into fin
fin >> student_input;

ios_base是所有流的基础，用于维护状态信息、控制信息，确保信息流正常。状态信息告诉人们流是否正常，比如failbit提示存在逻辑错误，eofbit提示已到文件末尾；控制信息表示应该如何输出数据，比如dec、hex、oct等。

ios_base的组成如下：

输入流（input streams）是一种从源读取数据的方式，继承自 std::istream ，基本运算符是 >> ；输出流（output streams）是一种向目标输出数据的方式，继承自 std::ostream ，基本运算符是 << 。istream 和 ostream 的交叉部分称为 iostream ，这部分流同时具有输入流和输出流的特征。

3.2 stringstreams 字符串流

stringstreams是把string字符串当作流处理的一种方式，适合处理混合数据类型的用例。字符串输出流为 std::ostringstream ，字符串输入流为 std::istringstream 。

void foo() {
    std::string initial_quote = "Hi I'm Addison Rae Updates";
    // create a stringstream
    std::stringstream ss(initial_quote); //用initial_quote初始化字符串流
    // data destinations
    std::string first;
    std::string last;
    std::string language, extracted_quote;
    ss >> first >> last >> language; //从字符串流中读入
    std::getline(ss, extracted_quote);
    std::cout << first << " " << last << language << " " << extracted_quote << std::endl;
}

<< 和 >> 读取字符直到任何空格为止，这些空格包括 / \n / \t / \r / \f / \v 等。

std::getline 从输入流is中读取字符到str中直到读取到delim字符。默认情况下，delim字符设置为 \n （即换行符）。特别注意：getline 函数会读取delim字符。

istream& getline(istream& is, string& str, char delim);

3.3 输出流 Output Stream

缓冲区：输出流中的字符会先存储在缓冲区，然后再刷新在目标位置。

刷新的时机：

• std::cout << std::flush
• std::cout << std::endl
• 当程序到达末尾时
• 当缓冲区满了时
• 当相连的流互相作用时（例：在使用cin输入前，输出流必须刷新）

cerr 被用于立即输出程序的错误信息，该信息不会存在缓冲区里；而 clog 被用于输出程序的错误信息，该信息会存在缓冲区里。后者常用于非必要错误信息的排查。

REMINDER: 由于 endl 会给输出流缓冲区带来不必要的刷新，因此若只是换行建议使用 \n 。

文件输出流：把数据写入文件的方式。输出流为 std::ofstream

创建文件输出流的方式：std::ofstream out("file.txt", file_flag)

其中，file_flag 表示创建输出流的模式，主要有三种：

• std::ios::trunc 清空文件，从头写，是默认设置
• std::ios::app 不清空，追加至末尾
• std::ios::ate 打开后光标直接追加至末尾

文件输出流使用举例：

int main()
{
    std::ofstream ofs("hello.txt");               //创建输出流
    if (ofs.is_open()) {                          //判断文件是否打开
        ofs << "Hello CS106L!" << '\n';           //在文件中输出文字
    }                                             //ofs是自己设置的输出流名称
    ofs.close();                                  //关闭文件
    ofs << "This won't get written.";
    ofs.open("hello.txt", std::ios::app);         //重新打开，模式设为追加
    ofs << "This will though! It's open again.";
    return 0;
}

文件输入流的用法和文件输出流完全对称。

3.4 输入流 Input Stream

混合型数据类型输入时，尽量不要混用cin和getline。

void cinGetline() {
    double pi;
    double tao;
    std::string name;
    std::cin >> pi;
    std::getline(std::cin, name);
    std::getline(std::cin, name);  //留意多出来的这行
    std::cin >> tao;
    std::cout << name << " " << pi << " " << tao << "\n";
}

当 getline 函数进行输入时，由于会读入 \n ，因此第一行 getline 读入的是上个输入在缓冲区遗留的换行符，第二个 getline 才会读入字符串。

§4 容器 Containers

4.1 STL (Standard Template Library)

STL是C++中非常实用的一个标准库，隶属于std标准库。STL包括四个部分：容器（containers）、迭代器（iterators）、函子（functors）和算法（algorithm）。

4.2 顺序容器 Sequence Container

顺序容器实现了可以按顺序访问的数据结构，如 vector / deque / array / list 。

vector容器：可调整大小的连续数组（动态数组）。

访问vector元素：

vector<int> vec(13);
for (size_t i = 0; i < 13; i++) {
    vec[i]++;    //不会检查i是否越界
    vec.at(i)++; //会检查i是否越界
}

vector 是如何调整大小的？

当 push_back 时发现 size == capacity，vector 会申请一块更大的连续内存，把旧元素搬过去，再插入新元素，然后释放旧内存。时空复杂度是O(1)。

一般而言，vector申请的连续内存是翻倍的。但这不是C++的强制规定。

另：vector::insert 插入中间元素时，为了保持连续存储和元素顺序，必须移动插入点之后的元素，所以它通常是O(n)，不像数组下标访问那样是O(1)。

deque容器：有两端的队列。同时存在 push_back 和 push_front 。

deque容器是如何演化的？

1. Map（控制块）

   deque 的核心可以理解为一个“指针的动态数组”。这些指针，也就是图中紫色的小格子，并不直接存放你的数据，而是存放 数据块（Data Blocks） 的内存地址。正因为如此，deque 的数据在内存中不需要像 vector 那样完全连续存放。

2. 头尾 O(1) 增长

   当你执行 push_front 或 push_back 时，deque 会先检查当前边缘的数据块是否还有空位。如果没有空位，它就会分配一个新的固定大小的数据块，并把这个新数据块的地址放入 Map 中下一个可用的位置。

   因为这个过程中只需要新增一个指针，已有元素本身并不会在内存中移动。所以 deque 在增长时，指向已有元素的指针和引用通常仍然有效。

3. 重新居中的增长方式

   如果你一直向同一侧插入元素，最终会到达控制块 Map 的边界。这时 deque 不会把所有实际数据整体移动，而是会分配一个更大的指针数组，并把原来的指针复制到新数组的中间位置。

   这种“双重间接寻址”机制保证了 deque 可以继续向两端增长，同时又避免了对实际数据进行大规模搬移。

4. 随机访问的计算方式

   当访问 deque[i] 时，CPU 并不会从头开始一个一个遍历。它会通过计算确定元素所在的数据块和块内位置：

   block = (i + offset) / block_size;
   cell  = (i + offset) % block_size;

   其中 block 用来找到 Map 中对应的数据块指针，cell 用来找到该数据块内部的具体元素。

   和 vector 的一次寻址相比，deque 通常需要两次跳转；但它同时保留了类似链表的两端灵活增长能力，以及接近数组的随机访问速度。

4.3 关联容器 Associative Container

关联容器实现了可以快速排序的有序数据结构。如：map / set

map容器：储存键值对，并按键排序。

即使没有定义键值对，编译器也会把未定义的键赋予一个默认值（通常为0）。

std::map 底层通常是一棵红黑树。插入 key-value 对时，map 会按照 key 的大小把节点放进树里，并通过旋转和变色保持平衡，所以它能自动有序，并且查找、插入、删除通常都是 O(log n)。

set容器：没有值的map，储存不重复的元素并排序。

4.4 无序关联容器 Unordered Associative Container

就是关联容器的无序版本，通常来说性能更快。如 unordered_set / unordered_map 。

底层实现是哈希表，因此时间复杂度更快。

总结：STL各容器的算法速度比较

§5 迭代器 Iterators

5.1 迭代器基础知识

迭代器是STL中用于遍历容器的通用位置对象。

container.begin()  //指向容器第一个元素的迭代器
container.end()    //指向容器最后一个元素后面的一个位置的迭代器
auto it = c.begin();   //直接初始化迭代器
++it;                  //迭代器向前进一个位置（使用it++会增加一个复制步骤，因此推荐++it）
auto& elem = *it;      //迭代器解引用
if (it == c.end())...  //判断迭代器是否到达结尾

迭代器的数据类型由所属的容器决定：

std::map<int, int> m{{1, 2}, {3, 4}};
std::map<int, int>::iterator it = m.begin();

5.2 迭代器的种类

输入迭代器（input iterators）：最基础的迭代器，允许读取元素。

特点：只能单次读取，只读，不可回退。

int main()
{
    std::cout << "Enter numbers (Ctrl+D to stop)\n";
    std::istream_iterator<int> start(std::cin);      //设置迭代器从输入开始阅读
    std::istream_iterator<int> end;                  //设置终止迭代器
    std::vector<int> numbers(start, end);            //把读取的数全部读入vector
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

如果指向的元素是结构体，可以使用operator -> 来访问元素。

输出迭代器（output iterators）：允许写入元素的迭代器。

int main()
{
    std::ostream_iterator<int> it(std::cout, ", ");
    //上面代码的意思是：创建输出迭代器，每输入一个数，迭代器输入到cout输出流里并在后面加“， ”
    *it = 10;
    ++it;      //实际上这个自增没有实际意义，因为没有所谓的下一个元素
    *it = 20;
    ++it;
    *it = 30;  //output: 10, 20, 30,
    return 0;
}

int main()
{
    std::vector<int> v;
    std::back_insert_iterator<std::vector<int>> it(v);
    //上面代码的意思是：定义一个动态数组，并定义指向动态数组的迭代器
    *it = 10;  //相当于v.push_back(10)
    ++it;      
    *it = 20;
    ++it;
    *it = 30;  //v现在的值为{10, 20, 30}
    return 0;
}

前向迭代器（forward iterator）：可以从前往后一个一个遍历元素，并且可以重复遍历同一段数据的迭代器。

特点：可以多次读取，只读，不可回退。

注意：对于流来说，前向迭代器容易导致错误，所以不要在流中使用前向迭代器。

//支持的语法
it1 == it2 //判断两迭代器是否相等
++it1 == ++it2

双向迭代器（bidirectional iterator）：可以从前往后遍历，也可以从后往前退回去的迭代器。

典例：std::map / std::set 的迭代器。

//支持的语法
--it;      //可以往回退，但不能随机游走

随机访问迭代器（random access iterator）：可以像数组下标一样直接跳到任意相对位置的迭代器。

典例：std::vector / std::deque

//支持的语法
++it;      // 向后走一步
--it;      // 向前退一步
it + n;    // 向后跳 n 个位置
it - n;    // 向前跳 n 个位置
it2 - it1; // 计算两个迭代器之间的距离
it[n];     // 访问 it 后面第 n 个元素
it1 < it2  // 比较位置先后

为什么迭代器的类型很重要？

• 一些内部储存的算法需要特定的迭代器类型才能实现；
• 容器的底层实现方式决定了迭代器的种类。随机访问迭代器适用于顺序容器，因为访问很快；相比之下，关联容器的随机访问就慢很多，所以关联容器一般采用双向迭代器。

§6 类 Classes

6.1 类的定义

面向对象编程（OOP, Object-oriented Programming）：以对象为中心的编程方式，专注于类的设计和实现。

类就是用户自定义的可以被声明为对象的类型。类包含一系列不同类型的对象、一组用于操作这些对象的函数，以及一组对这些对象和函数的访问限制。

容器就是在STL中被定义的类。

类包含 public 和 private 两个区域，public 是可以被外界访问的，private 只能被类里的元素访问。

构造函数（constructor）：初始化新产生的类的函数。

自定义构造函数：如果类定义在头文件，则 .h 文件写：

class MyID {
private:
    std::string name;
    std::string sunet;
    int idNumber;
public:
    MyID(std::string name, std::string sunet, int idNumber);
    //头文件可以写明构造函数的具体内容，也可以只是声明。构造函数需要与类同名，不需要写类型。
    std::string getName();
    std::string getSunet();
    int getID();
};

在 .cpp 文件写声明：

MyID::MyID(std::string name, std::string sunet, int idNumber) {  //注意声明域
    this->name = name;              //直接赋值时，表示类里定义的变量需要加this指针以示区分
    this->sunet = sunet;
    if (idNumber > 0) {
        this->idNumber = idNumber;  //如果不满足条件而没有自定义默认的构造函数，则默认初始化为0
    }
}

也可以（更推荐）使用成员初始化列表：

MyID::MyID(std::string name, std::string sunet, int idNumber) {
    name{name}, sunet{sunet} {};      //此处不能写this指针，留意末尾的{}
    if(idNumber > 0) idNumber{idNumber} {};
}
MyID::MyID() {
    name{EzraYang}, sunet{EzraY}, idNumber{2552778} {};
} //构造函数允许重载，没有参数意味着是默认构造函数，注意需要在头文件声明

析构函数（destructor）：在类执行完周期后，销毁类内变量的函数。

一般析构函数不会被显式调用，而是自动调用，当对象超出作用域的时候就会被调用。

MyAnotherID::~MyAnotherID() {
    delete[] my_array;
} //如果类内有动态申请过空间的变量要在此处释放

6.2 类的继承 Inheritance

类的继承指让一个子类基于父类已有的成员和接口继续扩展或改写功能，从而表达“子类是一种父类”的关系。

类的继承的两个作用：

1.动态多态：不同类型的对象可能需要同样的接口。

2.可扩展性：可以先写一个比较抽象的父类，然后再写更具体的子类。

类的继承举例：（一般写在头文件里方便使用，不过也能写在.cpp文件里）

class Shape {
public:
    virtual double area() const = 0;
    //这行代码称为纯虚函数，在父类定义，在子类中重写，表示允许被继承
    //它的意思是：定义一个纯虚函数area，返回double，并且该函数不会修改对象本身
    //“= 0”的意思是：该函数在父类只提供接口，不修改对象本身
};
class Circle : public Shape {  //定义Circle子类，以public的方式继承Shape父类
public:
    Circle(double radius): _radius{radius} {};  //子类的构造函数，用初始化列表绑定
    double area() const {
        return 3.14 * _radius * _radius;
    }  //重写area函数
private:
    double _radius;  //继承的另一个优点：能够封装类内变量
};

上文中的 class Circle : public Shape 里的 public 指的是类的继承类别。类别主要有 public / private / protected 三类，它们的区别是：

继承方式	父类 public 成员到子类里	父类 protected 成员到子类里	父类 private 成员
public 继承	还是 public	还是 protected	子类不能直接访问
protected 继承	变成 protected	还是 protected	子类不能直接访问
private 继承	变成 private	变成 private	子类不能直接访问

6.3 虚继承 Virtual Inheritance

菱形继承问题：假设子类B和C都继承自父类A，一个类D又同时继承B和C，A、B、C都定义了一个 func() 函数，那么在D中，如何定义 func() 函数不会导致混淆？

答：引入虚继承。虚继承的意思是：最终派生类，也就是这里的 D，对于共同的基类 A，应该只保留一份实例，而不是通过 B 和 C 各继承一份。此处，应该让B和C变为虚继承：

class A {
public:
    int x;
};

class B : virtual public A {}; //虚继承
class C : virtual public A {};

class D : public B, public C {};

结合虚拟性的多态性意味着我们可以获得动态类型。当父类指针/引用指向子类对象，并且调用的是 virtual 函数时，程序不会只看“变量声明成什么类型”，而会在运行时看“它实际指向的对象是什么类型”，然后调用对应子类的函数。

§7 类模板 Template Classes

7.1 类模板

类模板（class template）是用于生成类的模板。通过类模板，我们可以用不同的数据类型实例化出结构相似、功能相近的不同类。STL 中的 std::vector 就是一个经典例子：std::vector 本身是一个类模板，通过 vector<int>、vector<string> 等形式，可以生成用于存储不同数据类型的动态数组类。

template <typename T>
class Vector {
public:
    T& at(size_t index);
    void push_back(const T& elem);
private:
    T* elems;
}

同时，非类型模板参数（non-typename template parameters）是被允许存在的。比如，有时我们会选择使用 std::array 而不是 std::vector ，为了避免堆内存分配。

template<typename T, std::size_t N>
struct std::array { /*...*/ };
std::array<std::string> arr;

类模板的几个注意事项：

1. 在头文件定义的类模板，在 .cpp 文件里需要再次声明 template 语句。如：

   若在头文件写

   template <typename T>
   class Vector {
   public:
       T& at(size_t i);
   }

   那么在 .cpp 文件中就要写

   template <typename T>
   T& Vector<T>::at(size_t i) {  //留意这一行的Vector<T>
       // Implementation...
   }

2. 对于非类型模板参数而言，cpp文件需要引用头文件；对于类型模板参数而言，头文件需要在结尾引用cpp文件。如，上例中头文件需要在末尾写上：

   #include "Vector.cpp"

3. 在模板参数列表中，typename 和 class 是等价的。（但更建议写前者，易于区分）

7.2 常量正确性 Const correctness

const 关键字让被修饰对象无法被修改。

从设计上讲，设计类的时候，给不会改变对象的函数或方法最好加上 const 。如：若cpp文件定义函数：

void printVec(const Vector<int>& v) {       //注意此处也有const
    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v.at(i) << " ";
    }
    std::cout << std::endl;
}

则头文件要声明：

template<class T>
class Vector {
public:
    size_t size() const;
    bool empty() const;
    T& operator[](size_t index);   //会改变对象的函数不能加const
    T& at(size_t index) const;  
    void push_back(const T& elem);
}

加上 const 关键字，是在告诉编译器，该函数或方法不会改变类内的对象。未加常量修饰的函数不能作用于加了常量修饰的对象。

此处会自然地产生一个问题：那么，加了 const 关键字的函数如果要对对象作出修改，怎么办呢？

以下有三种方法：

1. 使用 const 重载（overloading）

   定义两个该函数，一个修饰，一个不修饰，这样编译器会自己选择使用哪种。

   template <class T>
   class Vector {
   public:
       const T& at(size_t index) const;
       //上面这行代码的两个const的意义是：
       //第一个const修饰返回值，表示：返回的元素不能被改。
       //第二个const修饰成员函数，表示：这个函数不能修改当前对象，并且可以被const对象调用。
       T& at(size_t index);
   }

2. 使用 const_cast

   该函数可以临时强制将某个值转换成常量，可以绕过编译器。不过一般来说非常少使用这种方法，如果这种函数需要改变对象，那就一开始别加常量修饰。

   template <typename T>
   T& Vector<T>::findElement(const T& value) {
       for (size_t i = 0; i < logical_size; i++) {
           if (elems[i] == elem) return elems[i];
       }
       throw std::out_of_range("Element not found");
   }
   template <typename T>
   const T& Vector<T>::findElement(const T& value) const {
       return const_cast<Vector<T>&>(*this).findElement(value);
   }

3. 使用 mutable 关键字

   mutable 可以绕过 const 关键字。这种方法一般用于debug。

   struct MutableStruct {
       int dontTouchThis;
       mutable double iCanChange;
   }
   const MutableStruct cm;
   cm.iCanChange = 3.14;

§8 函数模板 Template Functions

8.1 函数模板

和类一样，函数也有模板可用。比如，求两个数据中更小的那个：

template <typename T>
T min(const T& a, const T& b) {
    return a > b ? b : a;
}

调用函数模板时，有两种调用方式，一种是显式调用：

min<std::string>("Kim Petras", "Robyn")

一种是隐式调用：

min(2778, 592778);

需要注意的是，隐式调用可能会造成问题。比如，如果上例的显式调用转为隐式调用，那么编译器会默认两者比较的类型为 const char* ，而常量字符指针是不可进行比较的。

同时，若隐式调用的参数默认类型不一致，则可以使用 auto 字符修饰，如：

template <typename T, typename U>
auto min(const T& a, const U& b) {
    return a > b ? b : a;
}
min(2778, 59.2778);

函数模板举例：STL容器中的 find() 函数

template <typename Iterator, typername TElem>
Iterator find(Iterator begin, Iterator end, TElem value) {
    Iterator it = begin;
    while (it != end) {
        if (*it == value) break;
        ++it;
    }
    return it;
}
find<std::vector<int>::iterator, int>(b, e, 42);

8.2 概念 Concepts

概念是C++ 20的新特性，可以用于约束模板，使得编译器报错简洁。

template <typename T>
concept Comparable = requires(const T a, const T b) {
    {a < b} -> std::convertible_to<bool>;
};

template <typename T> requires Comparable<T>
T min(const T& a, const T& b);
//another shorthand
template <Comparable T>
T min(const T& a, const T& b);

概念模板约束分为概念、要求和限制三个部分，其中限制可以加入C++内置的概念，常见的有：

概念	大概意思	例子
same_as<T, U>	T 和 U 是完全同一个类型	same_as<int, int> 成立；same_as<int, const int> 不成立
derived_from<T, U>	T 是从 U 继承来的	class Dog : public Animal，则 derived_from<Dog, Animal> 成立
convertible_to<T, U>	T 可以转换成 U	int 可以转 double，所以成立
common_reference_with<T, U>	T 和 U 有一个共同的“引用类型”	比如 int& 和 const int& 可以共同看成 const int&
common_with<T, U>	T 和 U 有一个共同类型	比如 int 和 double 的共同类型一般是 double
integral<T>	T 是整数类型	int、long long、char、bool 都算
signed_integral<T>	T 是有符号整数	int、long long 成立；unsigned int 不成立
unsigned_integral<T>	T 是无符号整数	unsigned int 成立；标准里 bool 也会满足，比较反直觉
floating_point<T>	T 是浮点数类型	float、double、long double
assignable_from<T, U>	U 可以赋值给 T	assignable_from<int&, int> 成立，因为 int x; x = 3; 合法
swappable<T>	两个 T 类型对象可以交换	int a, b; swap(a, b); 合法
swappable_with<T, U>	T 和 U 两种类型之间可以交换	两种不同但兼容的类型能互相 swap

迭代器也有内置的概念：

概念	大概意思	典型例子
input_iterator	可以读取元素，可以 ++ 往后走	输入流迭代器，比如从 cin 读东西
output_iterator	可以写入元素，可以 ++ 往后走	back_inserter(v)、输出流迭代器
forward_iterator	可以往前走，而且可以多次遍历	forward_list 的迭代器
bidirectional_iterator	可以 ++，也可以 --	list、set、map 的迭代器
random_access_iterator	可以像数组一样跳着访问	vector、deque 的迭代器
contiguous_iterator	元素在内存中连续排列	原生指针、array、vector 的迭代器

8.3 可变参数模板 Variadic Templates

可变参数模板是指可以生成不同数量参数的函数的模板，主要解决了函数重载导致的代码冗余性。

可变参数模板包含四部分：基础函数、可变参数模板、参数包、扩展包。

template <Comparable T>
T min(const T& v){return v;} //基础函数：使递归必须有个终点
template <Comparable T, Comparable... Args> //可变参数模板：Comparable...Args表示拓展的参数
T min(const T& v, const Args&... args) { //参数包：容纳0个或多个参数
    auto m = min(args...); //扩展包：将参数包用一个具体类型代替
    return v < m ? v : m;
}

可变参数区域内数据的类型不一定要和前面的类型一致。普通模板参数 T 通常代表一个具体类型，但 typename... Args 代表“一串类型”，这串类型可以是 int, string, bool, double... 混在一起。

template <typename T, typename... Args>
void format(const std::string& fmt, T value, Args... args) {
    auto pos = fmt.find("{}");
    std::cout << fmt.substr(0, pos);
    std::cout << value;
    format(fmt.substr(pos + 2), args...);
}

8.4 模板元编程 Template Metaprogramming (TMP)

模板元编程的含义是：让编译器在“编译时”帮你算东西、生成东西，而不是等程序运行时再算。

我们知道，模板是编译器在编译时用于生成代码的。那么，我们也许可以让编译器在编译时就做一些计算，这就是模板元编程的由来。

例：使用模板元编程算阶乘

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;

这个代码在编译时就会给你算好7的阶乘。编译期计算的结果会直接“烤进”可执行文件里。

模板元编程不只是算数字，还可以“对类型编程”。比如：Boost::MPL library 。

TMP的语法有时很丑。现代 C++ 用 constexpr / consteval 替代一部分传统模板元编程。前者的意思是：“编译器，如果可以的话，请你尽量在编译期运行我。”后者的意思是：“编译器，你必须在编译期运行我。”

比如，上述计算编程的例子可以写为：

constexpr size_t factorial(size_t n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

consteval size_t factorial(size_t n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

§9 Lambda函数

9.1 Lambda函数

当函数作为参数传入其他函数时，该参数是作为一个函数指针存在的。

Lambda函数：能够捕获封闭作用域状态的函数。

Lambda函数的格式是：

auto lambda = [capture-values](arguments) {
    return expressions;
}

其中 capture-values 常用表示有：

capture-values 写法	含义	简单理解
[x]	capture x by value	把外面的 x 复制一份进 lambda
[&x]	capture x by reference	lambda 里面用的是外面那个 x 本体
[x, y]	capture x and y by value	复制 x 和 y
[&]	capture everything by reference	用到的外部变量全部按引用捕获
[&, x]	capture everything by reference except x by value	默认都按引用，但 x 单独复制
[=]	capture everything by value	用到的外部变量全部复制一份

例：写一个函数 find_if 寻找容器中符合要求的第一个变量。

int n;
std::cin >> n;
auto lessThanN = [n](int x) {return x < n;}; //Lambda函数
find_if(begin, end, lessThanN);

Lambda 表达式非常适合即时创建函数。Lambda函数不一定非得写成一个函数的形式，其也可以写成一个参数。

bool wouldMakePrestonHappy(Trail t) {
    return t.hasWaterfall;
}
bool isOneToThreeMiles(Trail t) {
    return t.distance > 1 && t.distance < 3;
}
int main() {
    vector<Trail> allTrails = getTrails();
    
    vector<Trail> myTrails = filter(allTrails, [](Trail t) {
        return t.hasWaterfall && t.distance > 1 && t.distance < 3;
    }); //留意此处即可

    cout << "These are my trails:\n\n";
    for (const auto& t : myTrails) {
        if (t.hasWaterfall) cout << t << "\n";
    }
    return 0;
}

补充：std::function 是函数或Lambda表达式的通用类型，任何仿函数、Lambda表达式、函数指针都可以转换为它，但是速度稍慢。

std::function<bool(int, int)> less = std::less<int> {};
std::function<bool(char)> vowel = isVowel; 
std::function<int(int)> twice = [](int x) { return x * 2; };

9.2 STL中的算法库 <algorithm>

STL中内置许多可以直接使用的算法模板，通过这些算法你可以一行代码完成：二分查找、最小值/最大值比较、字典序比较、排序、选择性删除、选择性复制、集合变换、随机抽样等事情。

9.3 ranges 和 views

范围/ranges是一种含有起点和终点的事物。ranges 是“新版 STL 算法接口”，让你少写 begin/end.

std::vector<char> v = {'a', 'b', 'c', 'd', 'e'};
auto it = std::ranges::find(v, 'c');

auto first = v.begin() + 1;
auto last = v.end() - 1;
auto it = std::ranges::find(first, last, 'c');

ranges 还用了 concepts，所以报错更友好。

template<class T>
concept range = requires(T& t) {
    ranges::begin(t);
    ranges::end(t);
};

view 是一种 range，它不会立刻生成结果，而是“懒惰地”基于另一个 range 做变换。

views 写法：filter + transform

std::vector<char> letters = {'a', 'b', 'c', 'd', 'e'};

auto f = std::ranges::views::filter(letters, isVowel);
auto t = std::ranges::views::transform(f, toupper);

auto vowelUpper = std::ranges::to<std::vector<char>>(t);

代码解释：

代码	含义
views::filter(letters, isVowel)	从 letters 里筛出元音
views::transform(f, toupper)	把筛出来的字符转大写
ranges::to<vector<char>>(t)	真正生成一个 vector<char>

views 可以用 | 串起来。

std::vector<char> letters = {'a', 'b', 'c', 'd', 'e'};

std::vector<char> upperVowel = letters
    | std::ranges::views::filter(isVowel)
    | std::ranges::views::transform(toupper)
    | std::ranges::to<std::vector<char>>();

§10 运算符重载 Operator Overloading

就像我们在类中声明函数一样，我们也可以声明运算符的功能。当我们将该运算符与新对象一起使用时，它会执行自定义函数或操作。就像函数重载一样，如果我们给它赋予相同的名称，它将覆盖运算符的行为。

大部分的运算符都可以重载，但是作用域解析、三目运算符、成员访问、成员指针访问、sizeof 、 typeid 、cast 这些涉及C++语法结构本身的运算符不能重载。

通用语法是：

return_type operator<symbol>(parameter_list);

比如重载小于号 <：

bool operator<(const StanfordID& other) const;

运算符重载有两种方式，一种是成员重载，把运算符重载写成类的成员函数。

头文件里：

class StanfordID {
private:
    string name;
    string sunet;
    int idNumber;

public:
    StanfordID(string name, string sunet, int idNumber);

    bool operator<(const StanfordID& other) const;
};

cpp 文件里：

bool StanfordID::operator<(const StanfordID& other) const {
    return idNumber < other.idNumber;
}

另一种是把重载写成普通函数，称为非成员重载：

bool operator<(const StanfordID& lhs, const StanfordID& rhs) {
    return lhs.getIdNumber() < rhs.getIdNumber();
}

两种方式的区别是参数数量不同，因为成员重载的左参数默认为指向该类的 this 指针。

如果非成员重载时涉及 private 里的参数时，可以要么使用 getter ，要么把该重载设置为友元函数 friend ，但后者通常不太安全，因此一般用前者。

这两种方式不要同时使用。会导致重载解析歧义，可能导致编译错误。

例：输出流 << 的重载

ostream& operator<<(ostream& out, const StanfordID& sid) {
    out << sid.name << " " << sid.sunet << " " << sid.idNumber;
    return out;
}

§11 特殊成员函数 SMF

11.1 SMF概述

特殊成员函数（Special Member Functions, SMF）是C++ 类里一些“对象生命周期相关”的函数：对象怎么出生、怎么复制、怎么赋值、怎么销毁、怎么移动。

六类SMF：

T()                      //默认构造函数
~T()                     //析构函数
T(const T&)              //拷贝构造函数
T& operator=(const T&)   //拷贝赋值函数
T(T&&)                   //移动构造函数
T& operator=(T&&)        //移动赋值函数

比如说定义一个 Widget 类：

class Widget {
public:
    Widget();                             //默认构造函数
    Widget (const Widget& w);             //拷贝构造函数
    Widget& operator = (const Widget& w); //拷贝赋值函数
    ~Widget();                            //析构函数
    Widget (Widget&& rhs);                //移动构造函数
    Widget& operator = (Widget&& rhs);    //移动赋值函数
}

11.2 拷贝构造与拷贝赋值

构造函数初始化的一般写法是：

Vector<T>::Vector()
{
    _size = 0;
    _capacity = 4;
    _data = new T[_capacity];
}

这个写法的问题是：成员变量可能先被默认初始化，然后你又在函数体里赋值，相当于多走了一步。

成员初始化列表（更推荐）：直接在对象创建时把成员变量构造好，不需要多走一步。

Vector<T>::Vector()
    : _size(0),
      _capacity(4),
      _data(new T[_capacity])
{
}

特别是标注了 const 常量的成员变量必须用成员初始化列表进行初始化，因为不能再赋值。引用也必须一开始就绑定，不能之后再改绑。

编译器会自动生成默认版本。默认拷贝的方式叫 member-wise copy，也就是“成员变量一个个复制”。但如果类里有指针，就容易出事。如果你的变量是指针，逐个成员复制将指向同一份已分配的数据，而不是一份新的副本。（称为浅拷贝）在析构时，两个指针分别释放同一块内存，会导致程序崩溃。因此，常常需要自定义SMF。新对象自己 new 一块数组，把旧数组里的元素一个个复制过来。这种方式叫深拷贝。

拷贝构造函数写法举例：

template <typename T>
Vector<T>::Vector(const Vector<T>& other)
    : _size(other._size),
      _capacity(other._capacity),
      _data(new T[other._capacity])
{
    for (size_t i = 0; i < _size; ++i) {
        _data[i] = other._data[i];
    }
}

11.3 delete 用于禁用SMF

= delete 的作用：明确告诉编译器，这个函数不允许被调用。

比如，如果不想类内对象被复制，就可以：

class PasswordManager {
public:
    PasswordManager();
    ~PasswordManager();

    PasswordManager(const PasswordManager& rhs) = delete;
    PasswordManager& operator=(const PasswordManager& rhs) = delete;
};

这样，写 PasswordManager b = a; 编译器就会报错。

一些关于SMF的原则：

Rule of Zero : 如果默认 SMF 能正常工作，就不要自己写。尽量让类里的资源由 std::string、std::vector、std::unique_ptr 这些标准库类型管理，自己的类就不用手写析构和拷贝逻辑。

Rule of Three : 如果你需要自定义析构函数，那么你很可能也需要自定义拷贝构造函数和拷贝赋值运算符。原因是：你一旦需要手写析构，往往说明你在手动管理资源，比如 new 出来的堆内存。如果你只写析构，不写拷贝构造和拷贝赋值，就很容易出现浅拷贝、重复释放、悬空指针等问题。

§12 移动语义 Move Semantics

12.1 为什么要引入移动语义

当需要创建一个与已知对象一致的对象时，普通的拷贝构造函数因为复制需要额外的开销。当这个对象很大（比如高清图片）时，这个额外的开销会极其可观，因此考虑如果原对象不需要了，能不能从原对象那里直接“偷”过来。

具体来说，就是让新对象直接取原对象的地址，而原对象则变为空指针。让原对象变成空指针是为了防止原对象析构时把数据清除导致新对象变成野指针。这就是移动语义。

移动语义一般用于需要复制一个不需要再使用的对象时，或者函数返回值时。使用移动语义后，不要再对原对象作任何修改，因为经过移动的原对象状态是不确定的。

12.2 持久对象和临时对象

持久对象lvalue是有明确地址、能长期存在到作用域结束的东西，可以出现在等号运算符的两侧；临时对象rvalues是无明确地址、只能作用于一行代码的东西，只能出现在等号运算符的右侧。

持久对象和临时对象都可以引用，但是声明不同，编译器根据该声明可判断对象类型：

void upload(Photo& pic);   // 给持久对象用
void upload(Photo&& pic);  // 给临时对象用

12.3 移动语义的写法

移动构造函数的写法：

Photo::Photo(Photo&& other)
    : width(other.width),
      height(other.height),
      data(other.data) {
    other.data = nullptr;
    other.width = 0;
    other.height = 0;
}

移动赋值函数的写法：

Photo& Photo::operator=(Photo&& other) {
    if (this == &other) return *this;

    delete[] data;

    width = other.width;
    height = other.height;
    data = other.data;

    other.width = 0;
    other.height = 0;
    other.data = nullptr;

    return *this;
}

12.4 std::move 和SMFs

当持久对象需要转变成临时对象时，可以使用 std::move 进行转换。

Photo b = a;              // copy，a 是 lvalue
Photo b = takePhoto();    // move，takePhoto() 是 rvalue
Photo b = std::move(a);   // move，强行把 a 当 rvalue

std::move 本质上只是把 lvalue 转成 rvalue，它本身不做什么神秘操作；真正移动资源的是移动构造函数或移动赋值运算符。

同样，被move之后的对象不要轻易使用，因为状态不确定。被 move 后的对象应该仍然能析构、能重新赋值，但它内部内容不应该再被你假设为原来的内容。

Photo::Photo(Photo&& other) {
    keywords = std::move(other.keywords);
}

Rule of Five : 如果你已经定义了拷贝构造、拷贝赋值和析构函数，那么最好也定义移动构造和移动赋值；否则代码仍然能运行，但可能因为不能移动而做很多不必要拷贝。

§13 std::optional 和类型安全

13.1 类型安全 Type Safety

类型安全是一个语言、或者一个函数签名，在多大程度上能保证程序行为不会出错。类型系统越能提前表达你的意图，程序越安全。

有时，一个函数的签名和其实际的作用效果并不一致，比如下面这个函数：

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

当vec是一个空容器时，pop_back() 没有实际意义，因此程序报错。函数签名承诺一定返回值，但真实情况是：有时有值，有时没值。

13.2 std::optional 和monadic optional

std::optional<T> 是一个模板类，它表示：要么有一个 T 类型的值，要么什么都没有。

#include <optional>
std::optional<int> a = 5;
std::optional<int> b = std::nullopt; //注意和nullptr区分

常用接口：

接口	作用	有值时	没值时	示例
.has_value()	判断 optional 里面有没有值	返回 true	返回 false	a.has_value()
.value()	取出 optional 里面的值	返回里面的值	抛出 std::bad_optional_access 错误	a.value()
.value_or(default_value)	取值；如果没值就用默认值	返回里面的值	返回你给的默认值	b.value_or(999)
直接当 bool 用	判断有没有值，常用于 if / while	表现为 true	表现为 false	if (a) { ... }

#include <optional>
#include <iostream>

int main() {
    std::optional<int> a = 5;
    std::optional<int> b = std::nullopt;

    std::cout << a.has_value() << "\n"; // true
    std::cout << b.has_value() << "\n"; // false

    std::cout << a.value() << "\n";     // 5
    // std::cout << b.value() << "\n";  // 抛出 bad_optional_access

    std::cout << a.value_or(999) << "\n"; // 5
    std::cout << b.value_or(999) << "\n"; // 999

    if (a) {
        std::cout << a.value() << "\n"; // 5
    }
}

上例的vec函数可以像这样使用 std::optional 改写：

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

调用时必须判断：

auto last = vec.back();

if (last.has_value()) {
    cout << last.value();
}

但实际上真正的STL库并没有大量使用optional，原因有：

• 写起来比较啰嗦，到处都要 .value()、.has_value()。

• 有性能成本，C++ 标准库很在意性能。

• C++ 的设计哲学是：不牺牲性能，给程序员控制权。

• 有些情况我们想要 std::optional<T&>，但 C++ 不支持直接存引用的 optional。

monadic 是一种设计模式：把多个程序片段，也就是函数，组合起来，并且把返回值包在一种带有额外计算语义的类型里。对 std::optional 来说，这个“额外语义”就是：这个值可能存在，也可能不存在。之前提到的 views 链式管道也是这种设计模式。

monadic optional就是：把 std::optional 当成一个“可能中断的计算管道”。如果里面有值，就继续执行下一个函数；如果没值，就自动跳过后面的计算，继续保持 nullopt，或者走备用逻辑。

monadic optional的常见接口有：

接口	作用	如果 optional 有值	如果 optional 没值	传入函数 f 应该返回什么	整体返回什么
.and_then(f)	继续执行一个可能失败的操作	调用 f(value)	跳过，返回 nullopt	std::optional<U>	std::optional<U>
.transform(f)	对里面的值做一次普通变换	调用 f(value)，并把结果重新包进 optional	跳过，返回 nullopt	普通值 U	std::optional<U>
.or_else(f)	给空 optional 提供备用方案	保持原来的值	调用 f() 获取备用 optional	std::optional<T>	std::optional<T>

这种设计模式在Rust、Swift、JavaScript等语言中很常见，但是在C++中不多见。

§14 RAII、智能指针、如何建立C++项目

14.1 RAII：资源获取即初始化

RAII (Resource Acquisition is Initialization) 的思想是：类用到的资源应该在构造函数里获取，在析构函数里释放。这样对象一创建就处于可用状态，对象离开作用域时资源自动释放。

在C++中，除了指针，需要手动获取、释放的资源有：

资源	获取	释放
堆内存	new	delete
文件	open	close
锁	try_lock / lock	unlock
socket	socket	close

有时，如果中间抛异常，手写的释放语句可能根本执行不到。C++ 代码里隐藏着很多可能抛异常的路径，所以手动管理资源很容易漏掉。

比如以下这份代码，看起来有 delete p，但如果中间任何地方抛异常，比如 firstName()、lastName()、字符串拼接、输出操作，程序会直接跳出当前函数，delete p 就执行不到，于是内存泄漏。

Pet* p = new Pet(petId);

if (p->type() == "Dog" || p->firstName() == "Fluffy") {
    std::cout << p->firstName() << " "
              << p->lastName() << " is paw-some!\n";
}

std::string returnStr = p->firstName() + " " + p->lastName();

delete p;
return returnStr;

RAII 的修法是：不要让普通代码负责释放资源，让对象的析构函数负责。

比如，对lock而言：lock_guard 就是一个 RAII wrapper：构造时加锁，析构时解锁。

void cleanDatabase(std::mutex& databaseLock, std::map<int, int>& db) {
    std::lock_guard<std::mutex> lg(databaseLock);

    // 临界区：修改数据库
    // 就算这里抛异常，lg 离开作用域时也会自动 unlock
}

14.2 智能指针 Smart Pointer

智能指针就是“包住裸指针的对象”，构造时接管动态内存，析构时自动释放。

RAII原则告诉我们，写程序时尽量不要显式使用 new 和 delete ，而应该使用智能指针。因为前者在程序运行到中途出现异常时不会自动释放内存，继而导致内存泄漏；而后者在检测到异常时会自动析构内存。

auto n = std::make_unique<Node>();
// do something
// n 离开作用域时自动 delete

三种智能指针：

智能指针	所有权模型	能不能复制	什么时候释放资源	典型用途
std::unique_ptr<T>	独占所有权	不能复制，可以移动	这个 unique_ptr 析构时释放	一个对象只有一个明确主人
std::shared_ptr<T>	共享所有权	可以复制	最后一个 shared_ptr 析构时释放	多个对象共同拥有同一资源
std::weak_ptr<T>	弱引用，不拥有资源	可以复制	不负责释放	配合 shared_ptr，解决循环引用

一般默认优先使用 std::unique_ptr<T> 。这种智能指针不能复制，原因是如果允许复制，就会出现两个指针都以为自己拥有同一块内存。第一个析构时把内存删了，第二个就指向已经被释放的内存，可能造成悬空指针或二次释放。

shared_ptr 解决了复制 unique_ptr 的问题：它不会在第一个指针析构时就释放底层内存，而是等所有共享指针都离开作用域。但shared_ptr 有一个经典坑：循环引用。如：

struct A {
    std::shared_ptr<B> b;
};

struct B {
    std::shared_ptr<A> a;
};

如果 A 指向 B，B 又指回 A，它们的引用计数可能永远不会变成 0，于是内存泄漏。

修法是让其中一边不拥有对方，使用弱指针：

struct A {
    std::shared_ptr<B> b;
};

struct B {
    std::weak_ptr<A> a;
};

14.3 构建C++项目

如何编译多文件的C++项目？

第一种方法：命令行，用于小项目的编译

g++ -std=c++20 main.cpp pet.cpp utils.cpp -o main

第二种方法：Makefile

make 是一个 build system 程序，可以帮你编译，不用手动编译项目里的每个文件；它还能指定编译器，并追踪哪些文件自上次编译后发生了变化。

# Compiler
CXX = g++

# Compiler flags
CXXFLAGS = -std=c++20

# Source files and target
SRCS = $(wildcard *.cpp)
TARGET = main

# Default target
all:
	$(CXX) $(CXXFLAGS) $(SRCS) -o $(TARGET)

# Clean up
clean:
	rm -f $(TARGET)

含义是：

语句	含义
CXX = g++	使用 g++ 编译器
CXXFLAGS = -std=c++20	使用 C++20 标准
SRCS = $(wildcard *.cpp)	找到当前目录所有 .cpp 文件
TARGET = main	生成的可执行文件叫 main
all:	默认构建目标
clean:	删除编译产物

然后只需运行 make 就可以进行编译生成可执行文件。

第三种方法：CMake

CMake 是 build system generator，也就是“构建系统生成器”。它帮你生成 Makefile。可以理解为：CMake 是 Makefile 的更高层抽象。

cmake_minimum_required(VERSION 3.10)
project(cs106l_classes)

set(CMAKE_CXX_STANDARD 20)

file(GLOB SRC_FILES "*.cpp")

add_executable(main ${SRC_FILES})

含义是：

CMake 语句	含义
cmake_minimum_required(VERSION 3.10)	要求 CMake 版本至少为 3.10
project(cs106l_classes)	项目名叫 cs106l_classes
set(CMAKE_CXX_STANDARD 20)	使用 C++20 标准
file(GLOB SRC_FILES "*.cpp")	找到所有 .cpp 文件
add_executable(main ${SRC_FILES})	把这些源文件编译成名为 main 的可执行文件

CMake的使用流程：

mkdir build  //新建一个 build 文件夹，专门放编译中间文件
cd build     //进入 build 文件夹
cmake ..     //读取上一级目录里的 CMakeLists.txt，生成 Makefile
make         //根据 Makefile 编译项目
./main       //运行生成的程序

推荐的项目结构：

my_project/
├── CMakeLists.txt 告诉 CMake 怎么构建项目
├── main.cpp
├── pet.cpp        类成员函数实现
├── pet.h          类声明、函数声明
└── build/         存放编译生成的文件，不要把源码放这里

如果用 Visual Studio 生成器，最后也可以用：

cmake --build .

END