15.标准库算法

yyyylllll / 2024-08-31 / 原文

15.标准库算法

15.1 引言

无事可记

15.2 最低迭代器要求(Minimum Iterator Requirements)

容器的一个重要的部分就是它所支持的迭代器类型。这决定了容器可以使用哪种算法。例如，vector和array都支持random-access iterators。所有的标准库算法都可以用于vector，不改变容器大小的算法也可以用于array。采用迭代器参数的每个标准库算法都要求这些迭代器提供最低级别的功能。例如，如果算法需要前向迭代器，则该算法可以在支持前向迭代器、双向迭代器或随机访问迭代器的任何容器上运行。

标准库算法不依赖于它们所操作的容器的实现细节。只要容器（或内置数组）的迭代器满足算法的要求，算法就可以在容器上运行。

标准库容器的实现非常简洁。这些算法与容器分离，仅通过迭代器间接对容器的元素进行操作。这种分离使得编写适用于各种容器类的泛型算法变得更加容易。

使用产生可接受性能的“最弱迭代器”有助于生成最大可重用的组件。例如，如果算法只需要正向迭代器，则可以将其与任何支持正向迭代器、双向迭代器或随机访问迭代器的容器一起使用。但是，需要随机访问迭代器的算法只能与具有随机访问迭代器的容器一起使用。

15.2.1 迭代器失效

迭代器仅指向容器元素，因此当发生某些容器修改时，迭代器可能会失效。例如，如果在向量上调用 clear，则其所有元素都将被销毁。在调用 clear 之前指向该向量元素的任何迭代器现在都将无效。

在这里，我们总结了迭代器在insert和erase操作期间何时失效。

When erasing from a container, iterators to the erased elements are invalidated. In addition:

15.3 Lambda表达式

lambda表达式允许自定义匿名函数，并将它们传递给函数。表达式在函数内部定义，可以使用和操作封闭函数的局部变量。lambda 函数是 C++11 引入的，有助于使用 STL 算法对数据进行排序或处理。排序函数要求您提供一个二元谓词，以帮助确定元素的顺序。二元谓词是一个这样的函数，即对两个参数进行比较，并在一个小于另一个时返回 true，否则返回 false。这种谓词通常被实现为类中的运算符，这导致编码工作非常烦琐。使用 lambda 函数可简化谓词的定义。

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

int main(){
    const size_t SIZE{4};
    array<int,SIZE> values{1,2,3,4};
    ostream_iterator<int> output{cout," "};

    cout<<"values contains: ";
    copy(values.cbegin(), values.cend(), output);
    cout << "\nDisplay each element multiplied by two: ";

    // output each element multiplied by two
    for_each(values.cbegin(), values.cend(),
             [](auto i) {cout << i * 2 << " ";});

    // add each element to sum
    int sum = 0; // initialize sum to zero
    for_each(values.cbegin(), values.cend(), [&sum](auto i) {sum += i;});

    cout << "\nSum of value's elements is: " << sum << endl; // output sum
}

15.3.1 for_each算法

for_each的前两个参数代表要处理的元素的范围。

    const size_t SIZE{4};
    array<int,SIZE> values{1,2,3,4};
    ostream_iterator<int> output{cout," "};

    cout<<"values contains: ";
    copy(values.cbegin(), values.cend(), output);
    cout << "\nDisplay each element multiplied by two: ";

    // output each element multiplied by two
    for_each(values.cbegin(), values.cend(),
             [](auto i) {cout << i * 2 << " ";});

上述代码中，处理范围从values的第一个元素到最后一个元素。第三个参数指定范围内每个元素要调用的函数。对于上例，for_each将当前的每个元素传递给lambda表达式作为lambda表达式的参数，然后表达式使用这些元素执行它的功能。

15.3.2 Lambda with an Empty Introducer

[](auto i) {cout << i * 2 << " ";}

([ ])此方括号为lambda introducer，后面跟参数列表和函数体。lambda表达式可以使用表达式定义位置的函数的变量。lambda introducer允许指定表达式使用的变量。在C++11中必须将参数的类型明确指定，在C++14中可以使用自动类型推断(auto)。

void timesTwo(int i){
    cout << i * 2 << " ";
}

如果我们实现定义了如上所述的函数，for_each函数就可以将上述函数作为第三个参数，如下所示：

for_each(values.cbegin(), values.cend(), timesTwo);

15.3.3 Lambda with a Nonempty Introducer—Capturing Local Variables

 for_each(values.cbegin(), values.cend(), [&sum](auto i) {sum += i;});

第二次调用for_each函数，再次使用lambda表达式：

[&sum](auto i) {sum += i;}

此表达式通过引用捕获局部变量sum。

15.3.4 Lambda表达式的返回类型

如果lambda的函数体包含如下类型的语句，编译器可以推断lambda表达式的返回类型：

return expression;

其他情况下，lambda表达式的返回类型为void，除非显式的指定表达式的返回类型：

[](parameterList) -> type {lambdaBody}

15.4 算法

下述为C++中的几个算法

15.4.1 fill, fill_n, generate and generate_n

‍

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

// generator function returns next letter (starts with A)
char nextLetter(){
    static char letter{'A'};
    return letter++;
}

int main(){
    array<char,10> chars;
    fill(chars.begin(),chars.end(),'5');//fill chars with 5s

    cout<<"chars after filling with 5s:\n";
    ostream_iterator<char> output{cout," "};
    copy(chars.cbegin(),chars.cend(),output);

    //fill first five elements of chars with As
    fill_n(chars.begin(),5,'A');

    cout << "\n\nchars after filling five elements with As:\n";
    copy(chars.cbegin(), chars.cend(), output);

    // generate values for all elements of chars with nextLetter
    generate(chars.begin(), chars.end(), nextLetter);

    cout << "\n\nchars after generating letters A-J:\n";
    copy(chars.cbegin(), chars.cend(), output);

    // generate values for first five elements of chars with nextLetter
    generate_n(chars.begin(), 5, nextLetter);

    cout << "\n\nchars after generating K-O for the"
       <<" first five elements:\n";
    copy(chars.cbegin(), chars.cend(), output);
    cout << endl;

    // generate values for first three elements of chars with a lambda
    generate_n(chars.begin(),3,[](){
        static char letter{'A'};
        return letter++;
    });

    cout << "\nchars after using a lambda to generate A-C "
       <<"for the first three elements:\n";
    copy(chars.cbegin(), chars.cend(), output);
    cout << endl;

}

fill算法：

fill(chars.begin(),chars.end(),'5');//fill chars with 5s

上述代码，将字符5放置到从chars.begin()开始到chars.end()结束的每个位置上。两个参数都至少应该是forward iterators。

fill_n算法：

    //fill first five elements of chars with As
    fill_n(chars.begin(),5,'A');

上述代码将字符A放入到chars的前五个元素的位置。第一个参数至少应该是output iterator。第二个参数指明了应该插入几个元素。第三个参数指明了插入的元素。

generate算法：

    // generate values for all elements of chars with nextLetter
    generate(chars.begin(), chars.end(), nextLetter);

generate 算法将对生成器函数 nextLetter 的调用结果放在从 chars.begin（）到 chars.end（）的每个 chars 元素中，但不包括 chars.end（）。作为第一个和第二个参数提供的迭代器必须至少是正向迭代器。函数 nextLetter定义一个名为 letter 的静态局部 char 变量，并将其初始化为“A”。第 12 行中的语句返回 letter 的当前值，然后对其值进行后递增，以便在下次调用该函数时使用。

generate_n算法：

    // generate values for first five elements of chars with nextLetter
    generate_n(chars.begin(), 5, nextLetter);

使用 generate_n 算法将对生成器函数 nextLetter 的调用结果放在chars的五个元素中，从 chars.begin（）开始。作为第一个参数提供的迭代器必须至少是输出迭代器。

在generate_n算法中使用lambda表达式：

    // generate values for first three elements of chars with a lambda
    generate_n(chars.begin(),3,[](){
        static char letter{'A'};
        return letter++;
    });

equal, mismatch and lexicographical_compare

15.5 函数对象(仿函数)

重载函数调用操作符的类，其对象常称为函数对象（function object），即它们是行为类似函数的对象，也叫仿函数(functor)。其实就是重载“()”操作符，使得类对象可以像函数那样调用。函数对象可以没有参数，也可以带有若干参数，其功能是获取一个值，或者改变操作的状态。

如果一个类将()运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。函数对象是一个对象，但是使用的形式看起来像函数调用，实际上也执行了函数调用，因而得名。返回值为bool类型的一元函数对象，就称之为一元谓词。二元谓词同理。

#include <iostream>
using namespace std;

class CAverage
{
public:
    double operator()(int a1, int a2, int a3)
    {  //重载()运算符
        return (double)(a1 + a2 + a3) / 3;
    }
};

int main()
{
    CAverage average;  //能够求三个整数平均数的函数对象
    cout << average(3, 2, 3);  //等价于 cout << average.operator(3, 2, 3);
    return 0;
}

()是目数不限的运算符，因此重载为成员函数时，有多少个参数都可以。average 是一个对象，average(3, 2, 3) 实际上就是 average.operator(3, 2, 3)，这使得 average 看上去像函数的名字，故称其为函数对象。

15.5.1 函数对象应用示例

C++STL中有以下实现“累加”功能的算法（函数模板）:

template <class InIt, class T, class Pred>
T accumulate(InIt first, InIt last, T val, Pred op);

#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
using namespace std;

// binary function adds square of its second argument and the
// running total in its first argument, then returns the sum
int sumSquares(int total,int value){
    return total + value * value;
}

// Class template SumSquaresClass defines overloaded operator()
// that adds the square of its second argument and running
// total in its first argument, then returns sum
template<typename T>
class SumSquaresClass{
public:
    // add square of value to total and return result
    T operator()(const T& total, const T& value){
        return total + value * value;
    }
};

int main() {
    const size_t SIZE{10};
    array<int, SIZE> integers{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    ostream_iterator<int> output{cout, " "};//why? ostream_iterator 迭代器

    cout << "array integers contains: ";
    copy(integers.cbegin(), integers.cend(), output);

    // calculate sum of squares of elements of array integers
    // using binary function sumSquares
    int result{accumulate(integers.cbegin(), integers.cend(),0, sumSquares)};

    cout << "\n\nSum of squares of integers' elements using "
            << "binary function sumSquares: " << result;

    // calculate sum of squares of elements of array integers
    // using binary function object
    result = accumulate(integers.cbegin(), integers.cend(),0, SumSquaresClass<int>{});

    cout << "\n\nSum of squares of integers' elements using binary"
            << "\nfunction object of type SumSquaresClass<int>: "
            <<result;

    // calculate sum of squares array's elements using a lambda
    result = accumulate(integers.cbegin(), integers.cend(),0,
                        [](auto total, auto value){return total + value * value;});

    cout << "\n\nSum of squares of integer's elements using a lambda: "
            << result << endl;
}