算法的泛化過程

　　將一個敘述完整的算法轉化為程序代碼，不是什麼難事。然而，如何將算法獨立與其所處理的數據結構之外，不受數據結構的羁絆呢？換個說法，如何將我們所寫的程序算法適用於任何（或者大部分）未知的數據結構（比如array，vector，list等）呢？

　　關鍵在於，只要把操作對象的型別加以抽象化，把操作對象的標示法和區間目標的移動行為抽象化，整個算法也就在一個抽象層面上工作了。整個過程稱為算法的泛型化（generalized），簡稱泛化。

　　以簡單的循序查找為例，編寫find()函數，在array中尋找特定值。面對整數array，寫出如下程序：

int* find(int* arrayHead, int arraySize, int value)
{
    int i=0;
    for (; i<arraySize; ++i)
    {
        if (arrayHead[i] == value)
        {
            break;
        }
    }

    return &(arrayHead[i]);
}

　　該函數在某個區間內查找value。返回的是一個指針，指向它所找到的第一個元素；如果沒有找到，就返回最後一個元素的下一位置（地址）。

　　“最後一個元素的下一位置”稱為end。為什麼不返回null？因為，end指針可以對其他種類的容器帶來泛型效果，這是null所無法達到的。事實上一個指向array元素的指針，不但可以指向array內部任何位置，也可以指向array尾端以外的任何位置。只不過當指針指向array尾端以外的位置時，它只能用來與其他array指針相比較，不能提領（dereference）其值。

    const int arraySize = 7;
    int ia[arraySize] = {0, 1, 2, 3, 4, 5, 6};
    int* end = ia + arraySize;

    int * ip = find(ia, sizeof(ia)/sizeof(int), 4);
    if (ip == end)
    {
        cout<<"4 not found"<<endl;
    }
    else
    {
        cout<<"4 found. "<<*ip<<endl;
    }

　　上述find()函數寫法暴露了太多的實現細節（例如arraySize），為了讓find()適用於所有類型的容器，其操作應該更抽象化些。讓find()接受兩個指針作為參數，標示一個操作區間：

int* find(int* begin, int*end, int value)
{
    while(begin !=end && *begin != value)
        ++begin;

    return begin;
}

　　由於find()函數之內並無任何操作是針對特定整數array而發的，所以我們可以把它改成一個template：

template<typename T>
T* find(T* begin, T* end, const T& value)
{
    // 注意，以下用到了operator!=, operator*, operator++
    while (begin != end && *begin != value)
        ++begin;

    // 注意，以下返回操作用會引發copy行為
    return begin;
}

　　注意數值傳遞由pass by value改為pass by reference const, 因為value的型別可為任意，對象一大，傳遞成本便會提升。

　　在上述代碼中，傳入的指針必須支持以下四種操作行為：

• inequality 判斷不相等
• dereferencelm 提領
• prefix increment 前置式遞增
• copy 復制

　　上述操作符可以被重載（overload），find()函數就可以從原聲（native）指針的思想框框中跳脫出來。我們可以設計一個class，擁有原生指針的行為，這就是迭代器（iterator）：

template<typename Iterator, typename T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
    while(begin != end && *begin != value)
        ++begin;

    return begin;
}

　　這便是完全泛型化的find()函數。

來自：STL源碼剖析

STL源碼剖析簡體中文完整版(高清晰掃描帶目錄)PDF 下載見 http://www.linuxidc.com/Linux/2016-04/129761.htm