简历模板文档,wordpress怎么seo,太原在建,给网站底部做友情链接文章目录 一、stack1.利用适配器2.栈的实现 二、queue三、deque1.deque介绍2.deque的接口3.deque的基本使用4.deque的效率5.deque的原理 一、stack
1.利用适配器
我们不可能写了一份数组栈以后#xff0c;还要在手写一个链式栈#xff0c;这样显得太冗余了。于是我们可以利… 文章目录 一、stack1.利用适配器2.栈的实现 二、queue三、deque1.deque介绍2.deque的接口3.deque的基本使用4.deque的效率5.deque的原理 一、stack
1.利用适配器
我们不可能写了一份数组栈以后还要在手写一个链式栈这样显得太冗余了。于是我们可以利用适配器传递一个我们想要使用的类型。这样我们的栈就可以做到数组栈和链式栈的秒切换了。从我们用的角度来说并没有太大差别但是底层早已大变样了。 templateclass T, class Containerclass stack{public:private:Container _con;};2.栈的实现
有了上面的思路我们就可以很容易的完成栈的接口
#pragma once
#includevector
#includelist
namespace Sim
{templateclass T, class Container vectorTclass stack{public:void push(const T val){_con.push_back(val);}void pop(){_con.pop_back();}const T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_stack(){stackint st1;stackint, listint st2;st1.push(1);st1.push(2);st1.push(3);st1.push(4);while (!st1.empty()){cout st1.top() ;st1.pop();}cout endl;}
};二、queue
如下所示是queue的模拟实现需要注意的是queue是不可以用vector进行适配的因为vector并未提供pop_front接口但是如果想要强制适配的话也是可以的使用erase接口即可
#pragma once
#pragma once
#includevector
#includelist
namespace Sim
{templateclass T, class Container listTclass queue{public:void push(const T val){_con.push_back(val);}void pop(){_con.pop_front();}const T front(){return _con.front();}const T back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue(){queueint q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout q1.front() ;q1.pop();}cout endl;}
};三、deque
1.deque介绍
虽然我们上面使用的适配器缺省参数都是vector或者list但是我们会发现库里面的stack和list它的适配器都是deque。deque听名字好像是个队列名字是双端队列。但是队列是有先进先出的特性的它不是那么特别符合队列。 Deque(通常发音像“deck”)是双端队列的不规则缩写。双端队列是具有动态大小的序列容器可以在两端(前端或后端)扩展或收缩。
特定的库可能以不同的方式实现deque通常是某种形式的动态数组。但在任何情况下它们都允许通过随机访问迭代器直接访问单个元素并根据需要通过扩展和收缩容器来自动处理存储。
因此它们提供了类似于向量的功能但在序列的开始而不仅仅是在序列的末尾也可以有效地插入和删除元素。但是与vector不同deque不能保证将其所有元素存储在连续的存储位置:通过偏移指向另一个元素的指针来访问deque中的元素会导致未定义的行为。
vector和deque都提供了非常相似的接口可以用于类似的目的但两者在内部的工作方式却完全不同:vector使用单个数组偶尔需要为增长重新分配而deque的元素可以分散在不同的存储块中容器内部保留必要的信息以便在恒定时间内使用统一的顺序接口(通过迭代器)直接访问其任何元素。因此deque在内部比vector更复杂但这使得它们在某些情况下更有效地增长特别是对于非常长的序列重新分配变得更加昂贵。
对于涉及频繁插入或删除除开始或结束位置以外的元素的操作deque的性能更差迭代器和引用的一致性也不如列表和前向列表。
2.deque的接口
如下所示是deque的接口我们可以发现它似乎同时具有list和vector的接口。而且它的迭代器还是随机迭代器。
deque的接口像是vector和list的合体。但是它看似很强实际上效率不是很高。单论头插头删尾插尾删效率还是不错的但是综合性不是很好。
3.deque的基本使用
void test_deque()
{dequeint dq;dq.push_back(1);dq.push_back(2);dq.push_back(3);dq.push_back(4);for (int i 0; i dq.size(); i){cout dq[i] ;}cout endl;
我们可以得知
4.deque的效率
我们在前面说过deque的综合效率是不高的。我们可以用下面的代码来看出
void test_op()
{srand(time(0));const int N 1000000;vectorint v1;vectorint v2;v1.reserve(N);v2.reserve(N);dequeint dq1;dequeint dq2;for (int i 0; i N; i){auto e rand();//v1.push_back(e);//v2.push_back(e);dq1.push_back(e);dq2.push_back(e);}// 拷贝到vector排序排完以后再拷贝回来int begin1 clock();// 先拷贝到vectorfor (auto e : dq1){v1.push_back(e);}// 排序sort(v1.begin(), v1.end());// 拷贝回去size_t i 0;for (auto e : dq1){e v1[i];}int end1 clock();int begin2 clock();sort(dq2.begin(), dq2.end());int end2 clock();printf(deque copy vector sort:%d\n, end1 - begin1);printf(deque sort:%d\n, end2 - begin2);
} deque效率慢的原因主要就是因为它的随机访问[]的效率太低
5.deque的原理
我们知道 对于数组可以下标随机访问但是存在扩容问题中间和头部插入效率低下 对于链表任意位置插入删除效率合适按需申请释放但是不支持随机访问 而现在我们使用的deque的结构是这样它是一段一段的开空间每段空间都是一样大的然后通过一个中控数组指针数组进行连接起来。想要扩容就在连接一块空间即可。当指针数组满了就中控数组扩容即可。这样一来扩容的代价就很低。不需要拷贝原来的数组。对于头插尾插也很简单就用专门的两个空间进行头插尾插即可 它相比vector极大的缓解了扩容、头插头删问题。但是它的[]运算符不够极致。它的[]需要计算在哪个buff数组在哪个buff数组的第几个。如果我们想要使用它的[]运算符它内部的逻辑会经历一下几个步骤
先看在不在第一个buff数组里面如果在就直接访问不在第一个buff数组里面i-第一个buff数组的size第几个buffi/buff.size()在这个buff的第几个i%buff.size()
它相比list可以支持随机访问cpu高速缓存访问效率不错头插尾插删除不错但是中间位置插入删除效率低下。因为我们需要扩容或者挪动buff的数据。无论哪一种效率都很低。
根据deque的底层原理其实对于高频的头插头删尾插尾删来说deque还很适合所以deque用于适配stack和queue来说是很合适的因为它们只涉及到头部和尾部的插入删除不涉及中间位置的插入删除
实际上在库里面的deque是更加复杂的它的迭代器由四个指针组成这使得deque更加复杂首先由node指向中控即指向当前的buff数组cur指向当前buff数组中的某个数据first和last指向当前数组的头和尾 好了本期内容就到这里了 如果对你有帮助的话不要忘记点赞加收藏哦
