PTT數位生活區 / C_and_CPP (C/C++)

[問題] PriorityQueue 的 operator overload問題

看板C_and_CPP (C/C++)作者 (胖胖貓)時間6年前 (2019/06/11 15:54), 6年前編輯推噓6(6推 0噓 20→)
留言26則, 5人參與, 6年前最新討論串1/2 (看更多)
開發平台(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，大部分都是談論解決方法，但沒有看到關於上述疑惑的說明 雖然有解決方案即可但還是希望有人可以解答這個無關痛癢的疑惑... 先謝謝大大們 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.222.86.91 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1560239661.A.746.html ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 06/11/2019 15:55:55
推
06/11 16:02, 6年前 , 1F
我的 #1SkteFdb 看有沒有解答到你的問題
06/11 16:02, 1F
→
06/11 16:02, 6年前 , 2F
簡而言之就是 C++ STL 預設就是用 < 來問你
06/11 16:02, 2F
→
06/11 18:18, 6年前 , 3F
人家預設就std::less阿
06/11 18:18, 3F
→
06/11 18:23, 6年前 , 4F
暸解 謝謝大大們
06/11 18:23, 4F
推
06/12 12:08, 6年前 , 5F
當初設計把less放在template第三格真的很鳥 正常狀況
06/12 12:08, 5F
→
06/12 12:08, 6年前 , 6F
下第二格也只會放vector不會放deque或其他東西
06/12 12:08, 6F
→
06/12 21:15, 6年前 , 7F
經xavier13540一說還真的沒傳過vector以外的
06/12 21:15, 7F
→
06/12 23:31, 6年前 , 8F
你的正常狀況真不正常
06/12 23:31, 8F
推
06/13 07:13, 6年前 , 9F
樓上都用deque還是很少用到min-heap?
06/13 07:13, 9F
推
06/13 07:48, 6年前 , 10F
deque 相對 vector 的一個優點是容器增大時不需複製/移動
06/13 07:48, 10F
→
06/13 07:49, 6年前 , 11F
到新的空間, 光這一點就很有理由在一些狀況下用 deque 了
06/13 07:49, 11F
→
06/13 07:57, 6年前 , 12F
嘛, 如果你真的對 comparator 在第三格感到很困擾的話
06/13 07:57, 12F
→
06/13 07:58, 6年前 , 13F
C++17 的 deduction guide 可以由建構子參數型態去推模版
06/13 07:58, 13F
→
06/13 08:00, 6年前 , 14F
然後 priority_queue 的建構子 comparator 都排在容器前面
06/13 08:00, 14F
→
06/13 09:54, 6年前 , 15F
std::priority_queue 要的不是 vector 也不是 deque
06/13 09:54, 15F
→
06/13 09:57, 6年前 , 16F
而是迭代器滿足 LegacyRandomAccessIterator 概念,
06/13 09:57, 16F
→
06/13 09:58, 6年前 , 17F
代表當你有需要抽換 container/allocator 的時候才會
06/13 09:58, 17F
→
06/13 09:59, 6年前 , 18F
知道它當成第二個參數的用意
06/13 09:59, 18F
推
06/13 15:32, 6年前 , 19F
我知道 但std::set不會把allocator放在less前面 不知
06/13 15:32, 19F
→
06/13 15:32, 6年前 , 20F
道當初設計把heap的第二格放容器的意義
06/13 15:32, 20F
→
06/13 22:50, 6年前 , 21F
因為你把 container 和 container adaptor 搞混了
06/13 22:50, 21F
→
06/14 12:00, 6年前 , 22F
並沒有 我分得清楚這兩者
06/14 12:00, 22F
→
06/14 12:23, 6年前 , 23F
不一樣的東西怎麼會拿來比參數的位置? 因為常抽換的
06/14 12:23, 23F
→
06/14 12:23, 6年前 , 24F
型別本來就不同
06/14 12:23, 24F
推
06/15 20:32, 6年前 , 25F
因為兩個都是底層 不影響使用段得到的東西
06/15 20:32, 25F
→
06/15 20:32, 6年前 , 26F
*端
06/15 20:32, 26F
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1S_rujT6 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1S_rujT6 (C_and_CPP)