一、基本概念
1.STL：standard template library 标准模板库
2.六大组件
容器（container）：各种数据结构，如vector、list、deque、set、map；类模板技术
序列式容器：每个元素有固定位置-线性表
关联式容器：各元素之间没有严格的物理上的位序关系-非线性的树结构？
算法（algorithm）：以有限的步骤解决逻辑或数学上的问题-sort、find、copy、for_each
- 质变算法：会改变区间内的元素内容-拷贝，替换，删除
- 非质变算法：不会改变区间内的元素内容-查找，计数
迭代器（iterator）：算法和容器的胶合剂；所有容器都有自己专属的迭代器
仿函数
适配器
空间配置器：动态空间配置、空间管理、空间释放
六大组件之间的关系：容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化（比如调整sort的排序方式？），适配器可以修饰仿函数。
3.STL优点
- 高可重用性
- 高性能
- 高移植性
二、容器
1.vector：能自动改变长度的数组（原理：倍增）
定义：
vector<int> a;
vector<int> b[233];
struct Rec{
int c;
}
vector<Rec> r;方法：
size：返回大小
empty：表明是否为空
clear：把vector清空
a.front()? == a[0];
a.back() == a[a.size() - 1]//取数组的最后一个元素
a.push_back(4)//在vector最后添加一个元素4
a.pop_back()//删除最后一个元素
迭代器的使用：
vector<int>::iterator i = v.begin();
auto i = v.begin();? ? ? ?//auto：自动适应数据类型迭代器可以当成指针来看
2.string的基本操作
2.1创建：构造函数||拷贝构造函数
2.2赋值：s.assign("aaa");
2.3拼接：s.append("aaa")? s += "aaa"
2.4存取字符串：
s.at(i) ：访问越界会抛出异常：invalid string position，安全性更高? ? ? ?
s[i]：不会做越界检查，但访问效率更高
?2.5查找：
s.find("xxx") 查找逻辑：从左往右查找，返回子串第一个字符的位置? ? ? ?
rfind()：right find：从右往左查找
2.6替换：
s.replace(1,3,"11");
????????param1：起始位置 ?
????????param2：（从起始位置算起）替换的字符个数 ? ?
????????param3：替换进去的字符串（该字符串的长度可以是任意的，和前两个参数没有关系）
2.7比较
a.compare(b)：a > b 返回值大于0；a < b 返回值小于0；a = b 返回0
注意比较逻辑：从第一个字符开始比，如果比得出之后的就不比了
> 、<、==有被重载，也可以使用
3.队列
//定义普通队列
queue<int> q;
queue<double> p;
//定义优先队列
priority_queue<int> a;//大根堆
priority_queue<int,vector<int>,greater<int>> b;//小根堆
//定义结构体队列
//创建结构体类型的优先队列，必须重载比较符号
//小根堆重载大于号，大根堆重载小于号
struct Rec{
int a,b;
bool operator < (const Rec& t){
return a < t.a;
}
};
priority_queue<Rec> d;3.1循环队列
push ? ?// 从队尾插入
pop ? ? // 从队头弹出
front ? // 返回队头元素
back ? ?// 返回队尾元素
3.2优先队列：
a.push(1)//插入一个元素1
a.top();//取最大值
a.pop()；//删除最大值
3.3双端队列：两端都可插入弹出，支持随机访问
deque<int> a;//定义[] ? ? ? ? ? ? ?// 随机访问
begin/end ? ? ? // 返回deque的头/尾迭代器
front/back ? ? ?// 队头/队尾元素
push_back ? ? ? // 从队尾入队
push_front ? ? ?// 从队头入队
pop_back ? ? ? ?// 从队尾出队
pop_front ? ? ? // 从队头出队
clear ? ? ? ? ? // 清空队列
4.栈
stack<int> stk;
stk.push(x);
stk.pop();//弹出栈顶元素；注意。只会执行弹出操作，不会返回弹出的元素
stk.top();//返回栈顶元素x注意：
优先队列，队列，栈没有clear
清空方式：重新初始化 - q = queue<int>();
5.set ：有序集合，用红黑树实现（类似于平衡二叉树）
5.1?迭代器
set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号*解除引用，仅支持++和--两个与算术相关的操作。
设it是一个迭代器，例如set<int>::iterator it;
若把it ++，则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it --，则it将会指向排在“上一个”的元素。
5.2定义
set<int> a;//不能包含重复元素
multiset<int> b;//可以包含重复元素
定义结构体必须重载小于号
a.insert(x);
a.find(x);//x在，返回x所在的迭代器；否则，返回a.end()
a.lower_bound(x);//找到大于等于x的最小的元素的迭代器
a.upper_bound(x);;//找到大于x的最小的元素的迭代器
6.map映射(二元组)
map<int,int> a;? ? ? ? //map<key,value> name
三、算法
1.reverse 翻转
reverse(a.begin(),a.end())//注意翻转区间是一个左闭右开区间
2.unique 去重
机制：把重复的部分后移，把未重复的部分前移(不会删除重复的元素),并返回最后一个不重复元素的下一个位置的迭代器：
{1,1,2,3,3,4}? --------------->{1,2,3,4,1,3}
想要彻底去除重复元素：
a.erase(unique(a.begin(),a.end()),a.end());3.sort 排序
sort(a.begin(),a.end());//顺序
sort(a.begin(),a.end(),greater<int>())//逆序
bool cmp(int a,int b){//cmp的逻辑：a是否应该排在b的前面
? ? ? ? return a < b;
}
sort(a.begin(),a.end(),cmp);//自定义排序方式，常用于结构体排序4. lower_bound/upper_bound 二分
lower_bound的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound的用法和lower_bound大致相同，唯一的区别是查找第一个大于（没有等于）x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
如果查找的数不存在，会返回尾迭代器。
在有序int数组（元素存放在下标1 ~ n）中查找大于等于x的最小整数的下标：
int i = lower_bound(a + 1, a + 1 + n, x) - a;//返回值是迭代器类型的，但返回值的差值是int数在有序vector<int>中查找小于等于x的最大整数（假设一定存在）：
int y = *--upper_bound(a.begin(), a.end(), x);
//第一个大于x的前一个元素就是第一个小于等于x的元素