【浅尝C++】STL第四弹=＞容器适配器底层实现原理/deque底层原理/stack、queue、priority介绍、常用接口示例及模拟实现

🏠专栏介绍：浅尝C++专栏是用于记录C++语法基础、STL及内存剖析等。
🎯每日格言：每日努力一点点，技术变化看得见。

stack的介绍及常用接口示例

stack介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

stack常用接口使用示例

下面给出上述接口的使用示例↓↓↓

#include <iostream>
#include <stack>
using namespace std;

void testStack()
{
	stack<int> stk;
	if(stk.empty())
	{
		cout << "初始时，栈为空，栈内有效元素数为：" << stk.size() << endl;
	}

	stk.push(1);
	stk.push(2);
	stk.push(3);
	stk.push(4);
	stk.push(5);
	cout << "插入后，栈中有效元素数为：" << stk.size() << endl;
	while(!stk.empty())
	{
		cout << stk.top() << " ";
		stk.pop();
	}
	cout << endl;
}

int main()
{
	testStack();
	return 0;
}

上述接口为常有接口，更多接口及细节请查看官方文档->stack官方参照文档

queue介绍与常用接口示例

queue介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

5. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

queue常用接口使用示例

下面给出上述接口的使用示例↓↓↓

#include <iostream>
#include <queue>
using namespace std;

void testQueue()
{
	queue<int>q;
	if(q.empty())
	{
		cout << "队列初始时为空，元素个数为：" << q.size() << endl;
	}

	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);

	cout << "此时队头元素是：" << q.front() << endl;
	cout << "此时队尾元素是：" << q.back() << endl;

	cout << "队列遍历结果为：";
	while(q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
}

int main()
{
	testQueue();
	return 0;
}

上述接口为常有接口，更多接口及细节请查看官方文档->queue官方参照文档

priority_queue介绍与常用接口示例

priority_queue介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，priority_queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器在需要时自动调用算法函数来自动完成此操作。

priority_queue常用接口使用示例

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的地方，都可以考虑使用priority_queue。

★ps：默认情况下priority_queue是大堆。

下面给出上面接口的使用示例（含大堆即小堆）↓↓↓

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

void testPQ()
{
	//默认大堆
	priority_queue<int> q;

	q.push(8);
	q.push(2);
	q.push(9);
	q.push(7);
	q.push(5);
	q.push(6);

	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;

	//小堆
	//注意：
	//第一个模板参数传入q2中要存储的数据类型
	//第二个模板参数传入用于封装priority_queue的容器，可以是vector或者deque
	//第三个传入仿函数（后序文章会介绍）
	priority_queue<int, vector<int>, greater<int>> q2;
	q2.push(8);
	q2.push(2);
	q2.push(9);
	q2.push(7);
	q2.push(5);
	q2.push(6);

	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
	cout << endl;
}

int main()
{
	testPQ();
	return 0;
}

容器适配器

什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

简而言之，适配器（配接器）就是使用已经有的容器的接口，封装出一个拥有不同功能的"新容器"。

deque介绍

deque的原理

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

deque中包含一个指向指针数组首地址的指针map。该指针数组称为中控器，每个指针数组元素指向一个定长数组。

当map指向的中控器（指针数组）容量不足时，则会开辟新的指针数组，并将旧的值拷贝进新指针数组。以头插为例（如下图所示），在deque头插一个元素0，此时中控器空间不足。deque创建新的指针数组，将map指针指向新的指针数组，并将旧数据拷入新数组中。在头部插入元素时，由于1到6所在空间不足，则需要在它们的前面开辟一个同等大小的数组，在该数组的最后一个位置放入0。如果继续插入-1、-2时，由于中控器指向的最前的数组中还有位置，则依次在0元素前插入-1和-2。尾部插入同理。因而deque的头插效率比vector高。

如果需要头部删除元素时，如果对应的一维数组还有元素，则只是将最前面的元素清除（例如，删除头部的-2）。

如果头删-1和0，此时第一个数组为空。此时并不会释放该一维数组，而是保留这一块空间，当用户头插时就不需要再申请空间了。

如果删除中间的元素，则需要像vector一样大量移动数据。（下图演示了，删除数据8）

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

迭代器中包含4个指针，node指向中控器某个一维数组的保存位置，first指向一维数组的开始位置，last指向一维数组的结束位置，cur指向当前元素的位置。

那deque是如何借助其迭代器维护其假想连续的结构呢？（它的begin、end迭代器如下图所示）

deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

大家在需要大量插入删除时，优先会选择list；需要随机访问+提高空间利用率时，优先选择vector。deque虽然没有list与vector的两个主要缺陷缺陷（空间利用率低，头插头删效率低），但它也没有list与vector的突出优点。因而它在编程中利用并不多。

为什么选择deque作为stack与queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。

但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高（相比于list）。

结合了deque的优点，而完美的避开了vector及list的缺陷。

stack模拟实现

下面代码使用默认使用deque容器封装了新的类——stack。↓↓↓

#include <iostream>
#include <deque>

using namespace std;

namespace jammingpro
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_back();
		}
		T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

queue模拟实现

下面代码使用默认使用deque容器封装了新的类——queue。↓↓↓

#include <iostream>
#include <deque>

using namespace std;

namespace jammingpro
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		T& front()
		{
			return _con.front();
		}
		T& back()
		{
			return _con.back();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

priority_queue模拟实现

下面代码使用默认使用vector容器封装了新的类——priority_queue。在进行插入时，将其插入于vector尾部并使用向上调整，保持堆结构；在删除元素，通过先将头尾元素交换，再删除原来位于头部的元素，最终使用向下调整算法保持堆结构。↓↓↓

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

namespace jammingpro
{
	template<class T, class Container = vector<T>, class Compare = greater<int>>
	class priority_queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
			adjustUp();
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjustDown();
		}
		T& top()
		{
			return _con.front();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		void adjustDown()
		{
			Compare com;
			int parent = 0;
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
				{
					child++;
				}
				if (com(_con[child], _con[parent]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void adjustUp()
		{
			Compare com;
			int child = _con.size() - 1;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
				{
					child++;
				}
				if (com(_con[child], _con[parent]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		Container _con;
	};
}

🎈欢迎进入浅尝C++专栏，查看更多文章。
如果上述内容有任何问题，欢迎在下方留言区指正b(￣▽￣)d