C++ queue 和priority_queue

目录

1.什么是queue

2.模拟实现

3.仿函数

模板参数Compare

仿函数

?4.什么是priority_queue

模拟实现

---

1.什么是queue

1.队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

2.队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3.底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

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

empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列

用法跟stack一样，可以看上一篇文章

2.模拟实现

queue.h

#include "string.h"
#include<iostream>
#include<stack>
#include<deque>


using namespace std;

namespace lty
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:

		void push(const T& x)
		{
			_con.push_back(x);
		}

		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;
	};

	void testqueue()
	{
		queue<int,deque<int>> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		q.push(5);

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

	}
}

queue.cpp

#include "queue.h"

using namespace std;

int main()
{
	lty::testqueue();
}

3.仿函数

模板参数Compare

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> maxHeap; // 默认大堆

    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 小堆

    maxHeap.push(5);
    maxHeap.push(3);
    maxHeap.push(8);

    minHeap.push(5);
    minHeap.push(3);
    minHeap.push(8);

    std::cout << "Max Heap (Top element): " << maxHeap.top() << std::endl;
    std::cout << "Min Heap (Top element): " << minHeap.top() << std::endl;

    return 0;
}

?

仿函数

仿函数实际就是一个类，这里类实例化出来的对象叫做函数对象，下面命名空间wyn中的两个仿函数就分别是两个类，在使用时直接用类进行实例化对象，然后让对象调用()的运算符重载，这样我们看到的调用形式就非常像普通的函数调用，但实际上这里并不是函数调用，而是仿函数实例化出来的对象调用了自己的operator()重载成员函数。

?

namespace lty
{
	template <class T>
	class less
	{
	public:
		bool operator()(const T& x, const T& y)const
		{
			return x < y;
		}
	};
	
	template <class T>
	class greater
	{
	public://将仿函数放成public，要不然class默认是私有的
		bool operator()(const T& x, const T& y)const
		{
			return x > y;
		}
	};
}
int main()
{
	lty::less<int> lessFunc;
	lty::greater<int> greaterFunc;
	lessFunc(1, 2);
	//你以为这里是函数调用，但他其实是仿函数对象lessFunc调用了他的成员运算符重载()函数。
}

?4.什么是priority_queue

优先级队列的适配会更复杂一些些。它的适配容器用的是vector。

优先级队列就不是什么先进先出了，它虽然叫队列，但它不是真队列。其实它的底层是堆，可以在任意时刻插入数据，默认是大堆，当然也可以通过仿函数去调整。

优先级队列有一个反人类的设计：传less仿函数，底层是大堆。传greater仿函数，底层是小堆。

它的一些接口

priority_queue和queue以及stack一样，他们都是由底层容器适配出来的适配器，之不过priority_queue采用的适配容器不再是deque而是vector，选择vector的原因也非常简单，在调用向上或向下调整算法时，需要大量频繁的进行下标随机访问，这样的情境下，vector就可以完美展现出自己结构的绝对优势

模拟实现

#pragma once

namespace lty
{
	// Compare进行比较的仿函数 less->大堆
	// Compare进行比较的仿函数 greater->小堆
	template<class T, class Container = vector<T>, class Compare = std::less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}

		template <class InputIterator>         
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			for (int i = (_con.size()-1-1)/2; i >= 0; --i)
			{
				adjust_down(i);
			}
		}

		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child],_con[child + 1]))
				{
					++child;
				}


				if (com(_con[parent],_con[child]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			adjust_down(0);
		}

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

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

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

	private:
		Container _con;
	};
}

命名空间 xzq：
这段代码位于命名空间 xzq 中，这是一个自定义的命名空间，用于将相关的类、函数等封装在一起，以避免与其他代码的命名冲突。

模板类 priority_queue：
这是一个模板类，它代表了一个优先队列的实现。它接受三个模板参数：T（元素类型），Container（底层容器类型，默认为 std::vector<T>），和 Compare（用于比较元素的仿函数，默认为 std::less<T>）

Compare 是一个模板参数，用于进行元素的比较。它是一个仿函数，可以是 std::less<T>（默认）或 std::greater<T>，具体取决于用户提供的优先队列类型。Compare 仿函数用于确定在堆中的元素排序方式，从而决定了是最大堆还是最小堆。在 priority_queue 类的各个成员函数中，通过调用 Compare 仿函数来进行元素的比较，从而实现了插入和调整堆的操作。

构造函数 priority_queue()：
这是一个默认构造函数，不需要使用 Compare 仿函数进行比较。

构造函数模板 priority_queue(InputIterator first, InputIterator last)：
在构造函数内部，使用 Compare 仿函数来执行比较操作，以确定元素的顺序。在添加元素后，通过调用 adjust_down 函数来构建堆。

成员函数 adjust_up(size_t child)：
在上浮操作中，使用 Compare 仿函数执行比较，以确定是否需要交换父子节点的位置，从而保持堆的性质。

成员函数 push(const T& x)：
在插入操作中，首先将新元素添加到底层容器 _con，然后通过调用 adjust_up 函数来执行上浮操作，保证新元素位于合适的位置。

成员函数 adjust_down(size_t parent)：
在下沉操作中，使用 Compare 仿函数执行比较，以确定是否需要交换父子节点的位置，从而保持堆的性质。

成员函数 pop()：
在删除操作中，首先将顶部元素与底层容器的最后一个元素交换，然后通过调用 adjust_down 函数来执行下沉操作，保证堆的性质。

成员函数 const T& top()：
通过返回 _con[0]，获取优先队列的顶部元素。
?