一、仿函数
1.1 仿函数的介绍
仿函数，是一种特殊类型的类，它重载了（）运算符，使得这个类的使用看起来像一个函数，因此它又称为函数对象。
具体来说，仿函数就是将函数的特性赋予到类上，使得这个类有了类似函数的行为。
1.2 仿函数的优势
C++设计仿函数之初，其实就是想替代庞杂难懂的函数指针，将函数指针替换为简单易懂的仿函数。
这里列举两个常用的仿函数——less和greater
template<class T> struct less { bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> struct greater { bool operator()(const T& x, const T& y) { return x > y; } };
二、priority_queue
细节：
- priority_queue也是容器适配器，默认容器使用vector
- 其底层数据结构是堆，并且默认情况为大堆
如果不了解堆，可以先看往期【数据结构】【版本2.0】【树形深渊】——二叉树入侵 - 为了能方便调整大小堆，增加了仿函数的模板
template<class T, class Container = vector<T>, class Compare = less<T>> 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[child+1])) { ++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，标明公有属性
- 成员变量是一个正向迭代器
- 提供带参构造函数（其余的默认成员函数不用显式定义，浅拷贝即可）
template<class 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
template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; typedef __reverse_iterator<iterator, 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
template<class T> class list { public: typedef __list_node<T> node; typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; typedef __reverse_iterator<iterator, 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（优先级队列），实际上就是堆。并且也完美实现了同为适配器的反向迭代器，至此，对于适配器有了更深一步的了解和运用。
真诚点赞，手有余香
