priority_queue和仿函数
1 priority_queue的介绍
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素
中最大的。 - 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶
部的元素)。 - 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue
提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的
顶部。 - 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过
随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素 - 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue
类实例化指定容器类，则使用vector。 - 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用
算法函数make_heap、push_heap和pop_heap来自动完成此操作。
2 priority_queue的底层
#include<iostream>
#include<vector>
using namespace std;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 LL
{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):_con(first, last){// 向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}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(){return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//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(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){// 选出大的那个孩子if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))++child;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}private:Container _con;};
}
函数指针是可以传给函数的，这是实现回调机制、策略模式等功能的基础。但在模版中要求传的是类型，并且函数指针操作复杂，所以有了仿函数
1.极端情况，类里没有重载比较大小
2.改变内部比较逻辑
仿函数是“具备函数调用行为的自定义类型，其核心特征是通过重载 operator() 使其行为类似函数调用 。
struct Adder {int operator()(int a, int b) const {return a + b;}
};Adder add;
int result = add(3, 5); // 调用方式与函数完全一致