STL(标准模板库) 简介
STL 简介： STL(Standard Template Library) 标准模板库，是“容器”的集合。
STL 中常见的集合有：向量 (vector)、 栈 (stack)、 队 列 (queue)、 优先队列 (priority queue)、 链表 (list)、 集合 (set)、 映射 (map) 等容器。
C++标准模板库的核心包括以下三个组件：
| 组件 | 描述 |
|---|---|
| 容器(Containers) | 容器是用来管理某一类对象的集合。C++提供了各种不同类型的 容器，比如deque、list、vector、map等。 |
| 算法(Algorithms) | 算法作用于容器。它们提供了执行各种操作的方式，包括对容器 内容执行初始化、排序、搜索和转换等操作。 |
| 迭代器(iterators) | 迭代器用于遍历对象集合的元素。这些集合可能是容器，也可能 是容器的子集。 |
STL内的所有组件都由模板(template)构成，其元素可以是任意类型。
1 向量(vector)
1.1 什么是vector
向量 (vector) 是一个顺序容器 (Sequence Container),它能够存放各种类型的对象。
可以简单的认为， 向量是一个能够存放任意类型的动态数组(元素个数可变)。
1.2 vector的常见函数
| 函数名 | 函数说明 |
|---|---|
| push_back(元素) | 增加一个元素到向量后面 |
| insert(位置，元素) | 插入元素到向量的指定位置 |
| insert(位置，个数n,元素) | 插入n个相同的元素到指定位置 |
| insert(位置，向量头指针 first,向量尾指针end) | 将另一个向量从first位置开始到end结束(不包括end)之间的内容 插入该向量的指定位置。 |
| erase(位置) | 删除指定位置的元素 |
| erase(开始位置，结束位置 ) | 删除向量中(first,last)中元素 |
| pop_back() | 弹出(删除)向量的最后一个元素 |
| clear() | 清除向量所有元素，size()变为0 |
| 运算符[i] | 取向量下标为i的元素 |
| front() | 取向量第一个元素 |
| back() | 取向量最后一个元素 |
| begin() | 返回向量头指针(迭代器),指向第一个元素 |
| end() | 返回向量尾指针，指向向量最后一个元素的下一个位置 |
| rbegin() | 反向迭代器，指向最后一个元素 |
| rend() | 反向迭代器，指向第一个元素之前的位置 |
| size() | 返回向量中实际元素的个数。 |
| resize(大小) | 重新设定向量的大小，也就是可以保存元素的个数。 |
| max_size() | 得到vector最大可以是多大。 |
| empty() | 判断向量是否为空，等价于size()为0。 |
| swap() | 交换两个同类型向量的数据。 |
对应于数组，要注意：向量的大小是可变的，开始时向量为空，随着不断插入元素，向 量自动申请空间，容量变大。
注意学会使用： sort()、reverse()等函数对vector进行排序、逆序等操作。
1.3 例子：vector的存储和遍历
注意掌握 vector构造的4个常见方法：
(1)vector():创建一个空 vector
(2)vector(n):创建一个元素个数为 n 的 vector
(3) vector(n,t):创建一个元素个数为 n 且值为 t 的 vector
(4)vector(begin,end):复 制(begin,end)区间内另一个数组的元素到 vector中
#include<bits/stdc++.h>
using namespace std;
void print(vector<int> v) {
//遍历 vector 中的元素
for(int i=0; i<v.size(); i++) {
//vector: 可以使用下标访问，但不能越界
cout<<v[i]<<" ";
}
}
int main() {
//定义方法一：定义 vector 存储 int 类型的变量
//vector<int> v;
//size(): 获取 vector 存储元素的个数
//cout<<v.size()<<endl;
//注意：常见错误， vector<int>v 定义一个空 vector, 不可以用下标θ和1来访问元素
//v[0]=10;
//v[1]=20;
//v.push_back(10);
//v.push_back(20);
//v.push_back(30);
//cout<<v.size()<<endl;
//print(v);
//定义方法二：定义一个长度为5的 vector, 默认值为0
//vector<int> v(5);
//定义方法三：定义长度为5的 vector, 默认值为80
//vector<int> v(5,80);
//定义方法四：使用数组初始化 vector
int a[]={10,20,30,40,50};
//sizeof(): 计算变量占用的字节数
//sizeof(a)/sizeof(int): 计算数组的实际长度
cout<<sizeof(a)/sizeof(int)<<endl;
vector<int> v(a,a+sizeof(a)/sizeof(int));
v.push_back(10);
print(v);
return 0;
}
1.4 例子：vector的插入、删除、获取头尾元素
#include<bits/stdc++.h>
using namespace std;
void print(vector<int> v) {
//遍历 vector 中的元素
for(int i=0; i<v.size(); i++) {
//vector:可以使用下标访问，但不能越界
cout<<v[i]<<" ";
}cout<<endl;
}
int main() {
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
cout<<"第一个元素："<<v.front()<<" "<<*v.begin()<<endl;
cout<<"最后一个元素："<<v.back()<<endl;
print(v);
//insert(位置,元素):位置必须提供位置指针
//向 vector 中下标为1的位置插入元素100
v.insert(v.begin()+1,100);
print(v);
//向 vector 中 下 标 为 1 的 位 置 插 入 5 个 1 0 0
v.insert(v.begin()+1,5,100);
print(v);
vector<int> v2;
v2.push_back(100);
v2.push_back(200);
v2.push_back(300);
//向 vector 下标为1的位置插入 v2 中下标为1到最后的所有元素
v.insert(v.begin()+1,v2.begin()+1,v2.end());
print(v);
//删除 vector 中下标为1的元素
v.erase(v.begin()+1);
print(v);
//从向量中下标为1的元素开始删除到最后
v.erase(v.begin()+1,v.end());
print(v);
return 0;
}
1.5 例子: resize()、swap()、sort()、reverse() 函数
#include<bits/stdc++.h>
using namespace std;
void print(vector<int> v) {
//遍历 vector 中的元素
for(int i=0; i<v.size(); i++) {
//vector: 可以使用下标访问，但不能越界
cout<<v[i]<<" ";
}
cout<<endl;
}
int main() {
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
vector<int> v2;
v2.push_back(100);
v2.push_back(300);
swap(v1,v2);
cout<<"v1:";
print(v1);
cout<<"v2:";
print(v2);
int a[]= {5,3,1,4,2};
vector<int> v(a,a+5);
sort(v.begin(),v.end());
print(v);
reverse(v.begin(),v.end());
print(v);
//重置 vector的大小为20
v.resize(2);
print(v);
return 0;
}
1.6 例子：二维 vector
#include<bits/stdc++.h>
using namespace std;
int main() {
//定义二维 vector
vector<vector<int>> v;
for(int i=0;i<5;i++) {
//需要先建立一个一维的vector，紧接着push_back
vector<int> temp;
for(int j=0;j<5;j++) {
temp.push_back(i+j);
}
v.push_back(temp);
}
//输出
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
cout<<v[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
2 栈(stack)
2.1 什么是栈
栈是一种后进先出 (First in last out, 简称 FILO 或者LIFO) 的元素序列，访问和删除都只能 对栈顶的元素(即最后一个被加入栈的元素)进行，并且元素也只能被添加到栈顶。栈内的 元素不能访问。如果一定要访问栈内的元素，只能将其上方的元素全部从栈中删除，使之变 成栈顶元素才可以。
stack 容器有广泛的应用。例如，编辑器中的 undo (撤销)机制就是用堆栈来记录连续的变化。 撤销操作可以取消最后一个操作，这也是发生在堆栈顶部的操作。
2.2 栈的常见函数
| 函数名 | 函数说明 |
|---|---|
| push(元素) | 入栈 |
| pop() | 出栈 |
| top() | 返回栈顶元素 |
| size() | 返回元素个数 |
| empty() | 判断栈是否为空 |
2.3 栈的存入和遍历
#include<bits/stdc++.h>
using namespace std;
int main() {
// stack<int> s;
// s.push(10);//入栈
// s.push(20);
// s.push(30);
// cout<<s.top()<<endl;
// s.pop();// 出栈
// cout<<s.top()<<endl;
/*
向栈中存入元素，直到遇到-1结束
*/
stack<int> s;
int x;
while(1){
cin>>x;
if(x==-1) break;
s.push(x);
}
//将元素逐个访问(将元素逐个弹出)
while(s.empty()==false) {
cout<<s.top()<<endl;// 获取栈顶元素
s.pop();//弹出栈顶元素
}
return 0;
}
3 队列(queue)
3.1 什么是队列
queue: 就是“队列”。
队列是先进先出的(First in first out), 队头的访问和删除操作
只能在队头进行，添加操作只能在队尾进行。不能访问队列中间的元素。
特点：先进先出 (FIFO), 队尾进，队头出。
3.2 队列的常见函数
| 函数名 | 函数说明 |
|---|---|
| push(元素) | 进队，从队尾入队 |
| pop() | 出队，从队头出队 |
| front() | 返回队头元素 |
| back() | 返回队尾元素 |
| size() | 返回队列中元素个数 |
| empty() | 判断队列是否为空 |
3.3 队列的存储与遍历
#include<bits/stdc++.h>
using namespace std;
int main() {
// queue<int> q;
// //i入队：从队尾入
// q.push(10);
// q.push(20);
// q.push(30);
// //打印队头、队尾
// cout<<q.front()<<" "<<q.back()<<endl;
// //出队：从队头出
// q.pop();
// cout<<q.front()<<" "<<q.back()<<endl;
queue<int> q;
int x;
while(1) {
cin>>x;
if(x==-1)break;
q.push(x);// 入队
}
//访问队列元素：相当于将队列元素一直弹出，直到队列为空
while(q.empty()==false) {
cout<<q.front()<<endl;
q.pop();// 出队
}
return 0;
}
迭代器
1.1 什么是迭代器
迭代器(iterator): 用来指向、遍历、修改容器元素的变量，类似指针。
A、可遍历STL 容器内全部或部分元素的对象
B、指出容器中的一个特定位置
| 操作 | 效果 |
|---|---|
| * | 返回当前位置上的元素值。 |
| ++ | 将迭代器前进至下一元素 |
| ==和!= | 判断两个迭代器是否指向同一位置 |
| = | 为迭代器赋值(将所指元素的位置赋值过去) |
1.2 迭代器函数
| 操作 | 效果 |
|---|---|
| begin() | 返回一个迭代器，指向第一个元素 |
| end() | 返回一个迭代器，指向最后一个元素之后 |
#include<bits/stdc++.h>
using namespace std;
int main() {
char s[]="hello stl";
char *p;//&s &s[0]
//p 是一个指向字符数组的指针，相当于一个迭代器
for(p=s;*p!='\0';*p++){
//p 是指针，指向数组的不同位置，*p 是元素
cout<<*p<<"";
}cout<<endl;
int a[]= {10,20,30,40,50};
vector<int> v(a,a+5);
//定义迭代器，命名为 it
vector<int>::iterator it;
//迭代器指向 vector<int> 的首元素
it=v.begin();
(*it)++;
cout<<*it<<" "<<v[1]<<endl;
//利用迭代器循环遍历 vector
cout<<"迭代器遍历 vector:";
for(it=v.begin();it<v.end();it=it+2) {
cout<<*it<<" ";
}
cout<<endl;
//利用迭代器反向遍历 vector
vector<int>::reverse_iterator rit;
cout<<"反向迭代器遍历：";
for(rit=v.rbegin(); rit!=v.rend(); rit++) {
cout<<*rit<<" ";
}
cout<<endl;
return 0;
}
1.3 迭代器分类
常用的迭代器按功能强弱分为： 输入、输出、正向、双向、随机访问五种，这里只介绍常用 的三种。
不同容器的迭代器，其功能强弱有所不同。例如，排序算法需要通过随机访问迭代器来访问 容器中的元素，因此有的容器就不支持排序算法。
A、 正向迭代器。
假 设 p 是一个正向迭代器，则 p 支持以下操作：++p,p++,*p。
此外，两个正向迭代器可以互相赋值，还可以用=和!=运算符进行比较。
B、 双向迭代器。
双向迭代器具有正向迭代器的全部功能。
双向迭代器p 支持-p 和 p--, 使得 p 朝和++p 相反的方向移动。
C、 随机访问迭代器。
随机访问迭代器具有双向迭代器的全部功能。
随机访问迭代器p 还支持以下操作：
> p+=i: 使得 p 往后移动 i 个元素。
> p-=i: 使得 p 往前移动 i 个元素。
> p+i: 返 回 p 后面第 i 个元素的迭代器。
> p-i: 返 回 p 前面第 i 个元素的迭代器。
> p[i]: 返回 p 后面第 i 个元素的引用。
> 两个随机访问迭代器 p1、p2 还可以用く、>、<=、>=运算符进行比较。 pl<p2 的含义是： p1 经过若干次(至少一次)++操作后，就会等于 p2。
表 达 式p2-p1 表示迭代器 p2 所指向元素和迭代器 p1 所指向元素的序号差 (p2 和 pl 之间的元素个数减一)。
1.4 不同容器支持的迭代器
| 容器 | 迭代器类别 |
|---|---|
| vector | 随机 |
| deque | 随机 |
| list | 双向 |
| set/multiset | 双向 |
| map/multimap | 双向 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
| priority queue | 不支持迭代器 |
STL 容器的通用操作
1 与大小相关的操作
size() 一返回当前容器的元素数量
empty() 一判断容器是否为空
max size() 一返回容器能容纳的最大元素数量
2 比较
==,!=,<,<=,>,>=
比较操作两端的容器必须属于同一类型
如果两个容器内的所有元素按序相等，那么这两个容器相等
采用字典式顺序判断某个容器是否小于另一个容器
3 元素操作
insert(pos,e) 一 将元 素e 的拷贝安插于迭代器 pos 所指的位置
erase(beg,end) 一移除[beg,end] 区间内的所有元素
clear()一移除所有元素
4 赋值和交换
swap- 用于交换元素
5 与迭代器(iterator)相关的操作
(容器需支持迭代器)
begin()一返回一个迭代器，指向第一个元素
end()一返回一个迭代器，指向最后一个元素之后
rbegin() 一返回一个逆向迭代器，指向逆向遍历的第一个元素
rend()一返回一个逆向迭代器，指向逆向遍历的最后一个元素之后