【C++】STL--priority_queue（优先级队列）使用及其模拟实现、容器适配器和deque（双端队列）了解

1. priority_queue

1.1. priority_queue的介绍 priority_queue官方文档

• 优先队列是一种容器适配器，按照严格的弱排序标准，顶部一定是当前包含元素中最大的一个
• 优先队列的上下文环境是堆，堆中能够任意插入元素，但是只支持访问最大堆元素（也就是优先队列中的顶部元素）
• 优先队列同样是一种容器适配器，它封装了一个底层标准容器，暴露了堆需要所需要的底层容器的一些必要操作，隐藏了不需要的操作
• 优先队列封装的底层容器可以是标准容器，也可以是其他特定设计的容器，但是这个容器必须要支持随机访问迭代器：
  • empty()：检测容器是否为空
  • size()：返回容器中有效元素个数
  • front()：返回容器中第一个元素的引用
  • push_back()：在容器尾部插入元素
  • pop_back()：删除容器尾部元素
• 标准容器中vector和deque是满足这些条件的，在没有指定底层容器的情况下，默认将vector作为标准容器
• 至于为什么要底层要能够支持随机访问迭代器呢？这是为了方便随时在内部构造堆。容器适配器会在需要的时候调用算法函数，例如make_leap、push_leap、pop_heap等

1.2. priority_quere的使用

优先队列使用vector作为底层容器，并且在vector中加入堆算法，将vector构造成了一个堆，所以可以说优先队列就是一个堆，所以在碰见堆的时候就要想到优先队列。（默认情况下，priority_queue是一个大堆）

我们来看一下下面的代码：

int main()
{
	vector<int> v = { 3,2,5,7,1,10,9,8,6,4 };
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
 
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
 
	cout << endl;
 
	//如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
 
 
	return 0;
}

运行结果：

很明显在没有特殊说明的情况下，直接top()打印priority_queue是从大到小的（说明是一个大堆）。但是我们通过调整priority_queue的第三个参数，也就是前面我们提到的比较规则将弱排序改为greater<>即可实现小顶堆。

1.2.1. 重载<、>

如果priority_queue中包含了自定义类型话，因为需要使用比较器，所以需要对运算符<、>进行重载。

我们使用之前实现过的Date时间类举一个例子：

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{
	}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}
private:
	int _year;
	int _month;
	int _day;
};
void TestPriorityQueue()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2025, 9, 18));
	q1.push(Date(2025, 9, 19));
	q1.push(Date(2025, 9, 20));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2025, 9, 19));
	q2.push(Date(2025, 9, 18));
	q2.push(Date(2025, 9, 20));
	cout << q2.top() << endl;
}

运行结果：

1.3. priority_queue的模拟实现

我们现在已经清楚了，优先队列就是一个堆，并且底层容器是vector，并且默认情况下是最大堆，所以实现起来还是比较好实现的：

//优先级队列 -- 大堆 <  小堆 >
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
	void AdjustUp(int child)
	{
		Compare comFunc;
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			//if (_con[parent] < _con[child])
			if (comFunc(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void AdjustDown(int parent)
	{
		Compare comFunc;

		size_t child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && comFunc(_con[parent], _con[child]))
			{
				++child;
			}
			if (comFunc(_con[parent], _con[child]))
			{
				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()
	{
		assert(!_con.empty());
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}


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

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

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


private:
	Container _con;
};

这里如果有对堆不太熟悉的同学，可以去回顾一下这种数据结构，我后面可能会专门写篇来细讲一下堆的相关知识。

2. 容器适配器

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

2.2. STL标准库中stack、queue的底层结构 虽然后stack和queue也能够存放元素，但是并没有将其划分到容器行列，而是称之为容器适配器。这是因为，stack和queue其实本身并没有涉及到内存的管理之类的底层操作，只是它们内部封装了其他的底层容器，像默认使用的deque：

3. deque

3.1. deque的介绍 vector是单向开口的连续的线性空间，deque是双向开口的连续的线性空间。双向开口的意思就是说，能够在头部和尾部进行元素的删除和插入。虽然说vector也能够在头部进行元素的删除和插入，但是操作的时间效率比较低。

3.1.1. deque和vector的差异：

• deque是双向的，所以支持在常数时间内对头部和尾部元素进行删除和插入操作
• deque是由几段连续的空间组成的，这几段空间通过某种方式连接起来，可以理解成一种伪连续。所以说，deque是没有_capacity的概念的，因为deque随时可以增加空间，这也就避免掉了vector中“空间不够 - 扩容 - 赋值 - 释放原空间”这一过程

3.1.2. deque的空间长什么样 deque是由一段一段的定量连续空间组合而成的，一旦需要再头部或者尾部插入元素，就需要配置一段新的定量连续空间，并且将其串联在头部或尾部。而deque的最大任务就是在分配这些定量的连续空间上，通过提供随机访问接口，制造一种空间整体连续的假象。这样的配置空间方式虽然能够避免vector配置空间“扩容 - 赋值 - 释放”的复杂过程，但代价就是迭代器的复杂化：

deque的迭代器就长下面这样：

3.2. deque的中控器

在上面我们可以看见有一个map，这是干嘛的呢？

deque采用一块所谓的map ( 注意，不是STL的map容器)作为主控，这里所谓的map是一块连续的空间，其中每个元素都是指针，指向另一端(较大的)连续线性空间，称为缓冲区：

map:  [ p0 ][ p1 ][ p2 ][ p3 ] ...
        ↓     ↓     ↓     ↓
       buf0  buf1  buf2  buf3

buf0: [ a0 ][ a1 ][ a2 ] ... [ a63 ]

缓冲区才是deque的储存空间主体。SGI版本的STL库下允许我们指定缓冲区的大小，默认值是0表示将使用512bytes缓冲区。 所以抽象地来说，deque类似于一个动态的二维数组：

• map 是第一维（指针数组）。
• 缓冲区是第二维（每个小数组）。
• 访问第 k 个元素时，先用 k / buffer_size 找到是第几个缓冲区，再用 k % buffer_size 找到缓冲区内的下标。

逻辑索引 k
   ↓
map[k / buffer_size]   → 找到缓冲区指针
   ↓
buffer[k % buffer_size] → 找到元素

看上去就像是二位数字，通过row、col来确定元素位置。

3.3. deque的迭代器 我们刚才讲到了，为了维持整体空间连续的假象，deque的迭代器变得复杂化，那么具体来讲，这个任务会落在迭代器的operator++和operator--两个运算符身上。 接下来我们简单地介绍一下，deque应该做些什么，这样比较好理解为什么我们说它十分复杂：

• 首先我要能够指向分段连续空降buffer（缓冲区）的位置
• 并且能够判断是否处于buffer的边缘
• 当处于头部或者尾部边缘时，那么前进或者后退操作必将导致跳跃到上一个或者下一个缓冲区
• 这也就要求随时掌管map中控器

3.4. deque的缺陷

• 与vector 比较 ，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高 ，而且在扩容时，也不需要搬移大量的元素，因此其效率是必 vector 高的。
• 与list比较 ，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

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

4. 为什么选择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 不仅效率高，而且内存使用率高。

也就是说，不用遍历的特性避开了deque的缺陷，同时deque能够发挥它的优点！

（本篇完）