[C++] Functor (仿函式) - A Function-Like Object PART I - Start From qsort

Functor 簡單來說就是具有 function 功能的 object
因此 functor 讓我們可以像是呼叫 function 般的去使用一個 object
這個技巧賦予我們在寫程式時更方便與安全的方法




讓我們從 C 開始講起，假設今天我們要將一個陣列中所存放的整數加以排序 (先假設從小排到大)，我們可以利用 stdlib.h 中所提供的 qsort 來達到目的：

int compare (const void* lhs, const void* rhs)
{
    return ( *(int*)lhs - *(int*)rhs );
}

int main()
{
    int value[] = {1, 3, 2, 4};
    qsort(value, sizeof(value)/sizeof(int), sizeof(int), compare);
    return 0;
}

很基本且簡單的 qsort 用法的範例，基本上跟 cpprefence [1] 上的差不多。這個 qsort 好用的地方就在於他套用在幾乎所有不同型態的陣列上 -- 因為他們可以被轉型成 void*。雖然被轉型成 void* 之後，陣列中的每個 element 就失去其原本型別的意義，也因此無法比較大小，但是 qsort 藉由最後一個參數 - 其型別是個 function pointer - 來獲知說兩個 element 要如何比較大小。

現在我們來看稍為複雜一點點的例子：

typedef struct BigData
{
    int num;
} BigData;

int compare (const void* lhs, const void* rhs)
{
    const BigData* a = (const BigData*)lhs;
    const BigData* b = (const BigData*)rhs;
    return (a->;num - b->;num);
}

int main()
{
    BigData value[10];
    qsort(value, sizeof(value)/sizeof(BigData), sizeof(BigData), compare);
    return 0;
}

假設現在我們要排序的陣列其型別是個 user-defined structure BigData，基本使用法不變，只是把 int 改成 BigData 而已。但我們都知道 struct 的複製是很費時的，如果我們直接呼叫 qsort 來針對 value 這個陣列排序的話，我們將花費相當大量的時間在排序過程中將兩個 element 交換位置時所需的複製行為，而這問題在 structure 的 size 相當大時會變得相當可怕。一個常見的解法是透過 pointer 來排序，兩個 element 若需要交換位置，則我們只需將指向他們的 pointer 交換即可，藉此可避免大量的複製時間：

typedef struct BigData
{
    int num;
} BigData;

int compare (const void* lhs, const void* rhs)
{
    const BigData* a = *(const BigData**)lhs;
    const BigData* b = *(const BigData**)rhs;
    return (a->;num - b->;num);
}

int main()
{
    BigData value[10];
    BigData* pvalue[10];
    for(int i=0; i<;10 ++i)
        pvalue[i] = value + i;
    qsort(pvalue, sizeof(pvalue)/sizeof(BigData*), sizeof(BigData*), compare);
    return 0;
}

這個做法相當於是交換兩個 element 的 index，雖然實際資料的位置從沒變動過，但是因為 index 改了，所以如果藉由排序後的 index 去看原始資料時就宛如資料已經經過排序了，如此一來當我們透過 pvalue 依序去存取 value 裡的 elements 時，看到的就會是排序後的值。

以上是關於 C 的 qsort 的一些基本介紹與應用，只是當我們從 C 移到 C++ 時，整個世界可就不一樣了。當 OO (Object Oriented - 物件導向) 開始參與其中時，qsort 很明顯的將不再適用於 class 上，因此在 PART II 我們就來看看究竟會遇上什麼樣的問題? functor 能為我們提供怎樣的解決方案? 並且介紹 C++ 的 sorting function: std::sort。

To be continued...

Reference:
[1] http://www.cplusplus.com/reference/