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

8月 21, 2011

我讀 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主要有三個優點

Function Object 比一般函數聰明，它可以維護內部的狀態，記錄呼叫過程中發生的事。
通常 Function Object 的效能比函數指標好，因為比較容易最佳化。
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的元素

調和的靈感