本课时有配套视频讲解，购买后即可观看（永久有效）
STL Vector
一、课上练习
编程练习
二、知识总结
✨ 核心思想
vector 是 C++ 标准模板库（STL）中的一个非常核心和常用的容器，提供了动态数组的功能。这意味着它可以在运行时动态地改变大小，能够根据需要自动扩展来容纳更多的元素。vector 在使用上类似于普通的数组，但提供了更多的灵活性和高级功能。
✨ 特性
vector 具有以下核心特性：
- 动态大小：与普通数组固定大小不同，vector 可以根据需要扩展和缩小。
- 连续存储：vector 的元素在内存中连续存放，这意味着可以通过指针算术直接访问任何元素，保证了高效的元素访问和兼容性。
- 自动管理内存：vector 内部自动处理所有内存分配和释放的操作。
✨ 常用操作
vector 支持以下常用操作：
- 插入元素：可以在 vector 的末尾添加元素（
push_back()），或在任意位置插入元素（insert()）。 - 删除元素：可以删除 vector 末尾的元素（
pop_back()），或删除任意位置的元素（erase()）。 - 访问元素：可以通过下标操作符（
operator[]）或at()方法访问元素。at()方法与下标操作符的区别在于，它会检查下标是否越界。 - 大小管理：
size()返回当前元素的数量，capacity()返回不重新分配内存的情况下 vector 可以容纳的元素数量，resize()可以改变 vector 的大小，reserve()可以预先分配内存以减少重新分配的次数。
✨ 性能考虑
vector 各操作的时间复杂度：
- 访问性能：直接访问任意元素的时间复杂度为 O(1)。
- 插入和删除性能：在 vector 的末尾插入或删除元素的时间复杂度也为 O(1)。然而，在 vector 的开始或中间位置插入或删除元素的时间复杂度为 O(n)，因为可能需要移动元素来维持连续的存储。
- 空间复杂度：由于需要支持动态扩展，vector 可能会分配比当前元素数量更多的内存空间。
✨ 应用场景
vector 适用于以下场景：
- 当需要一个能够动态变化大小的数组时，vector 是一个很好的选择。
- 如果你需要频繁地在序列的尾部添加或删除元素，而不是在中间或开始，vector 的性能是非常优越的。
- 当需要经常随机访问序列中的元素时，vector 由于其连续内存的特性，提供了极佳的性能。
总的来说，vector 是一个非常通用且高效的容器，适用于多种不同的编程场景，是每个 C++ 程序员必须掌握的基本工具之一。
✨ 代码实现
下面的代码展示了 vector 的各种常用操作，包括创建、添加、删除、访问、插入和清空等：
vector常用操作代码示例
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int main() {
6 // 创建并初始化vector
7 vector<int> vec = {1, 2, 3, 4, 5};
8
9 // push_back: 在vector末尾添加一个元素
10 vec.push_back(6);
11
12 // pop_back: 删除vector末尾的元素
13 vec.pop_back();
14
15 // size: 获取vector中元素的数量
16 cout << "Size of vector: " << vec.size() << endl;
17
18 // access: 访问vector中的元素
19 cout << "Element at index 2: " << vec[2] << endl;
20 // 或者使用at方法访问，它会检查索引是否越界
21 cout << "Element at index 2 (using at): " << vec.at(2) << endl;
22
23 // insert: 在指定位置插入元素
24 vec.insert(vec.begin() + 2, 10); // 在索引2的位置插入10
25 cout << "After insert: ";
26 //索引遍历
27 for(int i = 0; i < vec.size(); i++) {
28 cout << i << " ";
29 }
30 cout << endl;
31
32 // erase: 删除指定位置的元素
33 vec.erase(vec.begin() + 2); // 删除索引2的元素
34 cout << "After erase: ";
35 for(auto it = vec.begin(); it != vec.end(); ++it) { //iterotor 遍历
36 cout << *it << " ";
37 }
38 cout << endl;
39
40 // clear: 清空vector中的所有元素
41 vec.clear();
42 cout << "After clear, size of vector: " << vec.size() << endl;
43
44 // empty: 检查vector是否为空
45 if(vec.empty()) {
46 cout << "Vector is empty now." << endl;
47 }
48
49 return 0;
50}✨ 执行示例
以下通过一系列操作，展示 vector 内部状态的变化过程：
1操作 vector内容 size capacity(可能值)
2-----------------------------------------------------------------------
3vector<int> v; [] 0 0
4v.push_back(10); [10] 1 1
5v.push_back(20); [10, 20] 2 2
6v.push_back(30); [10, 20, 30] 3 4 ← 容量翻倍扩展
7v.push_back(40); [10, 20, 30, 40] 4 4
8v.push_back(50); [10, 20, 30, 40, 50] 5 8 ← 再次翻倍
9v.pop_back(); [10, 20, 30, 40] 4 8 ← 容量不缩小
10v.insert(v.begin()+1, 99); [10, 99, 20, 30, 40] 5 8
11v.erase(v.begin()+2); [10, 99, 30, 40] 4 8
12v[0] = 5; [5, 99, 30, 40] 4 8
13v.clear(); [] 0 8 ← 容量不缩小关键观察：
push_back在容量不够时会自动扩展，通常是翻倍（实际倍数取决于编译器实现）。扩展时会分配新内存、拷贝旧数据、释放旧内存，所以偶尔会比较慢。pop_back和clear不会释放内存（capacity 不变），只是减少 size。insert和erase在中间位置操作时需要移动元素，因此效率为 O(n)。
二维 vector 的使用
vector 可以嵌套使用来创建二维动态数组：
1vector<vector<int>> grid;
2
3// 创建 3×4 的二维数组，初始值为0
4grid.assign(3, vector<int>(4, 0));
5
6// 状态：
7// grid[0] = [0, 0, 0, 0]
8// grid[1] = [0, 0, 0, 0]
9// grid[2] = [0, 0, 0, 0]
10
11grid[1][2] = 5; // 修改第2行第3列
12// grid[1] = [0, 0, 5, 0]
13
14grid.push_back({1, 2, 3}); // 添加一行
15// grid[3] = [1, 2, 3] 注意：这行只有3个元素✨ 解题步骤详解
在竞赛和日常编程中使用 vector 的常见模式：
- 代替固定大小数组：当数组大小在运行时才确定时，用
vector代替v(n) int a[n]（变长数组不是标准C++）。 - 存储不定长数据：如读入不确定数量的数据，用
push_back逐个添加。 - 邻接表存图：
vector或adj[N] vector，每个节点的邻居用一个 vector 存储。 - 排序和去重：
sort(v.begin(), v.end())排序后，v.erase(unique(v.begin(), v.end()), v.end())去重。 - 作为函数参数：传递 vector 时建议用引用
vector，避免拷贝整个数组。如果不修改，用& v const vector。& v
✨ 常见错误
- 访问越界：
v[i]不做边界检查，访问不存在的下标会导致未定义行为（可能不报错但结果错误）。建议调试时用v.at(i)替代，它会在越界时抛出异常。 - 在空 vector 上调用
v[0]或v.front()：空 vector 没有任何元素，访问会崩溃。操作前应先检查v.empty()。 - 遍历时修改 vector：在用迭代器遍历时执行
insert或erase会使迭代器失效。如果需要边遍历边删除，应使用erase的返回值更新迭代器，或者从后往前遍历。 - size() 返回无符号整数：
v.size()返回size_t（无符号类型）。v.size() - 1在 vector 为空时会下溢为一个极大的数，导致循环条件判断错误。建议用(int)v.size() - 1或先判空。 - 频繁在头部插入：
v.insert(v.begin(), x)的时间复杂度为 O(n)，如果需要频繁在头部操作，应该使用deque而非 vector。
三、课后练习
编程练习
- 期末考试成绩排名：L3174