装修企业网站源码,百度广告买下的订单在哪里找,网络营销是怎么发展的,网页怎么制作视频前言
上一期我们介绍了stack和queue的使用#xff0c;本期我们来模拟实现一下他们#xff01;
本期内容介绍 容器适配器 deque介绍 为什么stack和queue的底层选择deque为默认容器#xff1f; stack 模拟现实 queue 模拟实现 什么是容器适配器#xff1f; 适配器是一种设…前言
上一期我们介绍了stack和queue的使用本期我们来模拟实现一下他们
本期内容介绍 容器适配器 deque介绍 为什么stack和queue的底层选择deque为默认容器 stack 模拟现实 queue 模拟实现 什么是容器适配器 适配器是一种设计模式该种模式是将一个类的接口转换为用户希望的另一个接口 什么是设计模式 设计模式是一套被反复使用的多数人知晓的经过分类编目的代码设计经验的总结。 总结设计模式就是一种常用的编程套路该套路被很多人知晓和使用具有可靠性 常见的设计模式有单例设计模式、工厂设计模式等。 举个例子
你平时手机没电了你是拿充电器先到插板上去充而不是直接去拿电线充。因为电线直接充是不符合我们的需求的一下子弄不好你就被干没了我们要用插板提供的接口插充电器才可以充其实本质你手机充的还是电线里面的电。只是把他转换了一下充电器就像是一个适配器将电源的接口转换成手机充电口的接口使得手机可以与电源连接起来充电。同样地容器适配器也起到了类似的作用它将一个容器的接口转换成另一个容器的接口使得原本不兼容的容器能够协同工作。
deque介绍 stack和queue中虽然也可以存放元素但是STL并没有将他们划分到容器的行列里面而是将其称为容器适配器这里是因为stack和queue只是对其他的容器进行了包装STL中stack和queue底层默认deque deque就是我们在上一期介绍stack和queue的时候看到了他们的模板参数多了一个的那个容器类型的默认容器 什么是deque?
deque到底是什么呢上一期专门没有介绍就等到这一期来介绍 deque叫双端队列是一种双开口的连续空间的数据结构。双开口的含义是可以在头和尾两端进行插入和删除操作而且时间复杂度为O(1)与vector相比头插效率高不需要在头删时挪动大量的数据了与list相比空间利用率比较高所以我们可以认为他是list和vector的结合版可以支持元素的随机访问。支持头尾的插入删除而且效率很高 注意duque并不是真的连续的空间而是由一段段连续的小空间拼接而成实际的deque类似于一个动态的二维数组 这个中控数组实际上一个数组指针里面存的就是每个小段的数组的地址这个中控数组是可以扩容的 所以双端队列的底层是一段假象的连续空间实际上是分段连续的为了维护其“整体连续”以及随机访问的假象重任就落在了deque的迭代器身上了 deque的迭代器也很复杂 deque是如何借助迭代器维护其假想的连续结构的呢 它的底层搞了两个迭代器start和finish一个指向第一个buffer小段数组另一个指向最后一个buffer小数组遍历时从第一个buffer开始如果不到最后一个buffer的最后一个位置即finish的最后一个end就到下一个buffer继续遍历直到遍历完 deque是如何用下标[]来访问的 因为中控数组中的每个小buffer数组的长度都是一样大的所以我们在访问第i个位置时通过 i / N 获取他是在那个buff数组再根据 i % N来确定他是在第几个从而实现了下标遍历~ deque的缺陷 与vector相比deque的优势是在头部插入和删除的时候不需要移动元素效率特别高而在扩容时也不需要移动大量的元素因此这里是效率比vector高的 与list相比它的底层的空间是连续的空间利用率高不需要额外的存储字段 但是deque也有很致命的缺陷 不适合遍历一位在遍历时deque的迭代器要频繁的去检测其是否移动到了都一小段的边界导致效率下降所以在实际中需要线性结构中一般优选的是vector和list 不适合在中间插入删除、因为你在某个中间的buffer插入时如果满了得扩容删除时怎么删你不可能说--size吧人家下标可不管这些解决的办法就是删除时缩容但是缩容后就有新问题如何知道第i个位置的元素导致效率降低 以及它的[]的效率很一般下面有代码验证 void test_op1()
{srand(time(0));const int N 1000000;dequeint dq;vectorint v;for (int i 0; i N; i){auto e rand() i;v.push_back(e);dq.push_back(e);}int begin1 clock();sort(v.begin(), v.end());int end1 clock();int begin2 clock();sort(dq.begin(), dq.end());int end2 clock();printf(vector:%d\n, end1 - begin1);printf(deque:%d\n, end2 - begin2);
}
我们知道sort的底层会大量的用到[]结果差了三倍多 第二个
void test_op2()
{srand(time(0));const int N 1000000;dequeint dq1;dequeint dq2;for (int i 0; i N; i){auto e rand() i;dq1.push_back(e);dq2.push_back(e);}int begin1 clock();sort(dq1.begin(), dq1.end());int end1 clock();int begin2 clock();// vectorvectorint v(dq2.begin(), dq2.end());sort(v.begin(), v.end());dq2.assign(v.begin(), v.end());int end2 clock();printf(deque sort:%d\n, end1 - begin1);printf(deque copy vector sort, copy back deque:%d\n, end2 - begin2);
}
这个是把一个deque的数据拷贝到vector排完了再拷回来都比deque快
所以ton过这两个栗子足以证明deque的[]效率可见一般了~
为什么stack和queue的底层选择deque为默认容器 STL选择让他默认为栈和队列的原因有两个 1、stack和queue不需要遍历他们根本没有迭代器。只是需要在固定的一端或两端进行插入和删除操作 2、在stack中元素增加时与vector相比deque的扩容效率更高deque扩容不需要移动大量的数据。 综上两点deque完美的解决stack和queue的问题而且正好弥补了用vector和list的缺陷所以STL就选择了他作为默认的容器 OK我们来看看它的接口 直接包含了vector和list所有的好用接口
stack的模拟实现
我们以前在数据结构的时候实现栈使用的是单链表或顺序表这里你也可以接着这样玩直接用vector和list。但是我这里就不这样玩了我直接来使用deque templateclass T, class Container dequeTclass stack{public:stack(){}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}T top(){return _con.back();}const T top() const {return _con.back();}void push(const T val){_con.push_back(val);}void pop(){assert(!empty());_con.pop_back();}private:Container _con;}; 这里都很简单不在逐一解释 需要注意的是你可以不用写这个stack的默认构造因为stack这个类里面只有一个自定义类型的变量所以你不写编译器默认生成的那个就自己去调用调他自己成员的默认构造了 另外这里选择的是尾部实现的你也可以选择头部实现 queue模拟实现
同样的队列这里你也可以和数据结构那样搞个链表玩介绍了deque那必然用它~ templateclass T, class Container dequeTclass queue{public:queue() {}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}T front() {return _con.front();}const T front() const {return _con.front();}T back() {return _con.back();}const T back() const{return _con.back();}void push(const T val){_con.push_back(val);}void pop(){_con.pop_front();}private:Container _con;}; 和上面同样你也可以不写默认构造另外注意的是插入是尾插删除是头删 OK我测试一下 没有问题~OK本期分享就到这里好兄弟我们下期再见~ 结束语心怀理想勇往直前
