C++仿函数的介绍以及priority_queue的介绍和模拟实现

目录
1.仿函数
1.1仿函数的介绍
1.2自定义类型利用仿函数 
1.3自定义支持比力巨细，但是比力的逻辑不是自己想要的逻辑
 2.优先级队列priority_queue
2.1priority_queue的介绍
2.2priority_queue的利用
2.3priority_queue的模拟实现 

---

1.仿函数

1.1仿函数的介绍

        仿函数的本质是一个类模板，只是这个类重载了operator(),以是当利用一个它的对象时看起来像利用和函数一样，以是被称为仿函数。
        下面通过仿函数的形式来写一个小于和大于的比力：

1. #include <iostream>
2. using namepsace std;
4. template<class T>
5. class Less
6. {
7. public:
8.         bool operator()(const T& x, const T& y)
9.         {
10.                 return x < y;
11.         }
12. };
14. template<class T>
15. class Greater
16. {
17. public:
18.         bool operator()(const T& x, const T& y)
19.         {
20.                 return x > y;
21.         }
22. };
24. int main()
25. {
26.         Less<int> less_func;
27.         Greater<int> greater_fun;
28.         int a = 5;
29.         int b = 10;
30.         cout << less_func(a, b) << endl;
31.         cout << greater_fun(a, b) << endl;
33.         return 0;
34. }

复制代码

1.2自定义类型利用仿函数 

        自定义类型必要利用仿函数进行比力时，必要在自定义类型内里提供<和>等比力运算符的重载。比方对日期类进行比力：

1. #include <iostream>
2. using namespace std;
4. template<class T>
5. class Less
6. {
7. public:
8.         bool operator()(const T& x, const T& y)
9.         {
10.                 return x < y;
11.         }
12. };
14. template<class T>
15. class Greater
16. {
17. public:
18.         bool operator()(const T& x, const T& y)
19.         {
20.                 return x > y;
21.         }
22. };
24. class Date
25. {
26.         friend ostream& operator<<(ostream& _cout, const Date& d);
27. public:
28.         Date(int year = 1900, int month = 1, int day = 1)
29.                 : _year(year)
30.                 , _month(month)
31.                 , _day(day)
32.         {}
33.         bool operator<(const Date& d)const
34.         {
35.                 return (_year < d._year) ||
36.                         (_year == d._year && _month < d._month) ||
37.                         (_year == d._year && _month == d._month && _day < d._day);
38.         }
39.         bool operator>(const Date& d)const
40.         {
41.                 return (_year > d._year) ||
42.                         (_year == d._year && _month > d._month) ||
43.                         (_year == d._year && _month == d._month && _day > d._day);
44.         }
45. private:
46.         int _year;
47.         int _month;
48.         int _day;
49. };
51. int main()
52. {
53.         Less<Date> less_func;
54.         Greater<Date> greater_func;
55.         Date d1(2024, 9, 10);
56.         Date d2(2024, 8, 15);
57.         cout << less_func(d1, d2) << endl;
58.         cout << greater_func(d1, d2) << endl;
59.         return 0;
60. }

复制代码

 1.3自定义支持比力巨细，但是比力的逻辑不是自己想要的逻辑

         这个时候仿函数必要我们自己进行重新，比如想通过比力日期类的指针进行日期的比力时，就必要将仿函数写成下面这个样子：

1. #include <iostream>
2. using namespace std;
4. class DateLess
5. {
6. public:
7.         bool operator()(Date* p1, Date* p2)
8.         {
9.                 return *p1 < *p2;
10.         }
11. };
13. //日期类参考上一个代码中的日期类
15. int main()
16. {
18.         Date d1(2024, 9, 10);
19.         Date d2(2024, 8, 15);
21.         Date* p1 = &d1;
22.         Date* p2 = &d2;
23.         DateLess func;
25.         cout << func(p1, p2) << endl;
26.         cout << func(p2, p1) << endl;
27.         return 0;
28. }

复制代码

 2.优先级队列priority_queue

2.1priority_queue的介绍

        priority_queue的文档介绍
1.优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。priority_queue包含在queue这个头文件中。
2.雷同于堆，在堆中可以随时插入元素，而且只能检索最大堆元素(优先队列中位于顶部的元素)。在这内里(堆的介绍)中可以进行对堆的了解。
3.底层容器可以是任何标准容器类模板，也可以是其他特定计划的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操纵：
(1)empty()：检测容器是否为空。
(2)size()：返回容器中有效元素个数。
(3)front()：返回容器中第一个元素的引用。
(4)push_back()：在容器尾部插入元素。
(5)pop_back()：删除容器尾部元素。
4.标准容器vector和deque满意这些需求。默认情况下，假如没有为特定的epriority_queue类实例化指定容器类，则利用vector。
5.必要支持随机访问迭代器，以便始终在内部保持堆布局。容器适配器通过在必要时自动调用算法函数make_heap(),push_heap()和pop_heap()来自动完成操纵。
2.2priority_queue的利用

        优先级队列默认利用vector作为其底层存储数据的容器，在vector上又利用dui算法将vector中元素构造成堆的布局，因此priority_queue就是堆，以是必要用到堆的位置，都可以考虑利用priority_queue。注意：默认情况下priority_queue是大堆。

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <functional>
5. using namespace std;
7. void test_priority_queue()
8. {
9.         // 默认情况下，创建的是大堆，其底层按照小于号比较
10.         vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
11.         priority_queue<int> q1;
12.         for (auto& e : v)
13.                 q1.push(e);
15.         while(!q1.empty())
16.         {
17.                 cout << q1.top() << " ";
18.                 q1.pop();
19.         }
20. }
22. int main()
23. {
24.         test_priority_queue();
25.         return 0;
26. }

复制代码

        假如每次访问顶部元素时都访问的是最小元素，则必要建立小堆。利用的时候只必要把上述priority_queue<int> q1 改为 priority_queue<int, vector<int>, greater<int>>即可，默认大堆的情况下，给的仿函数是less<int>。
2.3priority_queue的模拟实现 

         优先级队列的存储布局就是一个堆，内里的向上调解算法(AdjustUp())和向下调解算法(AdjustDown())参考堆的布局和实现。

1. #pragma once
2. #include <vector>
3. template<class T>
4. class Less
5. {
6. public:
7.         bool operator()(const T& x, const T& y)
8.         {
9.                 return x < y;
10.         }
11. };
13. template<class T>
14. class Greater
15. {
16. public:
17.         bool operator()(const T& x, const T& y)
18.         {
19.                 return x > y;
20.         }
21. };
24. namespace XiaoC
25. {
26.         //默认是大堆,排升序,用小于符号
27.         template<class T, class Container = vector<T>, class Compare = Less<T>>
28.         class priority_queue
29.         {
30.         public:
31.                 void AdjustUp(int child)
32.                 {
33.                         Compare com;
34.                         int parent = (child - 1) / 2;
35.                         while (child > 0)
36.                         {
37.                                 //if (_con[parent] < _con[child])
38.                                 if (com(_con[parent], _con[child]))
39.                                 {
40.                                         swap(_con[child], _con[parent]);
41.                                         child = parent;
42.                                         parent = (child - 1) / 2;
43.                                 }
44.                                 else
45.                                 {
46.                                         break;
47.                                 }
48.                         }
49.                 }
51.                 void push(const T& x)
52.                 {
53.                         _con.push_back(x);
55.                         AdjustUp(_con.size() - 1);
56.                 }
58.                 void AdjustDown(int parent)
59.                 {
60.                         // 先假设左孩子小
61.                         int child = parent * 2 + 1;
63.                         Compare com;
64.                         while (child < _con.size())  // child >= n说明孩子不存在，调整到叶子了
65.                         {
66.                                 // 找出小的那个孩子
67.                                 //if (child + 1 < _con.size() && _con[child] < _con[child + 1])
68.                                 if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
69.                                 {
70.                                         ++child;
71.                                 }
73.                                 //if (_con[parent] < _con[child])
74.                                 if (com(_con[parent], _con[child]))
75.                                 {
76.                                         swap(_con[child], _con[parent]);
77.                                         parent = child;
78.                                         child = parent * 2 + 1;
79.                                 }
80.                                 else
81.                                 {
82.                                         break;
83.                                 }
84.                         }
85.                 }
87.                 void pop()
88.                 {
89.                         swap(_con[0], _con[_con.size() - 1]);
90.                         _con.pop_back();
91.                         AdjustDown(0);
92.                 }
94.                 const T& top() const
95.                 {
96.                         return _con[0];
97.                 }
99.                 size_t size() const
100.                 {
101.                         return _con.size();
102.                 }
104.                 bool empty() const
105.                 {
106.                         return _con.empty();
107.                 }
108.         private:
109.                 Container _con;
110.         };
111. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告