一.仿函数
仿函数，顾名思义就是模仿函数，它其实是一个类，类里面重载了运算符（），在调用这个重载的运算符时，让我们感觉是调用函数一样，可以说相当于C语言里的函数指针一样，但是函数指针的可读性不好，不如仿函数。
仿函数的特点
1.仿函数即使定义相同，也可能有不同的类型；
2.仿函数通常比一般函数速度快；
3.仿函数使程序代码变简单。
例子
1. template<class T> 2. class Less 3. { 4. public: 5. bool operator()(const T& x, const T& y) 6. { 7. return x < y; 8. } 9. }; 10. 11. int main() 12. { 13. int a = 10, b = 20; 14. Less<int> Le; 15. cout << Le(a, b) << endl; //像函数一样调用 16. 17. return 0; 18. }
二.模拟实现priority_queue
priority_queue即优先级队列，它的底层是一个堆，且默认是大堆，所以在模拟实现优先级队列时要先建堆，不了解的话可以参考文章：堆的实现
相关接口：
源码
1. //less是库里的仿函数， 用来判断左操作数是否小于右操作数，可以用来建大堆 2. //greater也是库里的仿函数，比较左操作数是否大于右操作数，可以用来建小堆 3. //库里比较的是内置类型的大小，如果是自定义类型，那么自定义类型里就必须要重载 > 或 < 运算符 4. template<class T,class Containers=vector<T>,class Compare=less<T>> 5. class priority_queue 6. { 7. private: 8. //默认建大堆 9. //向下调整 10. void AdjustDown(int parent) 11. { 12. Compare com; 13. int child = 2 * parent + 1; 14. while (child < _con.size()) 15. { 16. if (child + 1 < _con.size() && com(_con[parent], _con[child+1])) 17. { 18. child++; 19. } 20. 21. if (com(_con[parent], _con[child])) 22. { 23. std::swap(_con[parent], _con[child]); 24. parent = child; 25. child = 2 * parent + 1; 26. } 27. else 28. break; 29. } 30. } 31. 32. //向上调整 33. void AdjustUp(int child) 34. { 35. Compare com; 36. int parent = (child - 1) / 2; 37. while (child > 0) 38. { 39. if (com(_con[parent], _con[child])) 40. { 41. std::swap(_con[parent], _con[child]); 42. child = parent; 43. parent = (child - 1) / 2; 44. } 45. else 46. break; 47. } 48. } 49. public: 50. priority_queue() //默认构造 51. { 52. ; 53. } 54. template<class Inputiterator> //迭代器区间构造 55. priority_queue(Inputiterator first, Inputiterator last) 56. { 57. while (first != last) //插入数据 58. { 59. _con.push_back(*first); 60. first++; 61. } 62. 63. //建堆 64. for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; i--) 65. { 66. AdjustDown(i); 67. } 68. } 69. 70. void push(const T& x) //插入 71. { 72. _con.push_back(x); 73. //AdjustDown(0); 74. AdjustUp(_con.size() - 1); 75. } 76. 77. void pop() 78. { 79. std::swap(_con[0], _con[_con.size() - 1]); //第一个元素和最后一个元素交换 80. _con.pop_back(); 81. 82. AdjustDown(0); 83. } 84. 85. const T& top() const //取堆顶数据 86. { 87. return _con[0]; 88. } 89. 90. bool empty() 91. { 92. return _con.size() == 0; 93. } 94. 95. size_t size() 96. { 97. return _con.size(); 98. } 99. 100. private: 101. Containers _con; 102. };
三.例题：数组中K个最大的元素
链接：
数组中第K个最大的元素
题目再现：
题解：
这个就类似于topk问题，我们可以先建个大堆（大堆是排降序，小堆是排升序），然后出掉前 K-1 个数据，此时堆顶数据即最终的答案，并返回。
之前在C语言那里的时候，还得自己造轮子，手搓一个堆出来，但是C++不用了，直接使用优先级队列priority_queue
1. class Solution { 2. public: 3. int findKthLargest(vector<int>& nums, int k) 4. { 5. priority_queue<int> pq; //建大堆 6. for(auto& e:nums) 7. { 8. pq.push(e); //插入数据到堆里 9. } 10. 11. while(--k) //出掉前k-1个数据 12. { 13. pq.pop(); 14. } 15. 16. return pq.top(); //返回堆顶数据 17. } 18. };
🐬🤖本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；🕊️👻
😄😆希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；🥰🤩
😍😁谢谢你的阅读。😸😼
