1.介绍STL

容器通用函数如下：

.size():容器内的元素个数，无符号整型
.empty():判断容器是否为空，返回一个bool值
.front():返回容器第一个元素
.back():返回容器最后一个元素
.begin():指向容器第一个元素的指针。
.end():指向容器最后一个元素的下一个位置的指针
.swap(b):交换两个容器的内容
::iterator:迭代器

2.迭代器

迭代器是一个广义的指针，有时候可以认为他就是一个指针。模板使算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。

for(vector<int>::iterator it=a.begin();it!=a.end();it++)
	cout<<*it<<endl;

3.vector

vector（向量）是一个封装了动态大小数组的顺序容器（Sequence Container)。顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素，支持数组表示法和随机访问。vector使用一个内存分配器动态处理存储需求。使用的时候加上头文件#include < vector>

(1)初始化
vector为什么叫容器，因为它可以存放各种类型的对象，可以是C++标准数据类型，也可以是结构体类型。

vector<int>a;    //创建一个数组，类型是int,数组名是a
vector<int>a(100);  //创建一个数组a，元素个数是100个，初始值都是0
vector<int>a(10,666);   //创建一个数组a，元素个数是10，所有的元素都被初始化为666.
vector<int>b(a);     //创建一个数组b，将其初始化为a，这里面的实现是一个函数来实现复制。
vector<int>b(a.begin()+3,a.end()-3);   //创建一个数组b，然后将数组a的区间为[a.begin()+3,a.end()-3]的元素复制到b。

//上面是创建一维数组，那么创建二维数组
vector<int>a[5];  //相当于创建了5个vector，每个都是一维数组。

(2)增加元素

往vector添加元素既可以加在后面，也可以加在中间，非常自由。但是效率很低。因为如果加在中间，那么以中间为起点往后面的所有元素都需要向后面移动。

a.push_back(5);  //在向量尾部增加一个元素5
a.insert(a.begin()+1,10);  //在a.begin()+1指向元素前插入一个10.
//也就是说，先将a.begin()后面的所有元素向后移动一个单位，这个时候a.begin()+1的位置空出来
//最后将插入的元素插入a.begin()+1的位置即可
a.insert(a.begin()+1,5,10);  //在a.begin()+1指向的元素前插入5个10.
//也就是说，a.begin()后面的所有元素整体往后面移动5个单位（4个字节（int））
//这个时候，区间[a.begin()+1,a.begin()+5]是空出来的（相当于空出来，实际上
//不是空的，是前面移动的元素的值）。最后将需要插入的元素插入即可。
a.insert(a.begin()+1,b,b+3);   //将数组b下标[0,3]区间的元素插入到[a.begin()+1,a.begin()+4].

(3)删除元素

同增加一样，可以任意删除区间，位置的元素，当然，与增加元素类似。删除元素后，剩下的元素会紧密排列。

a.pop_back(); //删除向量中最后一个元素。
a.erase(a.begin()+1);    //删除指定位置的元素
a.erase(a.begin()+3,a.end()-3);   //删除区间的元素。
a.clear();  //清空vector

(4)遍历元素

可以用数组表示法来遍历容器元素
可以用迭代器来遍历

for(int i=0;i<a.size();i++)
	cout<<a[i]<<endl;

for(vector<int>::iterator  it=a.begin(),it<a.end();it++)
	cout<<*it<<endl;

(5)改变向量大小

resize可以改变当前向量的大小，如果它比当前向量大，则填充默认值；如果比当前小，则舍弃后面的部分。

a.resize(5);  //如果a里面有10个元素，则后面5个元素舍弃。

(6)find
find(begin,end,target)//在区间[begin.end]寻找target，返回找到的位置
下面用一个例子解释find，erase，insert函数

// find / insert / erase
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));  //想一想为什么需要使用sizeof(a)/sizeof(int)形式
	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);   //pos指向3所在的位置
 
	// 在pos位置之前插入30
	v.insert(pos, 30);
	vector<int>::iterator it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据
	v.erase(pos);
	it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

4.栈（stack）

栈的特性就是先进后出，后进先出。在STL中，栈也是这样，只能对栈顶进行操作。需要头文件#include< stack>

stack<int> s;   //创建一个栈，类型是int
s.push(x);   //x入栈
s.pop();  //将栈顶元素出栈
s.top();   //取栈顶
s.empty();   //判断栈是否空，如果是空的，返回true
s.size();   //求栈大小

给一个例题来复习stack的使用
web导航

#include<iostream>
using namespace std;
#include<stack>
#include<cstring>
#include<string>
#include<cstdio>

int main()
{
	stack<string>backward;   //后向栈
	stack<string>forward;   //前向栈
	string c="NULL";   //初始化
	string cur = "http://www.acm.org/";   //初始值
	while (cin >> c && c != "QUIT")  //当C为QUIT的时候退出循环。
	{
		if (c == "VISIT")    //查看新网页
		{
			backward.push(cur);  //先将上一个网页入栈保存下来，
			cin >> cur;    //输入要查看的网页
			cout << cur << endl;   //输出网页
			while (!forward.empty())
				forward.pop();
		}
		else if(c=="BACK")
		{
			if (backward.empty())
				cout << "Ignored"<<endl;
			else
			{
				forward.push(cur);
				cur = backward.top();
				backward.pop();
				cout << cur << endl;
			}
		}
		else
		{
			if (c == "FORWARD")
			{
				if (forward.empty())
					cout << "Ignored"<<endl;
				else
				{
					backward.push(cur);
					cur = forward.top();
					cout << cur << endl;
					forward.pop();
				}
			}
		}
	}
	return 0;
}

下面是这个题目的图解：现在没时间，之后再贴上（2022，9.14. 19.05）

5.queue

队列的特点是先进先出，后进后出。
图解：
待补

queue<int>q:创建一个队列，队列的元素类型是int
push(x):x入队
pop():出队
front():取队头
empty():判断队列是否为空，若为空，返回true
size():求队列大小，返回元素个数

一个简单的例题复习队列
骑士移动

#include<iostream>
using namespace std;
#include<queue>  //队列

typedef struct
{
	int x;
	int y;
	int step;
}Move;   

 //8个方位的移动
int dx[8] = { -2,-2,-1,-1,1,1,2,2, };
int dy[8] = { 1,-1,2,-2,2,-2,1,-1 };
const int Max = 1000;
int map[Max][Max];

bool visit[Max][Max];  //记录走过的地方
int main()
{
	int N;
	cin >> N;
	while (N--)
	{
		memset(visit, false, sizeof(visit));
		int L;
		cin >> L;   //输入地图大小
		Move start, end;  //骑士开始的位置和终点位置
		Move now;   //当前位置
		queue <Move>q;   //创建一个队列
		q=queue<Move>();   //清空队列
		cin >> start.x >> start.y;    //输入开始位置
		cin >> end.x >> end.y;    //输入终点位置
		if (start.x == end.x && start.y == end.y)    //如果开始位置就是终点位置
		{
			cout << "0\n";
			continue;
		}
		
		start.step = 0;   //开始位置的步数为0
		q.push(start);  //起点入队
		visit[start.x][start.y] = 0;   //起点理所应当只能走一次，所以预先标记
		int x, y,step=0;
		while (!q.empty())
		{
			int break_break = 0;   //后面可能用得到
			start = q.front();  //队头取出来
			q.pop();  //然后弹出队头
			x = start.x;
			y = start.y;
			step = start.step;   //step就是从起点走到当前位置的所走步数

			for (int i = 0; i < 8; i++)  //以弹出的队头为中心，扩展四周
			{
				int tx = x + dx[i];
				int ty = y + dy[i];
				if (tx == end.x && ty == end.y)  //到达终点
				{
					step++;
					cout << step << endl;
					break_break = 1;
					break;
				}
				if (tx >= 0 && tx < L && ty >= 0 && ty < L && !visit[tx][ty])  //该位置没有越界且没有被走过
				{
					now.x = tx;
					now.y = ty;
					now.step = step + 1;
					q.push(now);
					visit[tx][ty] = true;   //记得标记这个位置走过了
				}
			}
			if (break_break == 1)
				break;
		}
		
		
	}
	return 0;
}

6.list

list是一个双向链表，可以在常数时间内插入和删除，不支持数组表示法和随机访问。使用时需要引入头文件#include< list>

list iterator的使用
函数声明接口说明
begin() 返回第一个元素的迭代器
end() 返回最后一个元素下一个位置的迭代器
rbegin() 返回第一个元素的reverse_iterator,即end位置
rend() 返回最后一个元素下一个位置的reverse_iterator,即begin位置
cbegin() (C++11) 返回第一个元素的cosnt_iterator
cend() (C++11) 返回最后一个元素下一个位置的const_iterator
crbegin() (C++11) 即crend()位置
crend() (C++11) 即crbegin()位置

list 的专用成员函数