【C++】优先级队列+反向迭代器

priority_queue的先容

通常用堆来实现，能在O(log n)的时间复杂度内插入和提取最高（或最低）优先级的元素。

   

• 优先队列是一种容器适配器，根据严酷的弱排序标准，它的第一个元素总是它所包罗的元素中最大的(默认情况)。
  
• 此上下文类似于堆，在堆中可以随时插入元素，而且只能检索最大堆元素(优先队列中位于顶部的元素)。
  
• 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
  
• 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作
  empty()：检测容器是否为空
  size()：返回容器中有效元素个数
  front()：返回容器中第一个元素的引用
  push_back()：在容器尾部插入元素
  pop_back()：删除容器尾部元素
  
• 标准容器类vector和deque满意这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
  
• 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
  

    弱排序标准是一种在数学和编程中用于界说元素之间排序关系的二元关系。它要求关系满意以下三个重要性质：
1.自反性：对于任何元素a，a与自身是相等的。
2.传递性：如果a小于b，且b小于c，则a小于c。
3.连通性：对于任何两个元素a和b，要么a小于b，要么b小于a
  priority_queue的使用

1.默认情况下是大堆，其底层按照less比力；若创建小堆，将第三个模板参数换成greater的比力方式；
2.如果在priority_queue中放自界说类型的数据，用户需要在自界说类型中提供> 或者< 的重载。
数组中第k大的元素

   大堆方法：第三个模板参数直接使用less排序，利用前置–的特性，k–
将优先级队列中的前k-1个元素删除掉

    小堆方法：第三个模板参数要传入greater排序函数，运用topk问题思想，创建前k个元素的小堆，从数组的第k个元素开始遍历。如果当前元素大于堆顶元素（堆顶是最小值），则移除堆顶元素，并将当前元素参加堆。最后，堆顶元素即为数组中第k大的元素。

  priority_queue的模拟实现

仿函数

   又称函数对象，是类模板，通过重载()运算符，使得类模板的对象可以像函数一样被调用。
区分：函数模板要传对象，类模板要传参数是类型，不能加括号

  向下调整

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

复制代码

  通过比力器 Compare 确定堆的类型。用于从父节点开始向下调整堆结构，确保堆的性质得到满意。
作用：维护堆的性质，确保插入或移除操作后堆的结构仍然有效。
应用场景：插入新元素后或移除堆顶元素后调用。
  向上调整

1. void Adjustup(int child)
2. {
3.         Compare com;
4.         int parent = (child - 1) / 2;
5.         while (child > 0)
6.         {
7.                 if (com(_con[parent],_con[child]))
8.                 {
9.                         swap(_con[parent], _con[child]);
10.                         child = parent;
11.                         parent = (child - 2) / 2;
12.                 }
13.                 else
14.                 {
15.                         break;
16.                 }
17.         }
18. }

复制代码

  通过比力器 Compare 确定堆的类型。用于从子节点开始向上调整堆结构，确保堆的性质得到满意。
作用：维护堆的性质，确保插入新元素后堆的结构仍然有效。
应用场景：插入新元素后调用。
  构造函数

   复制元素：将迭代器范围内的所有元素复制到内部容器 _con 中。
构建堆：从最后一个非叶子节点开始，运用向下调整法逐步向上调整堆结构，确保堆的性质得到满意。
  删除

   交换堆顶元素与末了元素，然后调用尾删函数，或者直接size–实现删除功能，再从堆顶即下标为0的位置开始向下调整来满意堆序
  插入

   插入新元素后，从最后索引位置size()-1来向上调整满意堆序。
  自界说类测试(日期类)

1.         class Date
2.         {
3.         public:
4.                 Date(int year = 1900, int month = 1, int day = 1)
5.                         : _year(year)
6.                         , _month(month)
7.                         , _day(day)
8.                 {
9.                 }
11.                 bool operator<(const Date& d)const
12.                 {
13.                         return (_year < d._year) ||
14.                                 (_year == d._year && _month < d._month) ||
15.                                 (_year == d._year && _month == d._month && _day < d._day);
16.                 }
18.                 bool operator>(const Date& d)const
19.                 {
20.                         return (_year > d._year) ||
21.                                 (_year == d._year && _month > d._month) ||
22.                                 (_year == d._year && _month == d._month && _day > d._day);
23.                 }
25.                 friend ostream& operator<<(ostream& _cout, const Date& d);
26.         private:
27.                 int _year;
28.                 int _month;
29.                 int _day;
30.         };
32.         ostream& operator<<(ostream& _cout, const Date& d)
33.         {
34.                 _cout << d._year << "-" << d._month << "-" << d._day;
35.                 return _cout;
36.         }
38.         struct LessPDate
39.         {
40.                 bool operator()(const Date* p1, const Date* p2)
41.                 {
42.                         return *p1 < *p2;
43.                 }
44.         };
45. }

复制代码

1. void test_priority_queue2()
2. {
3.         priority_queue<Date*, vector<Date*>, LessPDate> pq;
4.         pq.push(new Date(2024, 6, 7));
5.         pq.push(new Date(2025, 1, 19));
6.         pq.push(new Date(2025, 10, 24));
7.         while (!pq.empty())
8.         {
9.                 cout << *pq.top() << " ";
10.                 pq.pop();
11.          }
12.         cout << endl;
13.         //测试仿函数的调用，与日期类无关
14.         Less<int>lessfunc;
15.         cout << lessfunc(10, 24) << endl;
16.         cout << lessfunc.operator()(10, 24) << endl;
17. }

复制代码

  优先级队列的界说：priority_queue<Date*, vector<Date*>, LessPDate> 表示优先级队列中存储的是 Date 类型的指针，底层容器是 vector，比力器是 LessPDate。
插入元素：通过 push 方法插入三个 Date 对象。
输出元素：通过 while 循环依次输出队列中的元素，直到队列为空。

  团体代码

1. #pragma once
2. #include<vector>
3. #include<functional>
5. //仿函数/函数对象
6. template <class T>
7. class Less
8. {
9. public:
10.         bool operator()(const T& x, const T& y)
11.         {
12.                 return x < y;
13.         }
14. };
15. template <class T>
16. class Greater
17. {
18. public:
19.         bool operator()(const T& x, const T& y)
20.         {
21.                 return x > y;
22.         }
23. };
25. namespace ee
26. {
27.         template<class T,class Container=vector<T>, class Compare=less<T>>
28.         class priority_queue
29.         {
30.         private:
31.                 void Adjustdown(int parent)
32.                 {
33.                         Compare com;
34.                         int child = 2 * parent + 1;
35.                         while (child < _con.size())
36.                         {
37.                                 if (child + 1 < _con.size() && com(_con[child],_con[child + 1]))
38.                                 {
39.                                         child++;
40.                                 }
42.                                 if (com(_con[parent],_con[child]))
43.                                 {
44.                                         swap(_con[parent], _con[child]);
45.                                         parent = child;
46.                                         child = 2 * parent + 1;
47.                                 }
49.                                 else
50.                                         break;
51.                         }
52.                 }
54.                 void Adjustup(int child)
55.                 {
56.                         Compare com;
57.                         int parent = (child - 1) / 2;
58.                         while (child > 0)
59.                         {
60.                                 if (com(_con[parent],_con[child]))
61.                                 {
62.                                         swap(_con[parent], _con[child]);
63.                                         child = parent;
64.                                         parent = (child - 2) / 2;
65.                                 }
66.                                 else
67.                                 {
68.                                         break;
69.                                 }
70.                         }
71.                 }
72.         public:
73.                 priority_queue()
74.                 {
75.                 }
77.                 template<class InputIterator>
78.                 priority_queue(InputIterator first, InputIterator last)
79.                 {
80.                         while (first != last)
81.                         {
82.                                 _con.push_back(*first);
83.                                 first++;
84.                         }
86.                         //建堆
87.                         for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
88.                         {
89.                                 Adjustdown(i);
90.                         }
91.                 }
93.                 void pop()
94.                 {
95.                         swap(_con[0], _con[_con.size() - 1]);
96.                         _con.pop_back();
97.                         Adjustdown(0);
98.                 }
100.                 void push(const T& x)
101.                 {
102.                         _con.push_back(x);
103.                         Adjustup(_con.size() - 1);
104.                 }
106.                 const T& top()
107.                 {
108.                         return _con[0];
109.                 }
111.                 bool empty()
112.                 {
113.                         return _con.empty();
114.                 }
116.                 size_t size()
117.                 {
118.                         return _con.size();
119.                 }
120.         private:
121.                 Container _con;
122.         };

复制代码

反向迭代器

   顾名思义是用于反向遍历的工具。反向迭代器通常通过容器的 rbegin() 和 rend() 方法获取。rbegin() 返回指向容器最后一个元素下一个位置的反向迭代器(end)，而 rend() 返回指向容器第一个元素的反向迭代器(begin)。

1. namespace ee
2. {
3.         template<class Iterator,class ref,class ptr>
4.         struct ReverseIterator
5.         {
6.                 typedef ReverseIterator<Iterator, ref, ptr> self;
7.                 Iterator _it;
9.                 ReverseIterator(Iterator it)
10.                         :_it(it)
11.                 { }
13.                 ref operator*()
14.                 {
15.                         Iterator tmp = _it;
16.                         return *(--tmp);
17.                 }
19.                 ptr operator->()
20.                 {//返回解引用对象的地址
21.                         return &(operator*());
22.                 }
24.                 self& operator++()//前置++
25.                 {
26.                         --_it;
27.                         return *this;
28.                 }
30.                 self& operator--()
31.                 {
32.                         ++_it;
33.                         return *this;
34.                 }
36.                 bool operator!=(const self& s)const
37.                 {
38.                         return _it != s._it;
39.                 }
40.         };
41. }

复制代码

  一般接纳镜像对称的方式来模拟实现，即rbegin对应end，rend对应begin。
在重载*运算符时需要注意解引用的是迭代器当前指向的前一个位置，因为rbegin是最后元素的下一个位置，有大概为空会造成非法访问，或者是哨兵位头节点的位置。
++和–分别实现自减和自增的操作来满意反向迭代器的功能。
     若不使用镜像对称的方式来模拟实现反向迭代器，那么*操作符的重载就要跟随发生变革。
    vector中适配

记得包罗ReverseIterator.h头文件即可
   

  list中适配

   

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