男鞋 东莞网站建设,软件技术 网站建设教程,网站开发费用摊销年限,投简历的平台#x1f431;作者#xff1a;一只大喵咪1201 #x1f431;专栏#xff1a;《C学习》 #x1f525;格言#xff1a;你只管努力#xff0c;剩下的交给时间#xff01; 栈 | 队列 | 优先级队列 | 反向迭代器#x1f63c;容器适配器#x1f648;什么是适配器#x1f64… 作者一只大喵咪1201 专栏《C学习》 格言你只管努力剩下的交给时间 栈 | 队列 | 优先级队列 | 反向迭代器容器适配器什么是适配器STL标准库中stack和queue的底层结构简单了解dequestack模拟实现queue模拟实现priority_queue仿函数(函数对象)模拟实现反向迭代器总结这篇文章主要讲解的是栈和队列以及优先级队列的模拟实现要像模拟实现必须先了解容器适配器。容器适配器
什么是适配器
适配器是一种设计模式设计模式是指一套反复使用的多人知晓的经过分类编目的代码设计经验的总结。
我们之前就接触过一种设计模式叫做迭代器再加上现在的适配器一共是两种设计模式。 迭代器不暴露底层细节封装后提供统一的方式访问容器的一种模式。适配器将一个类的接口转换成客户希望的另外一个接口的模式。 就像我们生活中使用的电源适配器一样已经有的接口是家里的插口它是220V的而我们经常使用的电子设备用到的电压远没有这么高所以就需要将电压进行转换转换成我们能用的低电压。
比如手机充电器它就将220V电压转换到了手机能承受的低电压。
STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和queue列只是对其他容器的接口进行了包装。 红色框中的是容器类型也就是被改造容器栈和队列使用的容器是双端队列(deque)优先级队列使用的是vector。栈和队列就是将这些已有容器的接口进行改造符合我们的要求这种改造容器出来的结构就是容器适配器。
简单了解deque deque(双端队列)是一种双开口的连续空间的数据结构。可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 这是它的成员函数。 它的逻辑结构如上图所示但实际上并不是连续的空间而是由多段连续的小空间拼接成的。 中控指针数组中存放着多段小连续数组空间的地址所以它是一个指针数组。 连续数据空间的地址是从中控数组的中间位置开始存放的之后开辟的小连续数组空间的地址向右或者向左存放。 当小连续数组被放满数据以后就会开辟新的小连续数组。如果是尾插则将新的小连续数组的指针放在中控指针数组中间位置的右边并且将元素从小连续数组的头部开始插入直到满了。如果是头插则将新的小连续数组的指针放在中控指针数组中间位置的坐标并且将元素从小连续数组的尾部开始插入直到满了。 当中控指针数组存满数据以后就会将中控指针数组进行扩容用了存放更多小连续数组的指针。
大概知道了它的存储结构以后将deque与vector和list作个对比。
与vector比较deque在头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素只需要搬移指针就行因此其效率是比vector高的。与list比较deque的底层是连续空间空间利用率比较高高速缓存命中率高而且不需要存储额外字段最重要的是deque支持下标随机访问。 但是deque有一个致命缺陷不适合遍历。因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下。除此之外在使用下标随机访问时还需要根据下标计算出这个下标在哪个小连续数组中有一定的消耗速度没有vcetor快。而且在中间插入删除时虽然没有挪动大量的数据但也是有一定的消耗速度没有list快。 虽然deque结合了vector和list的优点但是都没有做到vector和list那么极致所以在实际中需要线性结构时大多数情况下优先考虑vector和list。
deque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构进行改造。
stack stack是一个后进先出的数据结构它不是容器而是容器适配器。
常用成员函数 有了stringvectorlist的基础看到这些接口应该会非常熟悉并且知道它们怎么用。
本喵简单演示下怎么使用
#include stack
#include iostream
using namespace std;int main()
{stackint st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);st1.push(5);while (!st1.empty()){cout st1.top() ;st1.pop();}cout endl;return 0;
}入栈顺序是12345出栈顺序是54321。
模拟实现 使用泛型编程将适配器要改造的容器类型设置成模板参数Container并且给它一个缺省参数如果没有指定被改造容器类型就使用deque。 stack容器适配器就是要将已有的容器接口进行改造从而符合我们对要求所以成员变量只有一个容器类型。 stack类中不需要有显式的构造函数因为编译器自动生成的默认构造函数就能满足要求。 自动生成的默认构造函数对自定义类型调用它的默认构造函数。 对内置类型不做处理。
我们这里没有内置类型只有一个自定义类型而这个自定义类型还是一个已有的容器所以会调用它的默认构造函数来进行初始化。
接下来就是改造已有容器的接口让它符合我们对要求。 上图所示代码就是stack那些接口的模拟实现。这些接口都是根据栈的特性来写的。 栈的特性先进后出插入数据时尾插出数据时尾删访问数据只能访问栈顶数据也就是尾部的数据。 改造的已有容器我们使用的是模板给了它一个缺省值默认使用deque作为被改造容器。
既然是模板参数而且是一个缺省值那么我们也可以指定被改造的容器类型。
被改造容器必有接口改造后的接口push_back()push()pop_back()pop()back()top()empty()empty()size()empty()
有这些接口的容器目前我们接触到的而且比较合适的也就是vectorlist以及deque。 使用默认deque的容器适配器stack。 使用指定vector的容器适配器stack。 使用指定list的容器适配器stack。
虽然STL标准库中默认的也是deque但是我们在使用的时候也可以像上面一样指定被改造的容器对于栈来说只要能接受它扩容造成的空间浪费是可以使用vector的。
queue queue是一个先进先出的结构他同样是一个容器适配器。
常用接口 简单演示
void Queue_test()
{queueint q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout q.front() ;q.pop();}cout endl;
}进队列的顺序是1234出队列的顺序也是1234。
模拟实现 和栈一样同样使用模板被改造的容器给一个确实值默认使用deque成员变量只有被改造的容器。
同样不需要显式构造函数编译器自动生成的默认构造函数就能够满足需求。
下面实现它的各种接口 同样是对已有容器的接口进行改造。
已有容器必有接口改造后接口push_back()push()pop_frontpop()back()back()front()front()empty()empty()size()size()
和栈一样有这些接口的容器我们学习过的并且合适的只有list和dequevector是没有front()接口的。 默认使用deque的容器适配器queue。 指定list的容器适配器queue。
queue和satck有一点不同的是queue不能使用vector作为被改造的容器因为vector中没有front()接口而queue是需要用到这个接口的。
虽然STL中使用的默认容器是deque但是也可以指定list但是使用list的话就得接受它的缺点所以说使用deque更好。
priority_queue 优先级队列其实就是我们曾经学过的堆关于堆的内容在本喵的文章堆的使用原理中有详细介绍有兴趣的小伙伴可以去看看。 优先队列是一种容器适配器根据严格的排序标准它的第一个元素总是它所包含的元素中最大或者最小的。 此结构类似于堆在堆中可以随时插入元素并且只能检索最大或者最小堆元素(优先队列中位于顶部的元素)。 同样也是容器适配器它默认采用的容器是vector。
我们知道堆的物理结构是数组而逻辑结构是一个完全二叉树所以说vector是最适合优先级队列的已有容器。
常用接口 简单使用
void Priority_queue_test()
{priority_queueint pq;pq.push(3);pq.push(5);pq.push(6);pq.push(2);pq.push(1);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;
}在将数据插入优先队列的时候时乱序插入的。 输出到时候这些数据按照从大到小的顺序输出。
优先级队列是一个堆按照输出结果来看第一个堆顶数据是6第二个堆顶的数据时5第三个是3以此类推。
还原一下这几个数据入队列后的堆结构 可以看到这是一个大根堆。 优先级队列默认情况下是按照大根堆的方式构建的。 那么怎么让它成为小根堆呢 输出结果中第一个堆顶数据是1第二个是2以此类推。
来看它的堆结构 可以看到这是一个小根堆。 在创建priority_queue时模板实例化传了三个参数。第一个是插入的数据类型。第二个是底层容器的类型。第三个是仿函数。 是大根堆还是小根堆主要的依据就这个仿函数它决定了内部的比较方式。
仿函数(函数对象) 红色框中是一个比较函数两个数相比如果第一个比第二个大则返回真。 在Func_test函数中调用上面的比较函数来进行两个数比较站在这个函数的角度它不知道比较的方式是什么只是使用它的结果。 在主函数中调用Func_test函数的时候还需要将比较函数当作实参传过去。也就是主函数告诉子函数用Greater去比较但是不告诉子函数具体的比较细节。 这种方式就是我们自己学习过的回调函数。在子函数中通过函数指针的方式来调用这个比较函数。 此时比较函数的两个形参类型是确定的只能是int类型如果要比较别的类型就不行了。
而且函数指针的使用感觉不是很方便这属于C语言的糟粕所以C为了弥补就有了仿函数。 仿函数可以像函数一样使用但是不是真的函数。 templateclass T
class greater
{
public:bool operator()(const T x, const T y) const{return x y;}
};写这样的一个类模板第一个数比第二个大时返回真。 使用泛型编程编译器自动推演数据类型。类中没有成员变量只有一个成员函数类对象大小为1字节。 使用operator重载函数运算符括号。 此时使用仿函数同样实现了函数指针的功能而且还支持不同类型的数据比函数指针好用。
templateclass T
class less
{
public:bool operator()(const T x, const T y) const{return x y;}
};趁热打铁将第一个数小于第二个数时返回真的仿函数也写出来。
模拟实现 优先队列也是容器适配器所以和前面的成员变量一样只是默认的被改造容器使用的vector。
除此之外还有一个模板参数是仿函数默认使用less也就是第一个数比第二个数小返回真因为优先级队列要建堆涉及到了比较所以要给它一个比较依据。
因为要建大根堆和小根堆所以就需要向上调整和向下调整数据先来实现一下这两个函数。
向上调整
void adjust_up(size_t child)
{Compare com;size_t parent (child - 1) / 2;while (child 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}elsebreak;}
}假设仿函数使用less建立的是大根堆。 父节点比子节点小父子节点交换位置。交换后父节点成为新的子节点再和他的父节点进行比较。直到子节点到了根的位置说明这次的向上调整结束。 向下调整
void adjust_down(size_t parent)
{Compare com;size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child],_con[child 1])){child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}elsebreak;}
}假设仿函数使用less建立的是大根堆。 父节点比子节点小父子节点交换位置。交换后的子节点成为新的父节点继续和它的子节点比较。直到子节点的下标超出数组size说明这次向下调整结束。 这里简单说明一下详细内容可看本喵另一篇文章堆的使用原理。 可以看到priority_queue是有构造函数的所以要实现一下。 使用迭代器区间初始化的构造函数在初始化列表中将底层容器初始化以后它是无序的而堆是有序的所以采用向下调整建堆。 使用向下调整建堆时间复杂度是O(N*logN)。 这里必须要显式写一个无参的构造函数。
因为已经有使用迭代器区间的构造函数了此时编译器就不会自动生成无参的默认构造函数了如果不用迭代器区间初始化去创建一个优先级队列对象就会导致没有构造函数可掉会报错没有合适的构造函数。 这是其他接口的模拟实现。
底层容器必有接口改造后接口push_back()push()pop_back()pop()operator[]top()empty()empty()size()size()
在向堆中插入数据和删除数据时都需要重新调整堆结构使其符合大堆或者小堆。
插入数据堆调整 新插入数据实际上进行了尾插插入到了数组的最后一个位置也就是二叉树最后一个元素。 要想继续符合堆结构就需要将这个新的数据进行向上调整让它位于正确的位置。
删除数据堆调整 删除数据删除的是数组的第一个元素如果直接删除掉不仅破环了堆结构而且还需要进行大量的数据挪动。 所以将第一个元素和最后一个元素的位置互换进行尾删然后将第一个元素向下调整让它位于正确的位置。 默认使用的底层容器是vector默认使用的仿函数是less。 指定底层结构是vector知道仿函数是less和默认情况一样。 指定底层容器vector指定仿函数greater。
说明 priority_queue类模板的三个参数中只有第一个不是缺省值后两个都是缺省值。 虽然只需要给第一个和第三个传参就行。 但是和函数一样给带有缺省参数的函数或模板传参时只能从左向右传。
所以要想指定仿函数还需要指定底层容器。
反向迭代器
我们模拟实现stringvectorlist等结构的时候都没有模拟实现过反向迭代器是因为反向迭代器最好的实现方式也是使用适配器。
既然是适配器那么它改造的是谁呢改造的是正向的迭代器无论是普通反向迭代器还是const反向迭代器改造的都是普通正向迭代器。 改造的底层容器是正向迭代器所以第一个模板参数是一个迭代器具体是list迭代器还是vector迭代器并不知道所以采用的是泛型编程。
第二个和第三个模板参数和list中迭代器一样是为了简化const反向迭代器的代码而加的模板参数。 被改造容器接口改造后的接口operator*()operator*()operator–()operator()operator()operator–()operator!()operator!()反向迭代器需要构造函数因为迭代器都是迭代器来初始化的。 在进行解引用运算符重载的时候先进行了减减然后才进行的解引用。 无论是链表还是vector它们的正向迭代器和反向迭代器都是对称的。 begin()和rend()指向同一个位置。end()和rbegin()指向同一个位置。 当解引用rbegin()的时候此时得到的内容并不是结构中的内容所以要先进行end()减减再解引用。
当解引用rend()的时候此时得到的是首元素的内容但是我们要的是结构之外的第一个内容所以要进行begin()减减在解引用。
所以说反向迭代器的解引用要将底层容器的迭代器先减减再解引用。
在list中验证 在我们曾经写的list中将reverse_iterator和const_reverse_iterator定义出来和普通迭代器一样如上图中红色框中所示。 再在list中写获得rbeginrend以及crbegincrend的接口根据前面的分析是用正向迭代器对称初始化的如上图所示。 可以和标准库中的反向迭代器一样使用。 可以和标准库中的const反向迭代器一样使用。 const的迭代器同样不可以被修改。
在vector中验证 在我们之前写的vector中定义俩种反向迭代器如上图中红色框中所示。 和list一样写对应的接口函数如上图中所示。 和标准库中的反向迭代器一样可以正常使用。 修改const迭代器指向的内容时也会报常量不可修改的错误。 反向迭代器我们只写了一份。 底层容器是list迭代器和vector的迭代器都可以正常使用。
总结
这篇文章主要讲解的就是适配器模式无论是stackqueuepriority_queue还是迭代器它们都是容器适配器这是底层的容器不一样而且我们也发现适配器是真的好用。
