一级函数与 algorithm


在一些语言中,若函数可以传递,该语言中会称其一级函数(first-class function),就这点而言,C++ 早就具备,不过有些开发者认为,应该要包含可以创建匿名函数的能力,在语言才称具有一级函数的特性,就这点来说,C++ 11 有了 lambda 表达式后,才算符合这点。

无论如何,C++ 现在无疑地是具有一级函数的特性了,而在algoritm标头文件中,定义了一些函数,可以接受函数或 lambda 表达式作为实参,在〈lambda 表达式〉就看过了for_eachsort的运用。

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而设计,如果不想事先决定目标容器的容量,可以使用iteratorback_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并不是真的把元素从原容器去除了,它只是将要去除的元素往后移,然后返回这些元素的起点,如果这些元素你真的不要了,可以使用vectorerase方法。例如:

#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的说明吧!


展开阅读全文