目录
- 一、 priority_queue
- 1.priority_queue的介绍
- 2.priority_queue的使用
- 2.1、接口使用说明
- 2.2、优先级队列的使用样例
- 3.priority_queue的底层实现
- 3.1、库里面关于priority_queue的定义
- 3.2、仿函数
- 1.什么是仿函数?
- 2.仿函数样例
- 3.3、实现优先级队列
- 1. 1.0版本的实现
- 2. 2.0版本的实现
- 二、反向迭代器适配器
前言
继上一篇stack和queue我们讲解了其实现原理,里面也提到了容器适配器的概念,本篇我们要讲的优先级队列,也是一种容器适配器,另外我们再顺带讲一下反向迭代器,这个也是一个容器适配器哦,废话不多说,我们直接切入正题
一、 priority_queue
1.priority_queue的介绍
priority_queue他是一种容器适配器,但其实他底层和堆差不多,接口和堆也非常像,功能也是,默认情况下是大堆,你也可以用仿函数把他改成小堆
它的接口有以下几个:
- empty():检测容器是否为空
- size():返回容器中有效元素个数
- front():返回容器中第一个元素的引用
- push_back():在容器尾部插入元素
- pop_back():删除容器尾部元素
priority_queue的底层是堆,堆其实是完全二叉树,而完全二叉树的物理结构又是类似数组这种连续的物理空间,所以说适配priority_queue的容器要能够随机访问下标,需要支持随机访问迭代器,以便始终在内部保持堆结构,一般我们用vector作为它的默认容器,deque也可以
2.priority_queue的使用
2.1、接口使用说明
2.2、优先级队列的使用样例
priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5);
while (!pq.empty())
{cout << pq.top() << " ";pq.pop();
}
//打印结果是5,4,3,2,1
tips:默认情况下大的优先级高,底层是个大堆
3.priority_queue的底层实现
3.1、库里面关于priority_queue的定义
priority_queue类模板参数多了一个Compare,这个参数是用来调节大小堆的,默认的less是大堆,greater是小堆
tips:
3.2、仿函数
1.什么是仿函数?
仿函数又被叫做函数对象,它们是通过重载operator()运算符的类的实例,它们可以像函数那样被调用,具有这样特性的就是仿函数
2.仿函数样例
template<class T>
struct Less
{bool operator()(const T& x, const T& y){return x < y;}
};int main()
{Less<int> lessfunc;cout << lessfunc.operator()(1, 2) << endl;cout << lessfunc(2, 3) << endl;//就这样乍一看还以为是函数调用,其实这是仿函数cout << Less<int>()(1, 2) << endl;//通过匿名对象来调用return 0;
}
3.3、实现优先级队列
1. 1.0版本的实现
template<class T,class Container=vector<T>>
class priority_queue
{
public:size_t size(){return _con.size();}void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 <_con.size() && _con[child] < _con[child + 1]){child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);//先尾插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(){return _con.empty();}private:Container _con;
};
这里重点讲一下向上调整建堆和向下调整建堆,我们以建小堆为例:
向下调整的原理和向上调整很像,我就不多讲解了
2. 2.0版本的实现
template<class T>
struct less//这个虽然叫less但是它是大堆
{bool operator()(const T& x, const T& y){return x < y;}
};
template<class T>
struct greater//这个虽然叫greater,但是他是小堆
{bool operator()(const T& x, const T& y){return x > y;}
};
template<class T,class Container=vector<T>,class Com=less<T>>
class priority_queue
{
public:size_t size(){return _con.size();}void adjust_up(size_t child){Com com;//搞一个仿函数对象size_t 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(size_t parent){Com 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[child] > _con[parent])//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& val){_con.push_back(val);//先尾插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(){return _con.empty();}private:Container _con;
};
tips:
int main()
{priority_queue<int,vector<int>,greater<int>> pq;//注意这里:如果你要传仿函数的参数类型,一定不要忘记了这个vector<int>//不能跳过这个缺省参数去传他后面的其他参数,切记切记!!!return 0;
}
二、反向迭代器适配器
反向迭代器适配器,可以根据正向迭代器适配出它相应的反向迭代器
反向迭代器的实现思想其实很简单,相比我们前面list的实现;我们在这里实现反向迭代器主要是利用正向迭代器来替我们完成,库里面的实现讲求了对称,begin/end和rbegin/rend是堆成的
template<class iterator, class Ref, class Ptr>
struct ReserveIterator
{typedef ReserveIterator<iterator, Ref, Ptr> Self;iterator _it;ReserveIterator(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;}
};
关于容器适配器之类的容器我们就先讲到这里,我们下期浅谈一下模板✌