• 算法入门篇-STL之Vector，Stack，Queue,list

    这里写目录标题

    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;

    • 1
    • 2

    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，每个都是一维数组。


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    (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].

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    (3)删除元素

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

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

    • 1
    • 2
    • 3
    • 4

    (4)遍历元素

    1. 可以用数组表示法来遍历容器元素
    2. 可以用迭代器来遍历
    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;

    • 1
    • 2
    • 3
    • 4
    • 5

    (5)改变向量大小

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

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

    • 1

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

    // find / insert / erase
#include 
#include 
#include 
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    4.栈（stack）

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

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

    #include
using namespace std;
#include
#include
#include
#include

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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

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

    5.queue

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

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

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

    #include
using namespace std;
#include  //队列

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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    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 的专用成员函数

    • merge(b): 将链表b与调用链表合并，在合并之前，两个链表必须已经排序，合并后经过排序的链表被保存在调用链表中，b为空。
    • remove(val):从链表中删除val的所有节点。
    • splice(pos,b):将链表b的内容插入pos的前面，b为空
    • reverse():将链表翻转
    • sort():将链表排序
    • unique():将连续的相同元素压缩为单个元素。不连续的相同元素无法压缩，因此一般先排序后去重

    其它成员函数如下：

    • push_front(x): 将x从链表头插入
    • push_back(x): 将x从链表尾插入
    • front(): 返回链表头
    • back(): 返回链表尾
    • insert(p,t): 在p之前插入t
    • erase§: 删除p
    • clear(): 清空链表
  • 相关阅读:
    Cinemachine各组件功能介绍
    Shell sed编辑器
    PCIE下载的驱动安装
    vue3 知识点(二)
    【中国知名企业高管团队】系列49：VIVO
    ceph 删除 osd 重新添加 osd down 重建
    前端学习记录~2023.8.19~JavaScript重难点实例精讲～第7章 ES6（2）
    AlphaPose Pytorch 代码详解（一）：predict
    NoSQL的特点以及与RDBMS的区别
    【论文精度】Transformer--Attention Is All You Need
  • 原文地址：https://blog.csdn.net/m0_60343477/article/details/126842782