STL基础
STL全称为 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合;
STL由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的，
- 容器： 管理某一些对象的集合；可分为序列式容器、关联式容器、无序关联式容器、容器适配器；
- 算法： 为容器提供了执行各种操作的方式；
大部分算法都包含在头文件
<algorithm>中，少部分位于头文件<numeric>中。
-
迭代器： 对容器中的读和写都是通过迭代器完成的，迭代器可用于遍历对象集合的元素；
-
容器的分类
1. 序列式容器：
以线性顺序排列的方式存储某一指定类型的数据；元素在容器中的位置同元素的值无关，即容器不是排序的，元素的排列与元素的值无关；
主要包括：
○ vector 向量容器；
○ list 列表容器；
○ deque 双端队列容器；
2. 关联式容器：
关联式容器使用键值对（pair 类型）的方式存储数据；若已知目标元素的键，就可以直接找到目标元素的值；
根据容器内部存储的元素是否有序，又可进一步划分为：排序容器和哈希容器；
a. 排序容器：
排序容器中的元素默认是由小到大排序好的，即便是插入元素，元素也会插入到适当位置，所以其在查找时具有非常好的性能；
底层采用红黑树存储结构，适用于有序处理元素，查找元素
O
(
l
o
g
n
)
O(logn)
O(logn)；
主要包括：
○ set 集合容器；
○ multiset多重集合容器；
○ map映射容器；
○ multimap 多重映射容器；
序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。
b. 哈希容器（无序容器、无序关联容器）：
和排序容器不同，哈希容器中的元素是未排序的，元素的位置由哈希函数确定；
底层采用哈希表存储结构，适用快速查找元素
O
(
1
)
O(1)
O(1)；
主要包括：
○ unordered_set 哈希集合；
○ unordered_multiset 哈希多重集合；
○ unordered_map 哈希映射；
○ unordered_multimap 哈希多重映射；
1. 序列式容器：
1.1. vector
- 倍增思想：
操作系统中为程序分配空间时，所需时间与空间大小无关，与申请次数有关；因此vector变长数组应该尽量减少空间申请的次数，所以vector分配空间时采用倍增思想：当变长数组长度不够时，就再申请一块原来两倍大小的空间，然后再将原本的数复制过去；
- 支持随机寻址，可以直接使用数组下标访问元素；
- 支持比较运算，按字典序
#include<vector>
- 初始化
vector<int> v1; //定义一个int类型的元素
vector<int> v2(10); //定义一个长度为10的数组，默认值为0
vector<int> v3(10,1); //定义一个长度为10的数组，指定值为1
vector<int> v4[10]; //定义一个长度为10的vector，相当于二维数组
- 成员函数
vector<int> a;
a.empty(); //判断a是否为空
a.size(); //返回a的元素个数
a.clear(); //清空a的所有元素
a.push_back(); //在a的尾部添加一个元素
a.pop_back(); //移除a的尾部元素
a.front(); //返回a的第一个元素的值
a.back(); //返回a的最后一个元素的值
a.begin(); //返回第一个元素的迭代器（地址）
a.end(); //返回最后一个元素的后一个位置的迭代器
a.rbegin(); //返回最后一个元素的迭代器
a.rend(); //返回第一个元素的前一个位置的迭代器
- 数据的遍历
- 使用迭代器进行遍历
//迭代器定义
//容器类名::iterator 迭代器名
vector<int>::iterator i;
for (vector<int>::iterator i = a.begin(); i != a.end(); i++)
cout << *i << endl; //访问的是地址指针 所以要加*
//为了进一步简化书写，使用auto，auto可以根据变量的值自动推导变量的类型
for (auto i = a.begin(); i != a.end(); i++)
cout << *i << endl;
- 增强for循环（范围for循环）
在增强for循环中，不需要事先指明数组遍历起点和遍历长度，增强for循环会自动根据数组长度将数组中的每一个数据赋值给同类型的val，逐个遍历数组中每一个元素；
type iterable[n];
for(type val:iterable) //type val = arr[i]
{
// do something with val
}
vector<int> a;
for (auto i : a)
cout << i << " ";
- 随机寻址遍历
for (int i = 0; i < a.size(); i++)
cout << a[i] << endl;
1.2. pair
- 二元组，可以将两个元素组成一个新元素；
- 支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
pair<int, string> p;
p = {1, a};
cout << p.first << endl;
//输出 1
cout << p.second << endl;
//输出 a
1.3. deque
- 双端队列，可以同时在队头队尾进行插入删除；
- 支持随机访问；
#include<deque>
- 初始化
deque<int> d; //创建一个空deque
deque<int> a(10); //创建一个长度为10的deque，默认值都为0
deque<int> b(10,1); //创建一个长度为10的deque，值都为1
- 成员函数
deque<int> d;
d.empty();
d.size();
d.clear();
d.begin(); //返回第一个元素的迭代器（地址）
d.end(); //返回最后一个元素的后一个位置的迭代器
d.rbegin(); //返回最后一个元素的迭代器
d.rend(); //返回第一个元素的前一个位置的迭代器
d.push_back(int x); //在队尾插入一个元素
d.pop_back(); //弹出队尾元素
d.push_front(int x); //在队头插入一个元素
d.pop_front(); //弹出队头元素
d.front(); //返回d的第一个元素的值
d.back(); //返回d的最后一个元素的值
d.earse(); //移除一个元素或一段元素，有多个重载函数
- 遍历方式
- 迭代器
for (auto i = d.begin(); i != end(); i++)
cout << *i << endl;
- 随机寻址
for (int i = 0; i < d.size(); d++)
cout << d[i] << endl;
- 增强for循环
for (auto i : d)
cout << i << endl;
1.4. list
2. 关联式容器：
2.1. map
- 关联数组，提供一对一的数据处理，是键值对的集合，存储的都是pair数据类型；
- 键值对的键不能重复也无法修改，每个键的值都是独一无二的；
- 支持
[]，可以用键的值作为下标访问对应的值； - 会自行根据键的大小对存储的键值对进行排序；
- 对于容器中存储的每一个元素，都可以用
++和--来找自己的前驱和后继元素，时间复杂度也是 O ( l o g n ) O(logn) O(logn)；
#include<map>
- 初始化
map<string, int> m1; //创建一个空的map
map<string, int> m2 = {{"a", 1}, {"b", 2}}; //初始化好两个键值对
- 成员函数
map<string, int> m;
m.empty();
m.size(); //map中键值对个数
m.clear();
m.begin(); //返回指向m中第一个键值对的地址
m.end(); //返回指向最后一个键值对所在位置的下一个地址
m.insert(pair); //向m插入一个键值对
m.erase(); //删除指定位置或指定区域的pair
m.find(key); //查找key键，查找成功就返回其地址，否则就返回m.end()容器的最后一个位置的后一个地址;
m.count(key); //返回指定键的出现次数（因为map中键值对唯一，因此返回最大值为1，可以用于检测一个键值对是否存在）
m.at(key); //查找key键对应的值，没找到就报错
m.lower_bound(key); //返回第一个大于等于（不小于）key的键值对的迭代器
m.upper_bound(key); //返回第一个大于key的键值对的迭代器
- 数据插入
m.insert({"student_id", 111});
m["student_score"] = 360;
- 数据删除
//1. 迭代器删除
ad = m.find("student_name");
m.erase(it);
//2. 关键字删除
m.earse("student_name");
//3. 区间删除
m.earse(m.begin(), m.end());
- 数据遍历
- 迭代器
for (auto i = m.begin(); i != m.end(); i++)
cout << i->first << " " << i->second << endl; //map存储的是pari，要用pari的方式取数据
- 数组直接遍历
需要键可以按某种顺序枚举出来的情况下，用随即寻址的方式遍历整个map容器；
2.2. multimap
- 大部分特性与map相似，但是multimap可以同时存储多个相同键值对；
- 与map容器相比，multimap没有
at()成员方法； - 不支持
[]，没有重载[]运算符实现（与multimap中键值对可能不是唯一的有关）；
#include<map>
multimap<string, int> m;
m.find(key); //返回key键在m容器中出现的次数
2.3. set
- 集合set的所有插入、删除和查找操作都在 O ( l o g n ) O(logn) O(logn)内实现，效率高；基于红黑树实现，动态维护有序序列；
- 键值对的键和值要相等，因此进行操作时可以只提供value，可以看成一个是一维集合（因为key和value的值是相等的）；
- 容器中不能存在相同元素，同时set中的元素都是有序的；
- 不支持
[]； - 若要修改一个元素的值，需要先删除掉旧值，然后再重新插入新的值（为了保护set的有序性）;
- 对于容器中存储的每一个值，都可以用
++和--来找自己的前驱和后继元素，时间复杂度也是 O ( l o g n ) O(logn) O(logn)；
#include<set>
- 初始化
set<int> s;
- 成员函数
s.empty();
s.size();
s.clear();
s.begin(); //返回指向s中第一个元素的地址
s.end(); //返回指向最后一个元素所在位置的下一个地址
s.insert(val); //向s中插入一个元素
s.erase(); //删除指定位置或指定区域的value
s.find(val); //查找值为val的元素，查找成功就返回其地址，否则就返回s.end();
s.count(key); //返回指定值的出现次数（set中值不能重复，因此返回最大值为1，可以用于检测一个元素是否存在）
s.lower_bound(val); //返回第一个大于等于（不小于）val的值的迭代器
s.upper_bound(val); //返回第一个大于val的值的迭代器
- 数据插入
//1. 直接插入指定值
s.insert(1);
//2. 在指定区域插入指定值（为了维护set有序性，插入后整个set会自动重新排序，插入的位置最后可能会变）
s.insert(s.begin(), 1);
- 数据删除
//1. 删除指定值
s.earse(1);
//2. 删除指定地址上的值
s.earse(s.begin());
//3. 删除指定区间里的值
s.earse(s.begin(), s.end());
- 遍历方式
- 迭代器遍历
for (auto i = s.begin(); i != end; i++)
cout << *i << endl;
2.4. multiset
- 相比于set，multiset可以存储多个值相同的元素；
#include<set>
multiset<set> s;
s.find(1); //返回1的出现次数
3. 无序关联式容器
3.1. unordered_map
3.2. unordered_multimap
3.3. unordered_set
3.4. unordered_multiset
4. 容器适配器
4.1. stack
-
初始化
-
成员函数
-
遍历方式
4.2. queue
-
初始化
-
成员函数
-
遍历方式
4.3. priority_queue
-
初始化
-
成员函数
-
遍历方式
