Re: [問題] 二維vector sort

看板C_and_CPP作者yoco315 (眠月)時間16年前 (2009/10/11 09:19)推噓13(13推 0噓 3→)

留言16則, 13人參與討論串2/2 (看更多)

※ 引述《dreamroyc ()》之銘言： : 宣告方式是這個樣子 : vector<vector<string> > input; : 這當中我想以每一個陣列的第二個元素當作排序依據 : 如input[][1] 類似這樣你要傳入自己的「比較準則」我們可以寫一個函數專門用來比較兩個 vector<string> 的大小，準則是比較這兩個 vector<string> 的第一個元素，像是這樣…… typedef vector<string> strvec ; bool LessByElem_1(const strvec& v1, const strvec& v2) { return v1[1] < v2[1] ; } 然後把這個函數傳給 sort，這樣 sort 就知道要以這個函數當作比較的準則 sort ( input.begin(), input.end(), LessByElem_1 ) ; 但是有（大部分）的 compilier 並不懂得將函數指標 inline，所以上面這種寫法在效能會比手工打造的排序函數吃虧一點點，可是我們可以把這個比較準則設計成一個 class，然後覆載這個 class 的 operator()，這樣這個 class 實體就是一個有著類似函數行為的 object 也就是一個 function object(functor)，像是這樣…… struct LessByElem_1 { bool operator()(const strvec& v1, const strvec&2) const { return v1[1] < v2[1] ; } } ; 然後你就可以像這樣使用這個 class LessByElem_1 cmp ; sort ( input.begin(), input.end(), cmp ) ; 或是直接這樣 sort ( input.begin(), input.end(), LessByElem_1() ) ; 這樣你就獲得效能了，很好。但是事情還可以更好。使用 functor 的另外一個好處，就是物件可以有 data member，可以有「狀態」，所以我們可以設定一個 functor 的行為。假設有一天你突然想要依照第五個元素來排序你的 string vector，那比較原始的作法就是你另外寫了一個 class 叫做 LessByElem_4，比較好的作法是我們擴充我們的 functor class 讓他可以接受一個參數，這樣我們就可以彈性的指定這個 functor 要第幾個元素來排序 struct LessByElem { size_t idx_ ; LessByElem(const size_t idx) idx_(idx) {} bool operator()(const strvec& v1, const strvec& v2) const { return v1[idx_] < v2[idx_] ; } } ; sort ( input.begin(), input.end(), LessByElem(1) ) ; // 像這樣 sort ( input.begin(), input.end(), LessByElem(4) ) ; // 或是這樣這下我們不僅有了效率，還有了彈性！這個程式碼可以被用了！還不賴！但是還沒完美……因為這個 class 只能用在 vector<string>，這有點可惜，因為以後你可能會想要對 vector<int> 作類似的事情，所以讓我們把這個 functor class 設計成 template。 struct LessByElem { size_t idx_ ; LessByElem(const size_t idx) idx_(idx) {} template < typename T > bool operator()(const T& v1, const T& v2) const { return v1[idx_] < v2[idx_] ; } } ; 好啦，搞定了，ㄎㄎ。 -- To iterate is human, to recurse, divine. 遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.160.104.161

→

ADF

10/11 11:41, , 1^F

10/11 11:41, 1^F

推

VictorTom

10/11 12:40, , 2^F

10/11 12:40, 2^F

→

yoco315

10/11 14:29, , 3^F

10/11 14:29, 3^F