文章目录
- 一、priority_queue使用
- 仿函数控制优先级
- sort算法里的仿函数
- 二、手撕优先级队列
- 优先级队列的容器适配器
- 入堆
- 出堆
- top/size/empty
- 迭代器区间构造初始化(解耦)
- 三、仿函数
- 仿函数控制冒泡排序
- 仿函数控制priority_queue
- 比较逻辑仿函数使用场景
- 仿函数的其他使用场景
- 源码
一、priority_queue使用
priority_queue底层就是我们在数据结构初阶介绍的堆，只不过这里叠加了C++
的类、模板和我们下面要介绍的仿函数，并且它默认的结构是大根堆，使用测试如下：
仿函数控制优先级
我们要控制priority_queue的优先级需要用它的第三个模板参数，仿函数，有两个在库里的仿函数：
小于less仿函数<: 大的优先级高，排降序
大于greater仿函数>: 小的优先级高，排升序
我们会发现它的优先级逻辑和我们的理解是相反的，需要特别注意。
sort算法里的仿函数
之前在介绍sort排序算法时也提到了仿函数，它默认是排升序，要改变排序逻辑就要传不同的仿函数了，这里仿函数的逻辑就和我们想的一样了，less小于排升序，greater大于排降序。
还有一点需要注意，sort的仿函数传的是对象，所以后面要加()，相当于匿名函数，priority_queue传的是类型，所以不加括号。
二、手撕优先级队列
手撕优先级队列要用到很多在堆介绍的知识，如果有读者不太懂下面的操作建议去看看小编介绍的有关堆的文章：
数据结构与算法------堆(堆的实现、堆排序、TOP-K问题）
优先级队列的容器适配器
我们查文档可以看到优先级队列的容器适配器是vector，其实也可以用双端队列deque，但是用vector是最好的，因为优先级队列要频繁的下标随机访问，vector的效率更高,所以它的模板参数和成员函数为：
template<class T, class Container = vector<T>>Container _con;
入堆
//默认大堆
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;}}
}void push(const T& x)
{_con.push_back(x);Adjust_up(_con.size() - 1);
}
这里和C语言实现堆的区别就是不用自己写数组的插入删除操作，因为容器适配器，所以直接复用vector的相关接口就行了。
出堆
void Adjust_down(size_t parent)
{size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child])child++;if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();Adjust_down(0);
}
top/size/empty
int top()
{return _con[0];
}bool empty()
{return _con.empty();
}size_t size()
{return _con.size();
}
迭代器区间构造初始化(解耦)
vector<int> v = { 4,1,3,6,7,2 };
wusaqi::priority_queue<int> pq(v.begin(), v.end());
我们想调用如上迭代器区间构造初始化就还需要我们自己实现一个对应的迭代器区间构造构造函数，我们实现了它的迭代器区间构造但是不想实现它的默认构造(不带参构造)，就需要强制它生成默认构造，因为只要显示实现了一个构造函数编译器就不会自动生成默认构造了。
生成默认构造是为了初始化优先级队列的底层容器，因为默认构造会去调用自定类型的构造函数，当具体底层容器是什么取决于实例化对象时模板传的参数。这里的容器适配器可以体现一点，优先级队列底层存储数据的结构和堆算法本身是解耦的，在实际项目中，软件的耦合度一定是越低越好，耦合度低就意味着有更高的自由度。
priority_queue() = default;
这里我们可以挨个遍历容器尾插到优先级队列中，但是这样就相当于向上调整建堆了，时间复杂度比较高，效率更高的方法还是用向下调整建堆，所以我们首先把这段迭代器区间的值拷贝一份给_con，方法是走初始化列表用_con提供的迭代器区间构造，然后再向下调整建堆。
这里要用到迭代器类型模板，让它能适配更多容器。
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{auto it = first;while (it != last){push(*it);it++;}
}
上面是遍历迭代器区间并尾插，相当于向上调整算法建堆，效率不高，不推荐，下面的向下调整建堆才是最理想的方式。
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last):_con(first, last)
{//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){Adjust_down(i);}
}
三、仿函数
我们要明白,C++引入仿函数的目的是为了替代函数指针，因为函数指针用起来太复杂了，它的定义方式和常规的指针定义方式区别很大，用的时候很容易出问题。
函数指针还有一点缺陷，当函数指针类型做类模板参数时，无法直接创造出函数指针对象，因为指针类型实例化出的指针对象值是不确定的，不是存放指向函数对象的值，当然函数模板因为是传递对象就可以使用函数指针类型。
仿函数又名函数对象，它本质就是一个类，只不过重载了operator()，所以它定义出的对象可以像函数一样使用。(凡是重载了operator()的类都可以叫做仿函数)
再把它套上模板就可以支持任意类型数据比较了：
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;}
};
仿函数控制冒泡排序
下面我们用仿函数来控制冒泡排序排升序和降序：
template<class T, class compare>
void Bubble_sort(T* arr, int sz, compare cmp)
{int flag = 1; //默认有序for (int i = 0; i < sz - 1; i++) //躺数{for (int j = 0; j < sz - 1 - i; j++){if (cmp(arr[j + 1], arr[j])){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 0;}}if (flag == 1)break;}
}void test06()
{int arr[] = { 4,2,6,1,5,8,9,3,7 }; Bubble_sort(arr, 9, Less<int>()); for (auto ch : arr){cout << ch << " ";}cout << endl;Bubble_sort(arr, 9, Greater<int>());for (auto ch : arr){cout << ch << " ";}cout << endl;
}
这里要注意冒泡排序函数的模板是函数模板，不是类模板，需要通过调用函数传递对象参数来调用仿函数，不能像类模板那样：Bubble_sort<int,Less< int >> 只在模板参数这里传递仿函数类型，而不在函数参数哪里传递仿函数对象，如果非要这样传递，记住仿函数需要对象来调用，那需要在冒泡排序函数内调用仿函数时用匿名对象调用：compare()(arr[j], arr[j + 1])。
仿函数控制priority_queue
需要改动的就两个地方，一个是模板参数，多增加一个仿函数参数，因为默认排升序，建大堆，所以给一个缺省值类型Less< T> >。
还要把向上调整算法和向下调整算法的比较逻辑换成调用仿函数，这里和冒泡排序调用仿函数又有一点不同，冒泡排序是函数模板，调用仿函数是直接传递的仿函数对象，所以可以拿到参数直接使用，这里priority_queue是雷模板，仿函数传递过来的是仿函数类型，需要先实例化成对象后再使用，这里小编就不定义有名对象了，直接用匿名对象，少敲两行代码。
template<class T, class Container = vector<T>, class compare = Less<T>>void Adjust_up(size_t child){//compare cmp; size_t parent = (child - 1) / 2;while (child != 0){ //匿名对象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){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && compare()(_con[child], _con[child + 1]))child++;if (compare()(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}
比较逻辑仿函数使用场景
- 类不支持比较大小
- 类支持比较大小，但比较逻辑和预期不一致
这里小编补充一点，我们上面实现的仿函数都是空类(没有成员变量，对象空间大小为1字节）,所以空类也是有使用场景的。
仿函数的其他使用场景
在算法库中也有一些函数会用到仿函数，下面以find_if为例简单介绍一下：
我们查文档发现find是找到迭代器区间中第一个指向值为val的迭代器并返回，find_if是找到迭代器区间中第一个迭代器指向的值符合pred仿函数的值，并返回该迭代器，所以我们可以设计一个find_if用来查找第一个偶数：
class op1
{
public:bool operator()(int x){return (x % 2 == 0);}
};int arr[] = { 3,1,5,4,7,8,2 };auto it1 = find(arr, arr + 7, 1);cout << *it1 << endl;//查找第一个偶数auto it2 = find_if(arr, arr + 7, op1());cout << *it2 << endl;
运行结果：
源码
pq.h:
#pragma once
#include <algorithm>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;}
};namespace wusaqi
{template<class T, class Container = vector<T>, class compare = Less<T>>class priority_queue{public:priority_queue() = default;//template<class InputIterator>//priority_queue(InputIterator first, Inpu tIterator last)//{// auto it = first;// while (it != last)// {// push(*it);// it++;// }//}template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){Adjust_down(i);}}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);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private://默认大堆void Adjust_up(size_t child){//compare cmp; size_t parent = (child - 1) / 2;while (child != 0){ //匿名对象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){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && compare()(_con[child], _con[child + 1]))child++;if (compare()(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}private:Container _con;};
}
test.cpp:
using namespace std;
#include <algorithm>
#include <iostream>
#include <queue>
#include "pq.h"void test01()
{wusaqi::priority_queue<int> pq;pq.push(5);pq.push(1);pq.push(3);pq.push(7);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}void test02()
{////要传第三个模板参数必须要传第二个,不能跳跃传参//priority_queue<int, vector<int>, greater<int>> pq; //pq.push(5);//pq.push(1);//pq.push(3);//pq.push(7);//pq.push(2);//while (!pq.empty())//{// cout << pq.top() << " ";// pq.pop();//}//cout << endl;vector<int> v1 = { 2,4,1,6,3,5 };sort(v1.begin(), v1.end());for (auto ch : v1){cout << ch << " ";}cout << endl;//sort(v1.begin(), v1.end(), greater<int>());for (auto ch : v1){cout << ch << " ";}cout << endl;
}void test03()
{vector<int> v = { 4,1,3,6,7,2 };wusaqi::priority_queue<int> pq(v.begin(), v.end());while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}class A
{
public:A(int a = 0):_a(a){cout << "A(int a)" << endl;}~A(){cout << "~A()" << endl;}
private:int _a;
};void test04()
{//有名对象A aa1;A aa2(66);//匿名对象A();A(88);
}void test05()
{Less<int> Funcless;cout << Funcless(1, 2) << endl; //Funcless.operator()(1,2)
}//template<class T, class compare>
//void Bubble_sort(T* arr, int sz)
//{
// int flag = 1; //默认有序
// for (int i = 0; i < sz - 1; i++) //躺数
// {
// for (int j = 0; j < sz - 1 - i; j++)
// {
// if (compare()(arr[j], arr[j + 1]))
// {
// int tmp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = tmp;
// flag = 0;
// }
//
// }
// if (flag == 1)
// break;
// }
//}template<class T, class compare>
void Bubble_sort(T* arr, int sz, compare cmp)
{int flag = 1; //默认有序for (int i = 0; i < sz - 1; i++) //躺数{for (int j = 0; j < sz - 1 - i; j++){if (cmp(arr[j + 1], arr[j])){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 0;}}if (flag == 1)break;}
}void test06()
{int arr[] = { 4,2,6,1,5,8,9,3,7 };Bubble_sort(arr, 9, Less<int>());for (auto ch : arr){cout << ch << " ";}cout << endl;Bubble_sort(arr, 9, Greater<int>());for (auto ch : arr){cout << ch << " ";}cout << endl;
}void test07()
{wusaqi::priority_queue<int, vector<int>, Greater<int>> pq;pq.push(5);pq.push(1);pq.push(3);pq.push(7);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}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;
}class PDateLess
{
public:bool operator()(Date* pd1, Date* pd2){return (*pd1) < (*pd2);}
};class PDateGreater
{
public:bool operator()(Date* pd1, Date* pd2){return (*pd1) > (*pd2);}
};void test08()
{wusaqi::priority_queue<Date*, vector<Date*>, PDateLess> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));while (!q1.empty()){cout << *(q1.top()) << " ";q1.pop();}cout << endl;
}class op1
{
public:bool operator()(int x){return (x % 2 == 0);}
};void test09()
{int arr[] = { 3,1,5,4,7,8,2 };auto it1 = find(arr, arr + 7, 2);cout << *it1 << endl;//查找第一个偶数auto it2 = find_if(arr, arr + 7, op1());cout << *it2 << endl;
}int main()
{//test01();//test02();//test03();//test04();//test05();//test06();//test07();//test08();test09();return 0;
}
以上就是小编分享的全部内容了，如果觉得不错还请留下免费的赞和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~
)
