仿函数：对优先级队列的优化【C++】

一.仿函数

我们从它的名字上也能大致猜出个他的作用：模仿函数

1.1 定义形式

class less 
{
public:
	bool operator()(int x, int y)
	{
	
	}


};

1
2
3
4
5
6
7
8
9
10
11

这个仿函数确实是个模仿函数的，它的本质就是个类
并且对（）符号进行了重载

1.2 使用

其实能体现它模仿函数的特点：
其实是在使用的时候体现的。

int main()
{
	less test;
	test(1, 2);

}
1
2
3
4
5
6

这里我们将less类实例化，取名为test

当我们需要调用less函数中的()符号时，按照要求应该是：

test()(1,2);
1

但是这样就不长得像函数了，所以编译器就进行了优化
变成了：test(1,2)的调用方式。

这样长得就很像函数了。

二.仿函数对优先级队列的优化

这里举个优先级队列的例子，因为仿函数对优先级队列的实现有很大的优化。

同时及为了让大家更好了解到仿函数的使用场景

2.1 优先级队列

优先级队列：STL中的一种容器。

看起来取了一个队列的名字，但是和队列不能说像把，只能说毫无关系。
但是实际上的本质是我们以前的老朋友：堆

实际上堆的构建和实现博主以前其实都写过。
这里偷懒就不讲堆的构建思路了，就贴一个以前的博客。
堆的构建以及删除

2.1.1普通版

这里我们先对构造函数和向下调整来进行分析
因为仿函数能对优先级队列很多的接口进行优化，这里就挑一个进行讲解

i. 构造函数

template<class inputitetator>
priority_queue(inputitetator first, inputitetator last)
{
	while (first != last)
	{
		_con.push_back(*first);
		first++;
	}
	for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
	{
		adjustdown(i);
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

ii. 向下调整

void adjustdown(int parent)
{
	int child = parent * 2 + 1;
	while (child <= _con.size() - 1)
	{
		if (child + 1 <= _con.size() - 1 && if(con[child]< _con[child+1])
		{
			child++;
		}
		if (if(_con[parent]< _con[child]))
		{
			swap(_con[parent], _con[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这里大家有没有发现这个构造函数的缺陷了。

这个构造函数只能支持小堆的初始化
我们这里可以想想如果我们想要实现大堆的初始化需要干什么。

2.2.1 用仿函数优化

i. 回顾库

这里我们来回顾一下STL库中的优先级队列。

我们知道STL库中的默认类型是大堆。

那如果我们想要初始化成小堆呢？

在使用STL时，可以这么穿参数

std::priority_queue<int,std::vector<int>,std::greater<int>> pq1;
1

可以传一个 greater的类型。

这样就自动完成了大小堆的初始化分割。

接下来我们就要将我们的优先级队列优化成库中的类型。

ii. 实现大小堆的关键

我们想要实现大小堆的分隔，我们首先要知道大小堆构造的时候是从什么地方进行区分的。

关键就是在这个向下调整的函数中

void adjustdown(int parent)
{
	int child = parent * 2 + 1;
	while (child <= _con.size() - 1)
	{
		if (child + 1 <= _con.size() - 1 && con[child]< _con[child+1])
		{
			child++;
		}
		if (_con[parent]< _con[child])
		{
			swap(_con[parent], _con[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我们仔细看了代码后就能发现，决定堆中元素的分布是由其中的这串代码决定的。

if (_con[parent]< _con[child])
		{
			swap(_con[parent], _con[child]);
			parent = child;
			child = child * 2 + 1;
		}
1
2
3
4
5
6

这个函数决定了父节点和子节点的比较关系来确定是否要进行交换。

同时还有上面的一个部分

if (child + 1 <= _con.size() - 1 && con[child]< _con[child+1])
1

这个代码决定的前后两个子节点的交换关系

这里我们知道这两个就是堆分配关键后
我们应该能想到：只要控制了他们的大小关系，就能控制了大堆还是小堆。

iii.优化思路

我们现在知道了改变大小关系，就能改变他们的大小堆初始化。

那我们可不可以写两个比较函数
一个用来返回大于比较结果，一个用来返回小于号比较结果

确实可以用比较函数
但是这里我们要使用比较函数的话，就要用到函数指针
相信写过C语言的大伙应该都知道函数指针可读性有多差

所以现在，我们的主角：仿函数盛大登场。

我们知道仿函数本质是个类，所以仿函数还有一个关键的作用：
可以带模板

iiii. 比较仿函数的实现

这里博主的大于小于符号的实现搞错了，但是无伤大雅
因为思路都是一样的

template<class T>
class less
{
public:
	bool operator()(T& x, T& y)
	{
		return x < y;
	}
};
1
2
3
4
5
6
7
8
9

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

};

1
2
3
4
5
6
7
8
9
10
11

这里就是很容易的实现了，这里实现两种比较方式。
同时我们也能发现仿函数的另一个优势：
因为仿函数本质是类，所以可以用模板，这样想实现泛用性就十分简单

同时：
还记得上面我们使用STL库中的优先级队列时
需要传一个greater的参数吗
其实传的参数就是仿函数的类

所以我们是通过优先级队列类的参数模板来控制选哪个仿函数的
所以接下来我们就需要堆优先级队列的模板进行调整

iiiii. 优先级队列类的调整

这里其实就是在声明前，添加一个新类型，专门用来接收仿函数类型
同时给一个缺省值，防止用户忘记传参

template<class T, class container = std::vector<int>, class heapstyle = less<int> >
class priority_queue
{

}；
1
2
3
4
5

接下来就剩最后有个优化向下调整了

iiiiii. 优化向下调整

void adjustdown(int parent)
		{
		//因为仿函数本质是类，所以我们需要先对仿函数进行实例化
			heapstyle com;
			int child = parent * 2 + 1;
			while (child <= _con.size() - 1)
			{
			//用仿函数的重载符替代比较式
				if (child + 1 <= _con.size() - 1 && com(_con[child], _con[child+1]))
				{
					child++;
				}
				//用仿函数的重载符替代比较式
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = child * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

三.优先级队列实现的整体代码：

#include
#include


namespace priority_queue
{

	template<class T>
	class less
	{
	public:
		bool operator()(T& x, T& y)
		{
			return x < y;
		}

	};

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

	};

	template<class T, class container = std::vector<int>, class heapstyle = less<int> >
	class priority_queue
	{
	private:
		void swap(T& first, T& last)
		{
			T tmp = first;
			first = last;
			last = tmp;
		}

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

		void adjustdown(int parent)
		{
			heapstyle com;
			int child = parent * 2 + 1;
			while (child <= _con.size() - 1)
			{
				if (child + 1 <= _con.size() - 1 && com(_con[child], _con[child+1]))
				{
					child++;
				}
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = child * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	

	public:
		template<class inputitetator>
		priority_queue(inputitetator first, inputitetator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				first++;
			}
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjustdown(i);
			}

		}
		void push(const T& val)
		{
			_con.push_back(val);
			adjustup(_con.size() - 1);
		}
		T& top()
		{
			return _con[0];
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			if (_con.size() == 0)
			{
				return;
			}
			adjustdown(0);
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		container _con;
	};

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125