当前位置：首页 > news >正文

【c++】优先级队列|反向迭代器（vector|list）

news 2025/8/5 23:30:27

优先级队列的常用函数的使用

#include<iostream>
#include<queue>
using namespace std;int main()
{priority_queue<int>st;st.push(1);st.push(7);st.push(5);st.push(2);st.push(3);st.push(9);while (!st.empty()){cout << st.top() << " ";st.pop();}
}

在这里插入图片描述

优先级队列的实现

优先级队列本质上是一个堆，所以实现和堆差不多，不同的是作为优先级队列我们可以使用别的容器来当适配器，比如说我们用vector作为优先级队列的容器，也可以用dequeue(双端队列)来做优先级队列的容器，
本篇我们使用vector来作为优先级队列的容器
所以我们优先级队列的函数可以用vector的函数来封装

#pragma once
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
namespace bit{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;}};
template <class T, class Container = vector<T>, class Compare = less<T> >class priority_queue{public:priority_queue()=default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){push(*first);first++;}}void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){if (comp(c[child],c[parent])){swap(c[child],c[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){int child = parent * 2 + 1;while (child<c.size()){if (child + 1 < c.size() && comp(c[child + 1], c[child])){child = child + 1;}if (comp(c[child],c[parent])){swap(c[parent],c[child]);parent = child;child = parent * 2 + 1;}else{break;}}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T& top() const{return c[0];}void push(const T& x){    c.push_back(x);adjust_up(c.size() - 1);}void pop(){  swap(c[0], c[c.size() - 1]);c.pop_back();adjust_down(0);}private:Container c;Compare comp;};};
void test()
{bit::priority_queue<int, vector<int>, less<int>>st;st.push(4);st.push(7);st.push(3);st.push(1);st.push(5);st.push(2);while (!st.empty()){cout << st.top() << " ";st.pop();}}

优先级队列对自定义类型的排序

   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){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;};void test(){priority_queue<Date, vector<Date>, less<Date>>st;Date d1(2024, 4, 9);st.push(d1);st.push({2024,4,11});st.push(Date(2024, 4, 10));while (!st.empty()){cout << st.top() << " ";st.pop();}}

在这里插入图片描述

如果我们把地址放进优先级队列里面呢？？

  void test(){priority_queue<Date*, vector<Date*>, less<Date*>> st;st.push(new Date(2018, 10, 29));st.push(new Date(2018, 10, 30));st.push(new Date(2018, 10, 28));while (!st.empty()){cout << *(st.top()) << endl;st.pop();}}

在这里插入图片描述

这里为什么排序是无序的呢？？
因为它是按照地址的大小来排序的，但是每次new对象，他的地址大小是不确定的，所以排出来属无序的，我们可以实现一个仿函数来实现

   class  Dateless{public:bool operator()(const Date* x, const Date* y){return *x < *y;}};class  Dategreater{public:bool operator()(const Date* x, const Date* y){return *x > *y;}};

在这里插入图片描述

反向迭代器
首先迭代器是怎么将模版适配成所有类型的变量都可以使用？？
在这里插入图片描述

反向迭代器的实现

#pragma onceusing namespace std;
namespace zjw
{     template<class  Iterator,class Ref,class Ptr>struct Reverselterator{typedef Reverselterator<Iterator, Ref, Ptr>Self;Iterator _it;Reverselterator(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;}};
}

根据反向迭代器的特性，我们知道正向迭代器的++就是反向迭代器的–，正向迭代器的–就是反向迭代器的++，实现下面两个函数

	Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}

	Ref operator*(){Iterator tmp = _it;return *(--tmp);}

这个为什么要先–呢？
在这里插入图片描述

同时，需要在vector类或者list类中添加反向迭代器记录起始位置和结束位置的函数

  reverse_iterator rbegin(){//return reverse_iterator(end());return iterator(end());}reverse_iterator rend(){// return reverse_iterator(begin());return iterator(begin());}

这样写比较好理解，用正向迭代器的begin()做反向迭代器的rend(),用正向迭代器的end()做反向迭代器的rbegin(),

vector迭代器的重命名

         typedef T* iterator;typedef const T* const_iterator;typedef Reverselterator<iterator,T&,T*> reverse_iterator;typedef Reverselterator<const_iterator,const T&,const T*> const_reverse_iterator;

list迭代器的重命名

        typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&,const T*> const_iterator;typedef Reverselterator<iterator,T&,T*> reverse_iterator;typedef Reverselterator<const_iterator,const T&,const T*> const_reverse_iterator;