服务好的岑溪网站开发,中学加强校园网站建设,德州做网站哪家好,网站建设项目内容#x1fa90;#x1fa90;#x1fa90;欢迎来到程序员餐厅#x1f4ab;#x1f4ab;#x1f4ab; 今日主菜#xff1a; priority_queue类及反向迭代器 主厨#xff1a;邪王真眼 主厨的主页#xff1a;Chef‘s blog 所属专栏#xff1a;c大冒险 向着c… 欢迎来到程序员餐厅 今日主菜 priority_queue类及反向迭代器 主厨邪王真眼 主厨的主页Chef‘s blog 所属专栏c大冒险 向着c塔塔开 [本节目标] 1.仿函数 2.priority_queue 3.反向迭代器
一.仿函数
1.1仿函数是什么
仿函数Functor是一种重载了函数调用运算符operator()的类对象他的使用方法看起来与函数极其相似却又有不同因此成为仿函数
1.2仿函数的定义与使用
我们现在写一个可以比较两个变量大小的仿函数以及函数 templateclass T
class Less
{bool operator()(const Ta,const Tb ){return a b;}
};
templateclass Tbool Less(const T a, const T b ){return a b;} 那么问题来了仿函数的优势是什么呢
我们知道有时候为了在函数中调用别的函数我们需要传一个叫做函数指针的东西简单的函数还好复杂的函数的指针是真的难看懂于是乎仿函数横空出世你要用它就传个他的类就行一下子容易多了。
二、priority_queue
2.1 priority_queue的介绍 1. 优先队列是一种容器适配器STL中默认使用的容器是vector不过deque也可以 2. 他存储数据的结构是堆默认是大堆。 3. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 pop_back()删除容器尾部元素 4. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、 push_heap 和 pop_heap 来自动完成此操作。 2.2成员变量 templateclass T, class Container vectorT, class Compare LessTclass priority_queue{public://函数private:Container _con;}; 我们是直接模拟的STL的格式但事实上在模板参数那里应该把Container放到最后才合适因为我们一般不会修改使用的容器但会选择建一个大堆或者小堆STL的格式导致我们在调整为小堆时必须也写容器才行盲猜大佬写的时候喝假酒了。 2.3empty 判断容器适配器是否为空 bool empty(){reutrn _con.empty();} 2.4size 返回容器适配器的元素个数 size_t size(){return _con.size();} 2.5top 返回堆顶元素 注意事项我们的返回值是const类型没有非const这是因为如果你用非const就可能导致堆顶元素修改进而导致结构不再是大堆或小堆。 constT top()const{_con.front();} 2.6push 入堆 1.先尾插2.在向上调整 void push(T val){_con.push_back(val);UpAdjust();}void UpAdjust(size_t number)//大堆{int child number - 1;int parent child (child-1) / 2;while (child){if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;parent (child-1) / 2;}elsebreak;}} 这里我们既要思考如果建一个小堆那就要在写一个函数可是他们两个函数只有 这里需要改变一个是一个是。 于是乎我们立刻想到了再加一个模板参数用它来处理这个大于小于的问题, 如下 templateclass T
class Less
{bool operator()(const Ta,const Tb ){return a b;}
};
templateclass T
class Greater
{bool operator()(const T a, const T b){return a b;}
}; void push(T val){_con.push_back(val);UpAdjust();}Compare com;void UpAdjust(size_t number)//大堆{int child number - 1;int parent child (child-1) / 2;while (child){if (com(_con[parent] , _con[child])){swap(_con[child], _con[parent]);child parent;parent (child-1) / 2;}elsebreak;}} 2.7pop
出堆
这个就比较难了为了保证堆的结构尽可能不被破坏以降低时间复杂度我们选择
先把第一个元素和最后一个元素交换位置最后删除最后一个元素。在对堆顶进行向下调整法构造一个仿函数模板对象再利用重载的运算符进行比较
templateclass T
class Less
{bool operator()(const Ta,const Tb ){return a b;}
};
templateclass T
class Greater
{bool operator()(const T a, const T b){return a b;}
}; Compare com;void DownAdjust(size_t size){int parent 0;int child parent * 21;while (childsize){if (childsizecom(_con[child], _con[child 1]))child;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}elsebreak;}}void pop(){swap(_con[0], _con[size() - 1]);
_con.pop_back();DownAdjust(size());}
三、反向迭代器
反向迭代器是一种适配器它是根据不同容器的正向迭代器来生成对应的反向迭代器。
反向迭代器的rbegin对应迭代器的end位置rend对应begin位置。
3.1 成员变量
细节
使用struct标明公有属性成员变量是一个正向迭代器
template class Iterator,class Ref,class Ptr
struct ReverseItreator
{typedef ReverseIteratorIterator, Ref, Ptr self;Iterator it;
};
3.2默认成员函数
写一个缺省的构造别的编译器自动生即可。 ReverseItreator(Iterator valIterator()):it(val){}
3.3operator* Ref operator*(){Iterator its it;its--;return *its;}
3.4operator--
self operator--()
{return it;
}
self operator--()const
{Iterator its it;it;return its;
}
3.5operator self operator(){return --it;}self operator()const{Iterator its it;--it;return its;}
3.6operator- Ptr operator-(){return (*it);}
3.7operatoroperator! bool operator(const selfs){return it s.it;}bool operator !(const self s){return it s.it;}
3.8反向迭代器的应用
在容器中以vector举例
templateclass T
class vector
{
public:typedef T* Iterator;typedef const T* Const_Iterator;typedef ReverseIteratorIteartor, T, T* Reverse_Iterator;typedef ReverseIteratorIteartor, constT,cosnt T* Const_Reverse_Iterator;Iterator end(){return _finish;}Const_Iterator end()const{return _finish;}Iterator begin(){return _start;}Const_Iterator begin()const{return _start;}private:T* _start;T* _finish;
};
反向迭代器函数 Reverse_Iterator rbegin(){return (Reverse_Iterator)end();}Const_Reverse_Iterator rbegin()const{return (Const_Reverse_Iterator)end();}Reverse_Iterator rend(){return (Reverse_Iterator)begin();}Const_Reverse_Iterator rend()const{return (Const_Reverse_Iterator)begin();}
这时候我们就要提个问题了就拿rbegin了来说吧
看看这个函数怎么样 Reverse_Iterator begin(){return _finish;}
乍一看似乎完全没问题但是但是如果是list你咋办呢是deque你咋办呢他们都没有这个
_finish成员变量啊所以我们一开始就说了它是根据不同容器的正向迭代器来生成对应的反向迭代器。反向迭代器去调用正向迭代器的实现方法才能保证他的普适性。
总结
仿函数的用法及优势并在priority_queue适配器中加以应用对priority_queue进行了了解和模拟实现很久前就提到的了反向迭代器对迭代器这个概念有了更深的了解。
感觉有用的话就点个赞支持一下吧
