[問題] 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