C++优先级队列priority_queue、仿函数
文章目录
- 一、priority_queue的介绍和使用
- 1.1 priority_queue的介绍
- 1.2 priority_queue的使用
- 二、priority_queue的模拟实现
- 2.1 模拟实现SLT库中的priority_queue
- 2.2 库中的less与greater函数对象
- 2.3 priority_queue中存放自定义类型
- 三、仿函数
- 3.1 什么是仿函数？
- 3.2 仿函数的应用举例
一、priority_queue的介绍和使用
1.1 priority_queue的介绍
1.优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2.优先级队列类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先级队列中位于顶部的元素)。
3.优先级队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部“弹出，其称为优先级队列的顶部。
4.底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作:
○ empty():检测容器是否为空
○ size():返回容器中有效元素个数
○ front():返回容器中第一个元素的引用
○ push_back():在容器尾部插入元素
○ pop_back():删除容器尾部元素
5.标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6.需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
1.2 priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
注意: 默认情况下priority_queue是大堆。
| 函数声明 | 接口说明 |
|---|---|
| priority_queue()/priority_queue(first, last) | 构造一个空的优先级队列 |
| empty() | 检测优先级队列是否为空，是返回true，否则返回false |
| top() | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
二、priority_queue的模拟实现
2.1 模拟实现SLT库中的priority_queue
要模拟实现库中的priority_queue就要先了解库中的优先级队列的底层是什么样！下面是库中的priority_queue声明：
可以看到库中的优先级队列也是一个类模版，并且有三个模版参数。第一个参数就是要在队列中存储的元素类型；第二个参数是一个容器，所以优先级队列其实是通过容器来适配的；而第三个参数是一个仿函数(函数对象)，这个在下面会讲，只要知道这个仿函数默认传的缺省值是一个类类型，并且这个默认的缺省值类型要求的是建大堆。
由于优先级队列的底层结构就是堆，所以主要的是实现push和pop:
template<class T,class Container = vector<T>,class Compare = Less<T>>
class priority_queue
{
public:
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
Compare com; //函数对象
while (child > 0)
{
//if (_con[parent] < _con[child])
if(com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
Compare com; //函数对象
//if (child + 1 < _con.size()
// && _con[child] < _con[child + 1])
if(child + 1 < _con.size()
&& com(_con[child], _con[child + 1]))
{
child++;
}
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
如果没有显式给出仿函数，默认会用缺省值less(库中的less类)，那建的就是大堆。当然我们也可以自己实现仿函数的功能，并在实例化的时候传递：
//仿函数(函数对象)
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
//仿函数(函数对象)
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
void test_simulate_priority_queue()
{
PriQ::priority_queue<int,vector<int>,Less<int>> q; //传Less是建大堆
//PriQ::priority_queue<int,vector<int>,Greater<int>> q; //传Greater是建小堆
q.push(5);
q.push(1);
q.push(4);
q.push(3);
q.push(7);
q.push(6);
while (!q.empty())
{
cout << q.top() << " ";
q.pop();
}
cout << endl;
}
模拟实现priority_queue中就是通过仿函数来控制是建大堆还是建小堆的。因为大堆小堆的父子节点之间的大小关系就是通过仿函数来进行比较调整的。(注：上面的priority_queue是在PriQ这个命名空间域里实现的)
2.2 库中的less与greater函数对象
SLT库中也实现得有比较大小的函数对象less和greater:
比如我们要对一个数组进行排序，那可以用算法库中的sort函数来排序。例如我们要排一个降序排序，那就可以传greater类型的对象：
void test_Sort_PutFunc()
{
int a[] = { 4,1,8,3,2,5,7,6 };
//对a数组进行降序排序
sort(a, a + 8, greater<int>()); //greater<int>()是匿名对象
//下面的函数调用等价于上面一行
//greater<int> gt;
//sort(a, a + 8, gt);
for (auto e : a)
{
cout << e << " ";
}
cout << endl;
}
可以发现上面的sort函数中，对于第三个参数传的是一个geater类型的(匿名)对象，而我们在模拟实现优先级队列中传的是一个(类)类型。这是为什么呢？来看一下库中的sort函数与priority_queue容器的定义：
通过上图可以看到sort是函数模版，那函数的参数部分要求传的是一个对象；而priority_queue是一个类模版，而模版参数要求传的是一个类型，不是对象，但是我们在模拟实现优先级队列的里面也会先用这个类型去实例化出一个对象，然后再用这个对象去调用operator()函数。所以优先级队列的仿函数相较于sort函数，其实就是多了一层步骤而已，本质都是需要实例化出一个对象，通过这个对象才能去调用函数。
2.3 priority_queue中存放自定义类型
如果在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;
}
void TestPriorityQueue()
{
//大堆,需要用户在自定义类型中提供<的重载
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;
// 如果要创建小堆,需要用户提供>的重载
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(Date(2018, 10, 29));
q2.push(Date(2018, 10, 28));
q2.push(Date(2018, 10, 30));
cout << q2.top() << endl;
}
int main()
{
TestPriorityQueue();
return 0;
}
程序运行结果：
三、仿函数
3.1 什么是仿函数？
在C++中，仿函数(Functor) 是一种通过重载函数调用运算符operator()使得对象可以像函数一样被调用的机制。以下是仿函数的关键点解析：(仿函数也叫做函数对象)
1.对象模拟函数:
仿函数是类或结构体的实例，通过定义operator()运算符，使对象具备函数的行为。示例:
struct Adder
{
int operator()(int a, int b)
{
return a + b;
}
};
Adder add; //函数对象
int result = add(3, 4); //调用 add.operator()(3, 4),结果为7
2.携带状态!
仿函数可以包含成员变量，用于保存状态，在多次调用间保存数据。示例(统计调用次数):
struct Counter
{
int count = 0;
void operator()(int x)
{
cout << x << " ";
count++;
}
};
vector<int> vec = { 1, 2, 3 };
Counter cnt; //函数对象
for (auto e : vec)
{
cnt(e);
}
cout << "Called " << cnt.count << " times" << endl;
3.可以定义类模版
仿函数(函数对象)也支持可以作为模板参数传递，就像priority_queue容器的参数Compare，类型明确。
template<class T>
class Compare
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
int main()
{
Compare<int> less1;
cout << less1(1, 2) << endl;
Compare<double> less2;
cout << less2(2.2, 1.1) << endl;
return 0;
}
🔥仿函数的优势：
● 状态管理: 相比普通函数，仿函数通过对成员变量进行封装，避免了全局变量，提升安全性和封装性。
● 模板兼容性: STL算法(如sort、transform)要求可调用对象类型作为模板参数，仿函数直接满足要求，而函数指针需额外处理。
● 性能优化: 编译器更容易内联仿函数的调用，相比函数指针可能更高效。
🍓仿函数与函数指针的区别：
1.封装性: 仿函数可以封装状态，它们可以拥有数据成员。仿函数可以在多次调用之间保持一些内部状态。而函数指针只能指向一个独立的函数，这个函数没有自己的状态 。
2.灵活性: 由于仿函数是一个类，可以利用面向对象编程的特性。例如，可以定义多个仿函数类来完成不同的任务，或者通过继承来扩展已有的仿函数类，这样可以更容易地组合和复用代码。
3.内联函数: 使用仿函数可以使用内联函数，而使用内联函数的指针，编译器会将其当作普通函数对待。
【总结】
仿函数具体是一个类或者结构体，里面重载了operator()运算符，这样这个类的对象就可以像函数一样被调用。
3.2 仿函数的应用举例
比如：上面讲到的priority_queue中存放Date类型的对象。那如果此时我们不存储Date类型的对象，而是存储Date*那去拿堆顶的元素能拿到日期大的那个对象吗？
void TestPriorityQueue2()
{
//默认不传Compare是建大堆
priority_queue<Date*> q1;
q1.push(new Date(2018, 10, 29));
q1.push(new Date(2018, 10, 28));
q1.push(new Date(2018, 10, 30));
cout << *(q1.top()) << endl;
}
然而上面这段程序的运行结果却是让人疑惑，因为每次运行可能给出的日期都是随机的，并不是大堆或者小堆的堆顶元素：
那出现这种情况的原因是什么呢？我们再来看一下priority_queue的模版参数：
仿函数Compare的<>中的value_type就是T：
那此时就明白了，出现上面情况的原因就是仿函数比较的不是Date，而是Date*；Date*是一个指针(指针都是内置类型)，由于我们都是在堆上为每个Date类型的对象申请空间，申请的内存空间是随机的，则每个Date类型对象的指针大小可能就不同。那priority_queue就是按指针的大小来进行建堆的，所以每次运行得出的日期也就是随机的。那怎么解决上面的问题呢？很简单：实现一个通过Date*来比较Date类型对象大小的仿函数即可：
class PDateCompare
{
public:
bool operator()(const Date* x, const Date* y)
{
return *x < *y; //实际是日期类的比较(Date类里有<的重载)
}
};
void TestPriorityQueue2()
{
PriQ::priority_queue<Date*,vector<Date*>, PDateCompare> q1;
q1.push(new Date(2018, 10, 29));
q1.push(new Date(2018, 10, 28));
q1.push(new Date(2018, 10, 30));
cout << *(q1.top()) << endl;
}
程序运行结果：
由于我们传的仿函数是PDateCompare，那在priority_queue中的比较就会按照PDateCompare中定义的方式来进行比较。
