C++: STL 容器基础
前面的课程里，我们学了模板——让函数和类支持任意类型。
但真实项目中，你不需要自己写容器（如动态数组、链表）。
C++ 标准模板库（STL）已经提供了现成的容器，直接用就行！
1. 什么是 STL？
STL（Standard Template Library，标准模板库）是 C++ 标准库的一部分，包含：
| 组成部分 | 作用 | 示例 |
|---|---|---|
| 容器 | 存数据 | std::vector、std::array |
| 迭代器 | 遍历容器 | begin()、end() |
| 算法 | 操作数据 | std::sort、std::find |
| 函数对象 | 自定义比较逻辑 | std::less、std::greater |
💡 重点： STL 是模板实现的，所以能支持任意类型。
2. vector（最常用）
(1) 2.1 什么是 vector？
std::vector 是动态数组——大小能自动增长。
| 对比 | 普通数组 | vector |
|---|---|---|
| 大小 | 固定 | 动态 |
| 内存 | 栈或堆 | 堆 |
| 访问元素 | arr[i] |
vec[i] 或 vec.at(i) |
| 推荐度 | ⭐⭐ | ⭐⭐⭐⭐⭐ |
▶ 示例 1：vector 基本用法（难度⭐）
#include <iostream>
#include <vector>
int main() {
// 创建一个存 int 的 vector
std::vector<int> vec = {1, 2, 3, 4, 5};
// 访问元素
std::cout << "第一个元素：" << vec[0] << std::endl;
std::cout << "第二个元素：" << vec.at(1) << std::endl;
// 修改元素
vec[0] = 100;
// 获取大小
std::cout << "大小：" << vec.size() << std::endl;
return 0;
}
输出：
第一个元素：1
第二个元素：2
大小：5
💡 提示： vec.at(i) 会检查越界，如果越界会抛异常；vec[i] 不检查，效率高。
(2) 2.2 添加和删除元素
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
// 添加元素到末尾
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
// 删除末尾元素
vec.pop_back();
// 在指定位置插入元素
vec.insert(vec.begin() + 1, 15); // 在第二个位置插入 15
// 删除指定位置的元素
vec.erase(vec.begin() + 1); // 删除第二个元素
return 0;
}
(3) 2.3 遍历 vector
方法一：下标遍历（最常用）
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
for (size_t i = 0; i < vec.size(); i++) {
std::cout << vec[i] << " ";
}
std::cout << std::endl;
return 0;
}
方法二：范围 for（C++11，推荐）
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
for (int x : vec) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
方法三：迭代器（后面会学）
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
💡 推荐： 优先用范围 for（C++11），最简洁。
3. array（固定大小数组）
(1) 3.1 什么是 array？
std::array 是固定大小的数组，但比普通数组更安全。
| 对比 | 普通数组 | array |
|---|---|---|
| 大小 | 要知道 | 用 size() 获取 |
| 会不会退化成指针 | 会 | 不会 |
| 推荐度 | ⭐⭐ | ⭐⭐⭐⭐ |
▶ 示例 2：array 基本用法（难度⭐）
#include <iostream>
#include <array>
int main() {
// 创建一个存 5 个 int 的 array
std::array<int, 5> arr = {1, 2, 3, 4, 5};
// 访问元素
std::cout << "第一个元素：" << arr[0] << std::endl;
// 获取大小
std::cout << "大小：" << arr.size() << std::endl;
return 0;
}
输出：
第一个元素：1
大小：5
💡 重点： std::array 的大小是编译时确定的，不能改变。
4. deque（双端队列）
(1) 4.1 什么是 deque？
std::deque 是双端队列——能在两端快速添加/删除元素。
| 操作 | vector | deque |
|---|---|---|
| 末尾添加 | O(1) | O(1) |
| 头部添加 | O(n) | O(1) |
| 随机访问 | O(1) | O(1) |
▶ 示例 3：deque 基本用法（难度⭐⭐）
#include <iostream>
#include <deque>
int main() {
std::deque<int> dq;
// 在末尾添加
dq.push_back(10);
dq.push_back(20);
// 在头部添加
dq.push_front(5);
dq.push_front(1);
// 现在 dq 是：1, 5, 10, 20
for (int x : dq) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
输出：
1 5 10 20
5. list（双向链表）
(1) 5.1 什么是 list？
std::list 是双向链表——每个元素都存着前后元素的地址。
| 对比 | vector | list |
|---|---|---|
| 随机访问 | O(1) | ❌ 不支持 |
| 中间插入/删除 | O(n) | O(1) |
| 内存占用 | 小 | 大（每个元素多两个指针） |
▶ 示例 4：list 基本用法（难度⭐⭐）
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
// 在开头添加
lst.push_front(0);
// 在末尾添加
lst.push_back(6);
// 删除值为 3 的元素
lst.remove(3);
for (int x : lst) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
输出：
0 1 2 4 5 6
6. forward_list（单向链表）
(1) 6.1 什么是 forward_list？
std::forward_list 是单向链表——每个元素只存下一个元素的地址。
| 对比 | list | forward_list |
|---|---|---|
| 内存占用 | 较大 | 较小 |
| 能往前遍历吗？ | ✅ | ❌ |
| 推荐度 | ⭐⭐⭐⭐ | ⭐⭐（特定场景用） |
💡 建议： 除非你确定只需要往后遍历，否则用 std::list。
7. 容器选择指南
| 场景 | 推荐容器 |
|---|---|
| 需要动态大小 | std::vector |
| 大小固定，要保留 C 风格 | std::array |
| 需要在头部快速添加/删除 | std::deque |
| 需要频繁在中间插入/删除 | std::list |
| 只需要往后遍历，且要省内存 | std::forward_list |
💡 黄金法则： 优先用 std::vector，除非有明确理由用别的。
8. 实战：用 vector 实现动态数组（难度⭐⭐）
#include <iostream>
#include <vector>
#include <string>
struct Student {
std::string name;
int age;
double score;
};
int main() {
std::vector<Student> students;
// 添加学生
students.push_back({"Alice", 20, 92.5});
students.push_back({"Bob", 21, 88.0});
students.push_back({"Charlie", 19, 95.0});
// 遍历并输出
for (const auto& s : students) {
std::cout << "姓名：" << s.name
<< "，年龄：" << s.age
<< "，成绩：" << s.score << std::endl;
}
return 0;
}
❓ 常见问题
Q：vector 和 array 有什么区别？ A：> -
vector大小动态，存在堆上 > -array大小固定，存在栈上 > > 选择建议： 如果大小不确定，用vector；如果大小固定且较小，用array。 Q：为什么遍历 vector 推荐用范围 for？ A：因为更简洁，且不容易写错循环条件。 > > // 传统 for（容易写错条件） > for (size_t i = 0; i < vec.size(); i++) { ... } > > // 范围 for（简洁，不易错） > for (int x : vec) { ... } > Q：list 和 vector 哪个快？ A：看场景： > - 如果需要随机访问（vec[100]），vector快 > - 如果需要在中间插入/删除，list快
Q：关于STL containers最重要的是什么？ A：先理解核心概念，再通过实践例子来巩固。
📖 小节
- STL 容器是 C++ 标准库提供的现成数据结构
- vector 最常用（动态数组）
- array 用于固定大小场景
- deque 支持双端快速操作
- list 是双向链表，适合频繁插入/删除
- 优先用 vector，除非有明确理由用别的
📝 作业
-
基础题 (Difficulty ⭐)： 用
std::vector<int>存 5 个整数，遍历并输出。 -
进阶题 (Difficulty ⭐⭐)： 用
std::vector<std::string>存 3 个字符串，让用户输入，然后输出。 -
挑战题 (Difficulty ⭐⭐⭐)： 用
std::deque实现" palindrome 检测"： -
从两端往中间比，如果所有对应字符都相等，就是 palindrome
-
示例：
"racecar"是 palindrome，"hello"不是
- STL 容器分类：序列式（vector/list/deque）和关联式（set/map）
- vector 动态数组：尾部增删快，支持随机访问
- list 双向链表：任意位置插入快
- map 键值对容器：按键排序，查找 O(log n)
- set 集合容器：元素唯一，自动排序
9. 🚀 下一步
学会了 STL 容器基础，接下来我们学习 STL 算法（第35课）—— 用标准库提供的算法操作容器，不用自己写排序、查找……
