星期六的影院门口有你才热闹

星期日晚上带你去看夜景好不好

----《专属味道》

img

泛型算法

概述（Overview）

大多数算法都定义在头文件algorithm中，此外标准库还在头文件numeric中定义了一组数值泛型算法。一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的元素范围进行操作。

find函数将范围中的每个元素与给定值进行比较，返回指向第一个等于给定值的元素的迭代器。如果无匹配元素，则返回其第二个参数来表示搜索失败。

1
2
3
4
5
6
int val = 42;   // value we'll look for
// result will denote the element we want if it's in vec, or vec.cend() if not
auto result = find(vec.cbegin(), vec.cend(), val);
// report the result
cout << "The value " << val
    << (result == vec.cend() ? " is not present" : " is present") << endl;

迭代器参数令算法不依赖于特定容器，但依赖于元素类型操作。

泛型算法本身不会执行容器操作，它们只会运行于迭代器之上，执行迭代器操作。算法可能改变容器中元素的值，或者在容器内移动元素，但不会改变底层容器的大小（当算法操作插入迭代器时，迭代器可以向容器中添加元素，但算法自身不会进行这种操作）。

初识泛型算法（A First Look at the Algorithms）

只读算法（Read-Only Algorithms）

accumulate函数（定义在头文件numeric中）用于计算一个序列的和。它接受三个参数，前两个参数指定需要求和的元素范围，第三个参数是和的初值（决定加法运算类型和返回值类型）。

1
2
3
4
5
// sum the elements in vec starting the summation with the value 0
int sum = accumulate(vec.cbegin(), vec.cend(), 0);
string sum = accumulate(v.cbegin(), v.cend(), string(""));
// error: no + on const char*
string sum = accumulate(v.cbegin(), v.cend(), "");

建议在只读算法中使用cbegin和cend函数。

equal函数用于确定两个序列是否保存相同的值。它接受三个迭代器参数，前两个参数指定第一个序列范围，第三个参数指定第二个序列的首元素。equal函数假定第二个序列至少与第一个序列一样长。

1
2
// roster2 should have at least as many elements as roster1
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

只接受单一迭代器表示第二个操作序列的算法都假定第二个序列至少与第一个序列一样长。

写容器元素的算法（Algorithms That Write Container Elements）

fill函数接受两个迭代器参数表示序列范围，还接受一个值作为第三个参数，它将给定值赋予范围内的每个元素。

1
2
// reset each element to 0
fill(vec.begin(), vec.end(), 0);

fill_n函数接受单个迭代器参数、一个计数值和一个值，它将给定值赋予迭代器指向位置开始的指定个元素。

1
2
// reset all the elements of vec to 0
fill_n(vec.begin(), vec.size(), 0);

向目的位置迭代器写入数据的算法都假定目的位置足够大，能容纳要写入的元素。

插入迭代器（insert iterator）是一种向容器内添加元素的迭代器。通过插入迭代器赋值时，一个与赋值号右侧值相等的元素会被添加到容器中。

back_inserter函数（定义在头文件iterator中）接受一个指向容器的引用，返回与该容器绑定的插入迭代器。通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中。

1
2
3
4
5
vector<int> vec;    // empty vector
auto it = back_inserter(vec);   // assigning through it adds elements to vec
*it = 42;   // vec now has one element with value 42
// ok: back_inserter creates an insert iterator that adds elements to vec
fill_n(back_inserter(vec), 10, 0);  // appends ten elements to vec

copy函数接受三个迭代器参数，前两个参数指定输入序列，第三个参数指定目的序列的起始位置。它将输入序列中的元素拷贝到目的序列中，返回目的位置迭代器（递增后）的值。

1
2
3
4
int a1[] = { 0,1,2,3,4,5,6,7,8,9 };
int a2[sizeof(a1) / sizeof(*a1)];     // a2 has the same size as a1
// ret points just past the last element copied into a2
auto ret = copy(begin(a1), end(a1), a2);    // copy a1 into a2

replace函数接受四个参数，前两个迭代器参数指定输入序列，后两个参数指定要搜索的值和替换值。它将序列中所有等于第一个值的元素都替换为第二个值。

1
2
// replace any element with the value 0 with 42
replace(ilst.begin(), ilst.end(), 0, 42);

相对于replace，replace_copy函数可以保留原序列不变。它接受第三个迭代器参数，指定调整后序列的保存位置。

1
2
// use back_inserter to grow destination as needed
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

很多算法都提供“copy”版本，这些版本不会将新元素放回输入序列，而是创建一个新序列保存结果。

重排容器元素的算法（Algorithms That Reorder Container Elements）

sort函数接受两个迭代器参数，指定排序范围。它利用元素类型的<运算符重新排列元素。

1
2
3
4
5
6
7
8
9
10
void elimDups(vector<string> &words)
{
    // sort words alphabetically so we can find the duplicates
    sort(words.begin(), words.end());
    // unique reorders the input range so that each word appears once in the
    // front portion of the range and returns an iterator one past the unique range
    auto end_unique = unique(words.begin(), words.end());
    // erase uses a vector operation to remove the nonunique elements
    words.erase(end_unique, words.end());
}

unique函数重排输入序列，消除相邻的重复项，返回指向不重复值范围末尾的迭代器。

定制操作（Customizing Operations）

默认情况下，很多比较算法使用元素类型的<或==运算符完成操作。可以为这些算法提供自定义操作来代替默认运算符。

向算法传递函数（Passing a Function to an Algorithm）

谓词（predicate）是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法使用的谓词分为一元谓词（unary predicate，接受一个参数）和二元谓词（binary predicate，接受两个参数）。接受谓词参数的算法会对输入序列中的元素调用谓词，因此元素类型必须能转换为谓词的参数类型。

1
2
3
4
5
6
7
8
// comparison function to be used to sort by word length
bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}

// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);

lambda表达式（Lambda Expressions）

find_if函数接受两个迭代器参数和一个谓词参数。迭代器参数用于指定序列范围，之后对序列中的每个元素调用给定谓词，并返回第一个使谓词返回非0值的元素。如果不存在，则返回尾迭代器。

对于一个对象或表达式，如果可以对其使用调用运算符()，则称它为可调用对象（callable object）。可以向算法传递任何类别的可调用对象。

一个lambda表达式表示一个可调用的代码单元，类似未命名的内联函数，但可以定义在函数内部。其形式如下：

1
[capture list] (parameter list) -> return type { function body }

其中，capture list（捕获列表）是一个由lambda所在函数定义的局部变量的列表（通常为空）。return type、parameter list和function body与普通函数一样，分别表示返回类型、参数列表和函数体。但与普通函数不同，lambda必须使用尾置返回类型，且不能有默认实参。

定义lambda时可以省略参数列表和返回类型，但必须包含捕获列表和函数体。省略参数列表等价于指定空参数列表。省略返回类型时，若函数体只是一个return语句，则返回类型由返回表达式的类型推断而来。否则返回类型为void。

1
2
auto f = [] { return 42; };
cout << f() << endl;    // prints 42

lambda可以使用其所在函数的局部变量，但必须先将其包含在捕获列表中。捕获列表只能用于局部非static变量，lambda可以直接使用局部static变量和其所在函数之外声明的名字。

1
2
3
// get an iterator to the first element whose size() is >= sz
auto wc = find_if(words.begin(), words.end(),
                    [sz](const string &a) { return a.size() >= sz; });

解释一下：

这段代码使用了STL（标准模板库）中的find_if算法来查找满足特定条件的元素。让我们逐步解释每个部分的功能：

  1. auto wc = find_if(words.begin(), words.end(), [sz](const string &a) { return a.size() >= sz; });：这一行使用了find_if算法，它在指定范围内查找第一个满足特定条件的元素。具体来说：

    • words.begin()和words.end()指定了查找范围，即从words向量的起始位置到末尾位置。

    • [sz](const string &a) { return a.size() >= sz; }是一个lambda表达式，它定义了查找条件。lambda表达式的形式是[capture list](parameter list) { function body }，在这里：

      • [sz]是捕获列表，它捕获了外部变量sz，使lambda表达式可以访问并使用它。

      • (const string &a)是参数列表，它指定了lambda表达式的参数，这里是一个const引用到字符串。

      • { return a.size() >= sz; }是函数体，它定义了查找条件。这里，lambda表达式返回一个布尔值，即判断字符串a的大小是否大于等于sz。如果是，则返回true，表示找到了满足条件的元素。

  2. auto wc = ...;：使用auto关键字自动推导出迭代器的类型。wc是一个迭代器，它指向第一个满足条件的元素。

综上所述，这段代码的功能是查找在words向量中，第一个满足长度大于等于sz的字符串，并将指向该字符串的迭代器存储在wc中。

for_each函数接受一个输入序列和一个可调用对象，它对输入序列中的每个元素调用此对象。

1
2
3
// print words of the given size or longer, each one followed by a space
for_each(wc, words.end(),
            [] (const string &s) { cout << s << " "; });

lambda捕获和返回（Lambda Captures and Returns）

被lambda捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝。在lambda创建后修改局部变量不会影响lambda内对应的值。

1
2
3
4
5
size_t v1 = 42; // local variable
// copies v1 into the callable object named f
auto f = [v1] { return v1; };
v1 = 0;
auto j = f();   // j is 42; f stored a copy of v1 when we created it

这段代码使用了 C++11 中的 lambda 表达式来创建了一个可调用对象，并且捕获了一个局部变量 v1。让我们一步步解释代码的功能：

  1. size_t v1 = 42;: 这行代码声明并初始化了一个名为 v1 的本地变量，其值为 42。

  2. auto f = [v1] { return v1; };: 这行代码定义了一个 lambda 表达式，并将其赋值给变量 f。 lambda 表达式的形式为 [capture-list] (parameters) { body }，在这里：

    • [v1] 是捕获列表，它允许 lambda 表达式访问在 lambda 函数体内部使用的外部变量。[v1] 捕获了变量 v1，并在 lambda 函数体内部使用它。

    • { return v1; } 是 lambda 函数体，它包含了 lambda 表达式要执行的操作。在这里，lambda 函数体返回捕获的变量 v1 的值。

  3. v1 = 0;: 这行代码将变量 v1 的值更改为 0。

  4. auto j = f();: 这行代码调用了 lambda 表达式，并将其返回值赋值给变量 j。由于 lambda 表达式 [v1] { return v1; } 捕获了变量 v1 的值（在创建时进行了捕获），即使在调用 lambda 表达式时 v1 的值已经被修改为 0，lambda 表达式仍然返回了捕获时的值，也就是 42。因此，变量 j 的值为 42。

lambda可以以引用方式捕获变量，但必须保证lambda执行时变量存在。

1
2
3
4
5
size_t v1 = 42; // local variable
// the object f2 contains a reference to v1
auto f2 = [&v1] { return v1; };
v1 = 0;
auto j = f2();  // j is 0; f2 refers to v1; it doesn't store it

可以让编译器根据lambda代码隐式捕获函数变量，方法是在捕获列表中写一个&或=符号。&为引用捕获，=为值捕获。

可以混合使用显式捕获和隐式捕获。混合使用时，捕获列表中的第一个元素必须是&或=符号，用于指定默认捕获方式。显式捕获的变量必须使用与隐式捕获不同的方式。

1
2
3
4
5
6
// os implicitly captured by reference; c explicitly captured by value
for_each(words.begin(), words.end(),
            [&, c] (const string &s) { os << s << c; });
// os explicitly captured by reference; c implicitly captured by value
for_each(words.begin(), words.end(),
            [=, &os] (const string &s) { os << s << c; });

这两段代码是使用 lambda 表达式结合 STL 中的 for_each 算法来对 words 容器中的元素进行处理。它们展示了 lambda 表达式中捕获变量的不同方式，通过引用捕获和值捕获的不同组合。

第一段代码：

1
2
3
// os implicitly captured by reference; c explicitly captured by value
for_each(words.begin(), words.end(),
            [&, c] (const string &s) { os << s << c; });

这段代码使用了 [&, c] 的捕获列表。其中 & 表示以引用方式捕获外部作用域的变量，而 c 则表示以值的方式捕获。这意味着 os 变量会被隐式以引用方式捕获，而 c 则被显式以值的方式捕获。在 lambda 函数体中，os 是以引用方式捕获的，而 c 则是以值的方式捕获的。

第二段代码：

1
2
3
// os explicitly captured by reference; c implicitly captured by value
for_each(words.begin(), words.end(),
            [=, &os] (const string &s) { os << s << c; });

这段代码使用了 [=, &os] 的捕获列表。其中 = 表示以值的方式捕获所有外部作用域的变量，而 &os 则表示以引用的方式捕获 os 变量。这意味着 os 变量会被显式以引用方式捕获，而 c 则会被隐式以值的方式捕获。在 lambda 函数体中，os 是以引用方式捕获的，而 c 则是以值的方式捕获的。

总的来说，两段代码都使用了相同的 for_each 算法来遍历 words 容器中的元素，并对每个元素执行相同的操作，即将每个字符串及变量 c 的值输出到输出流 os 中。唯一的区别在于，它们对于变量 os 和 c 的捕获方式不同。

默认情况下，对于值方式捕获的变量，lambda不能修改其值。如果希望修改，就必须在参数列表后添加关键字mutable。

1
2
3
4
5
size_t v1 = 42; // local variable
// f can change the value of the variables it captures
auto f = [v1] () mutable { return ++v1; };
v1 = 0;
auto j = f();   // j is 43

对于引用方式捕获的变量，lambda是否可以修改依赖于此引用指向的是否是const类型。

transform函数接受三个迭代器参数和一个可调用对象。前两个迭代器参数指定输入序列，第三个迭代器参数表示目的位置。它对输入序列中的每个元素调用可调用对象，并将结果写入目的位置。

1
2
transform(vi.begin(), vi.end(), vi.begin(),
            [](int i) -> int { if (i < 0) return -i; else return i; });

为lambda定义返回类型时，必须使用尾置返回类型。

参数绑定（Binding Arguments）

bind函数定义在头文件functional中，相当于一个函数适配器，它接受一个可调用对象，生成一个新的可调用对象来适配原对象的参数列表。一般形式如下：

1
auto newCallable = bind(callable, arg_list);

其中，newCallable本身是一个可调用对象，arg_list是一个以逗号分隔的参数列表，对应给定的callable的参数。之后调用newCallable时，newCallable会再调用callable，并传递给它arg_list中的参数。arg_list中可能包含形如_n的名字，其中n是一个整数。这些参数是占位符，表示newCallable的参数，它们占据了传递给newCallable的参数的位置。数值n表示生成的可调用对象中参数的位置：_1为newCallable的第一个参数，_2为newCallable的第二个参数，依次类推。这些名字都定义在命名空间placeholders中，它又定义在命名空间std中，因此使用时应该进行双重限定。

1
2
3
4
5
6
7
8
9
using std::placeholders::_1;
using namespace std::placeholders;
bool check_size(const string &s, string::size_type sz);

// check6 is a callable object that takes one argument of type string
// and calls check_size on its given string and the value 6
auto check6 = bind(check_size, _1, 6);
string s = "hello";
bool b1 = check6(s);    // check6(s) calls check_size(s, 6)

bind函数可以调整给定可调用对象中的参数顺序。

1
2
3
4
// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);
// sort on word length, longest to shortest
sort(words.begin(), words.end(), bind(isShorter, _2, _1));

这段代码演示了如何使用 C++ 的 sort 算法对一个字符串向量 words 进行排序，以字符串的长度作为排序的标准。然而，这里使用了两种不同的排序方式，并且利用了函数对象和函数适配器。让我们逐步解释：

  1. sort(words.begin(), words.end(), isShorter);： 这行代码使用了 sort 算法来对字符串向量 words 进行排序。words.begin() 和 words.end() 指定了排序的范围，即从 words 的起始位置到末尾位置。排序的方式由第三个参数 isShorter 指定。这里 isShorter 是一个自定义的函数对象，它定义了字符串长度的比较规则，即按照字符串长度从短到长的顺序进行排序。

  2. sort(words.begin(), words.end(), bind(isShorter, _2, _1));： 这行代码也使用了 sort 算法来对字符串向量 words 进行排序。words.begin() 和 words.end() 仍然指定了排序的范围。不同之处在于第三个参数，这里使用了 bind 函数适配器。bind 函数适配器可以用来修改函数的参数顺序。在这里，bind(isShorter, _2, _1) 将 isShorter 函数对象的参数顺序进行了调换。具体来说，它将 isShorter 的第一个参数 _1 绑定到了 isShorter 的第二个参数，将 isShorter 的第二个参数 _2 绑定到了 isShorter 的第一个参数。这意味着排序将按照字符串长度从长到短的顺序进行，因为在比较时，先比较的是第二个字符串的长度（即 _2），再比较第一个字符串的长度（即 _1）。

综上所述，这段代码展示了如何使用不同的比较函数对象来对字符串向量进行排序，并且展示了如何使用 bind 函数适配器来修改函数的参数顺序。

默认情况下，bind函数的非占位符参数被拷贝到bind返回的可调用对象中。但有些类型不支持拷贝操作。

如果希望传递给bind一个对象而又不拷贝它，则必须使用标准库的ref函数。ref函数返回一个对象，包含给定的引用，此对象是可以拷贝的。cref函数生成保存const引用的类。

1
2
ostream &print(ostream &os, const string &s, char c);
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

这段代码使用了 for_each 算法，结合 bind 函数适配器，来对字符串向量 words 中的每个字符串调用 print 函数进行处理。让我们逐步解释：

  1. ostream &print(ostream &os, const string &s, char c);： 这是一个名为 print 的函数声明，它接受一个输出流 os、一个字符串 s 和一个字符 c 作为参数，并返回一个输出流引用。这个函数的功能可能是将字符串 s 输出到输出流 os 中，并在其末尾添加字符 c。

  2. for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));： 这行代码使用了 for_each 算法，它遍历了字符串向量 words 中的每个字符串，并对每个字符串调用 print 函数进行处理。在这里，bind 函数适配器用来绑定 print 函数的参数。具体来说：

    • words.begin() 和 words.end() 指定了需要遍历的范围，即从 words 的起始位置到末尾位置。

    • bind(print, ref(os), _1, ' ') 将 print 函数与参数绑定，创建了一个函数对象。这里：

      • print 是要绑定的函数。
      • ref(os) 用来将输出流 os 以引用的方式传递给 print 函数，因为通常输出流需要以引用方式传递。
      • _1 是一个占位符，表示绑定的函数对象将接受一个参数，该参数将在调用时传递给 print 函数的第二个参数 s。_1 与 for_each 算法中遍历的每个字符串 s 相对应。
      • ' ' 是要绑定的函数对象的最后一个参数，表示将空格字符添加到每个字符串的末尾。

    因此，for_each 算法会遍历 words 中的每个字符串，并对每个字符串调用 print 函数，将其输出到输出流 os 中，并在末尾添加一个空格字符。

综上所述，这段代码展示了如何使用 for_each 算法和 bind 函数适配器来对字符串向量中的每个元素调用自定义函数进行处理，并根据需要绑定函数的参数。

再探迭代器（Revisiting Iterators）

除了为每种容器定义的迭代器之外，标准库还在头文件iterator中定义了另外几种迭代器。

  • 插入迭代器（insert iterator）：该类型迭代器被绑定到容器对象上，可用来向容器中插入元素。
  • 流迭代器（stream iterator）：该类型迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流。
  • 反向迭代器（reverse iterator）：该类型迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
  • 移动迭代器（move iterator）：该类型迭代器用来移动容器元素。

插入迭代器（Insert Iterators）

插入器是一种迭代器适配器，它接受一个容器参数，生成一个插入迭代器。通过插入迭代器赋值时，该迭代器调用容器操作向给定容器的指定位置插入一个元素。

插入器有三种类型，区别在于元素插入的位置：

  • back_inserter：创建一个调用push_back操作的迭代器。
  • front_inserter：创建一个调用push_front操作的迭代器。
  • inserter：创建一个调用insert操作的迭代器。此函数接受第二个参数，该参数必须是一个指向给定容器的迭代器，元素会被插入到该参数指向的元素之前。
1
2
3
4
5
6
list<int> lst = { 1,2,3,4 };
list<int> lst2, lst3;   // empty lists
// after copy completes, lst2 contains 4 3 2 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
// after copy completes, lst3 contains 1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

这段代码使用了STL算法 copy 以及插入迭代器 front_inserter 和 inserter 来将一个列表 lst 中的元素复制到另外两个列表 lst2 和 lst3 中。让我们逐步解释这段代码的功能：

  1. list<int> lst = { 1,2,3,4 };： 这行代码创建了一个名为 lst 的列表，并初始化它为包含 1、2、3、4 这四个整数的列表。

  2. list<int> lst2, lst3;： 这行代码创建了两个名为 lst2 和 lst3 的空列表。

  3. copy(lst.cbegin(), lst.cend(), front_inserter(lst2));： 这行代码使用 copy 算法，将列表 lst 中的元素复制到列表 lst2 中。front_inserter(lst2) 是一个插入迭代器，它会将复制的元素插入到目标列表 lst2 的前面。因此，复制完成后，lst2 中的元素顺序是 4、3、2、1。

  4. copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));： 这行代码也使用 copy 算法，将列表 lst 中的元素复制到列表 lst3 中。inserter(lst3, lst3.begin()) 是另一种插入迭代器，它会将复制的元素插入到目标列表 lst3 中的指定位置，即 lst3.begin() 所指示的位置。由于是从列表的开始处插入，因此复制完成后，lst3 中的元素顺序是 1、2、3、4。

综上所述，这段代码展示了如何使用插入迭代器 front_inserter 和 inserter 将列表中的元素复制到另一个列表中，并控制复制后元素在目标列表中的顺序。

iostream迭代器（iostream Iterators）

istream_iterator从输入流读取数据，ostream_iterator向输出流写入数据。这些迭代器将流当作特定类型的元素序列处理。

创建流迭代器时，必须指定迭代器读写的对象类型。istream_iterator使用>>来读取流，因此istream_iterator要读取的类型必须定义了>>运算符。创建istream_iterator时，可以将其绑定到一个流。如果默认初始化，则创建的是尾后迭代器。

iostream迭代器（iostream Iterators）

istream_iterator从输入流读取数据，ostream_iterator向输出流写入数据。这些迭代器将流当作特定类型的元素序列处理。

创建流迭代器时，必须指定迭代器读写的对象类型。istream_iterator使用>>来读取流，因此istream_iterator要读取的类型必须定义了>>运算符。创建istream_iterator时，可以将其绑定到一个流。如果默认初始化，则创建的是尾后迭代器。

这段代码涉及到了 C++ 中的输入流迭代器 istream_iterator 的使用，以及如何从不同的输入源（标准输入流 cin 和文件流 ifstream）中读取数据。让我们一步步来解释：

  1. istream_iterator<int> int_it(cin);： 这行代码创建了一个名为 int_it 的 istream_iterator 对象，它被初始化为从标准输入流 cin 中读取整数。这意味着它将从标准输入中读取用户输入的整数数据，并将其作为迭代器进行处理。

  2. istream_iterator<int> int_eof;： 这行代码创建了一个名为 int_eof 的 istream_iterator 对象，它被初始化为默认的“结束迭代器”值。结束迭代器用于指示输入流的末尾，通常用于在循环中检查迭代器是否已经到达了流的末尾。

  3. ifstream in("afile");： 这行代码创建了一个名为 in 的文件流对象，并打开了名为 "afile" 的文件。ifstream 类是 C++ 中用于从文件中读取数据的输入流类。

  4. istream_iterator<string> str_it(in);： 这行代码创建了一个名为 str_it 的 istream_iterator 对象，它被初始化为从文件流 in 中读取字符串。这意味着它将从文件 "afile" 中读取字符串数据，并将其作为迭代器进行处理。

综上所述，这段代码展示了如何使用 istream_iterator 类从标准输入流和文件流中读取数据，并将其用作迭代器以便于在程序中进行处理。

对于一个绑定到流的迭代器，一旦其关联的流遇到文件尾或IO错误，迭代器的值就与尾后迭代器相等。

1
2
3
4
5
6
istream_iterator<int> in_iter(cin);     // read ints from cin
istream_iterator<int> eof;      // istream ''end'' iterator
while (in_iter != eof)      // while there's valid input to read
    // postfix increment reads the stream and returns the old value of the iterator
    // we dereference that iterator to get the previous value read from the stream
    vec.push_back(*in_iter++);

这段代码使用了输入流迭代器 istream_iterator 从标准输入流 cin 中读取整数，并将其存储到一个向量 vec 中。让我逐步解释：

  1. istream_iterator<int> in_iter(cin);： 这行代码创建了一个名为 in_iter 的 istream_iterator 对象，它被初始化为从标准输入流 cin 中读取整数。这意味着 in_iter 将从标准输入中读取用户输入的整数数据，并将其作为迭代器进行处理。

  2. istream_iterator<int> eof;： 这行代码创建了一个名为 eof 的 istream_iterator 对象。在这种情况下，没有提供流作为参数，因此 eof 被初始化为默认的“结束迭代器”值。结束迭代器用于指示输入流的末尾，通常用于在循环中检查迭代器是否已经到达了流的末尾。

  3. while (in_iter != eof)： 这是一个 while 循环，它的条件是迭代器 in_iter 不等于结束迭代器 eof。这个条件保证了只要输入流中还有有效的输入，就会继续执行循环。

  4. vec.push_back(*in_iter++);： 在循环体内部，这行代码执行了以下操作：

    • *in_iter 解引用迭代器 in_iter，获取迭代器当前指向的元素（即从输入流读取的整数）。

    • vec.push_back(...) 将解引用后的值添加到向量 vec 的末尾。

    • in_iter++ 是迭代器的后置递增操作符，它将迭代器向前移动一个位置，指向下一个输入流中的元素。注意，这里是后置递增，因此 *in_iter 返回的是旧的迭代器指向的元素，然后迭代器再自增，指向下一个位置。

综上所述，这段代码会持续从标准输入流中读取整数，直到输入流中没有更多的有效数据为止，然后将读取的整数存储到向量 vec 中。

可以直接使用流迭代器构造容器。

1
2
istream_iterator<int> in_iter(cin), eof;    // read ints from cin
vector<int> vec(in_iter, eof);      // construct vec from an iterator range

  1. istream_iterator<int> in_iter(cin), eof;： 这行代码创建了两个 istream_iterator 对象。第一个对象是 in_iter，它被初始化为从标准输入流 cin 中读取整数。第二个对象是 eof，它是一个默认构造的 istream_iterator，没有指定输入流作为参数。因此，eof 被初始化为默认的“结束迭代器”值。结束迭代器用于指示输入流的末尾，通常用于在循环中检查迭代器是否已经到达了流的末尾。

  2. vector<int> vec(in_iter, eof);： 这行代码创建了一个名为 vec 的向量，并通过迭代器范围构造函数来初始化它。这个范围从 in_iter 到 eof，即从标准输入流中读取的整数序列的起始迭代器到结束迭代器。向量 vec 会包含从输入流中读取的所有整数。

综上所述，这段代码的作用是从标准输入流 cin 中读取整数，然后将这些整数存储到向量 vec 中。

将istream_iterator绑定到一个流时，标准库并不保证迭代器立即从流读取数据。但可以保证在第一次解引用迭代器之前，从流中读取数据的操作已经完成了。

定义ostream_iterator对象时，必须将其绑定到一个指定的流。不允许定义空的或者表示尾后位置的ostream_iterator。

*和++运算符实际上不会对ostream_iterator对象做任何操作。但是建议代码写法与其他迭代器保持一致。

1
2
3
4
ostream_iterator<int> out_iter(cout, " ");
for (auto e : vec)
    *out_iter++ = e;    // the assignment writes this element to cout
cout << endl;

可以为任何定义了<<运算符的类型创建istream_iterator对象，为定义了>>运算符的类型创建ostream_iterator对象。

反向迭代器（Reverse Iterators）

递增反向迭代器会移动到前一个元素，递减会移动到后一个元素。

1
2
3
sort(vec.begin(), vec.end());   // sorts vec in "normal" order
// sorts in reverse: puts the smallest element at the end of vec
sort(vec.rbegin(), vec.rend());

不能从forward_list或流迭代器创建反向迭代器。

调用反向迭代器的base函数可以获得其对应的普通迭代器。

1
2
3
4
5
6
// find the last element in a comma-separated list
auto rcomma = find(line.crbegin(), line.crend(), ',');
// WRONG: will generate the word in reverse order
cout << string(line.crbegin(), rcomma) << endl;
// ok: get a forward iterator and read to the end of line
cout << string(rcomma.base(), line.cend()) << endl;

反向迭代器的目的是表示元素范围，而这些范围是不对称的。用普通迭代器初始化反向迭代器，或者给反向迭代器赋值时，结果迭代器与原迭代器指向的并不是相同元素。

这段代码是在处理一个逗号分隔的字符串时，使用了反向迭代器来找到最后一个逗号，并根据其位置来拆分字符串。让我们逐步解释代码的功能：

  1. auto rcomma = find(line.crbegin(), line.crend(), ',');： 这行代码使用了 find 算法，通过反向迭代器在字符串 line 中查找最后一个逗号的位置。line.crbegin() 返回 line 字符串的反向起始迭代器，而 line.crend() 返回 line 字符串的反向结束迭代器。这样，find 将从字符串的末尾开始搜索，直到找到第一个逗号。

  2. cout << string(line.crbegin(), rcomma) << endl;： 这行代码尝试使用从字符串末尾到最后一个逗号之间的字符来构造一个新的字符串。但是，它使用了 string 构造函数，将反向迭代器作为参数传递，这会导致构造的字符串是反向的，即以逆序的方式输出。

  3. cout << string(rcomma.base(), line.cend()) << endl;： 这行代码则采取了不同的方法。它使用了 base() 函数来获取反向迭代器的正向迭代器，然后使用这两个正向迭代器来构造一个新的字符串，从逗号的下一个位置直到字符串的末尾。因此，它能够正确地输出从逗号后面到字符串末尾的内容。

综上所述，第二行代码由于使用了反向迭代器构造字符串，导致了字符串逆序输出的问题，而第三行代码则通过转换为正向迭代器来解决了这个问题，正确地输出了所需的字符串片段。

泛型算法结构（Structure of Generic Algorithms）

五类迭代器（The Five Iterator Categories）

C++标准指定了泛型和数值算法的每个迭代器参数的最小类别。对于迭代器实参来说，其能力必须大于或等于规定的最小类别。向算法传递更低级的迭代器参数会产生错误（大部分编译器不会提示错误）。

迭代器类别：

  • 输入迭代器（input iterator）：可以读取序列中的元素，只能用于单遍扫描算法。必须支持以下操作：
    • 用于比较两个迭代器相等性的相等==和不等运算符!=。
    • 用于推进迭代器位置的前置和后置递增运算符++。
    • 用于读取元素的解引用运算符*；解引用只能出现在赋值运算符右侧。
    • 用于读取元素的箭头运算符->。
  • 输出迭代器（output iterator）：可以读写序列中的元素，只能用于单遍扫描算法，通常指向目的位置。必须支持以下操作：
    • 用于推进迭代器位置的前置和后置递增运算符++。
    • 用于读取元素的解引用运算符*；解引用只能出现在赋值运算符左侧（向已经解引用的输出迭代器赋值，等价于将值写入其指向的元素）。
  • 前向迭代器（forward iterator）：可以读写序列中的元素。只能在序列中沿一个方向移动。支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。因此可以使用前向迭代器对序列进行多遍扫描。
  • 双向迭代器（bidirectional iterator）：可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外，还支持前置和后置递减运算符--。除forward_list之外的其他标准库容器都提供符合双向迭代器要求的迭代器。
  • 随机访问迭代器（random-access iterator）：可以在常量时间内访问序列中的任何元素。除了支持所有双向迭代器的操作之外，还必须支持以下操作：
    • 用于比较两个迭代器相对位置的关系运算符<、<=、>、>=。
    • 迭代器和一个整数值的加减法运算+、+=、-、-=，计算结果是迭代器在序列中前进或后退给定整数个元素后的位置。
    • 用于两个迭代器上的减法运算符-，计算得到两个迭代器的距离。
    • 下标运算符[]。

算法形参模式（Algorithm Parameter Patterns）

大多数算法的形参模式是以下四种形式之一：

1
2
3
4
alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);

这个描述指的是STL（标准模板库）中的算法通常采用的四种参数模式。让我们逐一解释这些参数模式：

  1. alg(beg, end, other args);： 这种模式是最常见的，其中 alg 是算法的名称，beg 和 end 表示一个范围，通常是指定容器的起始迭代器和结束迭代器。算法将在此范围内操作。other args 表示其他可能需要传递给算法的参数。

  2. alg(beg, end, dest, other args);： 在这种情况下，除了传递输入范围的起始和结束迭代器外，还传递了目标容器的起始迭代器 dest。算法将结果存储到目标容器中，而不是修改输入范围。other args 表示其他可能需要传递给算法的参数。

  3. alg(beg, end, beg2, other args);： 在这种情况下，除了传递了输入范围的起始和结束迭代器外，还传递了第二个范围的起始迭代器 beg2。某些算法需要使用两个范围进行操作，例如合并两个有序序列。other args 表示其他可能需要传递给算法的参数。

  4. alg(beg, end, beg2, end2, other args);： 这种模式类似于第三种模式，不同之处在于它还传递了第二个范围的结束迭代器 end2。这种模式通常用于需要操作两个范围的算法，例如交集、并集等。other args 表示其他可能需要传递给算法的参数。

这些参数模式提供了一种通用的方式来在STL中调用算法，并且能够适应不同的情况和需求。

算法命名规范（Algorithm Naming Conventions）

接受谓词参数的算法都有附加的_if后缀。

1
2
find(beg, end, val);       // find the first instance of val in the input range
find_if(beg, end, pred);   // find the first instance for which pred is true

将执行结果写入额外目的空间的算法都有_copy后缀。

1
2
reverse(beg, end);              // reverse the elements in the input range
reverse_copy(beg, end, dest);   // copy elements in reverse order into dest

一些算法同时提供_copy和_if版本。

特定容器算法（Container-Specific Algorithms）

对于list和forward_list类型，应该优先使用成员函数版本的算法，而非通用算法。

链表特有版本的算法操作会改变底层容器。

Cpp-Primer-5th-Notes-CN/Chapter-10 Generic Algorithms at master · czs108/Cpp-Primer-5th-Notes-CN (github.com)