C++ STL priority_queue自定义排序实现方法详解
前面讲解 priority_queue 容器适配器时,还遗留一个问题,即当 <function> 头文件提供的排序方式(std::less<T> 和 std::greater<T>)不再适用时,如何自定义一个满足需求的排序规则。
首先,无论 priority_queue 中存储的是基础数据类型(int、double 等),还是 string 类对象或者自定义的类对象,都可以使用函数对象的方式自定义排序规则。例如:
#include<iostream> #include<queue> using namespace std; //函数对象类 template <typename T> class cmp { public: //重载 () 运算符 bool operator()(T a, T b) { return a > b; } }; int main() { int a[] = { 4,2,3,5,6 }; priority_queue<int,vector<int>,cmp<int> > pq(a,a+5); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } return 0; }
运行结果为:
2 3 4 5 6
注意,C++ 中的 struct 和 class 非常类似,前者也可以包含成员变量和成员函数,因此上面程序中,函数对象类 cmp 也可以使用 struct 关键字创建:
struct cmp { //重载 () 运算符 bool operator()(T a, T b) { return a > b; } };
可以看到,通过在 cmp 类(结构体)重载的 () 运算符中自定义排序规则,并将其实例化后作为 priority_queue 模板的第 3 个参数传入,即可实现为 priority_queue 容器适配器自定义比较函数。
除此之外,当 priority_queue 容器适配器中存储的数据类型为结构体或者类对象(包括 string 类对象)时,还可以通过重载其 > 或者 < 运算符,间接实现自定义排序规则的目的。
注意,此方式仅适用于 priority_queue 容器中存储的为类对象或者结构体变量,也就是说,当存储类型为类的指针对象或者结构体指针变量时,此方式将不再适用,而只能使用函数对象的方式。
要想彻底理解这种方式的实现原理,首先要搞清楚 std::less<T> 和 std::greater<T> 各自的底层实现。实际上,<function> 头文件中的 std::less<T> 和 std::greater<T> ,各自底层实现采用的都是函数对象的方式。比如,std::less<T> 的底层实现代码为:
template <typename T> struct less { //定义新的排序规则 bool operator()(const T &_lhs, const T &_rhs) const { return _lhs < _rhs; } };
std::greater<T> 的底层实现代码为:
template <typename T> struct greater { bool operator()(const T &_lhs, const T &_rhs) const { return _lhs > _rhs; } };
可以看到,std::less<T> 和 std::greater<T> 底层实现的唯一不同在于,前者使用 < 号实现从大到小排序,后者使用 > 号实现从小到大排序。
那么,是否可以通过重载 < 或者 > 运算符修改 std::less<T> 和 std::greater<T> 的排序规则,从而间接实现自定义排序呢?答案是肯定的,举个例子:
#include<queue> #include<iostream> using namespace std; class node { public: node(int x = 0, int y = 0) :x(x), y(y) {} int x, y; }; //新的排序规则为:先按照 x 值排序,如果 x 相等,则按 y 的值排序 bool operator < (const node &a, const node &b) { if (a.x > b.x) return 1; else if (a.x == b.x) if (a.y >= b.y) return 1; return 0; } int main() { //创建一个 priority_queue 容器适配器,其使用默认的 vector 基础容器以及 less 排序规则。 priority_queue<node> pq; pq.push(node(1, 2)); pq.push(node(2, 2)); pq.push(node(3, 4)); pq.push(node(3, 3)); pq.push(node(2, 3)); cout << "x y" << endl; while (!pq.empty()) { cout << pq.top().x << " " << pq.top().y << endl; pq.pop(); } return 0; }
输出结果为:
x y
1 2
2 2
2 3
3 3
3 4
可以看到,通过重载 < 运算符,使得 std::less<T> 变得适用了。
读者还可以自行尝试,通过重载 > 运算符,赋予 std::greater<T> 和之前不同的排序方式。
当然,也可以以友元函数或者成员函数的方式重载 > 或者 < 运算符。需要注意的是,以成员函数的方式重载 > 或者 < 运算符时,该成员函数必须声明为 const 类型,且参数也必须为 const 类型,至于参数的传值方式是采用按引用传递还是按值传递,都可以(建议采用按引用传递,效率更高)。
例如,将上面程序改为以成员函数的方式重载 < 运算符:
class node { public: node(int x = 0, int y = 0) :x(x), y(y) {} int x, y; bool operator < (const node &b) const{ if ((*this).x > b.x) return 1; else if ((*this).x == b.x) if ((*this).y >= b.y) return 1; return 0; } };
同样,在以友元函数的方式重载 < 或者 > 运算符时,要求参数必须使用 const 修饰。例如,将上面程序改为以友元函数的方式重载 < 运算符。例如:
class node { public: node(int x = 0, int y = 0) :x(x), y(y) {} int x, y; friend bool operator < (const node &a, const node &b); }; //新的排序规则为:先按照 x 值排序,如果 x 相等,则按 y 的值排序 bool operator < (const node &a, const node &b){ if (a.x > b.x) return 1; else if (a.x == b.x) if (a.y >= b.y) return 1; return 0; }
总的来说,以函数对象的方式自定义 priority_queue 的排序规则,适用于任何情况;而以重载 > 或者 < 运算符间接实现 priority_queue 自定义排序的方式,仅适用于 priority_queue 中存储的是结构体变量或者类对象(包括 string 类对象)。
到此这篇关于C++ STL priority_queue自定义排序实现方法详解的文章就介绍到这了,更多相关STL priority_queue自定义排序内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++ STL关联式容器自定义排序规则的2种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-04
- 这篇文章主要介绍了zlib库压缩和解压字符串STL string的实例详解的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++ STL中的容器适配器实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-20
- <STL 源码剖析>将其描述为空间配置器,理由是allocator可以将其它存储介质(例如硬盘)做为stl 容器的存储空间。由于内存是allocator管理的主要部分,因此,本文以STL内存管理为出发点介绍allocator...2020-04-25
stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)
这篇文章主要介绍了stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列),需要的朋友可以参考下...2020-04-25stl容器set,map,vector之erase用法与返回值详细解析
在使用 list、set 或 map遍历删除某些元素时可以这样使用,如下所示...2020-04-25- 关于set,必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序...2020-04-25
- 这篇文章主要介绍了C++在成员函数中使用STL的find_if函数实例,包括了STL中find_if函数的具体用法及相关的完整实例,非常具有参考借鉴价值,需要的朋友可以参考下...2020-04-25
Spring MVC使用jstl 标签c:forEach 遍历输出双层嵌套List的数据方式
这篇文章主要介绍了Spring MVC使用jstl 标签c:forEach 遍历输出双层嵌套List的数据方式,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-08-16c++利用stl set_difference对车辆进出区域进行判定
这篇文章主要介绍了set_difference,用于求两个集合的差集,结果集合中包含所有属于第一个集合但不属于第二个集合的元素,需要的朋友可以参考下...2020-04-25C++ STL入门教程(2) list双向链表使用方法(附程序代码)
这篇文章主要为大家详细介绍了C++ STL入门教程第二篇,list双向链表使用方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25- 这篇文章是关于C++语言的一个新的扩展——标准模板库的(Standard Template Library),也叫STL...2020-04-25
- 本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下...2020-04-25
Oracle用decode函数或CASE-WHEN实现自定义排序
这篇文章主要介绍了Oracle用decode函数或CASE-WHEN实现自定义排序功能,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-07-11- 这篇文章主要给大家介绍了关于vector的特殊性之为什么它不是STL容器的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用c++具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧...2020-04-25
- 本篇文章对c++中STL容器中的vertor与list的应用进行了详细的分析解释。需要的朋友参考下...2020-04-25
- 下面小编就为大家带来一篇关于STL的erase()陷阱-迭代器失效问题的总结。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- list就是数据结构中的双向链表(根据sgi stl源代码),因此它的内存空间是不连续的,通过指针来进行数据的访问,这个特点使得它的随即存取变的非常没有效率,因此它没有提供[]操作符的重载...2020-04-25
- 有序的stl容器在工程中应用什么方便和广泛,但是当我们需要自己的排序的时候,可以用仿函数来设置它...2020-04-25