一、stack
1.利用适配器
我们不可能写了一份数组栈以后，还要在手写一个链式栈，这样显得太冗余了。于是我们可以利用适配器，传递一个我们想要使用的类型。这样我们的栈就可以做到数组栈和链式栈的秒切换了。从我们用的角度来说并没有太大差别，但是底层早已大变样了。
template<class T, class Container> class stack { public: private: Container _con; };
2.栈的实现
有了上面的思路，我们就可以很容易的完成栈的接口
#pragma once #include<vector> #include<list> namespace Sim { template<class T, class Container = vector<T>> class 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() { stack<int> st1; stack<int, list<int>> 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 #include<vector> #include<list> namespace Sim { template<class T, class Container = list<T>> class 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() { queue<int> 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() { deque<int> 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; vector<int> v1; vector<int> v2; v1.reserve(N); v2.reserve(N); deque<int> dq1; deque<int> 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(); // 先拷贝到vector for (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
- 第几个buff=i/buff.size()
- 在这个buff的第几个=i%buff.size()
它相比list，可以支持随机访问，cpu高速缓存访问效率不错，头插尾插删除不错，但是中间位置插入删除效率低下。因为我们需要扩容或者挪动buff的数据。无论哪一种，效率都很低。
根据deque的底层原理，其实对于高频的头插头删，尾插尾删来说，deque还很适合，所以deque用于适配stack和queue来说是很合适的，因为它们只涉及到头部和尾部的插入删除，不涉及中间位置的插入删除
实际上在库里面的deque是更加复杂的，它的迭代器由四个指针组成，这使得deque更加复杂，首先由node指向中控，即指向当前的buff数组，cur指向当前buff数组中的某个数据，first和last指向当前数组的头和尾
好了，本期内容就到这里了
如果对你有帮助的话，不要忘记点赞加收藏哦！！！
