【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

这篇具有很好参考价值的文章主要介绍了【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这篇文章我们接着上一篇的内容,再来学一个STL里的容器适配器——priority_queue(优先级队列)

1. priority_queue的介绍和使用

1.1 priority_queue的介绍

我们上一篇文章学了queue(队列),那优先级队列也是在<queue>里面的:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

queue一样,priority_queue也是一个容器适配器,那他和queue有什么区别呢?我们一起来认识一下priority_queue
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

  1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
  2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
  3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
    empty():检测容器是否为空
    size():返回容器中有效元素个数
    front():返回容器中第一个元素的引用
    push_back():在容器尾部插入元素
  5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
  6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
首先我们看到它的默认底层容器不再是deque了,而是vector
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
当然不是只能用vector,只要支持这些操作的容器都可以,另外我们看到他对容器的迭代器是有要求的,要求得是随机迭代器random access iterators

那现在问一下大家,听到优先级队列有没有感到有点熟悉?

或者我们可以来看一下它的成员函数:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
有没有感觉有点熟悉?
🆗,这不就是我们之前数据结构学过的堆嘛(如果大家之前没有了解过堆或者遗忘了可以去看一下之前的文章)
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
我们在讲解堆的时候也提到过,优先级队列就是堆。

1.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

经过数据结构阶段的学习,这些常见的接口我们是可以直接上手使用的,其它的接口如果后续用到大家可以自己查阅文档,这里就不展开介绍了。

【注意】
默认情况下,priority_queue是大堆(大的优先级高)

我们来验证一下:

int main()
{
	priority_queue<int> q;
	q.push(1);
	q.push(0);
	q.push(5);
	q.push(2);
	q.push(1);
	q.push(7);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;

	return 0;
}

看一下结果:

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

那如果我们想使用小堆怎么做呢?

🆗,这时候就要用到一个东西叫做仿函数
怎么做呢?
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
我们要多传一个参数,即对应第三个模板参数。
不过呢,因为Compare 这个模板参数被设计在了第三个位置,所以我们要传第三个的话,也要传一下第二个。
那我们现在优先级队列里面放的是整型,就可以传一个greater<int>,让它变成小堆:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

int main()
{
	priority_queue<int, vector<int>, greater<int>> q;
	q.push(1);
	q.push(0);
	q.push(5);
	q.push(2);
	q.push(1);
	q.push(7);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;

	return 0;
}

那这个地方大家可能有这样的疑惑:

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
我们看到第三个模板参数给的缺省值是less <value_type>,less不是较小的意思嘛,但是默认对应的却是大堆;而我们把它变成小堆传的是 greater <value_type>,而greater却是较大的意思。
那除此之外:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
第二个模板参数是不是放到第三个位置比较好一点啊,因为默认容器我们一般不会去动它,但是第三个参数控制这个优先级,我们可能需要经常换,那这样我们传递三个参数的时候就必须把第二个也传上,但第二个一般我们不需要动,用默认的就是比较好的。
所以这个地方感觉设计的好像不是很好。

1.2.1 仿函数介绍

然后我们来解释一下这里用到的 greater<int>是个啥?
那我们先来认识一个东西——仿函数
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
他也是STL的六大组件之一。
那什么是仿函数呢?
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
🆗,仿函数(又称函数对象)其实就是一个类重载了(),使得这个类的使用看上去像一个函数。

举个栗子:

我们来写一个判断小于的仿函数,怎么做呢?
定义一个类,重载一下()就行了,函数体的实现根据我们的需求去写:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
ps:也可以用class,区别只是它的的默认访问限定符不同。
那我们来用一下这个仿函数:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
1小于2为真,所以打印结果为1。
🆗,那如果我们只看这一行:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
是不是就像是一个函数调用啊。
当然它本质是去调用了类里面的operator()

那要告诉大家的是仿函数它的作用和价值还是很大的,不过我们现在还不能很好的体会到。
C++其实本质搞出这个东西是因为函数指针太复杂了,而仿函数在很多场景能达到一个替代函数指针的作用。
就比如我们这里优先级队列控制这个大堆小堆,我们之前实现过堆,我们知道控制大堆小堆其实就是就是控制里面元素的比较方式不同。
那我们C语言解决这样的问题是不是就是去传一个函数指针嘛,就比如C语言里面那个qsort函数:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
它是不是就是通过传递一个函数指针来控制元素的比较方式啊。
而C++的sort就可以传仿函数去控制:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
当然不是只能传仿函数,我们看到它给的是一个模板。

那我们上面用到的greater包括默认给的less其实就是库里面提供的仿函数。

当然我们看到它可以写成这样greater<int>,那库里面的其实是实现成模板了。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
而我们刚才这样写的是只针对整型,如果像比较任意类型我们就可以将他实现成模板:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

1.2.2 在OJ中的使用:数组中的第K个最大元素

下面我们来看一个题:数组中的第K个最大元素
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

思路1:排序

那这道题我们最容易想到的方法应该就是堆数组排个序,如果数组是有序的,那我们想拿到第k个最大的元素,不是轻而易举嘛。
那直接用sort排序就行了,要注意sort默认是升序。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
但是题目要求时间复杂度为 O(n) ,那我们还有没有其它更好的算法呢?

思路2:priority_queue

🆗,我们是不是可以考虑使用优先级队列(堆)来搞啊。

那我们现在要使用优先级队列的话,还需要自己写吗?
是不是可以直接用啊——priority_queue
怎么做呢?
那我们知道它默认是大堆,那我们就用大堆,首先我们拿数组的数据建堆,怎么建?
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
我们可以选择这个迭代器区间的这个构造函数。
拿建好堆之后,默认是大堆,那我们就可以pop k-1次,然后堆顶的那个数据不就是第K个最大的数了嘛。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> q(nums.begin(),nums.end());
        while(--k)
        {
            q.pop();
        }
        return q.top();
    }
};

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

那这种写法的时间复杂度应该是多少呢?
🆗,应该是O(N+k*logN),大家可以自己算一下,这里建堆包括pop的时间复杂度我们之前二叉树的文章也讲过。

那还要其它方法吗?

思路3:TOP-K思想

我们还可以考虑用TOP-K的思想去解决这道题:
首先我们来复习一下TOP-K(时间复杂度是O(N*log2K))的思想,这也是我们之前文章讲过的内容:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那这道题我们可以怎么做呢?

我们是不是可以先拿前K个数建堆,这里我们想要获取最大得前K个,应该建小堆,然后一个个比较,不符合大小关系就调整,最终堆中得数据就是最大的前K个,那此时堆顶得数据不就是我们要的数嘛。
当然我们现在用的是库里面的priority_queue,没有向下调整这些接口,而且top返回的也是引用,也不能直接替换堆顶数据,所以我们可以先pop,然后再push。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //建小堆
        priority_queue<int,vector<int>,greater<int>> q(nums.begin(),nums.begin()+k);
        for(size_t i=k;i<nums.size();++i)
        {
            if(nums[i]>q.top())
            {
                q.pop();
                q.push(nums[i]);
            }
        }
        return q.top();
    }
};

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

2. priority_queue的模拟实现

那我们接下来就对priority_queue进行一个模拟实现:

那我们还是按照库里面的来,把它实现成一个容器适配器的类模板
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那它的结构就是这样的,第三个模板参数即比较的仿函数我们放到后面再搞。

2.1 核心接口

然后先我们来实现一下它的几个核心的接口:

首先写一下push:
那我们再来复习一下,堆的push怎么搞的?
🆗,堆的逻辑结构是一个完全二叉树,其物理结构,即底层实际的存储结构是一个一维数组(我们这里使用的是vector),我们push的时候先尾插一个数据,然后是不是要对它进行向上调整啊,确保插入新数据之后它还是一个堆。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那我们待会还要实现一下向上调整。
然后pop,再来回忆一下,堆的删除怎么搞?
🆗,是不是将堆顶的数据跟最后一个数据进行交换,然后删除数组最后一个数据,再进行向下调整啊。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
当然待会我们也要写一下向下调整。
然后top,那就简单了:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
然后还有size:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
empty:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
然后我们回过头来把向上调整实现一下。

2.2 向上调整

向上调整怎么搞(这里我们默认先按大堆来搞),回忆一下:

怎么调?
首先进行向上调整要保证之前的数据必须是一个堆。
然后看插入的数据满足不满足对应的大小关系,不满足就进行交换,直到满足为止。

100这个结点是不是大于它的父亲啊,那大堆中大的才应该做父亲,所以呢,就应该交换100和30这两个结点。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那调整一次就完了吗?
如果调整一次后满足了,那确实就结束了,但是现在是不是还不满足是一个大堆啊,那就要继续调整。
100还是大于它的父亲70:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

所以:

这个调整应该是一个循环的过程,那循环什么时候结束呢?
当调整到所有结点都满足大堆或小堆的关系时,或者需要一直调整,当插入的新数据一直交换到成为根结点时就结束了。
当然如果插入的数据直接满足,那一次也不需要调整。

我们把这种从下往上调整的算法叫做向上调整。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

思路还是和我们之前讲的一样。

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

2.3 向下调整

然后向下调整呢?
如何调整:

其实思路跟向上调整一样,只不过这次我们是从上往下,不符合关系的进行交换,直至使它成为一个新的大堆。

我们开始调整:

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
18在这里肯定不合适,它比自己的孩子还要小,所以要交换。
和谁交换?
34可以吗,34换到堆顶,它是不是还撑不住啊。
所以我们要选择它的孩子中大的那一个进行交换。
那在这里就是49。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

那现在18坐到原来49的位置,现在这个位置怎么样?

🆗,18是不是还是坐不稳啊。
还得进行交换。
选择18的孩子中大的那一个交换:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
现在是不是就可以了啊。
我们交换了两次完成了,所以这还是一个循环的过程。

那这个循环的交换过程应该什么时候停止?

是不是当交换到满足大小关系或者一直交换,直到自己成为叶子结点时结束啊。

void adjust_down(size_t parent)
{
	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		//得出较大(小堆则较小)的那个孩子
		if (child + 1 < _con.size()
			&& _con[child] < _con[child + 1])
			child++;

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

那我们来测试一下我们写的priority_queue

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
没问题。

2.4 仿函数less和greater模拟实现及使用

那然后呢我们把第三个模板参数加上,把仿函数实现一下:

我们刚才实现的是大堆,那我们想要小堆怎么办?
我们之前数据结构学习堆的时候就知道了,是不是把向上向下调整里面的比较的大于号换成小于就行了啊
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
但是,经过我们上面的学习以及对仿函数的介绍,我们是不是可以通过传仿函数去控制啊。
所以我们要增加一个模板参数,然后通过两个仿函数去控制比较大于还是比较小于,以此控制大堆还是小堆。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那怎么使用第三个参数呢?
我们这里和库里面保持一样,默认第三个参数class Compare的缺省值是仿函数less,对应的是大堆。
那这样做就可以了:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那这下我们就可以通过仿函数去控制大小堆 了。

来试一下:

现在默认用less是大堆:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那想要小堆怎么办?用greater就行了:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
🆗,就好了,大家理解一下这个过程:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
当然也可以这样写【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
就是用匿名对象嘛。

3. priority_queue 存放自定义类型数据

下面我们再来研究一个问题:

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);
private:
	int _year;
	int _month;
	int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}

现在有一个日期类,并重载了<<><

那现在呢,我想用我们的priority_queue(优先级队列)去存我们的自定义类型数据——日期类的变量,可以吗?

我们来试一下:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
没问题,可以,现在默认是大堆嘛,所以top是最大的那个日期。
如果换成小堆:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
那堆顶就是最小的。
那这里为什么可以,其实是因为我们的日期类重载了><,因为它里面建堆的过程是不是要进行比较啊。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
如果没有><的重载就不行了。
所以:
如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载

4. 拓展

🆗,再来看,如果是这样呢:

【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
现在它里面存的是Date* 的指针,我们来看下结果:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
好像没什么问题,不过结果好像不对。
而且:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
我们重新编译一下,再运行
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
哎呀,怎么回事。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
怎么结果会变化啊,为什么呢?

🆗,原因在于:

我们现在里面存的是啥,是Date* 的指针变量,那指针能比较大小嘛?
当然也可以,它是内置类型,指针比较大小的话就是去比较对应地址的大小嘛。
但是这里我们new出来的地址,它们的大小关系可认为是随机的,所以虽然可以比,但是这结果是我们想要的嘛,是不是不是啊。
我们想要的的是不是去比较它们指针指向的Date类对象的大小啊

指针是内置类型,我们也没法重载它的比较操作,那怎么办呢?

我们是不是可以使用仿函数来解决啊。
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
然后我们再运行:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
就会发现结果正确并且不会变化了。
那如果要小堆,很简单,再搞一个仿函数:
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用
就可以了。
所以这里我们看到有了仿函数,即使是内置类型,这里我们也可以去控制它的比较方式。

5. 源码展示

5.1 priority_queue.h

#pragma once
#include <vector>

namespace yin
{
	template <class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template <class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	template <class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void adjust_up(size_t child)
		{
			//Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[child] > _con[parent])等同于if (_con[parent] < _con[child])
				if (Compare()(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}
		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				//得出较大(小堆则较小)的那个孩子
				if (child + 1 < _con.size()
					//&& _con[child] < _con[child + 1])
					&& com(_con[child], _con[child + 1]))
					child++;

				//if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}
		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		const T& top() const
		{
			return _con[0];
		}
		size_t size() const
		{
			return _con.size();
		}
		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

5.2 test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
//#include <queue>
#include "priority_queue.h"

//int main()
//{
//	priority_queue<int, vector<int>, greater<int>> q;
//	q.push(1);
//	q.push(0);
//	q.push(5);
//	q.push(2);
//	q.push(1);
//	q.push(7);
//	while (!q.empty())
//	{
//		cout << q.top() << " ";
//		q.pop();
//	}
//	cout << endl;
//
//	return 0;
//}

仿函数
//template <class T>
//struct Less
//{
//	bool operator()(const T& x, const T& y)
//	{
//		return x < y;
//	}
//};
//int main()
//{
//	Less<int> lessfunc;
//	cout << lessfunc(1, 2) << endl;
//
//	return 0;
//}

//int main()
//{
//	//yin::priority_queue<int> q;
//	yin::priority_queue<int, vector<int>, greater<int>> q;
//
//	q.push(1);
//	q.push(0);
//	q.push(5);
//	q.push(2);
//	q.push(1);
//	q.push(7);
//	while (!q.empty())
//	{
//		cout << q.top() << " ";
//		q.pop();
//	}
//	cout << endl;
//
//	return 0;
//}

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);
private:
	int _year;
	int _month;
	int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}

//int main()
//{
//	 大堆,需要用户在自定义类型中提供<的重载
//	//yin::priority_queue<Date> q1;
//	//q1.push(Date(2018, 10, 29));
//	//q1.push(Date(2018, 10, 28));
//	//q1.push(Date(2018, 10, 30));
//	//cout << q1.top() << endl;
//
//	return 0;
//}

struct PDateLess
{
	bool operator()(const Date* p1, const Date* p2)
	{
		return *p1 < *p2;
	}
};
struct PDateGreater
{
	bool operator()(const Date* p1, const Date* p2)
	{
		return *p1 > *p2;
	}
};
int main()
{
	yin::priority_queue<Date*, vector<Date*>, PDateGreater> q2;
	q2.push(new Date(2018, 10, 29));
	q2.push(new Date(2018, 10, 28));
	q2.push(new Date(2018, 10, 30));
	cout << *(q2.top()) << endl;
	return 0;
}

这篇文章的内容就先到这里,欢迎大家指正!!!
【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用文章来源地址https://www.toymoban.com/news/detail-466736.html

到了这里,关于【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [C++] STL_priority_queue(优先级队列) 的使用及底层的模拟实现,容器适配器,deque的原理介绍

    priority_queue文档介绍 翻译: 1. 优先队列是一种 容器适配器 ,根据严格的弱排序标准, 它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于 堆 , 在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配

    2024年02月04日
    浏览(40)
  • C++ [STL容器适配器]

    本文已收录至《C++语言》专栏! 作者:ARMCSKGT 前面我们介绍了适配器模式中的反向迭代器,反向迭代器通过容器所支持的正向迭代器适配为具有反向迭代功能的迭代器,本节我们介绍STL中另一种适配器: 容器适配器 ! 前面我们提到过STL适配器模式,关于适配器的解释: S

    2024年02月11日
    浏览(43)
  • C++ STL学习之【容器适配器】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 A year from now you may wish you had started today. 明年今日,你会希望此时此刻的自己已经开始行动了。 适配器(配接器)是 STL 中的六大组件之一,扮演着轴承、转换器的角色,使得 STL 中组件的使用更为灵活,

    2023年04月22日
    浏览(55)
  • 【C++】STL之容器适配器——使用deque适配stack和queue

    个人主页:🍝在肯德基吃麻辣烫 分享一句喜欢的话:热烈的火焰,冰封在最沉默的火山深处。 本文章主要介绍容器适配器的功能,以及一个适配的场景。 容器适配器,按字面意思理解的话,就是用来对一个容器进行匹配的。在C++STL中,容器有:vector,list,deque,map,set等。

    2024年02月16日
    浏览(54)
  • STL容器适配器 -- stack和queue(使用+实现)(C++)

    栈和队列数据结构+画图分析如果对栈和队列的结构不了解的,可以先看该链接的内容 使用stack时需要头文件 #includestack stack是一种容器适配器,用于具有 后进先出 (LIFO)的环境中。只能从容器的一端(栈顶),执行删除、插入和提取操作。 stack是作为容器适配器实现的,容器

    2024年02月14日
    浏览(61)
  • 【C++入门到精通】C++入门 —— 容器适配器、stack和queue(STL)

    文章绑定了VS平台下std::stack和std::queue的源码,大家可以下载了解一下😍 前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象

    2024年02月12日
    浏览(44)
  • 【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)

    🌏博客主页: 主页 🔖系列专栏: C++ ❤️感谢大家点赞👍收藏⭐评论✍️ 😍期待与大家一起进步! 虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和

    2024年02月15日
    浏览(48)
  • 【STL】顺序容器与容器适配器

    给出以下顺序容器表: 顺序容器类型 作用 vector 可变大小的数组,支持快速访问,除尾元素的插入或者删除很慢 string 与vector相似,只不过专门用来存字符 list 双向链表。只能双向顺序访问,插入删除的效率都很高 forward_list 单向链表。只能单向顺序访问,插入删除的效率都

    2024年04月14日
    浏览(31)
  • 22 标准模板库STL之容器适配器

    概述         提到适配器,我们的第一印象是想到设计模式中的适配器模式:将一个类的接口转化为另一个类的接口,使原本不兼容而不能合作的两个类,可以一起工作。STL中的容器适配器与此类似,是一个封装了序列容器的类模板,它在一般序列容器的基础上提供了一

    2024年02月05日
    浏览(38)
  • STL: 容器适配器stack 与 queue

      目录 1.容器适配器 1.1 STL标准库中stack和queue的底层结构 1.2 deque的简单介绍(了解) 1.2.1 deque的原理介绍 1.2.2 deque的缺陷 1.2.3 为什么选择deque作为stack和queue的底层默认容器 2. stack的介绍和使用 2.1 stack的介绍  2.2 stack的使用 2.3 利用deque模拟实现stack 3.queue的介绍和使用 3.1 queue的

    2024年02月05日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包