模拟实现（优先级队列）priority_queue：优先级队列、仿函数、反向迭代器等的介绍

文章目录

前言
一、优先级队列
二、仿函数
三、反向迭代器
总结

前言

一、优先级队列

优先级队列本质是一个堆，使用vector容器进一步改进进行实现，优先级队列可以传入比较模板参数，来确定建立大根堆还是小根堆，比较模板参数本质上是一个仿函数。

namespace hhb
{template<class T>struct Less{bool operator()(const T& left, const T& right){return (left < right);}};template<class T>struct Greater{bool operator()(const T& left, const T& right){return (left > right);}};template <class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{private:void AdjustDown(int parent){Compare _com;// 找到子节点int child = parent * 2 + 1;// 找字节点中大的一个if (child + 1 < _con.size() && _com(_con[child], _con[child + 1])){++child;}while (child < _con.size()){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);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 (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con.front();}size_t size(){return _con.size();}private:Container _con;};
}

测试：

#include <iostream>
#include <vector>using namespace std;#include "Priority_queue.h"void test_priority_queue1()
{hhb::priority_queue<int> pq1;pq1.push(3);pq1.push(1);pq1.push(5);pq1.push(2);pq1.push(4);while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;vector<int> v;v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(3);v.push_back(5);hhb::priority_queue<int> pq2(v.begin(), v.end());while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;
}void test_priority_queue2()
{//Less<int> less;//cout << less(1, 2) << endl;hhb::priority_queue<int, vector<int>, hhb::Less<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;hhb::priority_queue<int, vector<int>, hhb::Greater<int>> pq2;pq2.push(5);pq2.push(4);pq2.push(3);pq2.push(2);pq2.push(1);while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;}class Date
{
public:Date(int year = 1949, int month = 10, int day = 1):_year(year),_month(month),_day(day){}Date(const Date& d){_year = d._year;_month = d._month;_day = d._day;}bool operator<(const Date& d) const{if (_year < d._year){return true;}else if (_year == d._year && _month < d._month){return true;}else if (_year == d._year && _month == d._month && _day < d._day){return true;}else{return false;}}bool operator>(const Date& d) const{if (_year > d._year){return true;}else if (_year == d._year && _month > d._month){return true;}else if (_year == d._year && _month == d._month && _day > d._day){return true;}else{return false;}}friend ostream& operator<<(ostream& out, const Date& d);private:int _year;int _month;int _day;
};ostream& operator<<(ostream& out, const Date& d)
{out << d._year << '-' << d._month << '-' << d._day;return out;
}void test_priority_queue3()
{hhb::priority_queue<Date, vector<Date>, hhb::Less<Date>> pq1;pq1.push(Date(2024, 9, 23));pq1.push(Date(2024, 10, 23));pq1.push(Date(2024, 8, 23));while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;hhb::priority_queue<Date, vector<Date>, hhb::Greater<Date>> pq2;pq2.push(Date(2024, 9, 23));pq2.push(Date(2024, 10, 23));pq2.push(Date(2024, 8, 23));while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;}int main()
{//test_priority_queue1();//test_priority_queue2();test_priority_queue3();return 0;
}

在这里插入图片描述

二、仿函数

仿函数指的是类的实例化对象可以像函数一样使用，也可以叫函数对象。
本质上，仿函数是在类中进行了()运算符重载。

template<class T>
struct Less
{bool operator()(const T& left, const T& right){return (left < right);}
};void test_priority_queue4()
{Less<int> less; // 类的实例化对象cout << less(1, 2) << endl; // 可以像函数一样使用
}

测试：

void test_priority_queue4()
{Less<int> less; // 类的实例化对象cout << less(1, 2) << endl; // 可以像函数一样使用
}

在这里插入图片描述

有些特殊情况下，必须要使用仿函数，比如在优先级队列中，比较两个指针

void test_priority_queue5()
{hhb::priority_queue<Date*> pq;pq.push(new Date(2024, 9, 23));pq.push(new Date(2024, 10, 23));pq.push(new Date(2024, 8, 23));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;
}

在这里插入图片描述

直接进行指针的比较，是随机的，应该比较指针指向的对象。

struct LessPDate
{bool operator()(const Date* left, const Date* right){return (*left < *right);}
};void test_priority_queue5()
{hhb::priority_queue<Date*, vector<Date*>, LessPDate> pq;pq.push(new Date(2024, 9, 23));pq.push(new Date(2024, 10, 23));pq.push(new Date(2024, 8, 23));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;
}

在这里插入图片描述

三、反向迭代器

反向迭代器使用的是一种是适配器模式。可以适配所有支持迭代器的容器
反向迭代器与正向迭代器是镜像的，如：反向迭代器的rbegin是正向迭代器的end();

在这里插入图片描述


namespace hhb
{template <class Iterator, class Ref, class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;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){return _it != s._it;}Iterator _it;};
}

vector：

namespace hhb
{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}reverse_iterator rbegin(){return end();}reverse_iterator rend(){return begin();}const_reverse_iterator rbegin() const{return end();}const_reverse_iterator rend() const{return begin();}}
}

list:

 template<class T> 
class list
{typedef list_node<T> Node;
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}
}

测试：

#include "vector.h"
#include "list.h"void test6()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout << e << " ";}cout << endl;hhb::list<int>::reverse_iterator rit1 = lt.rbegin();while (rit1 != lt.rend()){cout << *rit1 << " ";++rit1;}cout << endl;hhb::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e : v){cout << e << " ";}cout << endl;hhb::vector<int>::reverse_iterator rit2 = v.rbegin();while (rit2 != v.rend()){cout << *rit2 << " ";++rit2;}cout << endl;}