容器适配器
适配器:一种设计模式,该种模式是将一个类的接口转换成客户希望的另外一个接口.
stack和queue的底层结构
可以看出的是,这两个容器 相比我们之间见过的容器多了一个模板参数,也就是容器类的模板参数,他们在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,它们的底层是其他容器,对其他容器的接口进行了包装,它们默认的是使用deque
deque的简单介绍
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高.
deque底层结构
它并不是一段连续的空间,而是由多个连续的小空间拼接而成,相当于一个动态的二维数组.
如下图:
deque的迭代器
迭代器原理:迭代器用cur成员进行访问,每当走到last的位置,node的位置就往前挪动一个位置,然后cur继续从first我位置遍历到last的位置,一直如此,cur走到最后一个node的last的位置就停止遍历.
deque的优点
1.相比于vector,deque可以进行头插和头删,且时间复杂度O(1),扩容是也不需要大量挪动数据,因此效率是比vector高的.
2.相比于list,deque底层是连续的空间,空间利用率高,也支持随机访问,但没有vector那么高.
3.总的来说,deque是一种同时具有vector和list两个容器的优点的容器,有一种替代二者的作用,但不是完全替代.
deque的缺点
1.不适合遍历,因为在遍历是,deque的迭代器要频繁地去检测是否运动到其某段小空间的边界,所以导致效率低下.
2.deque的随机访问的效率是比vector低很多的，实际中，线性结构大多数先考虑vector和list.
下面是通过排序来测试vector和deque随机访问的效率
void TestDeque() { srand((unsigned int)time(nullptr)); deque<int> d; vector<int> v; for (size_t i = 0; i < 100000; ++i) { int randNum = rand(); v.push_back(randNum); d.push_back(randNum); } int begin1 = clock(); sort(v.begin(), v.end()); int end1 = clock(); int begin2 = clock(); sort(d.begin(), d.end()); int end2 = clock(); cout << "vector排序用时：" << end1 - begin1 << "ms" << endl; cout << "deque排序用时：" << end2 - begin2 << "ms" << endl; }
代码运行结果如下：
容易看出，deque的随机访问的效率是比vector低很多的。
deque可以作为stack和queue底层默认容器的原因：
- stack和queue并不需要随机访问，也就是说没有触及到deque的缺点，只是对头和尾进行操作。
- 在stack增容时，deque的效率比vector高，queue增容时，deque效率不仅高，而且内存使用率也高。
stack的模拟实现
知道了容器适配器后，stack的模拟实现就显得相当简单，我们只需要调用所指定容器的各个成员函数即可实现stack的各个函数接口。
| 成员函数 | 函数作用 | 实现方法 |
| push | 元素入栈 | 调用所指定容器的push_back |
| pop | 元素出栈 | 调用所指定容器的pop_back |
| top | 获取栈顶元素 | 调用所指定容器的back |
| size | 获取栈中有效元素个数 | 调用所指定容器的size |
| empty | 判断栈是否为空 | 调用所指定容器的empty |
| swap | 交换两个栈中的数据 | 调用所指定容器的swap |
namespace cl //防止命名冲突 { template<class T, class Container = std::deque<T>> class stack { public: //元素入栈 void push(const T& x) { _con.push_back(x); } //元素出栈 void pop() { _con.pop_back(); } //获取栈顶元素 T& top() { return _con.back(); } const T& top() const { return _con.back(); } //获取栈中有效元素个数 size_t size() const { return _con.size(); } //判断栈是否为空 bool empty() const { return _con.empty(); } //交换两个栈中的数据 void swap(stack<T, Container>& st) { _con.swap(st._con); } private: Container _con; }; }
queue的模拟实现
同样的方式，我们也是通过调用所指定容器的各个成员函数来实现queue的。
| 成员函数 | 函数作用 | 实现方法 |
| push | 队尾入队列 | 调用所指定容器的push_back |
| pop | 队头出队列 | 调用所指定容器的pop_front |
| front | 获取队头元素 | 调用所指定容器的front |
| back | 获取队尾元素 | 调用所指定容器的back |
| size | 获取队列中有效元素个数 | 调用所指定容器的size |
| empty | 判断队列是否为空 | 调用所指定容器的empty |
| swap | 交换两个队列中的数据 | 调用所指定容器的swap |
namespace cl //防止命名冲突 { template<class T, class Container = std::deque<T>> class queue { public: //队尾入队列 void push(const T& x) { _con.push_back(x); } //队头出队列 void pop() { _con.pop_front(); } //获取队头元素 T& front() { return _con.front(); } const T& front() const { return _con.front(); } //获取队尾元素 T& back() { return _con.back(); } const T& back() const { return _con.back(); } //获取队列中有效元素个数 size_t size() const { return _con.size(); } //判断队列是否为空 bool empty() const { return _con.empty(); } //交换两个队列中的数据 void swap(queue<T, Container>& q) { _con.swap(q._con); } private: Container _con; }; }
