【C++初阶】仿函数和priority_queue的模拟实现（附源码）

心已赠人 2024-04-22 12:12 65阅读 0赞

## 一.仿函数 ##

> 仿函数，顾名思义就是模仿函数，它其实是一个类，类里面重载了运算符（），在调用这个重载的运算符时，让我们感觉是调用函数一样，可以说相当于C语言里的函数指针一样，但是函数指针的可读性不好，不如仿函数。

### 仿函数的特点 ###

> 1.仿函数即使定义相同，也可能有不同的类型；
> 
> 2.仿函数通常比一般函数速度快；
> 
> 3.仿函数使程序代码变简单。

### 例子 ###

template<class T>
    class Less
    {
    public:
    	bool operator()(const T& x, const T& y)
    	{
    		return x < y;
    	}
    };
    
    int main()
    {
    	int a = 10, b = 20;
    	Less<int> Le;
    	cout << Le(a, b) << endl;   //像函数一样调用
    
    	return 0;
    }

--------------------

## 二.模拟实现priority\_queue ##

> priority\_queue即优先级队列，它的底层是一个堆，且默认是大堆，所以在模拟实现优先级队列时要先建堆，不了解的话可以参考文章：[堆的实现][Link 1]

相关接口：

![0c7c7660bdb0444ebc6bfc71114f1863.png][]

### 源码 ###

//less是库里的仿函数， 用来判断左操作数是否小于右操作数，可以用来建大堆
    //greater也是库里的仿函数，比较左操作数是否大于右操作数，可以用来建小堆
    //库里比较的是内置类型的大小，如果是自定义类型，那么自定义类型里就必须要重载 > 或 < 运算符
    template<class T,class Containers=vector<T>,class Compare=less<T>> 
    	class priority_queue
    	{
    	private:
            //默认建大堆
    		//向下调整
    		void AdjustDown(int parent)
    		{
    			Compare com;
    			int child = 2 * parent + 1;
    			while (child < _con.size())
    			{
    				if (child + 1 < _con.size() && com(_con[parent], _con[child+1]))
    				{
    					child++;
    				}
    				
    				if (com(_con[parent], _con[child]))
    				{
    					std::swap(_con[parent], _con[child]);
    					parent = child;
    					child = 2 * parent + 1;
    				}
    				else
    					break;
    			}
    		}
    
    		//向上调整
    		void AdjustUp(int child)
    		{
    			Compare com;
    			int parent = (child - 1) / 2;
    			while (child > 0)
    			{
    				if (com(_con[parent], _con[child]))
    				{
    					std::swap(_con[parent], _con[child]);
    					child = parent;
    					parent = (child - 1) / 2;
    				}
    				else
    					break;
    			}
    		}
    	public:
    		priority_queue()   //默认构造
    		{
    			;
    		}
    		template<class Inputiterator>   //迭代器区间构造
    		priority_queue(Inputiterator first, Inputiterator last)
    		{
    			while (first != last)   //插入数据
    			{
    				_con.push_back(*first);
    				first++;
    			}
    
    			//建堆
    			for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
    			{
    				AdjustDown(i);
    			}
    		}
    
    		void push(const T& x)   //插入
    		{
    			_con.push_back(x);
    			//AdjustDown(0);
    			AdjustUp(_con.size() - 1);
    		}
    
    		void pop()
    		{
    			std::swap(_con[0], _con[_con.size() - 1]);  //第一个元素和最后一个元素交换
    			_con.pop_back();
    
    			AdjustDown(0);
    		}
    
    		const T& top()  const  //取堆顶数据
    		{
    			return _con[0];
    		}
    
    		bool empty()
    		{
    			return _con.size() == 0;
    		}
    
    		size_t size() 
    		{
    			return _con.size();
    		}
    
    	private:
    		Containers _con;
    	};

--------------------

## 三.例题：数组中K个最大的元素 ##

### 链接： ###

### [数组中第K个最大的元素][K] ###

### 题目再现： ###

![c92696404b1e4047917147fb7257c3bf.png][]

### 题解： ###

> 这个就类似于topk问题，我们可以先建个大堆（大堆是排降序，小堆是排升序），然后出掉前 K-1 个数据，此时堆顶数据即最终的答案，并返回。

> 之前在C语言那里的时候，还得自己造轮子，手搓一个堆出来，但是C++不用了，直接使用优先级队列priority\_queue

class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) 
        {
            priority_queue<int> pq;   //建大堆
            for(auto& e:nums)
            {
                pq.push(e);   //插入数据到堆里
            }
    
            while(--k)   //出掉前k-1个数据
            {
                pq.pop();
            }
    
            return pq.top();   //返回堆顶数据
        }
    };

### ![15fdccbe01c9443fa6ce40fbd0e2cf9b.png][] ###

--------------------

> **??本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；?️?**
> 
> **??希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；??**
> 
> **??谢谢你的阅读。??**

[Link 1]: https://blog.csdn.net/m0_73868817/article/details/129773938
[0c7c7660bdb0444ebc6bfc71114f1863.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/bfc0d26f8ad346688e72210fb4dff354.png
[K]: https://leetcode.cn/problems/kth-largest-element-in-an-array/
[c92696404b1e4047917147fb7257c3bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/d32044eb30424bc8806ffcf63166a9da.png
[15fdccbe01c9443fa6ce40fbd0e2cf9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/121f46ba4b034002a7e726143d91e00a.png