文章目录
一.什么是容器适配器二.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
能够在两端高效地插入和删除元素,同时保持相对较高的随机访问效率。