C++之适配器（以优先队列为例）

🔥什么是适配器

以下是我在百度上看到的一句话。

对于这句话，我的理解如下。

举个生活中的例子

我们平常接触到的电流是220v，但是给手机充电时，肯定是用不了这么高的电压，所以我们通过“电源适配器”的转化，（充电器的全称是“电源适配器”，）变成合适的电压才能给手机充电。这里的“充电器”就起到了适配的作用。

🔥几种常见的适配器

c++中的适配器有三种：容器适配器，迭代器适配器，函数适配器

容器适配器：具体的有stack，queue，priorty-queue，默认的情况如下：stack和queue是基于deque实现的。
priorty-queue是在vector上实现的，可以根据第二个实参指定容器的类型，但是一定要符合标准，queue要求有push_back的操作，因此不能建立在vector的基础上，priorty-queue要求有随机访问的功能，因此建立在vector上。

🔥适配器如何使用

本文主要讲解priority_queue（优先级队列），我们需要了解以下知识：

• 优先级队列的底层使用堆实现的，因为堆的效率高，所以才用堆实现。
• 适配器的模版参数有多个，他们分别是：
• template <class T, class Container = vector, class Compare = less > class priority_queue;

画张图理解一下

void test()
{
	std::priority_queue<int,vector<int>,less<int>> pq;
	pq.push(1);
	pq.push(5);
	pq.push(0);
	pq.push(2);
	while (!pq.empty())
	{
		cout << pq.top()<<" ";
		pq.pop();
	}
	cout << endl;

}

输出的结果如下：
如图可以看出，他是按照降序排序的。

void test()
{
	std::priority_queue<int,vector<int>,greater<int>> pq;
	pq.push(1);
	pq.push(5);
	pq.push(0);
	pq.push(2);
	while (!pq.empty())
	{
		cout << pq.top()<<" ";
		pq.pop();
	}
	cout << endl;

}

输出结果如下

🔥适配器的模拟实现（以prrority_queue为例）

🏠 向上调整算法

//向上调整算法
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child>0)//直到孩子到达堆顶结束比较
			{
				if(com(_con[parent],_con[child]))
				//if (_con[child] > _con[parent])// 父亲小于孩子,孩子往上调
				{
					swap(_con[parent], _con[child]);//交换两个节点
					child = parent;//更新child
					parent = (child - 1) / 2;//更新parent
				}
				else
				{
					break;
				}
			}
		}

🏠 向下调整算法

		//向下调整算法
		void AdjustDown(int root)
		{
			Compare com;
			int parent = root;
			int child = parent * 2 + 1;
			while (child<_con.size())
			{
				//选出左右孩子大的哪一个
				//if (child + 1 < _con.size() && _con[child+1] > _con[child ])
				if(child+1<_con.size()&&com(_con[child],_con[child+1]))
				{
					++child;
				}
				if(com(_con[parent],_con[child]))
				//if (_con[child] > _con[parent])  父亲大于孩子,孩子往上调
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent + 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

🏠 插入数据

void push(const T& x)
		{
			_con.push_back(x);//插入数据之后破化了堆得性质
			AdjustUp(_con.size()-1);//从最后的位置开始调，调用向上调整算法，调成大堆
		}

🏠 删除数据

void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);//交换堆顶数据和最后一个数据
			_con.pop_back();//出堆顶的数据
			AdjustDown(0);//从跟的位置向下调整

		}

🏠 取出top数据

T& top()
		{
			return _con[0];
		}

🏠 判空

bool empty()
		{
			return _con.empty();
		}

🏠 元素个数（size）

size_t size()
		{
			return _con.size();
		}