stack&&queue
一.priority_queue介绍
1.优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2.此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
3.优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4.底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
5.标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6.需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
二.priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
默认情况下，priority_queue是大堆。
#include <vector> #include <queue>//priority_queue默认也用这个头文件 #include <functional> // greater算法的头文件 void TestPriorityQueue() { // 默认情况下，创建的是大堆，其底层按照小于号比较 vector<int> v{3,2,7,6,0,4,1,9,8,5}; priority_queue<int> q1; for (auto& e : v) q1.push(e); cout << q1.top() << endl; // 如果要创建小堆，将第三个模板参数换成greater比较方式 priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end()); cout << q2.top() << endl; }
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载
三.仿函数
3.1仿函数的介绍
对于上面的创建成小堆的格式，发现有一个：greater 参数，priority_queue中自带的缺省参数为less，即升序大堆，因此想要建大堆就不需要进行换参数的操作，直接priority_queue就是大堆，上面的结果就是这样，想要换成小堆就得这样：priority_queue, greater>通过利用仿函数可以将比较的顺序进行颠倒，通过改变内置的比较符号从而灵活的改变按照大小的排序。
仿函数又叫函数对象，仿函数就是一个类，仿函数的函数对象就是类对象，成员是什么无所谓，下面先看一个简单的例子：
namespace cfy { template<class T> class less { public://operator()就是一个运算符重载 bool operator()(const T& x, const T& y) const { return x < y; } }; template<class T> class greater { public: bool operator()(const T& x, const T& y) const { return x > y; } }; } int main() { cfy::less<int> lessFunc; lessFunc(1, 2); //lessFunc.operator()(1, 2);//实际上是这样的展开过程 return 0; }
即在之前的印象中，通过调用lessFunc，就可以把lessFunc看成一个函数名，但在这里lessFunc是一个函数对象，仿函数的对象，这个对象可以像函数一样去使用，但实际上这个对象不是直接像往常的函数一样直接调用。而是调用了运算符重载，即实际上就是这样：lessFunc.operator()(1, 2);但不会这样去写，因为运算符重载就是为了可读性。但这样有什么好处呢？感觉除了封装也没什么。
3.2仿函数的好处
C语言是如何解决升序降序的问题呢？比如qsort就是利用了函数指针，传入大于就是大于比较，传入小于就是小于比较。那C++兼容C，为什么不用函数指针呢？
STL所提供的各种算法，往往有两个版本，其中一个版本表现出最常用（或最直观的）的某种运算，第二个版本则表现出最泛化的演算流程，允许用户"以template参数来指定所要采行的策略",拿accumulate来说，他的一般行为是将指定范围内的所有元素相加，第二版本则允许你指定某种“操作”，取代第一版本中的“相加”行为。要将某种“操作”当做算法的参数，唯一办法就是先将该“操作”（可能拥有数条以上的指令）设计为一个函数，在将函数当做算法的一个参数；或是将该“操作”设计为一个所谓的仿函数（就语言层面而言是个class），再以该仿函数产生一个对象，并以此对象作为算法的一个参数。
而为什么函数指针可以达到“将数组操作当做算法的参数”，那又何必有所谓的仿函数呢？原因在于函数指针毕竟不能满足STL对抽象性的要求，也不能满足软件积木的要求---->函数指针无法和STL其他组件搭配,产生更灵活的变化。
那么以冒泡排序为例，我们看一下通过仿函数改变升序降序的方式：
#include<iostream> using namespace std; namespace cfy { template<class T> class less { public://operator()就是一个运算符重载 bool operator()(const T& x, const T& y) const { return x < y; } }; template<class T> class greater { public: bool operator()(const T& x, const T& y) const { return x > y; } }; } template<class T, class Compare> void BubbleSort(T* a, int n, const Compare& com)//解决升序降序的问题，函数指针可以，但是C++觉得不好用，就用仿函数 { for (int j = 0; j < n; j++) { int exchange = 0; for (int i = 1; i < n - j; i++) { //if (a[i] < a[i-1]) if (com(a[i - 1], a[i])) { swap(a[i - 1], a[i]); exchange = 1; } } if (exchange == 0) { break; } } } int main() { cfy::less<int> lessFunc; //lessFunc(1, 2); int a[] = { 2,3,4,5,6,2,1,7 }; BubbleSort(a, sizeof(a) / sizeof(int), lessFunc); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { cout << a[i] << " "; } cout << endl; cfy::greater<int> greaterFunc; BubbleSort(a, sizeof(a) / sizeof(int), greaterFunc); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { cout << a[i] << " "; } return 0; }
四.priority_queue模拟实现
既然已经知道优先级队列中的仿函数的相关知识，就可以模拟实现一个priority_queue了，与上次的stack/queue的模拟实现类似，底层也是适配器实现，没有用到迭代器。
PriorityQueue.h
#pragma once namespace cfy { template<class T> class less { public: bool operator()(const T& x, const T& y) const { return x < y; } }; template<class T> class greater { public: bool operator()(const T& x, const T& y) const { return x > y; } }; //大堆 template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { public: priority_queue() {} template<class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con(first, last) { //建堆:大堆 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) { adjust_down(i); } } void adjust_up(size_t child) { Compare com; size_t parent = (child - 1) / 2; while (child > 0) { //if (_con[parent] < _con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(size_t parent) { Compare com; size_t child = parent * 2 + 1; while (child < _con.size()) { //if (child + 1 < _con.size() && _con[child] < _con[child+1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child++; } //if (_con[parent] < _con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T& top() const { return _con[0]; } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }
test.cpp
#include<iostream> #include<vector> using namespace std; #include"PriorityQueue.h" int main() { cfy::priority_queue<int> pq1; int a[] = { 2,3,4,5,6,2,1,7 }; for (int i = 0; i < 8; i++) { pq1.push(a[i]); } cout << "大堆："; while (!pq1.empty()) { cout << pq1.top() << " "; pq1.pop(); } cout << endl; cfy::priority_queue<int, vector<int>, greater<int>> pq2;//小堆的方式，greater用不用cfy::限定符都行 for (int i = 0; i < 8; i++) { pq2.push(a[i]); } cout << "小堆："; while (!pq2.empty()) { cout << pq2.top() << " "; pq2.pop(); } cout << endl; return 0; }
五.仿函数之日期比较
之前说过，仿函数相当于一个灵活的比较的函数类，对于之前的日期类，当然可以通过仿函数进行比较：
#include<iostream> #include<vector> #include<queue> using namespace std; 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:i int _year; int _month; int _day; }; void TestPriorityQueue() { // 大堆，需要用户在自定义类型中提供<的重载 priority_queue<Date> q1; q1.push(Date(2018, 10, 29)); q1.push(Date(2018, 10, 28)); q1.push(Date(2018, 10, 30)); cout << q1.top() << endl; // 如果要创建小堆，需要用户提供>的重载 priority_queue<Date, vector<Date>, greater<Date>> q2; q2.push(Date(2018, 10, 29)); q2.push(Date(2018, 10, 28)); q2.push(Date(2018, 10, 30)); cout << q2.top() << endl; } int main() { TestPriorityQueue(); return 0; }
如果是Date*，就需要增加一个比较的仿函数：及地址解引用的仿函数。
#include<iostream> #include<vector> #include<queue> using namespace std; 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; }; struct PDateLess//地址的仿函数 { bool operator()(const Date* d1, const Date* d2) { return *d1 < *d2; } }; struct PDateGreater { bool operator()(const Date* d1, const Date* d2) { return *d1 > *d2; } }; void TestPriorityQueue() { // 大堆，需要用户在自定义类型中提供<的重载 priority_queue<Date> q1; q1.push(Date(2018, 10, 29)); q1.push(Date(2018, 10, 28)); q1.push(Date(2018, 10, 30)); cout << q1.top() << endl; // 如果要创建小堆，需要用户提供>的重载 priority_queue<Date, vector<Date>, greater<Date>> q2; q2.push(Date(2018, 10, 29)); q2.push(Date(2018, 10, 28)); q2.push(Date(2018, 10, 30)); cout << q2.top() << endl; //变成指针 :避免通过地址比较，需要自己写一个仿函数 //大堆 priority_queue<Date*, vector<Date*>, PDateLess> q3; q3.push(new Date(2018, 10, 29)); q3.push(new Date(2018, 10, 28)); q3.push(new Date(2018, 10, 30)); cout << *q3.top() << endl; //小堆 priority_queue<Date*, vector<Date*>, PDateGreater> q4; q4.push(new Date(2018, 10, 29)); q4.push(new Date(2018, 10, 28)); q4.push(new Date(2018, 10, 30)); cout << *q4.top() << endl; } int main()//仿函数高级用法：日期类举例 { TestPriorityQueue(); }
