避免重復代碼——know your library（續）

之前寫過一帖，避免重復代碼——know your library。今天外面下雨心情不咋，干脆再來發發牢騷好了 =v=

上周某公司來這邊招聘，C++版的卷裡據說有一題是要求對一個裝有自定義的struct的vector做排序的。struct有兩個field，一個int num和一個string name；排序要求按照num升序，如果num相等則按照name升序。原題到底是啥樣的我不知道，不過據說就是一個裸的struct，或許是這樣？

C++代碼　　　

struct Person {
    int num;
    string name;
};

Hmm...不知道原題裡的有沒有構造函數呢。隨便了。反正它上面是沒有重載<或==運算符的。另外，聽同學說原題裡的vector裡裝的是實例而不是指針，所以下面的代碼也反映了這點。不是我想放實例進去的哦 OTL

於是要排序。嗯，當時聽到一群剛考完的同學回到機房在討論排序算法該怎麼寫之類的。但這是C++诶，有標准庫來解決這問題，沒必要自己動手不是麼？

最低限度的，例如說這樣：

C++代碼

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
struct Person {
    int num;
    string name;
  
    Person(int num, string name)
        : num(num), name(name) {
    }
};
 
namespace std {
    template<>
    struct less<Person> {
        bool operator ()(const Person& p1, const Person& p2) {
            if (p1.num < p2.num) return true;
            if (p1.num == p2.num && p1.name < p2.name) return true;
            return false;
        }
    };
}
 
struct printElement {
    void operator ()(const Person& p) {
        cout << "Person: " << p.num << ", " << p.name << endl;
    }
};
 
int main() {
    vector<Person> v;
    v.push_back(Person(2, string("smith")));
    v.push_back(Person(1, string("john")));
    v.push_back(Person(2, string("micheal")));
    v.push_back(Person(1, string("micheal")));
    v.push_back(Person(3, string("albert")));
  
    sort(v.begin(), v.end(), less<Person>());
  
    for_each(v.begin(), v.end(), printElement());
}
 
// Output:
// Person: 1, john
// Person: 1, micheal
// Person: 2, micheal
// Person: 2, smith
// Person: 3, albert

（懶得用struct的initializer所以給Person加了個構造函數……不算作弊吧 =v=）

排序本身就用STL裡的std::sort()就完事了。因為Person上沒有定義<運算符，需要自己寫個functor來實現這個比較；懶得再發明別的名字，干脆就對std::less對Person做個特化算了。诶，自己寫排序多麻煩啊……

我不是說程序員不需要掌握各種基本排序算法的原理和實現方法，掌握基本攻還是絕對必要的。只不過原理容易掌握，真正要寫出production-quality code很難；既然標准庫裡有了，功能和性能都能滿足需要的話，就不必自己動手了。萬一自己寫錯了豈不是更糟？維護一個更大的codebase也不是好玩的事 XD

切一下題：STL是個大寶庫，裡面已經有很多神奇的東西了；能稱得上支持“標准C++”的編譯器肯定都帶有STL的實現，所以你（和你的上司）沒有拒絕STL的理由（前提是你們用的是標准C++）。其它強悍的庫，像Boost之類的，目前還沒有被包含在標准裡，所以用不用倒是看自己了。

等C++0x出來之後就更方便了……

C++代碼　　　

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
struct Person {
    int num;
    string name;
  
    Person(int num, string name)
        : num(num), name(name) {
    }
};
 
int main() {
    vector<Person> v;
    v.push_back(Person(2, string("smith")));
    v.push_back(Person(1, string("john")));
    v.push_back(Person(2, string("micheal")));
    v.push_back(Person(1, string("micheal")));
    v.push_back(Person(3, string("albert")));
 
    // use the new lambda syntax
    sort(v.begin(), v.end(), [](const Person& p1, const Person& p2) {
        if (p1.num < p2.num) return true;
        if (p1.num == p2.num && p1.name < p2.name) return true;
        return false;
    });
 
    // use the new "range-based for statement"
    for (Person p : v) {
        cout << "Person: " << p.num << ", " << p.name << endl;
    }
}

可惜裝這VS2010CTP的機器現在不在手上，不然倒可以試試我有沒有記錯C++0x裡的lambda語法。沒錯，VS2010已經支持部分的C++0x標准了，很多東西都會變得更方便 XD

不過VS2010支不支持新的range-based for statement來著？忘了……查了一下，發現是不會 T T

因為這個新的for循環語句是基於concept，而concept在VC10的編譯器的編寫過程中還沒定案，所以……T T

當然，如果Person這個struct有一個公認的自然順序，那最好還是直接在裡面重載<運算符，那樣要排序的話就能直接用兩個參數版本的sort()了。不過這裡舉的例子是題目，struct裡的內容不讓改，也就罷了。

題外話，不過這樣的一個裸struct在F#裡用tuple或者record來表示也可以嘛。如果用tuple，要對這樣一個list排序的話……

F#代碼　　

let l = [(2, "smith"); (1, "john"); (2, "micheal"); (1, "micheal"); (3, "albert")]
List.sort compare l;;
// val it : (int * string) list = [(1, "john"); (1, "micheal"); (2, "micheal"); (2, "smith"); (3, "albert")]

用List.sort compare就行了 T T 還有什麼能比這個更方便的麼？

Hmm，Ruby要是不用Struct來建個類型而是直接用數組的話……

Ruby代碼　　

 l = [[2, "smith"], [1, "john"], [2, "micheal"], [1, "micheal"], [3, "albert"]]
l.sort
#=> [[1, "john"], [1, "micheal"], [2, "micheal"], [2, "smith"], [3, "albert"]]

腳本語言用起來不爽的話就沒存在價值了 XDD

牢騷一篇，結束（逃