Re: [問題] 二維vector sort

[yoco315 (眠月)]

※ 引述《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:傳函式進去不會影響效能八
推 VictorTom:推....:)
→ yoco315:ADF 自己測一下
推 spir:好強
推 dreamroyc:感謝你，我測試看看
推 Cloud:注音文...科科
推 Ebergies:傳函式會多一個 function pointer, 在 compare 頻繁呼叫
→ Ebergies:時會對效能有不小的影響
推 nowar100:漂亮
推 holymars:idx_為什麼不寫進template裡 @@?
推 legnaleurc:這樣到時候 runtime 有機會改吧 我猜
推 Cloud:映象中compiler會把functor做inline
推 holymars:runtime有機會改..除非是有要寫LessByElem(i)這種code XD
推 lance7:太強了...
推 elfkiller:推,非常實用
推 ledia:依照第五個元素來排序 ..... 這是隱藏的哏嗎 ? XD