20260227 152127 Cpp 入门第十课

第十章：C++的百宝箱——STL（标准模板库）¶

你好！欢迎来到第十章！在前面的章节，我们学习了数组、链表、栈、队列等数据结构，但每次都要自己写代码实现，很麻烦。其实C++已经给我们准备了一个强大的百宝箱，里面有很多常用的数据结构和算法，可以直接拿来用，这就是STL（Standard Template Library，标准模板库）。学完本章，你就能轻松地使用各种容器和算法，让编程变得事半功倍！

10.1 STL程序范例 ¶

先来看一个简单的STL程序：使用 vector（动态数组）存储一些整数，然后用 sort 排序，最后用迭代器输出。

#include <iostream>
#include <vector>   // vector容器
#include <algorithm> // 算法，比如sort
using namespace std;

int main() {
    // 创建一个vector，存储整数
    vector<int> numbers;

    // 向尾部添加元素
    numbers.push_back(5);
    numbers.push_back(2);
    numbers.push_back(8);
    numbers.push_back(1);
    numbers.push_back(9);

    cout << "排序前：";
    for (int i = 0; i < numbers.size(); i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    // 使用STL的排序算法
    sort(numbers.begin(), numbers.end());

    cout << "排序后：";
    // 使用迭代器遍历
    for (vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

运行结果：

排序前：5 2 8 1 9 
排序后：1 2 5 8 9

这个程序展示了STL的核心三部分：容器（vector）、算法（sort）、迭代器（iterator）。下面我们一一学习。

10.2 STL概述 ¶

STL是C++标准库的一部分，它提供了三大组件：

容器：存储数据的结构，比如动态数组、链表、栈、队列、集合、映射等。
算法：对容器中的数据进行操作的函数，比如排序、查找、替换等。
迭代器：连接容器和算法的桥梁，像指针一样访问容器中的元素。

使用STL的好处：代码简洁、高效、可靠，不用自己重复造轮子。

10.3 容器 ¶

容器是用来存放数据的对象。根据组织方式不同，分为序列式容器和关联式容器。

10.3.1 vector（动态数组）¶

vector 是一个可以动态增长的数组，支持随机访问（用下标），在尾部插入删除效率高。

基本操作 ¶

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 定义
    vector<int> v1;               // 空vector
    vector<int> v2(5, 10);        // 5个元素，每个都是10
    vector<int> v3 = {1, 2, 3, 4}; // 初始化列表（C++11）

    // 添加元素
    v1.push_back(20);   // 尾部添加
    v1.push_back(30);

    // 访问元素
    cout << v1[0] << endl;         // 下标访问，不检查越界
    cout << v1.at(1) << endl;      // at会检查越界，抛出异常

    // 获取大小
    cout << "v1大小：" << v1.size() << endl;

    // 遍历
    for (int i = 0; i < v1.size(); i++) {
        cout << v1[i] << " ";
    }
    cout << endl;

    // 使用迭代器遍历
    for (vector<int>::iterator it = v1.begin(); it != v1.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 使用范围for循环（C++11）
    for (int x : v1) {
        cout << x << " ";
    }
    cout << endl;

    // 删除最后一个元素
    v1.pop_back();

    // 清空
    v1.clear();

    return 0;
}

常用成员函数：
- push_back()：尾部添加
- pop_back()：删除尾部
- size()：元素个数
- empty()：是否为空
- clear()：清空
- begin()、end()：返回首尾迭代器
- insert()、erase()：插入和删除（较复杂，需要迭代器）

10.3.2 list（双向链表）¶

list 是双向链表，不支持随机访问，但插入和删除非常快（尤其在中间）。

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {5, 2, 8, 1, 9};

    // 尾部添加
    lst.push_back(10);
    // 头部添加
    lst.push_front(0);

    // 遍历（只能用迭代器，不能用下标）
    for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 排序（list有自己的sort成员函数，比通用算法快）
    lst.sort();

    for (int x : lst) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

10.3.3 deque（双端队列）¶

deque 是双端队列，支持在头尾快速插入删除，也支持随机访问（但比vector稍慢）。

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq = {1, 2, 3};
    dq.push_back(4);    // 尾部加
    dq.push_front(0);   // 头部加

    for (int i = 0; i < dq.size(); i++) {
        cout << dq[i] << " ";   // 支持下标
    }
    cout << endl;

    dq.pop_back();      // 删除尾部
    dq.pop_front();     // 删除头部
    return 0;
}

10.3.4 stack（栈）¶

stack 是适配器容器，它基于其他容器（默认deque）实现，提供后进先出（LIFO）接口。

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> st;
    st.push(10);   // 入栈
    st.push(20);
    st.push(30);

    cout << "栈顶元素：" << st.top() << endl; // 30
    st.pop();      // 出栈（无返回值）
    cout << "栈顶元素：" << st.top() << endl; // 20
    cout << "栈大小：" << st.size() << endl;  // 2

    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

10.3.5 queue（队列）¶

queue 也是适配器容器，提供先进先出（FIFO）接口。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);   // 入队
    q.push(20);
    q.push(30);

    cout << "队头：" << q.front() << endl; // 10
    cout << "队尾：" << q.back() << endl;  // 30
    q.pop();      // 出队（队头）
    cout << "队头：" << q.front() << endl; // 20
    return 0;
}

10.3.6 set（集合）¶

set 是一个有序的集合，元素唯一，自动排序（默认升序）。查找效率高（红黑树）。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(2);   // 重复插入无效

    // 遍历（有序）
    for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 查找
    set<int>::iterator it = s.find(5);
    if (it != s.end()) {
        cout << "找到了：" << *it << endl;
    } else {
        cout << "没找到" << endl;
    }

    // 删除
    s.erase(2);
    return 0;
}

10.3.7 map（映射）¶

map 存储键值对（key-value），键唯一，自动排序。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> scores;
    scores["小明"] = 98;        // 通过键赋值
    scores["小红"] = 95;
    scores["小刚"] = 88;

    // 遍历
    for (map<string, int>::iterator it = scores.begin(); it != scores.end(); ++it) {
        cout << it->first << " : " << it->second << endl;   // first是键，second是值
    }

    // 查找
    string name = "小红";
    map<string, int>::iterator it = scores.find(name);
    if (it != scores.end()) {
        cout << name << "的成绩是：" << it->second << endl;
    } else {
        cout << "没找到" << endl;
    }

    return 0;
}

常用成员函数：
- insert(make_pair(key, value)) 或直接用 [key] = value（但 [] 如果键不存在会创建）
- find(key)：查找，返回迭代器，找不到返回 end()
- erase(key)：删除

10.4 迭代器 ¶

迭代器是一种类似于指针的对象，用来遍历容器中的元素。所有容器都提供 begin() 和 end() 成员函数，返回指向第一个元素和最后一个元素之后位置的迭代器。

迭代器分类（按功能）：
- 输入迭代器：只读，一次遍历
- 输出迭代器：只写，一次遍历
- 前向迭代器：可读写，只能向前（如 forward_list）
- 双向迭代器：可读写，能前后移动（如 list、set、map）
- 随机访问迭代器：可读写，支持 +、-、[] 等（如 vector、deque）

使用示例：

vector<int> v = {1, 2, 3, 4, 5};

// 正向迭代器
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    *it = *it * 2;   // 修改元素
}

// 常量迭代器（只读）
for (vector<int>::const_iterator it = v.cbegin(); it != v.cend(); ++it) {
    cout << *it << " ";
}

// 反向迭代器
for (vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit) {
    cout << *rit << " ";
}

C++11 可以用 auto 简化：

for (auto it = v.begin(); it != v.end(); ++it) { ... }

10.5 算法 ¶

STL提供了大量通用算法，都在 <algorithm> 头文件中。它们通过迭代器操作容器，不依赖于具体容器类型。

10.5.1 sort 排序 ¶

#include <algorithm>
vector<int> v = {5, 2, 8, 1, 9};
sort(v.begin(), v.end());                // 升序
sort(v.begin(), v.end(), greater<int>()); // 降序

也可以自定义排序规则（用函数或函数对象）：

bool cmp(int a, int b) {
    return a > b;   // 降序
}
sort(v.begin(), v.end(), cmp);

10.5.2 find 查找 ¶

vector<int> v = {5, 2, 8, 1, 9};
auto it = find(v.begin(), v.end(), 8);
if (it != v.end()) {
    cout << "找到了，位置：" << it - v.begin() << endl;
} else {
    cout << "没找到" << endl;
}

10.5.3 其他常用算法 ¶

reverse：反转
cpp reverse(v.begin(), v.end());
count：计数
cpp int cnt = count(v.begin(), v.end(), 5);
max_element、min_element：找最大最小值
cpp auto maxIt = max_element(v.begin(), v.end()); cout << "最大值：" << *maxIt << endl;
binary_search：二分查找（要求容器有序）
cpp if (binary_search(v.begin(), v.end(), 8)) { ... }
copy：复制
cpp vector<int> v2(v.size()); copy(v.begin(), v.end(), v2.begin());

10.5.4 算法与迭代器的配合 ¶

算法通过迭代器操作数据，所以同一个算法可以用于不同的容器。例如 find 可以用于 vector、list、deque 等。

10.6 编程实例讲解 ¶

实例1：统计学生成绩（使用vector和map）¶

题目：输入若干学生姓名和成绩，以“end”结束。然后输出所有学生的成绩，并按成绩从高到低排序输出。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
using namespace std;

struct Student {
    string name;
    int score;
};

bool cmp(const Student &a, const Student &b) {
    return a.score > b.score;   // 降序
}

int main() {
    vector<Student> students;
    string name;
    int score;

    cout << "请输入学生姓名和成绩（输入end结束）：" << endl;
    while (true) {
        cin >> name;
        if (name == "end") break;
        cin >> score;
        students.push_back({name, score});
    }

    // 排序
    sort(students.begin(), students.end(), cmp);

    // 输出
    cout << "\n成绩单（按分数降序）：" << endl;
    for (const auto &s : students) {
        cout << s.name << " : " << s.score << endl;
    }

    return 0;
}

实例2：单词计数器（使用map）¶

题目：输入一行英文句子，统计每个单词出现的次数（忽略大小写）。

#include <iostream>
#include <map>
#include <string>
#include <cctype>
#include <sstream>   // 字符串流
using namespace std;

string toLower(string s) {
    for (char &c : s) {
        c = tolower(c);
    }
    return s;
}

int main() {
    string line;
    cout << "请输入一行英文：";
    getline(cin, line);

    map<string, int> wordCount;
    stringstream ss(line);
    string word;

    while (ss >> word) {
        word = toLower(word);
        // 去掉标点符号（简单处理：只保留字母数字）
        string clean;
        for (char c : word) {
            if (isalnum(c)) {
                clean += c;
            }
        }
        if (!clean.empty()) {
            wordCount[clean]++;
        }
    }

    cout << "单词统计：" << endl;
    for (const auto &pair : wordCount) {
        cout << pair.first << " : " << pair.second << endl;
    }

    return 0;
}

实例3：集合运算（使用set）¶

题目：输入两个集合（整数），输出它们的并集、交集和差集。

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    set<int> set1, set2;
    int n, x;

    cout << "请输入第一个集合的元素个数：";
    cin >> n;
    cout << "请输入" << n << "个整数：";
    for (int i = 0; i < n; i++) {
        cin >> x;
        set1.insert(x);
    }

    cout << "请输入第二个集合的元素个数：";
    cin >> n;
    cout << "请输入" << n << "个整数：";
    for (int i = 0; i < n; i++) {
        cin >> x;
        set2.insert(x);
    }

    // 并集
    set<int> unionSet;
    set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
              inserter(unionSet, unionSet.begin()));
    cout << "并集：";
    for (int v : unionSet) cout << v << " ";
    cout << endl;

    // 交集
    set<int> interSet;
    set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
                     inserter(interSet, interSet.begin()));
    cout << "交集：";
    for (int v : interSet) cout << v << " ";
    cout << endl;

    // 差集（set1 - set2）
    set<int> diffSet;
    set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
                   inserter(diffSet, diffSet.begin()));
    cout << "差集（set1 - set2）：";
    for (int v : diffSet) cout << v << " ";
    cout << endl;

    return 0;
}

实例4：使用栈判断括号匹配 ¶

题目：输入一个字符串，包含 ()、[]、{}，判断括号是否匹配。

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isMatching(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

bool checkBrackets(const string &s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty() || !isMatching(st.top(), c)) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    string expr;
    cout << "请输入表达式：";
    cin >> expr;
    if (checkBrackets(expr)) {
        cout << "括号匹配" << endl;
    } else {
        cout << "括号不匹配" << endl;
    }
    return 0;
}

20260227 152127 Cpp 入门第十课

第十章：C++的百宝箱——STL（标准模板库）¶

10.1 STL程序范例 ¶

10.2 STL概述 ¶

10.3 容器 ¶

10.3.1 vector（动态数组）¶

基本操作 ¶

10.3.2 list（双向链表）¶

10.3.3 deque（双端队列）¶

10.3.4 stack（栈）¶

10.3.5 queue（队列）¶

10.3.6 set（集合）¶

10.3.7 map（映射）¶

10.4 迭代器 ¶

10.5 算法 ¶

10.5.1 sort 排序 ¶

10.5.2 find 查找 ¶

10.5.3 其他常用算法 ¶

10.5.4 算法与迭代器的配合 ¶

10.6 编程实例讲解 ¶

实例1：统计学生成绩（使用vector和map）¶

实例2：单词计数器（使用map）¶

实例3：集合运算（使用set）¶

实例4：使用栈判断括号匹配 ¶

10.7 阶段性编程练习 ¶

练习1：vector练习 ¶

练习2：list练习 ¶

练习3：map电话簿 ¶

练习4：set去重 ¶

练习5：队列模拟 ¶

练习6：算法综合 ¶

10.8 第10章编程作业 ¶

作业1：学生成绩管理系统（STL版）¶

作业2：文章词频统计 ¶

作业3：迷宫最短路径（选做）¶

作业4：多项式计算器 ¶

作业5：停车场模拟 ¶