引言

这篇文章主要是记录下刷题的过程，复习C++的基础的同时防止后面又得再刷一遍，知识包括stl的基本使用，刷题过程时的模板，计算机相关的知识。可能会混一些计算机组成原理，编译原理相关的东西，默认读者已经学会基本数据结构，比如数组链表之类的概念，比较特殊的比如红黑树知道有这种结构。

一、stl

C++标准模板库。可以简单理解为一系列封装好的通用API，正常来说最多会看看源码，不搞操作系统底层的不用了解太透彻。

二、迭代器

可以理解为对容器中元素的一种抽象的指针，用来遍历容器，本质可以当作一个外部访问容器内部元素和容器内部实现的一种桥梁，可以让外部写遍历的时候只用调接口，不用关注具体的实现细节（比如sort，可以对map，vector等多个容器使用而不用担心链表该咋样咋样，数组该咋样咋样）。

三、vector

基础概念

动态数组，最常见的 STL 容器。核心思想是减少频繁的数据申请。

• size(): 当前元素个数。
• capacity(): 当前已分配的存储空间，可容纳的元素数量。

当 size == capacity 时，vector 会进行扩容，通常会分配当前 capacity 的 1.5 到 2 倍的新空间。了解这一机制有助于性能优化，例如，已知最终大小可通过 reserve() 预分配内存，避免多次扩容开销。

四、常见用法

std::vector 核心使用

#include <vector>
#include <algorithm> // for std::sort

// 常见构造
std::vector<T> arr;              // 空 vector
std::vector<T> arr(n);           // n个默认值T()
std::vector<T> arr(n, k);         // n个值k

// 查看属性
arr.size();      // 元素个数，O(1)
arr.capacity();  // 已分配容量，O(1)
arr.empty();     // 是否为空 (size == 0)，O(1)

// 修改容量和大小
arr.reserve(n);  // 预分配内存，仅影响capacity，不影响size，不会缩容。
arr.resize(n);   // 改变size。变大则填充默认值或指定值，可能导致扩容；变小则移除多余元素，capacity不变。

// 元素增删改查
arr.push_back(x);       // 末尾添加元素x，O(1) 均摊
arr.emplace_back(args...); // 末尾原地构造元素，O(1) 均摊，常用于复杂对象。
arr.pop_back(); 		// 删除末位元素，O(1)，不返回值。
arr.clear();  			// 清空所有元素 (size=0)，capacity不变。
arr.erase(iter);        // 擦除迭代器iter指向的元素，返回下一个元素的迭代器，O(N)。
// arr.erase(begin, end); // 擦除区间[begin, end) 的元素，O(N)。

// 随机访问：arr[i] 或 arr.at(i) (带边界检查)

// 遍历
for(int i=0; i < arr.size(); ++i) { /* arr[i] */ }
for(auto& val : arr) { /* val */ } // 推荐使用引用以修改元素或避免拷贝。
// 注意：在遍历时修改容器结构 (如增删元素)，可能导致迭代器失效，应避免。

emplace_back vs push_back：

• 对于复杂类型，emplace_back 通过直接在 vector 内部构造对象，可以避免一次临时对象的创建和销毁，通常更高效。对于简单类型或已存在的对象，差异不大。

五、注意事项

STL 的 sort 算法是刷题利器，效率高且易用。

#include <algorithm> // for std::sort

// 默认升序排序
std::sort(arr.begin(), arr.end());

// 自定义比较函数 (降序示例)
std::sort(arr.begin(), arr.end(),
		 [](T a, T b){
			// 返回 true 表示 a 的优先级高于 b，a 将排在 b 之前
			return a > b;   // a更大则a优先级高，实现降序
		}
);

• std::sort 接受两个迭代器表示排序范围 [begin, end)。
• 第三个参数是可选的比较函数，可以是一个 Lambda 表达式。它接受两个参数 a 和 b，如果 a 应该排在 b 前面，则返回 true。
• 对于自定义结构体，通常需要重载 operator< 或提供自定义比较函数。也可以直接使用系统提供的两个方法模板std::greater<T>()和std::less<int>()