模板为什么通常写在头文件里#

这节课的模板代码放在了 xchen_algorithm.h，这是很常见的写法。

1
template<typename T>
2
void selection_sort(T arr[], int n) { ... }

原因很直接：

• 模板不是普通函数，它通常要在使用点看到完整定义
• 编译器看到 selection_sort(arr, n) 时，才会按 T=int、T=Student 等去实例化
• 如果只有声明没有定义，很多情况下链接阶段会找不到对应版本

所以这类小型模板算法，直接写在头文件里最省事。

TIP

为什么每个函数都要写 template<typename T>？

因为这四个函数是 四个独立的函数模板，不是一个模板包着四个函数。

所以 T 的作用域只在“紧随其后的那一个函数”里有效：

• 写在 min_element 前面，T 只能用于 min_element
• 写在 swap 前面，T 只能用于 swap
• 写在 selectionSort 前面，T 只能用于 selectionSort
• 写在 print_array 前面，T 只能用于 print_array

这不是“每种类型要手写一遍”，而是“每个模板函数都要声明自己的模板参数”。

如果只写一个模板头的写法

可以把多个操作放进同一个类模板里，让所有成员共享同一个 T：

1
template<typename T>
2
struct SelectionSortToolkit {
3
    static int min_element(T arr[], int begin, int end) { ... }
4
    static void swap(T& a, T& b) { ... }
5
    static void selectionSort(T arr[], int n) { ... }
6
    static void print_array(T arr[], int n) { ... }
7
};

区别：

• 函数模板版调用更自然：selectionSort(arr, n)
• 类模板版模板头只写一次，但调用更长：SelectionSortToolkit<int>::selectionSort(arr, n)

T&：可修改的引用#

1
void swap(T& a, T& b)

这里 a 和 b 直接绑定到外面的两个变量。

所以在函数里交换 a、b，外面的值也真的会被交换。

如果写成：

1
void swap(T a, T b)

那只是交换了两个副本，函数结束后外面不会变。

const T&：只读引用#

1
bool operator<(const Student& s1, const Student& s2)

这里有两层意思：

• &：不拷贝对象，直接引用原对象
• const：我承诺只读，不修改它

所以 const T& 很常见，因为它同时做到：

• 避免拷贝
• 不修改实参

std::ostream&：把同一个输出流继续传下去#

1
std::ostream& operator<<(std::ostream& out, const Student& s)

这里有三处值得看：

• std::ostream& out：out 是输出流对象的引用，不复制 std::cout
• const Student& s：s 是学生对象的只读引用
• 返回 std::ostream&：把同一个输出流返回去，支持链式输出

所以这句才成立：

1
std::cout << a << b << c;

前一次 << 的结果，还是那个 std::cout。

如何快速判断 &#

• T&：要改原对象
• const T&：不想拷贝，也不想改原对象
• std::ostream&：要把同一个输出流继续往后传

< 的两种常见写法#

成员函数写法：

1
struct Student {
2
    int id;
3
    std::string name;
4

5
    bool operator<(const Student& other) const {
6
        return id < other.id;
7
    }
8
};

非成员写法：

1
bool operator<(const Student& s1, const Student& s2) {
2
    return s1.id < s2.id;
3
    // return s1.name < s2.name;
4
}

<< 的意义#

1
std::ostream& operator<<(std::ostream& out, const Student& s) {
2
    return out << "(" << s.id << "," << s.name << ")";
3
}

• 返回 std::ostream&，支持链式输出
• 参数用 const Student&，避免拷贝且不修改对象
• 这样 print_array 才能直接打印 Student

这里的 & 可以顺手这样看：

• std::ostream& out：out 是输出流本身的别名
• const Student& s：s 是学生对象的只读别名
• 返回 std::ostream&：把同一个输出流继续传回去

带比较器的模板形态#

1
template<typename T, typename Compare>
2
int min_element(T arr[], int begin, int end, Compare comp) {
3
    int min_idx = begin;
4
    for (int i = begin + 1; i < end; ++i) {
5
        if (comp(arr[i], arr[min_idx])) {
6
            min_idx = i;
7
        }
8
    }
9
    return min_idx;
10
}
11

12
template<typename T, typename Compare>
13
void selection_sort(T arr[], int n, Compare comp) {
14
    for (int i = 0; i < n - 1; ++i) {
15
        int min_idx = min_element(arr, i, n, comp);
16
        if (min_idx != i) {
17
            swap(arr[min_idx], arr[i]);
18
        }
19
    }
20
}

用在 Student 上

1
xchen::selection_sort(arr, n); // 默认按 operator<，即按 id
2

3
xchen::selection_sort(
4
    arr,
5
    n,
6
    [](const Student& s1, const Student& s2) {
7
        return s1.name < s2.name;
8
    }
9
); // 按 name

• operator< 适合定义“默认顺序”
• 比较器参数适合定义“可切换顺序”

比较器函数 vs lambda#

先回到模板本体：

1
template<typename T, typename Compare>
2
int min_element(T arr[], int begin, int end, Compare comp) {
3
    int min_idx = begin;
4
    for (int i = begin + 1; i < end; ++i) {
5
        if (comp(arr[i], arr[min_idx])) {
6
            min_idx = i;
7
        }
8
    }
9
    return min_idx;
10
}

这里最关键的是这一句：

1
if (comp(arr[i], arr[min_idx]))

也就是说，模板并不关心“到底按面积比，还是按周长比”。

它只要求你传进来一个 comp，并且这个 comp 能回答这样一个问题：

• “arr[i] 应不应该排在 arr[min_idx] 前面？”

如果返回 true，就更新最小值位置；如果返回 false，就不更新。

代码里两种传法都用了。

第一种：传命名函数

1
bool less_shape_area(Shape* s1, Shape* s2)
2
{
3
    return s1->get_area() < s2->get_area();
4
}
5

6
xchen::selection_sort(arr, n, less_shape_area);

可以把它拆开理解成：

1
less_shape_area(arr[i], arr[min_idx])

而 less_shape_area 的意思是：

• 如果 arr[i] 的面积更小，就返回 true
• 所以排序结果会变成“按面积升序”

这个写法的优点是名字很明确：

• less_shape_area：按面积小的在前
• less_shape_perimeter：按周长小的在前
• greater_shape_area：按面积大的在前

只看函数名，基本就知道排序规则。

第二种：传 lambda

1
xchen::selection_sort(
2
    arr,
3
    n,
4
    [](Shape* s1, Shape* s2) {
5
        return s1->get_perimeter() > s2->get_perimeter();
6
    }
7
);

这个 lambda 没有名字，但作用和上面的函数完全一样。

它等价于“临时写一个比较器，然后立刻传进去”。

这里的逻辑是：

• 如果 s1 的周长比 s2 大，就返回 true
• 所以“更大”的元素会被当成“更靠前”
• 最终结果就是“按周长降序”

可以把它脑补成这种临时函数：

1
bool temp(Shape* s1, Shape* s2)
2
{
3
    return s1->get_perimeter() > s2->get_perimeter();
4
}

只是 lambda 不需要真的单独定义 temp 这个名字。

两者到底有什么关系

对模板来说，这两种写法没有本质区别：

• 命名函数：less_shape_area
• lambda：[](Shape* s1, Shape* s2) { ... }

它们都会被当成 comp，然后在模板内部这样使用：

1
comp(arr[i], arr[min_idx])

所以真正要抓住的不是“语法长得不一样”，而是：

• 你传进去的东西，必须能接收两个元素
• 它必须返回 bool
• 它定义了“谁应该排在前面”

什么时候用函数，什么时候用 lambda

如果规则会重复使用，适合写成命名函数：

• 代码更整齐
• 名字本身就是注释
• 多次排序时可以复用

如果规则只用一次，适合直接写 lambda：

• 不用额外起名字
• 逻辑离调用点更近
• 读代码时能立刻看到排序条件

头文件与 #pragma once#

xchen_algorithm.h 开头是：

1
#pragma once

作用：

• 防止头文件被重复包含
• 避免重复定义错误
• 对这种模板头文件尤其常见

它可以理解成“这个头文件本次编译只展开一次”。

命名空间#

• 避免与标准库或其他代码同名冲突
• 调用时语义清晰：xchen::selection_sort(...)

模板重载（按是否传比较器）#

• selection_sort(arr, n)：走默认 <
• selection_sort(arr, n, comp)：走自定义规则

print_array 的模板重载#

除了普通数组：

1
template<typename T>
2
void print_array(T arr[], int n)

还有指针数组版本：

1
template<typename T>
2
void print_array(T* arr[], int n) {
3
    for (int i = 0; i < n; ++i)
4
        std::cout << *arr[i] << ' ';
5
    std::cout << '\n';
6
}

这就是为什么 Shape* arr[] 也能直接被打印。

对照理解：

• Student arr[] 是“对象数组”，元素本身就是对象
• Shape* arr[] 是“指针数组”，元素是指向对象的指针
• 打印对象数组时直接 cout << arr[i]
• 打印指针数组时要先解引用：cout << *arr[i]

静态数组长度的写法#

main.cpp 里多次出现：

1
int n = sizeof(arr) / sizeof(arr[0]);

这只适用于当前作用域里的静态数组。

• sizeof(arr)：整个数组占多少字节
• sizeof(arr[0])：一个元素占多少字节
• 两者相除得到元素个数

但如果数组传进普通函数，参数会退化成指针，这招就不能用了。

Shape 这层到底想解决什么问题#

代码里有：

• Rectangle
• Circle
• Triangle

它们的面积公式不同、周长公式不同，但它们又都属于“图形”。

所以作者先抽出一个共同的上层：

• 图形都应该能算面积
• 图形都应该能算周长
• 图形都应该能告诉别人自己叫什么

这就是 Shape 的作用：先定义共同接口，再让不同图形各自实现。

这样后面就可以统一写成：

1
Shape* arr[] = {
2
    new Rectangle(2,3),
3
    new Circle(3),
4
    new Triangle(2,5,4)
5
};

虽然数组里装的是不同类型的对象，但在这一层都被统一看成 Shape，因此可以用同一套代码处理。

抽象基类（接口层）#

1
class Shape {
2
protected:
3
    double area, perimeter;
4

5
public:
6
    virtual ~Shape() {}
7
    virtual void calc_area() = 0;
8
    virtual void calc_perimeter() = 0;
9
    virtual std::string name() const = 0;
10

11
    double get_area() const { return area; }
12
    double get_perimeter() const { return perimeter; }
13

14
    friend std::ostream& operator<<(std::ostream&, const Shape&);
15
};

这段代码可以逐行拆开看：

• class Shape：定义“图形”这个基类
• area, perimeter：面积和周长是所有图形共有的数据
• calc_area()：要求所有图形都会算面积
• calc_perimeter()：要求所有图形都会算周长
• name()：要求所有图形都能返回名字
• get_area() / get_perimeter()：对外提供读取接口
• friend operator<<：允许直接打印图形对象

这里要特别注意：Shape 不是某一个具体图形，它更像图形这一类对象的公共接口。

virtual 在做什么#

这一组函数前面都有 virtual：

1
virtual ~Shape() {}
2
virtual void calc_area() = 0;
3
virtual void calc_perimeter() = 0;
4
virtual std::string name() const = 0;

virtual 的核心作用是：

• 当你通过“基类指针/基类引用”访问对象时
• 程序会根据“对象真实类型”决定调用哪个版本

例如：

1
Shape* p = new Rectangle(2, 3);
2
p->calc_area();

虽然 p 写成了 Shape*，但它实际指向的是 Rectangle 对象，所以这里应该执行的是 Rectangle::calc_area()。

这就是多态：接口统一，但实际执行的函数版本由对象真实类型决定。

如果没有 virtual，程序就很难在“统一接口”下正确区分矩形、圆形和三角形各自的实现。

=0 是什么意思？

1
virtual void calc_area() = 0;

这里的 =0 表示纯虚函数。

它的意思不是“把函数值设为 0”，而是：

• 基类这里只提要求
• 不给出具体实现
• 必须由子类来实现

所以 Shape 变成了抽象类：

• 你不能写 Shape s;
• 你只能把它当成一个统一接口

也就是说，Shape 的角色不是直接拿来创建对象，而是规定所有图形都必须提供哪些能力。

虚析构函数：virtual ~Shape() {}

这一句虽然短，但非常关键：

1
virtual ~Shape() {}

析构函数的作用，是对象销毁时执行清理工作。

这里把析构函数写成 virtual，是为了保证下面这种写法是安全的：

1
Shape* p = new Rectangle(2, 3);
2
delete p;

表面上看，p 的类型是 Shape*；但它实际指向的是 Rectangle 对象。

如果基类析构函数不是虚函数，delete p 时就可能只按 Shape 这一层来销毁，派生类那一层的清理过程无法正确执行。

把析构函数写成虚函数后，删除基类指针时会按真实类型销毁对象：

• 先执行派生类析构
• 再执行基类析构

这就是“通过基类指针删除派生类对象”时必须使用虚析构函数的原因。

在这份代码里，Rectangle / Circle / Triangle 没有自己额外管理资源，所以就算析构函数体是空的，virtual 仍然必须保留。

Rectangle : public Shape 是什么意思？

1
class Rectangle : public Shape {
2
private:
3
    double w, h;
4
};

这里不是“Rectangle 里面再放一个 Shape 对象”，而是：

• Rectangle 继承 Shape
• 也就是“矩形是一种图形”

这叫 is-a 关系：

• Rectangle is a Shape
• Circle is a Shape
• Triangle is a Shape

所以我们才可以把矩形对象交给 Shape*：

1
Shape* p = new Rectangle(2, 3);

这句成立的前提，就是矩形本来就是图形的一种。

访问控制：public / protected / private#

代码里三种访问级别都出现了：

1
class Shape {
2
protected:
3
    double area, perimeter;
4

5
public:
6
    virtual void calc_area() = 0;
7
};
8

9
class Rectangle : public Shape {
10
private:
11
    double w, h;
12
};

可以这样记：

• public：类外也能访问，是对外接口
• protected：类外不能直接访问，但派生类能访问
• private：只有当前类自己能访问

放在这份代码里：

• area / perimeter 放在 protected，因为子类算面积周长时要用到
• w / h / r / a / b / c 放在 private，因为它们只是具体图形的内部细节

派生类 + override#

派生类真正做的事，是把基类里的“要求”补成各自的“具体实现”。

例如矩形会写：

1
void calc_area() override {
2
    area = w * h;
3
}

圆形、三角形也会各自给出自己的公式。

override 的意思可以记成：

• “我就是在重写基类里的那个虚函数”

它的好处是：

• 如果函数签名写错，编译器会直接报错
• 能防止你以为自己重写了，实际上根本没重写成功

构造函数与初始化列表#

派生类构造函数是这种形式：

1
Rectangle(double w, double h) : w(w), h(h) {}
2
Circle(double r) : r(r) {}
3
Triangle(double a, double b, double c) : a(a), b(b), c(c) {}

这里 : w(w), h(h) 是初始化列表。

可以直接这样读：

• 左边的 w 是成员变量
• 右边的 w 是传进来的参数

所以 Rectangle(double w, double h) : w(w), h(h) {} 的意思就是：

• 用传进来的 w 初始化成员 w
• 用传进来的 h 初始化成员 h

这是 C++ 里很常见、也很标准的写法。

友元输出函数#

Shape 里有这一句：

1
friend std::ostream& operator<<(std::ostream&, const Shape&);

这里的 friend 表示：

• operator<< 不是 Shape 的成员函数
• 但我们授权它访问 Shape 的内部成员

对应定义是：

1
std::ostream& operator<<(std::ostream& out, const Shape& s)
2
{
3
    return out << "(" << s.name() << ":" << s.area << "," << s.perimeter << ")";
4
}

这样写的原因是：

因为我们想保留这种自然语法：

1
std::cout << shape;

<< 通常写成非成员函数更自然，但非成员函数默认不能访问类里的非公有成员，所以这里用 friend 授权。

同时，这里也再次体现了 & 的用法：

• std::ostream& out：输出流按引用传入，不复制 cout
• const Shape& s：图形按只读引用传入
• 返回 std::ostream&：这样才能继续连写 <<

还有一个细节：

1
s.name()

这里 name() 是虚函数，所以即使 s 的静态类型写成 Shape&，真正调用的仍然会是各个派生类自己的 name()。

多态输出与排序#

主程序的执行流程大致是：

1. 创建不同类型的图形对象
2. 用 Shape* 统一保存它们
3. 调用统一接口去计算面积和周长
4. 传入不同比较器进行排序
5. 统一打印

对应代码像这样：

1
for (Shape* s : arr)
2
{
3
    s->calc_area();
4
    s->calc_perimeter();
5
}

这一段的关键是：

• s 的写法是 Shape*
• 但每个 s 实际可能指向矩形、圆形、三角形
• 因为有 virtual，调用会自动分发到正确的版本

因此，这一段真正体现的是：

• 算法层：selection_sort
• 规则层：比较器
• 对象层：Shape 多态

三者是可以组合起来的。

还有两个小语法点：

1
s->calc_area();

• -> 用在指针上
• 如果是普通对象，就写成 obj.calc_area()

1
double get_area() const { return area; }

• 末尾的 const 表示这个成员函数不会修改对象状态
• 这种“读取型接口”通常都写成 const

资源管理提醒#

显式 delete：

1
for (Shape* s : arr)
2
    delete s;

这是因为前面用的是 new，所以最后要手动释放。

这里删除的是基类指针：

1
Shape* p = new Rectangle(2, 3);
2
delete p;

表面上删除的是 Shape*，但实际对象是 Rectangle。因此，析构函数必须是虚函数，程序才会按真实类型正确销毁对象。

现代 C++ 更推荐用智能指针（如 std::unique_ptr）管理生命周期，但这份代码的重点是先理解多态和继承。