顺的网站建设咨询,wordpress 列表圆点,北京建设信源资讯网站官网,玉溪做网站建设的公司优先级队列#xff0c;仿函数#xff0c;反向迭代器 优先级队列认识优先级队列模拟实现优先级队列 浅谈仿函数仿函数的大致了解仿函数的实现 反向迭代器什么是反向迭代器#xff1f;反向迭代器的实现 结语 优先级队列
认识优先级队列 优先级队列#xff08;priority_queue… 优先级队列仿函数反向迭代器 优先级队列认识优先级队列模拟实现优先级队列 浅谈仿函数仿函数的大致了解仿函数的实现 反向迭代器什么是反向迭代器反向迭代器的实现 结语 优先级队列
认识优先级队列 优先级队列priority_queue不是队列。优先级队列是一种容器适配器与栈stack队列queue具有类似的功能。 先来了解一下优先级队列有哪些功能。看下图 优先级队列底层是一个堆默认是大堆第二个参数默认给的是vector不适合list第三个参数是仿函数函数对象。 模拟实现优先级队列
大部分成员函数可以通过调用vector的成员函数来实现。
#pragma oncenamespace bit {//目前建堆默认大堆如果想建小堆怎么办templateclass T, class Container vectorTclass priority_queue {private://不想让别人知道这两个函数可以设置为私有void AdjustUp(int child){//向上调整需要和兄弟比较吗int parent (child - 1) / 2;while (child 0){if (_con[child] _con[parent]){std::swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}//向下调整删除数据调用void AdjustDown(int parent){Compare com;int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child 1] _con[child]){child;}if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}public:templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){//传过来的迭代器可能不是有序的所以要排序建堆。while (first ! last){push(*first);first;}}priority_queue()//会调用vector的默认构造函数{}void push(const T val){_con.push_back(val);AdjustUp(_con.size() - 1);}const T top() const{return _con[0];}bool empty() const{return _con.empty();}void pop(){//为什么swap不交换swap(_con[0], _con[_con.size() - 1]);//_con.size() - 1;//为什么这个程序不执行执行了但是size没变只是_con.size() - 1_con.pop_back();AdjustDown(0);}void swap(priority_queue pq){std::swap(_con, pq._con);}size_t size() const{return _con.size();}private:Container _con;};
}如果想建小堆但不增加代码量的冗余有办法吗
浅谈仿函数
仿函数的大致了解
怎么建小堆可以增加一个参数函数指针这个函数来控制大堆还是小堆。但是函数指针声明比较复杂有一些声明很长导致通用性变差。所以仿函数就来了。 写一个类类中写相应的方法这个类作为参数那么就可以调用该类中的方法了。 仿函数函数对象不是函数调用只是具有函数的功能。
如下代码是对上面代码的补充与修改
仿函数的实现
#pragma oncenamespace bit {templateclass T, class Container vectorT, class Compare Greaterintclass priority_queue {private://不想让别人知道这两个函数void AdjustUp(int child){Compare com;int parent (child - 1) / 2;while (child 0){if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){Compare com;int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child 1], _con[child])){child;}if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}public:templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){//传过来的迭代器可能不是有序的所以要排序建堆。while (first ! last){push(*first);first;}}priority_queue()//会调用默认的构造函数{}void push(const T val){_con.push_back(val);AdjustUp(_con.size() - 1);}const T top() const{return _con[0];}bool empty() const{return _con.empty();}void pop(){//为什么swap不交换swap(_con[0], _con[_con.size() - 1]);//_con.size() - 1;//为什么这个程序不执行执行了但是size没变只是_con.size() - 1_con.pop_back();AdjustDown(0);}void swap(priority_queue pq){std::swap(_con, pq._con);}size_t size() const{return _con.size();}private:Container _con;};
}
templateclass T
struct Less
{
public:bool operator()(T x, T y){return x y;}
};
templateclass T
struct Greater
{
public:bool operator()(T x, T y){return x y;}
};仿函数很方便类中写许多的函数资源的管理性不错参数就可以只传一个类封装性很强灵活性很高。
反向迭代器
什么是反向迭代器 **反向迭代器reverse_iterator)**就是迭代器的相反。rbegin就是endrend就是begin。 图中表示的rbeginrend就是反向迭代器。
那如何实现反向迭代器呢
反向迭代器的实现
仔细观察上面那张图begin与rbeginend与rend都是对称的。
·反向迭代器初始化可以调用正向迭代器的初始化
·反向迭代器就是正向迭代器 的––就是正向迭代器的。
先来看看库里面的反向迭代器是如何实现的。 反向迭代器中有一个正向迭代器成员。和–操作没有问题都是调用正向迭代器的和–函数但是解引用*函数中为什么要–
我们根据如下代码进行分析
#includeiostream
#includevector
using namespace std;int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vectorint::reverse_iterator rit v.rbegin();for (rit ! v.rend()){cout *rit ;rit;}cout endl;
})rbegin 是由 end 初始化的所以指向最后一个元素的下一个位置。所以解引用时rbegin 要到前一个位置返回前一个位置的元素rbegin不变rbegin 和 rend 相等时循环结束。
反向迭代器的实现
//反向迭代器可以封装一个正向迭代器各种操作可以调用正向迭代器的函数
templateclass Iterator, class Ref, class Ptr
class ReverseIterator {
private:Iterator _it;
public:typedef ReverseIteratorIterator, Ref, Ptr Self;ReverseIterator()//调用正向迭代器的构造函数{}ReverseIterator(const Iterator it):_it(it)//调用正向迭代器的拷贝构造函数{}Ref operator*()//解引用指向前一个位置的元素本身不变。{Iterator tmp _it;return *(--tmp);}Self operator()//调用正向迭代器--函数{--_it;return *this;}Self operator--()//调用正向迭代器函数{_it;return *this;}bool operator!(const Self s)//调用正向迭代器的!函数{return _it ! s._it;}
};结语 优先级队列priority_queue实现较为简单与数据结构中的堆很相似。实现优先级队列与实现栈和队列的区别是栈和队列可以直接复用其他容器的函数优先级队列则需要自己加一些东西进去加工如向下调整仿函数等。 仿函数替换成函数指针。函数指针很麻烦写个函数声明很长读懂也容易绕晕。仿函数就是一个类类中可以写许多函数封装的很好使用时很方便。 反向迭代器reverse_iterator)就是理解解引用*的过程写起来就是封装一个正向迭代器。
