优先级队列的常用函数的使用
#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 once using 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;
不同的是vector迭代器使用的是原生指针，这样写反向迭代器的好处是既可以给list使用，也可以给vector使用
注意反向迭代器的类命名空间必须和vector或list的命名空间一样.
测试vector的反向迭代器
测试list的反向迭代器
