31. STL适配器与迭代器详解

1.适配器

所谓适配器,就是将本来并不合适的东西,变得能让我们使用。

比如手机的充电器,家用电压一般为220V,而手机一般用5V的,或10多V的,直接连上去肯定不行, 所以就有了充电器,也叫电源适配器,它可以将本来为220V的电源,降压到我们能够使用的范围。

这里的容器适配器也是同理。

比如我们最常见的stack,栈就是一个容器适配器,它默认使用的是前面我们讲的deque容器,封装大量的无用函数,暴露出一些栈可以使用的函数,就成为了栈。

2.stack

可以看到源代码中的定义,其默认使用的容器就是deque

image-20240131221722553

简单来说,stack这个类本身并没有做什么事情,它仅仅只是调用了一些deque中的函数,就实现了我们常用的栈。

所谓栈,主要原理就是后入的先出。

比如当你向栈中推入1 2 3 4 5时,如果你想要取出数据,那就只能按5 4 3 2 1 这个顺序取,不允许随即访问里面的数据。

一般来说我们都是采用的默认容器:

#include<iostream>
#include<stack>
using namespace std;
int main() {
	stack<int> s;
	s.push(10);//向栈中推入数据
	cout<<s.top(); //获取栈顶数据
	s.pop(); //删除栈顶数据
	s.empty(); //判断当前栈是否为空
	s.size(); //获取当前元素个数

}

对于栈来说, 它的操作就上面几个,非常简单,主要是自己理解好它的逻辑。

当你调用函数的时候,参数传递就用的栈,在文本编辑器中,你写错了,要撤回,用的也是栈,栈的用途非常多。

3.queue

接下来是队列,使用的也非常频繁,它同样是一个容器适配器:

image-20240131221830548

可以看到, 它的底层同样也是用的deque,一般我们也采用默认即可。

队列与栈刚好相反,是先入的先出,就跟我们排队一样,先来的肯定要先办完事走,不能插队。

比如当我们用各种网盘下载资源的时候,一旦资源数量过多,就得排队,先点击下载的,肯定要先被下载,后面的都按一定顺序进行排序。

它同样很简单,主要是理解它的逻辑:

#include<iostream>
#include<queue>
using namespace std;

int main() {
	queue<int> q;
	q.push(10); //推入数据进行排队
	q.front(); //处理队头的数据
	q.pop();//删除队头的数据
	q.size(); //数据的个数
	//q.back(); 可以处理队尾的数据
	q.empty(); //判断是否为空
}

4.priority_queue

除了上面的先进先出的队列,还有这里的优先级优先的队列。

即每个元素是否被首先处理,取决于这个元素的优先级,并不是谁先来就能先被处理。

它默认使用的是vector容器:

image-20240131221957312

还可以看到它有第三个模板变量,看名字就是前面用的排序,为升序排序。

说白了,就是你往这个队列中推入数据的同时,它还会选择优先级最大的移动到队头,而它默认采用的是从大到小排序,即每次又将最大的移动到队头。

使用起来与queue基本一致:

#include<iostream>
#include<queue>
using namespace std;

int main() {
	priority_queue<int> q;
	q.push(10);
	q.push(5);
	q.push(7);
	q.push(40);
	
	while (!q.empty())
	{
		cout << q.top() << endl;
		q.pop();
	}
}

也可以参考前面关联式容器的自定义排序,自定义排序规则。

5.迭代器

迭代器在编程语言中是一个非常普遍的概念,它和上面的适配器很像,是为了抹平底层差异、提供外部方便使用的接口。

比如最简单的两个数据结构:数组与链表。

由于其底层存储数据的结构不同,导致我们想要遍历这两个数据结构内部的元素的方式不同。

而迭代器的作用就在于此,它可以抹平其底层的实现差异,提供给我们统一使用的接口。

6.反向迭代器

正向迭代器比较简单,就是begin与end这两个函数分别返回结构的开始与结束,使我们可以遍历其内的所有元素。

所以这里直接介绍反向迭代器,我们前面曾今用过,就是用来逆序输出的,比如list:

#include<iostream>
#include<list>
using namespace std;
int main() {
	list<int> ls{ 1,2,3,4,5 };

	for (auto i = ls.rbegin(); i != ls.rend(); i++) {
		cout << *i << endl;
	}
}

rbegin函数返回的是reverse_iterator<list<int>::iterator>类型,看起来非常长。

实际是一个reverse_iterator模板类型,其模板参数为list<int>的迭代器iterator

它的作用就是将原本应该做--操作的反向迭代器,实现了用++来完成。

7.插入迭代器

插入迭代器,看名字就知道是用来插入值的,它有三种类型:

插入适配器 作用
back_insert_iterator 在指定容器的尾部插入新元素,但前提必须是提供有 push_back() 成员方法的容器(包括 vector、deque 和 list)
front_insert_iterator 在指定容器的头部插入新元素,但前提必须是提供有 push_front() 成员方法的容器(包括 list、deque 和 forward_list)
insert_iterator 在容器的指定位置之前插入新元素,前提是该容器必须提供有 insert() 成员方法

老实说,并不常用,毕竟容器已经提供了相应的函数,何必又多此一举的封装一步呢。

不过使用这个插入迭代器后,插入值确实更加方便了,所以下面直接用一段代码演示一下它的使用流程:

#include<iostream>
#include<list>
using namespace std;
int main() {
	list<int> ls;

	front_insert_iterator<list<int>> f(ls); //给list类型的ls变量创建一个前插入迭代器

	f = 10; //插入前部
	f = 20; //插入前部
	f = 30; //插入前部