2011年8月21日 星期日

C++ Standard Library 讀書筆記: Function Object

我讀 C++ Standard Library: a Tutorial and Reference 後的筆記,主要內容來自 5.9小節,整個第八章,以及一些我自己的感想。

STL Algorithms

C++ STL Algorithms 裡一系列操作容器的函數,我一直以來都覺得這系列函數異常的難用。例如萬年範例 -- for_each 逐一打印容器的元素:
void print_int( int i ) {
    cout << i << endl;
}

for_each(v.begin(), v.end(), print_int); //逐一印出元素

乍看之下簡潔,但是這 for_each 有個致命的缺點,就是沒辦法傳入額外參數。例如我想對集合內的每個數值都加上一個固定值,用 for 迴圈再直覺不過:
int value = 5;
vector<int>::iterator it;
for(it=v.begin(); it!=v.end(); ++it)
    *it = *it + value;

這麼簡單的程式,想要改寫成for_each版本,馬上碰壁:
void add_value( int & i ) {
    i = i + ???;  // add something?
}

int main() {
    vector<int> v;
    for_each(v.begin(), v.end(), add_value);
}
問號的地方只能放常數或者全域變數,而兩個選項都很爛,我真正想要的是從 main 裡面傳入一個變數。所以很長一段時間我把 for_each 封印起來,乖乖自己寫 for 迴圈。

Function Object

直到最近,我才明瞭到 function object 可能是這個惱人的問題的答案。

所謂的 function object 就是一個object,但是實做了operator() 。它實際上是物件,但可以當作函數來呼叫。要發揮整個 STL Algorithms 的威力,就一定要瞭解 function object。萬年打印範例用funciton object 來實作就會長這樣子 :
class PrintInt{
    void operator() (int i) const {
        cout << i;
    }
};

for_each(v.begin(), b.end(), PrintInt());

PrintInt 就是一個 function object,它有實作operator()。 我們可以宣告一個物件變數 PrintInt p;  對他做好像函數呼叫的動作 p(); 而此時實際上呼叫的是 PrintInt::operator() 這個成員函數。 function object 最大的好處就是裡面可以定義成員變數,維護內部的狀態,而一般的函式做不到。我們回頭拿它來解決剛剛的惱人問題,就可以明白我在說什麼。這兒定義了一個很簡單的小物件AddValue,因為AddValue有實作operator() ,所以它是一個function object。
class AddValue {
    int value;
public:
    AddValue(int v) { value = v; }
    void operator()(int &i) { i = i+value; }
};

int main() {
    vector<int> v;
    for_each(v.begin(), v.end(), AddValue(5));
}

把AddValue物件當作參數傳入, 此時 for_each 針對集合元素的每次 function call 實際上是呼叫 AddValue::operator() ,而我們希望加上去的固定值,被當做 function object 的成員變數存起來了。這樣就巧妙的解決了額外參數的問題。

AddValue add10(10), add30(30); //建立許多function object在不同狀況使用
for_each(v.begin(), v.end(), add10);
for_each(v.begin(), v.end(), add30);

求平均值

「求平均值」是比較進階的例子,用 for_each 來計算整數集合的平均值。我們利用了 for_each 最後會回傳該 function object 的特性,把元素的總和(sum) 跟元素個數(num_element) 都紀錄在的function object的成員變數中,最後取平均值 :
class MeanValue {
    int sum;
    int num_element;
public:
    MeanValue() { sum = num_element = 0;}
    void operator() (int i) { sum += i; num_element++; }
    double value() { return (double)sum / (double)num_element); }
};

int main() {
    vecter<int> v;
    MeanValue m = for_each(v.begin(), v.end(), MeanValue());
    cout << m.value();
}

Function Object的優點

Function Object主要有三個優點
  1. Function Object 比一般函數聰明,它可以維護內部的狀態,記錄呼叫過程中發生的事。
  2. 通常 Function Object 的效能比函數指標好,因為比較容易最佳化。
  3. Function Object 可以當作 template 參數使用,一般的函數不行。

預先定義好的Function Object

除了自己寫 function object 以外,STL已經定義好了一系列常用的 function object 。這裡舉兩個簡單的範例,欲知詳情可以參閱 C++ Reference "functional"
int myint[] = {20,30,10,50,40};
vector<int> v(myint, myint+5);

sort( v.begin(), v.end(), less<int>() ); //排序由小到大
sort( v.begin(), v.end(), greater<int>() ); // 排序由大到小

remove_if( v.begin(), v.end(), bind2nd( greater<int>(), 40)); //移除所有大於40的元素