一級函式與 algorithm

在一些語言中，若函式可以傳遞，該語言中會稱其一級函式（first-class function），就這點而言，C++ 早就具備，不過有些開發者認為，應該要包含可以建立匿名函式的能力，在語言才稱具有一級函式的特性，就這點來說，C++ 11 有了 lambda 運算式後，才算符合這點。

無論如何，C++ 現在無疑地是具有一級函式的特性了，而在 algoritm 標頭檔中，定義了一些函式，可以接受函式或 lambda 運算式作為引數，在〈lambda 運算式〉就看過了 for_each、sort 的運用。

algoritm 中的東西很多，這邊只舉幾個常見的運用。

在〈使用 vector〉中看過 find，若要尋找首個奇數呢？可以使用 find_if，例如：

#include <algorithm>
#include <iostream> 
#include <vector>
using namespace std; 

int main() { 
    vector<int> number = {11, 12, 21, 30, 31, 41, 55, 66, 80, 98};

    auto p = find_if(number.begin(), number.end(), [] (int n) { return n % 2; });

    if(p != number.end()) {
        cout << *p << endl;
    }
    else {
        cout << "沒有奇數" << endl;
    }

    return 0; 
}

在 C++ 中，容器之類的操作常會涉及迭代器，因此使用上與其他具備一級函式特性的語言，在撰寫上較不直覺，然而，換來的是更大的彈性，因為只要是具有相同協定的結構，都可以套用這類操作。

以在一級函式的語言中，經常會舉 filter 之類的例子，如果 filter 出來的值是要保留在新的容器，可以使用 copy_if，例如：

#include <algorithm>
#include <iostream> 
#include <vector>
using namespace std; 

int main() { 
    vector<int> number = {11, 12, 21, 30, 31, 41, 55, 66, 80, 98};
    vector<int> dest(number.size());

    auto destEnd = copy_if(
        number.begin(), number.end(), dest.begin(), 
        [] (int n) { return n % 2; }
    );

    // 11 21 31 41 55
    for_each(dest.begin(), destEnd, [](int n) { cout << n << " "; });

    return 0; 
}

copy_if 第三個參數需要目標容器的迭代器（也就是目標容器的起點），在上例中指定為 dest.begin()，也就是 dest 的起點，如果找到符合的元素，就會將值複製至對應的位置，然後遞增迭代器，copy_if 執行過後會傳回迭代器（也就是已迭代至目標容器的哪個位置），為了要支援這樣的協定，目標容器必須有足夠的容量。

為什麼要這麼麻煩呢？因為 copy_if 是基於迭代器協定，而不是為了 vector 而設計，如果不想事先決定目標容器的容量，可以使用 iterator 的 back_inserter，這會包裹目標容器，目標容器必須支援 push_back 方法（例如 vector），傳回的迭代器若被用來指定值至對應位置時，底層會呼叫 push_back 方法在目標容器新增元素：

#include <algorithm>
#include <iostream> 
#include <vector>
#include <iterator>
using namespace std; 

int main() { 
    vector<int> number = {11, 12, 21, 30, 31, 41, 55, 66, 80, 98};
    vector<int> dest;

    copy_if(
        number.begin(), number.end(), 
        back_inserter(dest), [] (int n) { return n % 2; }
    );

    // 11 21 31 41 55
    for_each(dest.begin(), dest.end(), [](int n) { cout << n << " "; });

    return 0; 
}

如果 filter 出來的值想從原容器去除，可以使用 remove_if，例如：

#include <algorithm>
#include <iostream> 
#include <vector>
#include <iterator>
using namespace std; 

int main() { 
    vector<int> number = {11, 12, 21, 30, 31, 41, 55, 66, 80, 98};

    auto removeStart = remove_if(
        number.begin(), number.end(), 
        [] (int n) { return n % 2; }
    );

    // 12 30 66 80 98
    for_each(number.begin(), removeStart, [](int n) { cout << n << " "; });
    cout << endl;

    // 12 30 66 80 98 41 55 66 80 98
    for_each(number.begin(), number.end(), [](int n) { cout << n << " "; });

    return 0; 
}

實際上，remove_if 並不是真的把元素從原容器去除了，它只是將要去除的元素往後移，然後傳回這些元素的起點，如果這些元素你真的不要了，可以使用 vector 的 erase 方法。例如：

#include <algorithm>
#include <iostream> 
#include <vector>
#include <iterator>
using namespace std; 

int main() { 
    vector<int> number = {11, 12, 21, 30, 31, 41, 55, 66, 80, 98};

    auto removeStart = remove_if(
        number.begin(), number.end(), 
        [] (int n) { return n % 2; }
    );
    number.erase(removeStart, number.end());

    // 12 30 66 80 98
    for_each(number.begin(), removeStart, [](int n) { cout << n << " "; });

    return 0; 
}

至於具備一級函式的語言中愛談的 map，在 C++ 中可以使用 tranform 來解決，使用上跟 copy_if 類似，需要指定一個目標容器。例如：

#include <algorithm>
#include <iostream> 
#include <vector>
#include <iterator>
using namespace std; 

int main() { 
    vector<int> number = {11, 12, 21, 30, 31, 41, 55, 66, 80, 98};
    vector<int> dest;

    transform(
        number.begin(), number.end(), 
        back_inserter(dest), [] (int n) { return n * 10; }
    );

    // 110 120 210 300 310 410 550 660 800 980
    for_each(dest.begin(), dest.end(), [](int n) { cout << n << " "; });

    return 0; 
}

雖然以上都是傳遞 lambda 運算式，實際上它們也可以接受函式位址；其他函式的運用，就參考 algoritm 的說明吧！