第01章 C++ 编程基础：类、引用与模板

这一篇在干嘛？

第 1 章不直接讲数据结构，而是把后面 11 章要用到的 C++ 语言能力一次配齐：类如何封装数据、指针与引用怎么选、Big-Five 什么时候必须手写、模板怎么让一份代码服务所有类型。这些是读懂后续每一份结构实现的门票。

1.1 这本书在讲什么

数据结构 = 组织数据的方式 + 在其上操作的算法。同一个问题（比如”查找”），用无序表是 $O (N)$ ，用平衡二叉搜索树是 $O (lo g N)$ ，用哈希表平均 $O (1)$ ——数据结构的选择直接决定程序的上限。本书的任务就是把这些结构一个个拆开：内部怎么实现、各种操作代价多少、什么场景该用谁。

书中还有一个贯穿的主题：递归。一个函数通过调用自己来求解问题，它的正确性靠数学归纳法保证，它的效率靠”每次把问题缩小”来保证。

1.2 数学复习：三个必用工具

指数与对数。 $l o g$ 不写底时默认以 2 为底（算法书惯例）。必背的性质：

$l o g_{A} B = \frac{l o g _{C} B}{l o g _{C} A}$

白话：对数的底只是”换算系数”，不同底的对数只差常数倍——所以大 O 记号里根本不写底， $O (lo g N)$ 就是 $O (lo g_{2} N)$ 。

对数和指数互为反函数： $l o g_{B} B^{X} = X$ ；且 $l o g 1 = 0$ 、 $l o g 2 = 1$ 、 $l o g 1024 = 10$ 。后面分析”每次把规模折半”的算法（二分查找、堆操作）时， $lo g N$ 会反复出现：100 万的数据折半 20 次就到 1，这就是对数级算法快的直觉来源。

级数。最常用的三条：

$\sum_{i = 0}^{N} i = \frac{N ( N + 1 )}{2} \approx \frac{N ^{2}}{2}, \sum_{i = 0}^{N} 2^{i} = 2^{N + 1} - 1, \sum_{i = 1}^{N} \frac{1}{i} \approx lo g_{e} N$

白话：第一条是”从 1 加到 N”，二次级数，双层循环的代价就是它；第二条是几何级数，翻倍增长；第三条叫调和级数，增长慢得像对数——它解释了为什么某些”看似三层”的循环其实只有 $O (lo g N)$ 量级。

模运算： $A \equiv B (mod M)$ 表示 $A$ 除以 $M$ 的余数等于 $B$ 除以 $M$ 的余数。哈希表的”把大数映射到表内下标”（hash % tableSize）就是它的直接应用。

证明方法：归纳法（基例 + 归纳步骤，证明递归正确性的标准姿势）、反例法（推翻一个”显然成立”的猜想只需一个反例）、反证法（假设结论不成立，推出矛盾）。第 2 章分析最大子序列和算法时，归纳法会实际登场。

1.3 递归四铁律

递归就是”函数调用自己”，但裸地写必然死循环。书里给出四条铁律，违反任何一条都会出 bug：

基准情形（base case）：必须有不用递归就能解决的 smallest case。比如打印整数的例子，n < 10 时直接输出一位数字。
不断推进（making progress）：每次递归调用必须朝基准情形推进。打印整数时先递归打印”去掉最后一位”的数（printOut(n/10)），规模在缩小。
设计法则：假设所有递归调用都能正确工作——你不需要展开追踪每一层，只相信它对，然后验证”这一层的处理 + 子问题的答案”拼起来是对的。这和归纳法完全同构。
合成效益法则：求解时不要重复做同一个子问题的递归（否则退化，比如朴素的斐波那契递归是指数级的）。

void printOut(int n) {          // 递归打印非负整数（去掉前导 0）
    if (n >= 10)
        printOut(n / 10);       // 先打印高位部分（问题缩小：少一位）
    printDigit(n % 10);         // 再打印最后一位（基准情形的自然归宿）
}

白话：printOut(76234) 的调用链是 76234 → 7623 → 762 → 76 → 7。到了 7 不再递归直接输出，然后一层层返回时依次打印 6、2、3、4——递归”先深入后做事”的结构天然把数字反了过来，这是栈（第 3 章）特性的免费演示。

1.4 C++ 类：把数据和操作捆在一起

基本语法：类 = 数据成员 + 成员函数。构造函数负责初始化，比如一个 IntCell（存一个 int 的单元格）：

class IntCell {
  public:
    explicit IntCell(int initialValue = 0)
      : storedValue{ initialValue } { }        // 初始化列表：直接用初值构造成员
    int read() const                            // const 成员函数：不修改对象
      { return storedValue; }
    void write(int x)
      { storedValue = x; }
  private:
    int storedValue;
};

三个关键语法点，后面的代码里到处都是：

初始化列表（: storedValue{initialValue}）：成员在构造时”直接以初值构造”，而不是”先默认构造再赋值”。对类类型成员效率更高，对 const 成员和引用成员则是唯一手段。
explicit：禁止”单参数构造函数被隐式调用”——没有它，IntCell cell = 3; 这种把 3 悄悄变成 IntCell 的代码也能编译，几乎从来不是你想要的。
const 成员函数：在参数表后加 const，向编译器承诺”我不改这个对象”。只读访问器都应该是 const 的，这是 C++ 的接口契约。

接口与实现分离：类的声明放 .h 头文件，成员函数体放 .cpp，用作用域运算符 IntCell::read 标明归属。头文件用预处理器命令 #ifndef/#define/#endif 包起来，防止被重复包含。

vector 和 string：C++ 程序员不该手写裸数组。vector 是可自动扩容的数组（第 3 章会亲手实现一遍），string 是封装好的字符串，两者都管理自己的内存，不需要手动 delete。

1.5 指针、引用与内存管理

指针存放另一个对象的地址：

IntCell *p = new IntCell{42};   // 堆上构造对象，p 指向它
cout << p->read();              // 通过 -> 访问成员（等价于 (*p).read()）
delete p;                       // 用完归还内存，否则泄漏

白话：new 在堆（heap）上申请一块内存并构造对象；局部变量则住在栈上，函数返回自动销毁。堆上的对象没有”自动死亡”机制，必须 delete。忘删 → 内存泄漏；删了又用 → 悬空指针。这两个 bug 是后续实现链表、树时的头号杀手，所以书中大量使用”智能管理”的写法来规避。

左值与右值：左值有名字、有持久地址（能写在赋值号左边）；右值是临时的、即将消亡的（比如 x+1 的结果、函数返回的临时对象）。

引用是对象的别名，必须初始化且不能改绑。三大用途：

// 用途1：range-for 里避免拷贝每个元素
for (auto &x : v) ++x;
// 用途2：参数传递避免拷贝大对象
void print(const vector<int> &arr);   // 只读，加 const
void swap(int &a, int &b);            // 可写，别名直接改实参

白话：按值传参 = 把整个对象复印一份给函数；按引用传参 = 只传”原件的地址”。大对象（比如一个 10 万元素的 vector）按值传递的拷贝开销可能远超函数本身的工作，所以 C++ 的默认习惯是：大对象一律按引用传，只读就加 const。

std::move：把左值”标记成”右值，触发移动语义——不是复印 100 万元素，而是把对方的内部指针”偷”过来（三个指针赋值 vs 百万次拷贝）。这就是移动语义的价值。

1.6 Big-Five：一个类管好自己的生死拷移

类里有指针成员时，编译器默认生成的”逐成员拷贝”只会拷指针本身（浅拷贝），两个对象指向同一块内存，析构时双倍 delete——直接崩溃。所以要显式写全五件套：

成员	签名示例	干什么
析构函数	`~Vector()`	对象死亡时释放资源
拷贝构造	`Vector(const Vector &rhs)`	用已有对象初始化新对象（深拷贝）
移动构造	`Vector(Vector &&rhs)`	从将亡对象”接管”资源（廉价）
拷贝赋值	`Vector &operator=(const Vector &rhs)`	已有对象 = 另一个对象
移动赋值	`Vector &operator=(Vector &&rhs)`	已有对象接管将亡对象

class Vector {
  public:
    Vector(int initSize = 0) : theSize{initSize}, theCapacity{initSize + SPARE_CAPACITY}
        { objects = new Object[theCapacity]; }
    ~Vector() { delete[] objects; }
 
    Vector(const Vector &rhs)                       // 拷贝构造：逐元素复印
      : theSize{rhs.theSize}, theCapacity{rhs.theCapacity}, objects{nullptr}
    {
        objects = new Object[theCapacity];
        for (int k = 0; k < theSize; ++k)
            objects[k] = rhs.objects[k];
    }
 
    Vector(Vector &&rhs)                            // 移动构造：只偷三个字段
      : theSize{rhs.theSize}, theCapacity{rhs.theCapacity}, objects{rhs.objects}
    {
        rhs.objects = nullptr;                      // 让对方"空手"析构也不出错
        rhs.theSize = 0; rhs.theCapacity = 0;
    }
    // ... 赋值运算符常用 copy-and-swap 惯用法实现
  private:
    int theSize;
    int theCapacity;
    Object *objects;
};

白话：拷贝 = 复印一本书（贵）；移动 = 直接把书架搬走（三个指针赋值，便宜）。移动后必须把源对象置空，否则两个析构函数会删同一块内存。经验法则：类里只有普通成员（int、vector、string），默认生成的 Big-Five 就够用；一旦自己管理裸指针，五件套一个都不能少——或者干脆用 vector 代替裸指针，让 Big-Five 回归默认。

书里还有一条重要设计规则：只要存在需要析构函数的类，几乎必然也需要全部 Big-Five（有析构 → 说明在管资源 → 默认拷贝必错）。

1.7 模板：一份代码服务所有类型

数据结构不该和”存的到底是什么类型”绑死。函数模板把类型变成参数：

template <typename Comparable>
const Comparable &findMax(const vector<Comparable> &a) {
    int maxIndex = 0;
    for (int i = 1; i < a.size(); ++i)
        if (a[maxIndex] < a[i])
            maxIndex = i;
    return a[maxIndex];
}

白话：findMax 对 vector<int>、vector<double>、vector<string> 都能用——编译器按调用处的实际类型”盖章复制”一份对应代码。代价只有一个要求：类型必须支持 < 运算。

类模板同理，vector<int>、vector<string> 里的尖括号就是它。这带来一个工程问题：模板的代码通常必须整个放在头文件里（编译器实例化时要看得见实现），这正是本书代码的组织方式，也是附录 A 专门讨论分离编译的原因。

函数对象（function object）：当”比较方式”不止一种（比如按工资、按姓名排序同一个 Employee 数组），把比较逻辑做成带 operator() 的对象传进去：

class LessThan {
  public:
    bool operator()(const Employee &a, const Employee &b) const
      { return a.salary() < b.salary(); }
};
// 调用：findMax(v, LessThan{});  ——"LessThan{}" 就是个临时函数对象

白话：函数对象 = “能像函数一样调用的对象”。它比传函数指针更好内联、还能携带状态，是 STL 的 sort、优先队列自定义比较（第 6 章）的标准姿势。

1.8 矩阵：vector 的嵌套

C++ 没有内建二维数组的好用形态，书中用 vector<vector<Object>> 实现矩阵，核心是重载 operator[] 返回行的引用，让 m[i][j] 语法自然工作。resize 时先决定行数，再逐行设置列数。这个 Matrix 类在第 10 章动态规划（Floyd、背包）里会反复用到。

常见坑

浅拷贝陷阱：自己写类存了裸指针，却不写拷贝构造/赋值 → 两个对象共享同一块内存 → 双重 delete 崩溃，或者一个改了另一个”莫名”跟着变。看到”裸 new 必配 Big-Five”，或者干脆改用 vector/智能指针。另一个高频坑：按值传大对象导致性能暴跌——函数签名里该写 const T& 的地方写成了 T。

通关标准

学完本篇你应该能做到：① 手写一个带初始化列表和 const 成员函数的小类；② 说清什么时候必须手写 Big-Five、每件分别在哪触发；③ 解释 T、T&、const T&、T&& 四种传参/返回的差异并正确选择；④ 写一个函数模板和函数对象，并解释模板为什么影响头文件组织。

初始化列表和"构造函数体内赋值"有什么区别？什么时候必须用初始化列表？

初始化列表是”直接以给定值构造成员”，函数体内赋值是”先默认构造再赋值”，多一轮开销；对 const 成员、引用成员以及没有默认构造函数的类类型成员，初始化列表是唯一选择。

移动构造为什么必须把源对象的指针置为 nullptr？

否则源对象析构时会对同一块内存 delete[]，造成双重释放。置空后源对象变成”空壳”，析构空壳无害。

explicit 关键字阻止了什么？

阻止单参数构造函数参与隐式转换，例如 IntCell cell = 3;（把 3 隐式构造成 IntCell）。加上 explicit 后必须显式写 IntCell cell(3);，避免”意外的类型转换”。

递归的设计法则为什么成立？它和归纳法是什么关系？

设计法则说”假设递归调用正确，只需保证本层逻辑正确”。这正是归纳法：基准情形 = 归纳基础，本层逻辑正确 = 归纳步骤；两者合起来对任意规模成立，无需追踪展开每一层。

为什么书中数据结构多用模板而不是直接写 int 版本？

模板让数据结构与元素类型解耦：一份 vector<T> 实现服务所有类型，避免复制粘贴出 N 份几乎相同的代码；类型不匹配在编译期就报错，比 void* 方案安全。

description	补齐读这本书所需的全部 C++ 语言地基：类、指针引用、Big-Five、模板与矩阵，逐个讲清为什么需要它们。
tags	数据结构精讲

嵌入式开发之路

探索

第01章 C++ 编程基础：类、引用与模板

1.1 这本书在讲什么

1.2 数学复习：三个必用工具

1.3 递归四铁律

1.4 C++ 类：把数据和操作捆在一起

1.5 指针、引用与内存管理

1.6 Big-Five：一个类管好自己的生死拷移

1.7 模板：一份代码服务所有类型

1.8 矩阵：vector 的嵌套

关系图谱

目录

反向链接