惠州网站建设企业,建设企业品牌网站,中国建设工程造价管理协会,哈尔滨网站建设效果好快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《C语言》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 一、仿函数1.1 仿函数的介绍1.2 仿函数的优势 二、priority_queue2.1 push2.2 pop2.3 top2.4 size2.5 empty 三、… 快乐的流畅个人主页 个人专栏《C语言》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 一、仿函数1.1 仿函数的介绍1.2 仿函数的优势 二、priority_queue2.1 push2.2 pop2.3 top2.4 size2.5 empty 三、反向迭代器3.1 成员变量与默认成员函数3.2 operator*3.3 operator-3.4 operator3.5 operator- -3.6 relational operators 四、反向迭代器的适用4.1 vector4.1.1 rbegin4.1.2 rend 4.2 list4.2.1 rbegin4.2.2 rend 总结 一、仿函数
1.1 仿函数的介绍
仿函数是一种特殊类型的类它重载了运算符使得这个类的使用看起来像一个函数因此它又称为函数对象。
具体来说仿函数就是将函数的特性赋予到类上使得这个类有了类似函数的行为。
1.2 仿函数的优势
C设计仿函数之初其实就是想替代庞杂难懂的函数指针将函数指针替换为简单易懂的仿函数。
这里列举两个常用的仿函数——less和greater
templateclass T
struct less
{bool operator()(const T x, const T y){return x y;}
};templateclass T
struct greater
{bool operator()(const T x, const T y){return x y;}
};二、priority_queue
细节
priority_queue也是容器适配器默认容器使用vector其底层数据结构是堆并且默认情况为大堆 如果不了解堆可以先看往期【数据结构】【版本2.0】【树形深渊】——二叉树入侵为了能方便调整大小堆增加了仿函数的模板
templateclass T, class Container vectorT, class Compare lessT
class priority_queue
{
public:
private:Container _con;
};悄悄说一句其实容器模板和仿函数模板位置互换才更加合理平时不怎么会换默认容器但是会经常换仿函数来控制大小堆
2.1 push
入堆
细节
先尾插元素再使用向上调整算法
void push(const T x)
{_con.push_back(x);adjust_up(_con.size() - 1);
}向上调整算法
细节
构造一个仿函数模板对象再利用重载的运算符进行比较当然也可以使用匿名对象
void adjust_up(int child)
{Compare com;int parent (child - 1) / 2;while (child 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}
}2.2 pop
出堆
细节
先首尾元素互换再尾删元素最后使用向下调整算法
void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}向下调整算法
细节
构造一个仿函数模板对象再利用重载的运算符进行比较当然也可以使用匿名对象
void adjust_down(int parent)
{Compare com;int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child], _con[child1])){child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}
}2.3 top
获取堆顶元素
const T top() const
{return _con[0];
}2.4 size
获取堆中有效元素个数
size_t size() const
{return _con.size();
}2.5 empty
判断堆是否为空
bool empty() const
{return _con.empty();
}三、反向迭代器
其实反向迭代器也是一种适配器它是根据不同容器的正向迭代器来生成对应的反向迭代器。
同时反向迭代器追求一种对称美rbegin()在end()rend()在begin()。
3.1 成员变量与默认成员函数
细节
仍然使用struct标明公有属性成员变量是一个正向迭代器提供带参构造函数其余的默认成员函数不用显式定义浅拷贝即可
templateclass Iterator, class Ref, class Ptr
struct __reverse_iterator
{typedef __reverse_iterator self;Iterator _cur;__reverse_iterator(Iterator it): _cur(it){}
};3.2 operator*
细节
迭代器先自减再解引用返回返回引用为了区别普通迭代器和const迭代器
Ref operator*()
{Iterator tmp _cur;return *--tmp;
}3.3 operator-
细节
直接调用operator*()根据不同容器的数据取地址返回返回指针为了区别普通迭代器和const迭代器
Ptr operator-()
{return (operator*());
}3.4 operator
细节
反向迭代器的就是正向迭代器的- -为了区分前置和后置后置参数加上int无实际意义以示区分前置传引用返回后置传值返回
self operator()
{--_cur;return *this;
}self operator(int)
{Iterator tmp _cur;--_cur;return tmp;
}3.5 operator- -
细节同上
self operator--()
{_cur;return *this;
}self operator--(int)
{Iterator tmp _cur;_cur;return tmp;
}3.6 relational operators
bool operator!(const self s)
{return _cur ! s._cur;
}bool operator(const self s)
{return _cur s._cur;
}四、反向迭代器的适用
4.1 vector
templateclass T
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;typedef __reverse_iteratoriterator, T, T* reverse_iterator;typedef __reverse_iteratoriterator, const T, const T* const_reverse_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//...
}4.1.1 rbegin
reverse_iterator rbegin()
{return reverse_iterator(end());
}const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}4.1.2 rend
reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}4.2 list
templateclass T
class list
{
public:typedef __list_nodeT node;typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;typedef __reverse_iteratoriterator, T, T* reverse_iterator;typedef __reverse_iteratoriterator, const T, const T* const_reverse_iterator;iterator begin(){return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}//...
}4.2.1 rbegin
reverse_iterator rbegin()
{return reverse_iterator(end());
}const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}4.2.2 rend
reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}总结
这次学习了仿函数的概念和基本用法对于升降序、大小堆等转换具有极大便利。同时实现了新的容器适配器——priority_queue优先级队列实际上就是堆。并且也完美实现了同为适配器的反向迭代器至此对于适配器有了更深一步的了解和运用。 真诚点赞手有余香
