文章目录
一.什么是容器适配器二.stack栈2.1 stack的介绍2.2 stack的使用2.3 stack的模拟实现 三.queue队列3.1 queue介绍3.2 queue的使用3.3queue的模拟实现 四.deque的简单介绍1.STL标准库中stack和queue的底层结构2.deque的原理介绍3.deque底层结构工作原理扩容机制 4.deque的缺陷`deque` 的优点：缺点分析 5.为什么选择deque作为stack和queue的底层默认容器6.`deque` 迭代器的设计迭代器的示意图结论
一.什么是容器适配器
容器适配器是一种在编程中常用的设计模式，它允许我们将一个类的接口转换成另一个客户希望的接口。具体到容器适配器，它们用于转换已有的序列式容器（如vector、deque和list）以满足特定场景的需求。通过封装和重新组合这些容器中的成员函数，容器适配器可以提供不同的接口，使得原本的序列容器在新的使用情境下更加适用和高效。举例来说，栈（stack）就是一种典型的容器适配器。它通过封装一个底层序列容器（例如deque），并提供了栈操作所需的接口（如push、pop和top），使得这个底层序列容器能够像栈一样工作。这种模式使得我们可以在不改变已有容器的基础上，适配它们以满足不同的算法或应用需求。总结来说，容器适配器是一种灵活的设计模式，能够有效地重用现有的代码和容器功能，同时为不同的编程场景提供定制化的解决方案。
二.stack栈
2.1 stack的介绍
官方文档介绍点这里：stack的文档介绍
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。
压栈：栈的插入操作叫做 进栈 / 压栈 / 入栈 ，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2.2 stack的使用
需要包含头文件#include <stack
#include <iostream>#include <stack>using namespace std;int main() { stack<int> myStack; // 检测 stack 是否为空 if (myStack.empty()) { cout << "Stack is empty" << endl; } // 向 stack 中压入元素 myStack.push(10); myStack.push(20); myStack.push(30); // 返回 stack 中元素的个数 cout << "Size of stack: " << myStack.size() << endl; // 返回栈顶元素的引用 cout << "Top element: " << myStack.top() << endl; // 弹出 stack 中尾部的元素 myStack.pop(); cout << "Top element after pop: " << myStack.top() << endl; return 0;}
2.3 stack的模拟实现
namespace mystack{ template<class T,class Container=deque<T>> class stack { public: // 将元素 x 压入栈中 void push(const T& x) { _con.push_back(x); } // 弹出栈顶元素 void pop() { _con.pop_back(); } // 返回栈顶元素的引用 const T& top() const { return _con.back(); } // 返回栈中元素的个数 size_t size() { return _con.size(); } // 检测栈是否为空 bool empty() { return _con.empty(); } private: // 用于存储栈元素的容器 Container _con; };}这种写法采用了模板编程和容器适配器的思想。
模板编程：通过使用模板参数，类stack能够适用于不同的数据类型和底层容器。容器适配器：stack并不是从零开始实现数据存储，而是利用现有的标准容器（如deque）来实现其功能。这种方法减少了重复代码，提高了代码的重用性和可维护性。为什么这样写？
灵活性：通过模板参数，用户可以自定义stack的底层容器类型，而不仅限于deque。这使得stack更为灵活和通用。减少代码重复：利用现有的标准容器如deque、vector、list等，避免了重新实现基本的容器操作（如插入、删除等）。提高效率：使用标准库中的容器通常可以提供高效和经过优化的实现。为什么第二个模板参数是class Container = deque ?
默认参数：class Container = deque意味着Container默认使用deque作为底层容器。如果用户没有指定第二个模板参数，stack将使用deque作为其底层容器。适应性：deque是一个双端队列，支持在两端进行快速的插入和删除操作，非常适合用作stack的底层容器。模板参数也支持缺省值吗？
是的，模板参数支持缺省值。缺省值为模板提供了默认的行为，如果用户在实例化模板时没有提供某个模板参数，编译器将使用缺省值。在你的代码中，class Container = deque就是一个模板参数缺省值的例子。用户可以选择性地提供自己的容器类型，比如vector或list，也可以直接使用默认的deque。为什么没有默认成员函数以及赋值运算符重载函数？
类模板stack的默认构造函数、析构函数、拷贝构造函数和赋值运算符重载函数都是由编译器自动生成的。因为类模板stack中的成员变量_con是一个容器对象（如std::deque），而这些容器类本身已经提供了适当的构造、析构、拷贝和赋值操作，所以默认生成的函数能够正常工作。详解const T& top() const
在 const T& top() const 中，两个 const 限定符分别应用于不同的情况。
第一个 const 限定符
const T& top() 中的 const 表示返回的引用是一个常量引用。这意味着调用 top() 函数时，返回的引用不能用于修改栈中元素的值。这是为了保护栈的内部数据，确保它不会被意外修改。例如：
const T& top();
当你通过 top() 返回一个元素时，不能通过这个引用去修改该元素。
第二个 const 限定符
const T& top() const 中的第二个 const 修饰符用于声明 top() 函数本身是一个常量成员函数。这意味着该函数不会修改调用它的对象的状态。换句话说，你可以在一个常量对象上调用 top() 函数，并且它不会改变对象的状态。这样可以确保对对象进行只读访问。例如：
const T& top() const;
这个修饰符是对对象的“只读”承诺，保证了函数调用不会修改对象的任何成员变量。
综合作用
这两个 const 修饰符的结合确保了 top() 函数既不会修改对象的状态，也不会允许通过返回的引用修改对象的内部数据。这种设计提供了对栈对象的安全的只读访问，并保护了栈的内部数据免受意外修改。
对比 size 函数
例如，在 size() 函数中，仅需一个 const 修饰符：
size_t size() const;
这个修饰符仅表示 size() 函数不会修改对象的内部状态，因为它只是返回栈的大小，不涉及任何对内部数据的修改。这里不需要返回类型的 const 修饰符，因为 size() 返回的是一个值类型，而不是引用。
测试一下
void test_stack() { stack<int> s; // 默认使用 std::vector 作为底层容器 s.push(1); s.push(2); s.push(3); s.push(4); while (!s.empty()) { cout << s.top() << " "; // 输出栈顶元素 s.pop(); // 弹出栈顶元素 } cout << endl;}void test_stack1() { stack<int, list<int>> s; //也可指定使用 std::list 作为底层容器 s.push(1); s.push(2); s.push(3); s.push(4); while (!s.empty()) { cout << s.top() << " "; // 输出栈顶元素 s.pop(); // 弹出栈顶元素 } cout << endl;}测试结果如下：
三.queue队列
3.1 queue介绍
.
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
3.2 queue的使用
需要包含头文件#include
#include <iostream>#include <queue>using namespace std;void test_queue() { // 构造空的队列 queue<int> q; // 检查队列是否为空 if (q.empty()) { cout << "The queue is currently empty." << endl; } // 在队尾入队元素 q.push(10); q.push(20); q.push(30); q.push(40); // 输出队列大小 cout << "The queue size is: " << q.size() << endl; // 返回队头和队尾元素的引用 cout << "Front element is: " << q.front() << endl; cout << "Back element is: " << q.back() << endl; // 逐个出队并输出队头元素 while (!q.empty()) { cout << "Popping front element: " << q.front() << endl; q.pop(); } // 再次检查队列是否为空 if (q.empty()) { cout << "The queue is now empty." << endl; }}int main() { test_queue(); return 0;}
3.3queue的模拟实现
queue 不能用 vector 去适配，因为 vector 压根就没有 pop_front 这个接口。
namespace myqueue{//queue模拟实现template<class T,class Container=deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}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;};
四.deque的简单介绍
1.STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配
器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：
2.deque的原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和
删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。deque在功能上兼具了 vector 和 list 的一些优点。它支持在两端进行高效的插入和删除操作，同时也支持随机访问，这使得它在某些情况下非常有用。然而，要全面理解 deque，需要了解它的底层实现和它的优缺点。
3.deque底层结构
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
deque 是由一段段连续的小块空间组成的，这些小块空间通过一个中控指针数组连接起来。指针数组用于管理这些小块空间，使得在两端进行插入和删除操作时更加高效。
工作原理
小块空间分配：deque 最初分配一块小空间来存储元素。当这块空间用完时，它不会像 vector 那样进行整体扩容，而是分配一个新的小块空间。这种方法避免了频繁的内存拷贝，提高了效率。 中控指针数组： 为了管理这些小块空间，deque 维护了一个中控指针数组，指向这些小块空间。中控数组从中间位置开始存储指针，这样可以方便地在两端进行操作。 插入操作： 头插： 如果需要在头部插入元素，deque 不需要像 vector 那样移动数据，只需在头部前方分配新的小块空间即可。尾插： 如果需要在尾部插入元素，且最后一个小块空间没有满，可以直接插入。如果满了，则分配新的小块空间。扩容机制
虽然 deque 的小块空间不会扩容，但中控指针数组可能会满。当中控数组满了时，需要扩容。但这种扩容的代价相对较低，因为只需拷贝指针，并且每个指针只指向一个小块空间。
4.deque的缺陷
deque 的优点：
扩容代价低： 与 vector 相比，deque 的扩容代价更低，因为 deque 只需要为中控指针数组分配新的空间，而不是移动所有的元素。 高效的头尾插入和删除操作： deque 在头部和尾部插入和删除元素时不需要移动大量数据，这使得这些操作的效率较高。相比之下，vector 在头部插入或删除元素时需要移动大量数据，效率较低。 支持随机访问且效率比 list 好： 与 list 不同，deque 支持高效的随机访问。虽然 deque 的随机访问效率不如 vector，但比 list 好得多，因为 list 需要遍历节点才能访问特定位置的元素，而 deque 可以通过计算索引直接访问。缺点分析
虽然 deque 结合了 vector 和 list 的优点，但它也存在一些缺点：
deque 的结构在进行中间插入和删除操作时效率较低。因为在这种操作下，需要移动大量数据。虽然每个小数组（buffer数组）可以设计为不同大小来减少移动的数据量，但这会影响随机访问的效率。因此，标准的 deque 实现中每个小数组大小是固定的，这导致中间插入和删除时需要移动大量数据，效率较低。 空间管理复杂： deque 需要管理多个小块空间以及一个中控指针数组，这使得它的实现和维护比单纯的 vector 或 list 更复杂。这种复杂性可能带来一些额外的开销。 没有极致优化： 尽管 deque 结合了 vector 和 list 的优点，但这些优点在 deque 上并没有达到极致。对于需要频繁随机访问的场景，vector 更合适，因为它的随机访问效率最高。而对于需要频繁在头部或中间进行插入和删除的场景，list 更合适，因为它不需要移动大量数据。deque 在这些方面虽然能兼顾，但都不如 vector 和 list 那么高效。 内存使用： 由于 deque 需要维护多个小块空间和一个指针数组，相对于 vector 和 list，它的内存使用效率可能更低。这些额外的指针和小块空间可能导致内存碎片和更高的内存开销。
5.为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，
主要是因为：
结合了deque的优点，而完美的避开了其缺陷。
6.deque 迭代器的设计
deque（双端队列）是一个设计精巧的数据结构，它利用分段连续的内存块来模拟一个整体上连续的容器。为了维护这种“假想连续”的结构，deque 需要一个复杂的迭代器机制。以下是 deque 如何借助其迭代器来实现这一点的详细解释：
deque 的底层由多个小的内存块（通常称为缓冲区）组成，这些缓冲区通过一个指针数组（中控数组）进行管理。每个缓冲区都是一个连续的内存块。deque 的这种结构允许它在两端高效地进行插入和删除操作，同时避免了像 vector 那样的重新分配和搬移操作。迭代器的组成deque 的迭代器设计相对复杂，因为它必须处理以下几种情况： 这样，一个 deque 迭代器通常由以下几个部分组成：
deque 迭代器需要持有指向当前缓冲区的指针。缓冲区偏移量：deque 迭代器需要记录在当前缓冲区中的位置（偏移量）。指向中控数组的指针：deque 迭代器还需要持有指向中控数组的指针，用于在缓冲区间移动。buffer_ptr：指向当前缓冲区的指针。buffer_offset：在当前缓冲区中的偏移量。map_ptr：指向中控数组的指针（存储缓冲区指针的数组）。 迭代器操作由于 deque 的缓冲区不是全局连续的，所以迭代器需要执行额外的计算来确保操作的正确性。这包括： 前进与后退： 前进：当迭代器向前移动时，它可能会跨越缓冲区的边界。如果当前缓冲区的偏移量达到缓冲区的末尾，迭代器将需要移动到下一个缓冲区。后退：类似地，当迭代器向后移动时，它也可能需要跨越缓冲区的边界，回到前一个缓冲区。 随机访问： 随机访问操作（例如 operator+ 和 operator-）需要考虑跨越多个缓冲区。计算新的迭代器位置时，必须计算缓冲区之间的偏移，并更新指向相应缓冲区的指针。 迭代器的比较： 由于缓冲区是分段的，迭代器比较时需要比较缓冲区指针和偏移量，确保比较的正确性。迭代器的示意图
假设我们有一个 deque，其底层可能如下所示：
中控数组 +---------+---------+---------+---------+ | Buffer1 | Buffer2 | Buffer3 | Buffer4 | +---------+---------+---------+---------+其中每个 Buffer 都是一个内存块。一个 deque 迭代器可能包括：
当迭代器在 Buffer1 中向前移动时，它将继续保持在 Buffer1 中，直到达到末尾，然后移动到 Buffer2 中的起始位置。类似地，当向后移动时，它可能从 Buffer2 移动到 Buffer1 中的起始位置。
结论
deque 通过复杂的迭代器机制来维护其“假想连续”结构。迭代器需要跟踪多个缓冲区和中控数组的指针，同时处理跨缓冲区的移动和随机访问。尽管这种设计增加了迭代器的复杂性，但它使得 deque 能够在两端高效地插入和删除元素，同时保持相对较高的随机访问效率。
