C++ 容器适配器

文章目录

1. 适配器
2. stack和queue
- 2.1 deque
- - 2.1.1 deque的底层结构
  - 2.1.2 deque如何实现头插和随机访问
- 2.2 用deque实现栈和队列
- 2.3 deque的优缺点
3. priority_queue

1. 适配器

适配器是什么？
适配器是一种设计模式，实质上就是一种复用，即将一个类的接口，转换成客户希望的另外一个接口。

本篇博客将通过stack、queue、priority_queue这三种容器适配器， 来详细阐释容器适配器这种设计模式。

2. stack和queue

在C++ stl中，stack和queue在底层都是复用deque来实现的。

以下对deque进行简单的介绍。

2.1 deque

我们知道，list 的优点在于任意位置插入和删除数据，缺点则是每次插入都需要去申请资源(new的耗费是极大的)；vector的优点在于支持下标的随机访问，缺点是insert和erase需要挪动数据，耗费很大。

通过上述分析，我们可以看到两种容器各有优缺点，于是有人就想，能不能综合一下两者的优点，设计出一种更好的容器呢？所以，deque应运而生，但现在来看，deque的设计并不能说是成功的。

2.1.1 deque的底层结构

deque的底层结构相对而言，还是比较复杂的。
它的底层并非一段连续空间，而是多段较小连续空间，有点类似动态的二维数组。所以，双端队列的底层实际是分段连续的。

双端队列的底层结构如下图所示：

在这里插入图片描述
结合下图，能更好地理解：

在这里插入图片描述
具体的说明如下：

双端队列的核心在于其底层的中控数组map。map实质上是一个指针数组，其中每个指针都指向一段连续空间的开始位置。
双端队列的迭代器设计也很特殊。它的迭代器中有四个成员变量——first指向某段连续空间的开始位置,last指向这段连续空间的结束位置，cur为当前连续空间遍历到的位置，node则是指向map中的某个位置，所以实际上node是一个二级指针。
通过迭代器和中控器，既能将某段连续空间管理好，同时又能便捷切换到下一段连续空间， 这样就将实际分段的连续空间虚拟地连续在了一起。

实际使用时，last可由first计算得来，因为每一段连续空间中存储的数据个数是规定好的，再结合具体的数据类型，即可由first计算出last。

刚开始使用时，deque中只有一段连续的空间，随着数据不断插入，当cur == last时，便会再申请一段连续的空间，然后通过node,将first,last,cur都切换到这段新申请的连续空间上（node一般指向中控数组中，当前这段空间起始位置所对应的指针，故 node + 1 对应新开辟的连续空间起始位置所对应的指针）。

不过，中控数组也是有一定大小的，所以当中控数组满容后，也是需要扩容的，这个扩容是正常的数组扩容。

2.1.2 deque如何实现头插和随机访问

在这里插入图片描述

deque的头插，需要再开一段连续的空间，然后将start中的first指向这段空间的开始，last指向这段空间的结束，cur指向这段空间最后一个元素的位置，再将node - 1赋值给node。
在这样的设计下，每次头插都要 cur-- ，而这段空间的终止条件则为 cur != first,与尾插刚好相反，但实现了头插的空间复杂度为O(1)。

在这里插入图片描述

那么，如何实现随机访问呢？

这要分两种情况来讨论：

如果没有头插或者因头插开辟的数组为满。记下标为 i ,记每段连续空间的元素个数为buffer_size那么通过 i / buffer_size来确定在第几段连续空间，通过 i % buffer_size来确定是那段连续空间的哪个位置，这样就能正常访问到相应元素。
如果头插开辟的数组未满。那么将下标i更换成，头插开辟的数组满时对应的下标，即 i 需要加上一个此数组中还能插入的元素个数，这样就能将 i 按照情况1中进行处理，从而访问到相应元素。

2.2 用deque实现栈和队列

此处不过多赘述，栈和队列的相关接口都是复用deque的接口以实现的。

在这里插入图片描述

2.3 deque的优缺点

其实，博主个人认为deque不能说是vector与list的综合，本身deque就是一个不成功的缝合怪，个人觉得，deque更像是对vector的优化——能够实现下标随机访问，同时头插相比vector的效率更高，也没有像vector那样，2倍或1.5倍扩容，因此浪费空间较少，但是deque仍然没有实现高效率的任意位置的插入和删除(仍然需要挪动数据)，并不具备list那样的优势。