[问题] PriorityQueue 的 operator overload问题

楼主: fatcat8127 (胖胖猫)   2019-06-11 15:54:16
开发平台(Platform): (Ex: Win10, Linux, ...)
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
问题(Question):关于PriorityQueue的自定义struct中 opertor overloading 问题
喂入的资料(Input):
预期的正确结果(Expected Output):
错误结果(Wrong Output):Comppiler Error
程式码(Code):(请善用置底文网页, 记得排版,禁止使用图档)
补充说明(Supplement):
版上已经有很多大大们讨论关于 PriorityQueue Compare Function 的解决问题,
我将相关文章整理后再提出问题,以下说明仅凭我个人理解,不精确还请大大们指正。
(1) priority_queue<int,vector<int>> PQ;
默认的 priority_queue 是 max_heap,假若想实现 min_heap 时可以搭配 greater<int>
#include<functional>
priority_queue<int,vector<int>,greater<int>> PQ;
参考这篇( https://pse.is/ECW72 ):overload greater function
bool operator>(const struct_name &one,const struct_name &rhs){
return one.dis>rhs.dis;
}
priority_queue<PAIR,vector<PAIR>,greater<vector<PAIR>::value_type>> PQ;
(2) 自定义 function
struct COMP{
bool operator()(const PAIR &lhs,const PAIR &rhs){ return lhs.dis>rhs.dis; }
};
priority_queue<PAIR,vector<PAIR>,COMP> PQ;
(3) 将定义方式写在 struct 内
struct PAIR{
int id; double dis;
PAIR(int a=0,double b=0):id(a),dis(b){}
// (1) overload operator "less than", but unable to overload "greater than"
bool operator<(const PAIR &rhs)const{ return dis<rhs.dis; }
};
priority_queue<PAIR,vector<PAIR>> PQ;
上述是以ZJ-c942为例,用不同方式宣告使用 PriorityQueue。
附上程式码:https://ideone.com/lYQ8bo
我的问题:为何(3)将定义方式写在 strcut 内的这种方式,
overload operator时 只能是">"不能是"<",虽然说相关的operator都可以从"<"转换
查了一下 StackOverflow,大部分都是谈论解决方法,但没有看到关于上述疑惑的说明
虽然有解决方案即可但还是希望有人可以解答这个无关痛痒的疑惑... 先谢谢大大们
作者: LPH66 (-6.2598534e+18f)   2019-06-11 16:02:00
我的 #1SkteFdb 看有没有解答到你的问题简而言之就是 C++ STL 默认就是用 < 来问你
作者: firejox (Tangent)   2019-06-11 18:18:00
人家默认就std::less阿
楼主: fatcat8127 (胖胖猫)   2019-06-11 18:23:00
暸解 谢谢大大们
作者: xavier13540 (柊 四千)   2019-06-12 12:08:00
当初设计把less放在template第三格真的很鸟 正常状况下第二格也只会放vector不会放deque或其他东西
楼主: fatcat8127 (胖胖猫)   2019-06-12 21:15:00
经xavier13540一说还真的没传过vector以外的
作者: loveme00835 (发箍)   2019-06-12 23:31:00
你的正常状况真不正常
作者: xavier13540 (柊 四千)   2019-06-13 07:13:00
楼上都用deque还是很少用到min-heap?
作者: LPH66 (-6.2598534e+18f)   2019-06-13 07:48:00
deque 相对 vector 的一个优点是容器增大时不需复制/移动到新的空间, 光这一点就很有理由在一些状况下用 deque 了嘛, 如果你真的对 comparator 在第三格感到很困扰的话C++17 的 deduction guide 可以由建构子参数型态去推模版然后 priority_queue 的建构子 comparator 都排在容器前面
作者: loveme00835 (发箍)   2019-06-13 09:54:00
std::priority_queue 要的不是 vector 也不是 deque而是迭代器满足 LegacyRandomAccessIterator 概念,代表当你有需要抽换 container/allocator 的时候才会知道它当成第二个参数的用意
作者: xavier13540 (柊 四千)   2019-06-13 15:32:00
我知道 但std::set不会把allocator放在less前面 不知道当初设计把heap的第二格放容器的意义
作者: loveme00835 (发箍)   2019-06-13 22:50:00
因为你把 container 和 container adaptor 搞混了
作者: xavier13540 (柊 四千)   2019-06-14 12:00:00
并没有 我分得清楚这两者
作者: loveme00835 (发箍)   2019-06-14 12:23:00
不一样的东西怎么会拿来比参数的位置? 因为常抽换的型别本来就不同
作者: xavier13540 (柊 四千)   2019-06-15 20:32:00
因为两个都是底层 不影响使用段得到的东西*端

Links booklink

Contact Us: admin [ a t ] ucptt.com