【C++/STL】优先级队列,仿函数和反向迭代器

优先级队列

priority_queue.h

#pragma once
#include <vector>
#include <functional>
//仿函数/函数对象
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 Q
{template<class T,class Container=vector<T>,class Compare=less<T>>class priority_queue{private:Container _con;void AdjustDown(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child],_con[child+1]))//看清楚！！！if条件的后面不能加分号！！！{child++;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:priority_queue(){ }template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);first++;}//for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; i--)注意！！！size_t 永远大于0！循环无效for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}void push(const T& x){_con.push_back(x);AdjustUp(_con.size()-1);//push_back后size已经改变！}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}};void test_priority_queue1(){//建小堆priority_queue<int,vector<int>,Greater<int>> pq1;pq1.push(1);pq1.push(2);pq1.push(3);pq1.push(4);pq1.push(5);while (!pq1.empty()){cout << pq1.top() << " ";pq1.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;}//template<class T>struct LessDate{bool operator()(const Date* d1, const Date* d2){return *d1 < *d2;}};//void test_priority_queue2()//{//	//建小堆//	priority_queue<Date, vector<Date>, Greater<Date>> pq2;//	pq2.push(Date(2025,9,6));//	pq2.push(Date(2025, 9, 7));//	pq2.push(Date(2025, 9, 2));//	pq2.push(Date(2025, 9, 3));//	pq2.push(Date(2025, 9, 5));//	while (!pq2.empty())//	{//		cout << pq2.top() << " ";//		pq2.pop();//	}//	cout << endl;//}void test_priority_queue3(){//建小堆priority_queue<Date*, vector<Date*>,LessDate> pq3;pq3.push(new Date(2025, 9, 6));pq3.push(new Date(2025, 9, 7));pq3.push(new Date(2025, 9, 2));pq3.push(new Date(2025, 9, 3));pq3.push(new Date(2025, 9, 5));while (!pq3.empty()){cout << *pq3.top() << " ";pq3.pop();}cout << endl;}
}

仿函数

test.cpp

#include <iostream>
using namespace std;
#include "priority_queue.h"
//#include "priority_queue_standard.h"
int main()
{//bit::test_priority_queue2();//从大到小依次Q::test_priority_queue3();//仿函数/函数对象//这个类对象可以像函数一样使用Less<int> lessfunc;cout << lessfunc(1, 2) << endl;cout << lessfunc.operator()(1, 2) << endl;return 0;
}

反向迭代器

ReverseIterator.h

#pragma once
namespace W
{template<class Iterator,class Ref,class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator _it;ReverseIterator(Iterator it):_it(it);{}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s) const{return _it != s._it;}};