返回：0200 C++总目录 · 上一课：0209 Chap9 群体类和群体数据的组织 · 下一课：0211 Chap11 流类库与输入输出

1、资料清单

资料 内容 入口
教材 《C++语言程序设计（第4版）》Chap10，原书页码 414-496 抽取 Markdown 下载
课件 Chap10 课件，位于本地郑莉 C++ 资料目录 本地资料夹
例题源代码 C++V5 源代码 下载
VS2019 工程 C++V5 VS2019 solution 下载

Chap10 的主线是模板 → STL → 容器 → 迭代器 → 算法 → 排序与查找。第 9 章自己写数组、链表、栈和队列，第 10 章开始学会使用标准库，把常见数据结构和算法交给 STL。

2、颜色标注

颜色 含义 使用位置
蓝色 核心术语、定义 STL、容器、迭代器、函数对象、算法
绿色 推荐写法、主线 std::vector、std::sort、范围 for、泛型函数
黄色 易错点、边界条件 迭代器失效、折半查找要求有序、下标越界
红色 不建议做法 重复手写已有标准库算法、在无序数组中直接折半查找

3、学习目标

目标 要会到什么程度
泛型程序设计 理解代码不绑定某一种具体类型，而是通过模板复用
STL 三件套 知道容器负责存数据，迭代器负责访问，算法负责处理
迭代器 会用 begin()、end() 遍历容器，知道迭代器类似泛化指针
容器 会区分顺序容器、关联容器和容器适配器
函数对象 会写比较规则，理解 std::less、std::greater 和 lambda
算法 会使用 sort、find、count、accumulate、binary_search
排序查找 会复盘插入排序、选择排序、冒泡排序、顺序查找和折半查找

4、章节目录

小节 内容 本节关键词
10.1 泛型程序设计与 STL 模板、标准模板库、复用
10.2 迭代器 begin、end、遍历
10.3 容器 vector、list、deque、set、map
10.4 函数对象 比较器、谓词、lambda
10.5 算法 排序、查找、统计、累加
10.6 银行账户程序改进 用容器组织对象
10.7 STL 扩展 标准库实践、泛型思维

5、泛型程序设计与 STL

泛型程序设计强调把“算法逻辑”和“具体数据类型”分离。比如最大值函数不应该只能比较 int，也应该能比较 double、char，甚至用户自定义类型。

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

STL 是 C++ 标准库中最重要的一组泛型组件，可以把它理解成三件套：

组件 作用 例子
容器 负责保存一组对象 vector、list、deque、set、map
迭代器 负责以统一方式访问容器元素 begin()、end()、++it、*it
算法 负责对区间做处理 sort、find、count、accumulate

一个最典型的 STL 写法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{5, 2, 9, 1, 7};

    std::sort(values.begin(), values.end());

    for (int value : values) {
        std::cout << value << " ";
    }

    return 0;
}

STL 算法通常处理的是左闭右开区间：[begin, end)。end() 指向最后一个元素的后一个位置，不能解引用。

6、容器

容器用于管理一组对象。选容器时可以先问三个问题：是否需要按下标访问，是否经常在中间插入删除，是否需要按关键字快速查找。

类型 常用容器 特点 适合场景
顺序容器 vector 连续存储，支持快速下标访问 默认首选容器
顺序容器 list 双向链表，中间插入删除方便 频繁插入删除
顺序容器 deque 分段连续，两端插入删除方便 队列、双端队列
关联容器 set 关键字唯一，自动有序 去重、集合
关联容器 map 键值对，按键自动有序 字典、索引表
适配器 stack 后进先出 括号匹配、递归模拟
适配器 queue 先进先出 BFS、任务队列
适配器 priority_queue 优先级最高元素先出 堆、调度、TopK 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<int> scores{90, 86, 95};
    scores.push_back(88);

    std::map<std::string, int> age;
    age["Alice"] = 20;
    age["Bob"] = 21;

    std::cout << scores[0] << "\n";
    std::cout << age["Alice"] << "\n";

    return 0;
}

7、迭代器

迭代器可以看作泛化的指针。算法不直接关心容器内部怎么存储，只要容器能给出迭代器，算法就可以处理这一段数据。

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{1, 2, 3, 4, 5};

    for (std::vector<int>::iterator it = values.begin(); it != values.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

更现代的写法是：

1
2
3
for (int value : values) {
    std::cout << value << " ";
}

迭代器要注意两个边界：

问题 说明
end() 只是哨兵位置，不能写 *values.end()
迭代器失效 vector 扩容、插入、删除后，原有迭代器可能失效

8、函数对象与 lambda

函数对象本质上是“能像函数一样调用的对象”。STL 算法常常把比较规则、筛选规则作为参数传进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{1, 5, 2, 9, 7};

    std::sort(values.begin(), values.end(), std::greater<int>());

    for (int value : values) {
        std::cout << value << " ";
    }

    return 0;
}

使用 lambda 可以把比较规则直接写在调用处：

1
2
3
std::sort(values.begin(), values.end(), [](int a, int b) {
    return a > b;
});

这类写法的重点不是语法炫技，而是把“怎么比较”从算法中抽出来，让同一个算法能服务不同规则。

9、常用算法

STL 算法一般写在 <algorithm> 中，数值算法常见于 <numeric>。

算法 作用 示例
std::sort 排序 sort(v.begin(), v.end())
std::find 顺序查找 find(v.begin(), v.end(), key)
std::count 统计某个值出现次数 count(v.begin(), v.end(), key)
std::accumulate 累加区间 accumulate(v.begin(), v.end(), 0)
std::binary_search 判断有序区间中是否存在某值 binary_search(v.begin(), v.end(), key)
std::lower_bound 找第一个不小于目标的位置 lower_bound(v.begin(), v.end(), key) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> values{1, 2, 3, 4, 5, 5};

    int sum = std::accumulate(values.begin(), values.end(), 0);
    int countFive = std::count(values.begin(), values.end(), 5);
    bool hasThree = std::binary_search(values.begin(), values.end(), 3);

    std::cout << "sum = " << sum << "\n";
    std::cout << "countFive = " << countFive << "\n";
    std::cout << "hasThree = " << hasThree << "\n";

    return 0;
}

std::binary_search 和自己写的折半查找一样，都要求数据已经按同一规则排序。无序数组不能直接折半查找。

10、排序与查找复盘

课后题集中在排序和查找，这是从“自己写算法”过渡到“理解 STL 算法”的基础。

算法 思想 时间复杂度 复盘重点
插入排序 把待排序元素插入到前面有序区间 O(n²) 当前元素前面已经有序
选择排序 每一趟选出最小元素放到前面 O(n²) 每趟确定一个最终位置
冒泡排序 相邻元素比较交换，较大值逐渐后移 O(n²) 交换与提前结束
顺序查找 从头到尾逐个比较 O(n) 适合无序表
折半查找 每次排除一半区间 O(log n) 只能用于有序表

真实工程中，排序优先使用std::sort；本章手写排序的价值是理解比较、交换、边界和循环不变量。

11、课后习题答案

10-1 简单说明插入排序的算法思想

插入排序的基本思想是：把序列分成“已排序区间”和“未排序区间”，每一趟从未排序区间取出一个元素，将它按关键字大小插入到已排序区间的合适位置。重复这个过程，直到所有元素都插入完成。

核心不变量是：处理第 i 个元素之前，[0, i) 已经有序。

10-2 直接插入排序并输出每一趟结果

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
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>

template <typename T>
void printValues(const std::vector<T>& values) {
    for (const T& value : values) {
        std::cout << value << " ";
    }
    std::cout << "\n";
}

template <typename T>
void insertionSort(std::vector<T>& values) {
    for (std::size_t i = 1; i < values.size(); ++i) {
        T current = values[i];
        std::size_t j = i;

        while (j > 0 && current < values[j - 1]) {
            values[j] = values[j - 1];
            --j;
        }

        values[j] = current;
        printValues(values);
    }
}

int main() {
    std::vector<int> data{
        1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
        2, 4, 6, 8, 10, 12, 14, 16, 18, 20
    };

    std::cout << "排序前：\n";
    printValues(data);

    std::cout << "插入排序过程：\n";
    insertionSort(data);

    std::cout << "排序后：\n";
    printValues(data);

    return 0;
}

运行结果的最后一行为：

1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

插入排序在前半段本来有序时移动次数较少；当 2、4、6... 进入前半段时，就能看到元素逐步向后搬移。

10-3 简单说明选择排序的算法思想

选择排序的基本思想是：每一趟从未排序区间中选出关键字最小的元素，将它交换到未排序区间的开头。第 i 趟结束后，前 i + 1 个元素就是最终位置。

10-4 直接选择排序并输出每一趟结果

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
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <utility>
#include <vector>

template <typename T>
void printValues(const std::vector<T>& values) {
    for (const T& value : values) {
        std::cout << value << " ";
    }
    std::cout << "\n";
}

template <typename T>
void selectionSort(std::vector<T>& values) {
    for (std::size_t i = 0; i + 1 < values.size(); ++i) {
        std::size_t minIndex = i;

        for (std::size_t j = i + 1; j < values.size(); ++j) {
            if (values[j] < values[minIndex]) {
                minIndex = j;
            }
        }

        std::swap(values[i], values[minIndex]);
        printValues(values);
    }
}

int main() {
    std::vector<int> data{
        1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
        2, 4, 6, 8, 10, 12, 14, 16, 18, 20
    };

    std::cout << "排序前：\n";
    printValues(data);

    std::cout << "选择排序过程：\n";
    selectionSort(data);

    std::cout << "排序后：\n";
    printValues(data);

    return 0;
}

选择排序的比较次数固定，和初始序列是否接近有序关系不大。

10-5 简单说明交换排序的算法思想

交换排序的基本思想是：通过比较两个元素的关键字，如果它们的相对次序不满足排序要求，就交换它们。反复执行比较和交换，直到整个序列满足顺序要求。冒泡排序就是典型的交换排序。

10-6 升序冒泡排序并输出每一趟结果

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <utility>
#include <vector>

template <typename T>
void printValues(const std::vector<T>& values) {
    for (const T& value : values) {
        std::cout << value << " ";
    }
    std::cout << "\n";
}

template <typename T>
void bubbleSortAscending(std::vector<T>& values) {
    if (values.empty()) {
        return;
    }

    std::size_t last = values.size() - 1;

    while (last > 0) {
        std::size_t lastExchangeIndex = 0;

        for (std::size_t j = 0; j < last; ++j) {
            if (values[j + 1] < values[j]) {
                std::swap(values[j], values[j + 1]);
                lastExchangeIndex = j;
            }
        }

        last = lastExchangeIndex;
        printValues(values);
    }
}

int main() {
    std::vector<int> data{
        1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
        2, 4, 6, 8, 10, 12, 14, 16, 18, 20
    };

    std::cout << "排序前：\n";
    printValues(data);

    std::cout << "升序冒泡排序过程：\n";
    bubbleSortAscending(data);

    std::cout << "排序后：\n";
    printValues(data);

    return 0;
}

这里的 lastExchangeIndex 是优化：如果某一趟后半段没有交换，说明后半段已经有序，下一趟不必再比较。

10-7 降序冒泡排序并输出每一趟结果

降序排序只需要把比较方向反过来：升序时小的往前冒，降序时大的往前冒。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <utility>
#include <vector>

template <typename T>
void printValues(const std::vector<T>& values) {
    for (const T& value : values) {
        std::cout << value << " ";
    }
    std::cout << "\n";
}

template <typename T>
void bubbleSortDescending(std::vector<T>& values) {
    if (values.empty()) {
        return;
    }

    std::size_t last = values.size() - 1;

    while (last > 0) {
        std::size_t lastExchangeIndex = 0;

        for (std::size_t j = 0; j < last; ++j) {
            if (values[j + 1] > values[j]) {
                std::swap(values[j], values[j + 1]);
                lastExchangeIndex = j;
            }
        }

        last = lastExchangeIndex;
        printValues(values);
    }
}

int main() {
    std::vector<int> data{
        1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
        2, 4, 6, 8, 10, 12, 14, 16, 18, 20
    };

    std::cout << "排序前：\n";
    printValues(data);

    std::cout << "降序冒泡排序过程：\n";
    bubbleSortDescending(data);

    std::cout << "排序后：\n";
    printValues(data);

    return 0;
}

最终结果为：

1
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

10-8 简单说明顺序查找的算法思想

顺序查找从表头开始，逐个元素与待查找关键字比较。如果找到相等元素，则查找成功；如果遍历完整个序列仍未找到，则查找失败。顺序查找不要求数据有序。

10-9 顺序查找函数模板

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
#include <iostream>
#include <vector>

template <typename T>
int seqSearch(const std::vector<T>& values, const T& key) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (values[i] == key) {
            return static_cast<int>(i);
        }
    }

    return -1;
}

int main() {
    std::vector<int> data{
        1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
        2, 4, 6, 8, 10, 12, 14, 16, 18, 20
    };

    int key = 6;
    int index = seqSearch(data, key);

    if (index == -1) {
        std::cout << "没有找到数字 " << key << "\n";
    } else {
        std::cout << key << " 是第 " << index + 1 << " 个数字\n";
    }

    return 0;
}

输出：

1
6 是第 13 个数字

10-10 简单说明折半查找的算法思想

折半查找用于有序序列。每次取当前查找区间的中间元素与关键字比较：

  1. 如果相等，查找成功。
  2. 如果关键字更小，只在左半区间继续查找。
  3. 如果关键字更大，只在右半区间继续查找。
  4. 当左边界超过右边界时，说明查找失败。

10-11 折半查找函数模板

题目给出的原数组是无序的，因此折半查找前需要先排序，或者直接准备一个有序数组。下面代码先使用 std::sort 排序，再调用折半查找。

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
34
35
36
37
38
39
40
41
42
43
44
45
#include <algorithm>
#include <iostream>
#include <vector>

template <typename T>
int binSearch(const std::vector<T>& values, const T& key) {
    int low = 0;
    int high = static_cast<int>(values.size()) - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (values[mid] == key) {
            return mid;
        }

        if (key < values[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    std::vector<int> data{
        1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
        2, 4, 6, 8, 10, 12, 14, 16, 18, 20
    };

    std::sort(data.begin(), data.end());

    int key = 6;
    int index = binSearch(data, key);

    if (index == -1) {
        std::cout << "没有找到数字 " << key << "\n";
    } else {
        std::cout << key << " 是排序后第 " << index + 1 << " 个数字\n";
    }

    return 0;
}

输出：

1
6 是排序后第 6 个数字

原答案中直接对 data1 调用折半查找，但 data1 初始顺序不是完全升序。这里补上 std::sort，让代码和折半查找前提保持一致。

12、本章复盘清单

检查项 是否掌握
能说清 STL 的容器、迭代器、算法分别负责什么 □
能用 vector 保存一组数据并遍历输出 □
能用 sort 和 lambda 写升序、降序排序 □
能解释 begin() / end() 的左闭右开区间 □
能写出插入排序、选择排序、冒泡排序的基本代码 □
能区分顺序查找和折半查找的适用条件 □
知道折半查找必须用于有序数据 □
能把手写算法和 STL 算法对应起来复盘 □

本章学习时可以把“手写版本”和“STL 版本”对照看：手写排序查找用于理解过程，STL 算法用于实际编码。复盘重点不只是背代码，而是看清楚数据区间、比较规则和边界条件。