【STL】容器适配器

 放在专栏【C++知识总结】，会持续更新，期待支持

1、什么是适配器？

我们生活中就存在大量的适配器，最常见的莫过于我们常见的电源适配器，它的作用就是将交流电源转化为直流电源进行输出，可以说电源适配器在电流转换之间扮演着一个轴承、转换器的角色。

1.1、适配器概念

适配器（也称之为配接器adapter）作为STL的六大组件之一，在STL中同样扮演轴承、转换器的角色。adapter这个概念实际上是一种设计模式：将一个class的接口转化为另一个class的接口，使原本因接口不兼容而不能合作的classes可以一起合作。

就比如马上就要讲的，stack的相关操作底层实际上是调用了deque的对应的函数接口，或者queue的相关操作我们也可以实现成在底层调用list的对应的接口。具有这种将一个类的接口转化成客户想要的另一个类的接口的性质的，我们称之为适配器（配接器）。

2、STL中的适配器

2.1、适配器分类

在STL所提供的各种适配器中，改变仿函数接口者，我们称之为函数适配器（function adapter）；改变容器接口者称之为：容器适配器（container adapter）；改变迭代器接口者，称之为迭代器适配器（iterator adapter）。本章我们讲的主要是容器适配器。

2.2、stack

2.2.1、stack介绍

stack是一种先进后出（FILO -> First In Last Out）的数据结构，只具有一个出入口，如下图所示：

 我们查阅文档就可以发现，stack是以deque作为其底层容器，也就是说，stack的push、pop、top等相关操作，其实底层都是调用的deque的相关接口，这也是为什么stack被归类为适配器而非容器的原因所在。至于为何采用deque作为其底层容器，本文后面会进行讲解。

2.2.2、stack使用

在使用时，我们平常并不需要修改其底层容器，只需传一个模板参数类型即可，使用时需包含头文件<stack>。如下所示：

 当然，我们也可以更换其底层容器，不过有一点需要注意的是，作为栈的底层容器必须要支持以下几个操作：

• empty        ： 判空
• size            ：有效元素个数
• back           ：尾部元素
• push_back ：尾插
• pop_back   ：尾删

因此，诸如vector、list都可以作为其底层容器：

stack的常用接口也非常的少，基本上常用的就是以上我所讲的一些。接下来我们来模拟实现一个stack。

2.2.3、stack的模拟实现

这里我们也可以按库中那样，默认以deque作为其底层容器来实现，不过这里我们换一个底层容器，用vector来实现,模拟实现也很简单，全都是用底层容器的接口来完成：

2.3、queue

2.3.1、queue的介绍

queue也是默认以deque作为其底层容器，我们平常在使用时，直接传一个模板参数T即可，当然我们也可以修改其底层容器，不过要作为queue的底层容器，必须要具有以下几个接口：

• empty         ：判断是否空
• size            ：有效元素个数
• front           ：获取头部元素
• back           ：获取尾部元素
• push_back ：尾插
• pop_front    ：头删

queue是一个先进先出（FIFO，First In Firet Out）的数据结构,其从一端插入元素，从另一端删除元素。

2.3.2、queue的使用

 queue的使用也很简单，在使用之前要包含头文件<queue>:

 2.3.3、queue的模拟实现

这里我们来模拟一个以list为底层容器的链式队列，queue的接口底层通通调用list对应的接口来实现：

 3、deque双端队列（了解即可）

3.1、deque介绍

deque是一个双端队列，可以实现在头尾两端的相关操作，并且在头尾两端的操作十分高效。与vector相比，vector虽然也可以实现在头部的操作，但实现起来比较复杂，要挪动后面的所有元素，而与list相比，由于其底层空间是连续空间，所以空间利用率要高于list，并且list不支持下标的随机访问，而deque则支持。

因此，可以说deque是集合了list与vector各自的优点（头尾高效操作+随机访问元素），但是自古以来鱼与熊掌不可兼得，deque虽集合了各自的优点，但是却做不到vector与list那么极致。deque的数据结构较为复杂，尤其是其迭代器。不过作为一个容器适配器来说，我们仅仅需要其头尾两端/或者一端的中间的插入删除相关操作。接下来我们来看一下它的结构。

3.2、deque的结构

3.2.1、deque的基本介绍

 如上图所示，deque采用map作为主控，这里的map并非STL容器中的map，这里的map是一小块连续的空间，每个元素都是一个指针（数组指针），该指针指向了一块缓冲区，这里的缓冲区用来deque存储数据。（有点类似于二维数组vector<vector<T>>）。

3.2.2、deque的迭代器

deque的迭代器设计十分复杂，如下所示：

 这里迭代器中的node指向中控器中的node节点，其first与last分别指向node指向的缓冲区的起始位置以及最后一个位置，cur则指向当前所在缓冲区的位置，++或者--进行对缓冲区内的数据遍历，当cur指针指向last位置时，此时的++或--则是指向中控器中的下一个node节点。因此我们看到deque的结构确实复杂，其遍历操作效率低下，因为每一次的++或--操作，都要检测迭代器是否指向缓冲区的两端。

3.2.3、deque的扩容机制

相比于vector，vector的扩容是分为3步走，开辟更大一块空间->将原空间数据进行拷贝->释放原有空间，这里的拷贝如果vector存储的是自定义类型，其中还要涉及深拷贝，而deque由于其中控器中存储的都是一个个的指针，因此在扩容时，仅仅只需要将其数组指针进行拷贝，这里就不存在深拷贝的问题，因为指针是内置类型，内置类型在拷贝时是值拷贝（浅），因此deque的扩容要比vector高效的多。

3.2.4、deque的随机访问

deque虽然支持随机访问，但是其效率也是不如vector的，这里假如我们第一个缓冲区已经存在了3个数据，且每一个缓冲区的大小固定为10，这里我们要想实现访问第25个数据，在vector中则只需要vector[24]即可访问到该数据，而在deque中则需要：1、先找到其所在的缓冲区。2、再找到在缓冲区的第几个位置。

这里则是（25-3）/10：找到在第几个缓冲区，（25-3）%10，找到其在缓冲区的第几个位置。我们可以看到，缓冲区的大小会影响其随机访问的效率，所以在SGI版本下，为了提高随机访问的效率，其缓冲区的大小都是固定不变的。

 3.2.5、为什么采用deque作为stack与queue的默认底层容器？

这是因为对于stack来说，只要具有尾部操作的容器都可以作为其底层容器，比如list与vector，而queue只要具有头尾两端相关操作的容器，都可以作为其底层容器，诸如list。但是这里为何要采用deque呢？因为首先，deque的两端操作都很高效，达到了O(1)的时间复杂度，再接着deque的扩容也要比vector更加高效，并且空间由于是连续的，所以空间利用率要高于list。虽然说deque的遍历，以及在中间位置相关操作的效率不如list与vector，但是stack与queue并不需要遍历的相关操作，也不需要在中间位置插入删除，仅仅只需要其两端操作。所以deque作为其默认底层容器，完美的避开了deque的所有缺点，而又很好的利用了其优点。

end.

生活原本沉闷，但跑起来就会有风！🌹