615 字
2 分钟
优先级队列 priority_queue 与 仿函数 greater / less
@TOC
优先级队列 priority_queue 与 仿函数 greater / less
仿函数
定义及优点
定义：定义一个类，类里面重载函数运算符()，将该类的对象作为函数的入参，那么在函数中同样能调用重载符()里面的方法。
优点：相比于普通函数，仿函数的声明更为简单。
例如：用普通函数，仿函数写一个swap函数，并将其以参数的形式，如下：
//普通函数template<class T>void _swap(T& a, T& b){ T c = a; a = b; b = c; }//声明参数void(*p)(int&, int&) = _swap;再来看看仿函数写法：
//仿函数template<class T>struct _swap{ void operator()(T& a, T& b) { T c = a; a = b; b = c; }};//声明参数_swap<int> p;我们可以看到函数指针，在面向对象开发的过程中编写有点繁琐，所以C++的仿函数借此代替了函数指针。
有了上面理解的铺垫就可以，很轻松的理解下面两个仿函数了。
greater
template<class T>class greater{public: bool operator()(const T& a, const T& b) { return a > b; }};less
template<class T>class less{public: bool operator()(const T& a, const T& b) { return a < b; }};优先级队列
priority_queue
定义：优先级队列的本质其实是一个堆，插入数据时内部按照所给的仿函数为参考进行（堆）排序，确保第一个元素为最值，存在默认的缺省值，一般采用vector为适配器，Less为仿函数.
如下：
template <class T, class Container = vector<T>, class Compare = less<T>>构造/类的成员
template <class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public: priority_queue() { } template <class InputIterator> priority_queue(InputIterator first, InputIterator last) { InputIterator it = first; while (it != last) { push(*it); it++; } //循环遍历插入即可 }private: Container c; Compare comp;);Compare是仿函数的类型，Container是适配器的类型 。
这里我们采用的是适配器模式，在对象生命周期结束时，会自动调用默认的构析函数。因为适配器为自定义类型，所以又会自动调用适配器的构析函数，所以我们不需要写构析函数，同理拷贝构造也可以不写。
这里我们写了一个以迭代器为参数的构造函数，所以还是要写一个无参的默认构造函数，什么事都不用做，因为适配器会自动调用它的构造函数。
插入函数 push(const T& x)
插入函数的实现就是利用适配器的插入，再将其插入的数进行向上调整即可。
再向上调整的过程中利用反函数的返回结果作为参考。
void AdjustUp(int child){ int father = (child - 1) / 2; while (father >= 0) { if (comp(c[father], c[child])) { swap(c[father], c[child]); child = father; father = (child - 1) / 2; } else break; }}
void push(const T& x){ c.push_back(x); AdjustUp(c.size() - 1);}删除函数 pop()
删除函数和堆的删除相同。
void AdjustDown(int father){ int child = father * 2 + 1, n = c.size(); while (child < n) { if (child + 1 < n && comp(c[child], c[child + 1])) child++; if (comp(c[father], c[child])) { swap(c[father], c[child]); father = child; child = father * 2 + 1; } else break; }}
void pop(){ swap(c[0], c[c.size() - 1]); c.pop_back(); AdjustDown(0);}其他接口
其他功能可以直接通过适配器的调用即可.
bool empty() const{ return c.empty();}size_t size() const{ return c.size();}const T& top() const{ return c[0];}源代码
源代码如下:
template<class T> class less { public: bool operator()(const T& a, const T& b) { return a < b; } };
template<class T> class greater { public: bool operator()(const T& a, const T& b) { return a > b; } };
template <class T, class Container = vector<T>, class Compare = less<T> > class priority_queue { public: priority_queue() {
} template <class InputIterator> priority_queue(InputIterator first, InputIterator last) { InputIterator it = first; while (it != last) { push(*it); it++; } } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } const T& top() const { return c[0]; }
void AdjustUp(int child) { int father = (child - 1) / 2; while (father >= 0) { if (comp(c[father], c[child])) { swap(c[father], c[child]); child = father; father = (child - 1) / 2; } else break; } }
void push(const T& x) { c.push_back(x); AdjustUp(c.size() - 1); }
void AdjustDown(int father) { int child = father * 2 + 1, n = c.size(); while (child < n) { if (child + 1 < n && comp(c[child], c[child + 1])) child++; if (comp(c[father], c[child])) { swap(c[father], c[child]); father = child; child = father * 2 + 1; } else break; } }
void pop() { swap(c[0], c[c.size() - 1]); c.pop_back(); AdjustDown(0);
}
private: Container c; Compare comp;
};结语
以上就是本期的全部内容了，喜欢就多多关注吧！！！
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
优先级队列 priority_queue 与 仿函数 greater / less
https://blog.csdn.net/GenshiN__IMPACt_/article/details/137709257 部分信息可能已经过时
相关文章 智能推荐
1
STL - list
数据结构 系统介绍 STL list 的结构特点、常用接口和迭代器用法，并通过模拟实现理解双向链表容器的核心机制。
2
栈和队列的实现及相关面试题（超详细！！！）
数据结构 分别实现栈和队列的核心接口，说明两种线性结构的特点，并解析相关的典型笔试题。
3
决战排序之巅(一)
数据结构 实现插入排序、希尔排序、选择排序与堆排序，并通过大规模数据测试比较不同算法的性能。
4
决战排序之巅（二）
数据结构 实现并分析归并排序与计数排序，比较两种算法的基本思想、代码细节、时间复杂度和适用场景。
5
单链表的实现
数据结构 介绍链表的结构与分类，重点实现无头单向链表的增删查改及销毁等基础操作。