• 因为它们实现共同的操作，所以称之为“算法”；而“泛型”、指的是它们可以操作在多种容器类型上。
• 泛型算法本身不执行容器操作，只是单独依赖迭代器和迭代器操作实现。
• 头文件： #include <algorithm>或者 #include <numeric>(算数相关)
• 大多数算法是通过遍历两个迭代器标记的一段元素来实现其功能。
• 必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但不能直接添加或者删除元素。

一、find

• vector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value);
• 输入：两个标记范围的迭代器和目标查找值。返回：如果找到，返回对应的迭代器，否则返回第二个参数，即标记结尾的迭代器。

二、初识泛型算法

• 标准库提供了超过100个算法，但这些算法有一致的结构。
• 理解算法的最基本的方法是了解它们是否读取元素、改变元素、重排元素顺序。

1、只读算法

• 只读取范围中的元素，不改变元素。
• 如 find和 accumulate（在numeric中定义，求和）。
• find_first_of，输入：两对迭代器标记两段范围，在第一段中找第二段中任意元素，返回第一个匹配的元素，找不到返回第一段的end迭代器。
• 通常最好使用cbegin和cend。
• equal：确定两个序列是否保存相同的值。

2、写容器元素的算法

• 一些算法将新值赋予序列中的元素。
• 算法不检查写操作。
• fill： fill(vec.begin(), vec.end(), 0); 将每个元素重置为0
• fill_n： fill_n(vec.begin(), 10, 0);
• 插入迭代器back_inserter：
  • 用来确保算法有足够的空间存储数据。
  • #include <iterator>
  • back_inserter(vec)
• 拷贝算法copy：
• 输入：前两个参数指定输入范围，第三个指向目标序列。
• copy (ilst.begin(), ilst.end(), back_inserter(ivec));
• copy时必须保证目标目的序列至少要包含与输入序列一样多的元素。

3、重排容器元素的算法

• 这些算法会重排容器中元素的顺序。
• 排序算法sort：
  • 接受两个迭代器，表示要排序的元素范围。
• 消除重复unique：
  • 之前要先调用sort
  • 返回的迭代器指向最后一个不重复元素之后的位置。
  • 顺序会变，重复的元素被“删除”。
  • 并没有真正删除，真正删除必须使用容器操作。

三、定制操作

1、向算法传递函数：

• 谓词（predicate）：

  • 是一个可调用的表达式，返回结果是一个能用作条件的值
  • 一元谓词：接受一个参数
  • 二元谓词：接受两个参数

• 例子：

  • stable_sort：
    • 保留相等元素的原始相对位置。
    • stable_sort(words.begin(), words.end(), isShorter);

2、lambda表达式

2.1 可调用对象

可调用==对象==：==对象==或一个==表达式==，如果可以对其使用调用运算符则称它为可调用的。

• 函数
• 函数指针
• 重载了函数调用运算符的类
• Lambda表达式

2.2 lambda表达式

有时可能希望操作可以接受更多的参数。

Lambda表达式主要解决了以下两个技术问题：

1. 匿名函数的问题：传统C++语言中，如果要使用一个函数对象，必须定义一个具名的函数对象或使用函数指针，这会导致代码冗长，不便于代码重构和维护。Lambda表达式可以直接定义匿名的函数对象，方便代码编写。
2. 捕获变量的问题：Lambda表达式可以在定义时捕获外部变量，并在表达式中使用，这种方式解决了函数对象使用外部变量时需要定义多个函数对象的问题。同时Lambda表达式提供了捕获变量的多种方式，如值捕获、引用捕获和引用捕获并修改等，方便了变量的使用和修改。

• lambda表达式表示一个可调用的代码单元，可以理解成是一个未命名的内联函数。 形式

1

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

• 其中capture list捕获列表是一个lambda所在函数定义的局部变量的列表（通常为空）。不可忽略。
• return type是返回类型。可忽略。
• parameter是参数列表。可忽略。
• function body是函数体。不可忽略。
• auto f = [] {return 42;}

与函数的差别

• 必须使用尾置类型来表示返回类型
• 可以忽略返回类型。默认情况下，如果一个Lambda体内含有return之外的任何语句，则编译器假定Lambda返回void。但是与函数不同，返回void的lambda不能返回值
• 不能有默认参数

例子

• find_if:
  • 接受一对表示范围的迭代器和一个谓词，用来查找第一个满足特定要求的元素。返回第一个使谓词返回非0值的元素。
  • auto wc = find_if(words.begin(), words.end(), [sz](const string &a){return a.size() >= sz;});
• for_each：
  • 接受一个可调用对象，并对序列中每个元素调用此对象。
  • for_each(wc, words.end(), [](const string &s){cout << s << " ";})

3、lambda捕获和返回

• 定义lambda时会生成一个新的类类型和该类型的一个对象。
• 默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员，在lambda对象创建时被初始化。
• 值捕获：前提是变量可以拷贝，size_t v1 = 42; auto f = [v1] {return v1;};。
• 引用捕获：必须保证在lambda执行时，变量是存在的，auto f2 = [&v1] {return v1;};
• 尽量减少捕获的数据量，尽可能避免捕获指针或引用。
• 隐式捕获：让编译器推断捕获列表，在捕获列表中写一个&（引用方式）或=（值方式）。auto f3 = [=] {return v1;}
• 可变Lambda: 改变值捕获的变量 :

1

size_t v1 = 42; auto f=[v1]()mutable{return ++v1};  v1=0; auto j=f(); // j=43

• 改变引用捕获变量 : 取决于引用指向的是一个const or not

lambda捕获列表：

4、参数绑定

• lambda表达式更适合在一两个地方使用的简单操作。
• 如果是很多地方使用相同的操作，还是需要定义函数。
• 函数如何包装成一元谓词？使用参数绑定。

bind参数绑定是解决回调函数传递参数问题的一种技术手段。 在C++中，回调函数是指在某个函数中传入另一个函数的指针，以便在主函数中调用。通常情况下，回调函数需要传递一些参数才能完成其功能。在调用时，需要在主函数中手动传递这些参数，这样就会导致代码冗长、可读性差、维护困难等问题。 使用bind参数绑定，可以将回调函数中需要传递的参数提前绑定，形成一个新的函数对象，这个函数对象可以像回调函数一样在主函数中使用，但不再需要手动传递参数。这样就可以大大简化代码，提高代码可读性和可维护性。

例如，假设有一个回调函数func，需要传递两个参数a和b，在主函数中使用时，可以使用bind绑定这两个参数：

1
2
3
4
5
6
7

int add(int x, int y) {
    return x + y;
}
auto add10 = std::bind(add, 10, std::placeholders::_1);

std::cout << add10(5) << std::endl; // 输出 15
std::cout << add10(7) << std::endl; // 输出 17

标准库bind函数

• 定义在头文件functional中，可以看做为一个通用的函数适配器。
• auto newCallable = bind(callable, arg_list);
• 我们再调用newCallable的时候，newCallable会调用callable并传递给它arg_list中的参数。
• _n代表第n个位置的参数。定义在placeholders的命名空间中。using std::placeholder::_1;
• auto g = bind(f, a, b, _2, c, _1);，调用g(_1, _2)实际上调用f(a, b, _2, c, _1)
• 非占位符的参数要使用引用传参，必须使用标准库ref函数或者cref函数。

在这个例子中，我们使用std::bind将add函数的第一个参数绑定为10，并将第二个参数留空，即使用占位符std::placeholders::_1表示。这样，我们得到了一个新的函数add10，它只需要一个参数（y），它将x固定为10，因此在调用add10时，只需要传递另一个参数即可。

bind绑定参数的例子 假设我们有一个函数printNumAndString，需要同时输出一个整数和一个字符串，代码如下：

1
2
3
4

void printNumAndString(int num, const std::string& str)
{
    std::cout << num << ": " << str << std::endl;
}

现在我们有一个数组nums和一个字符串str，我们希望将printNumAndString应用于数组nums的所有元素和字符串str，使用for循环可以实现：

1
2
3
4
5

int nums[] = {1, 2, 3, 4, 5};
std::string str = "hello";
for (int i = 0; i < 5; i++) {
    printNumAndString(nums[i], str);
}

但是如果我们想要使用STL算法std::for_each来完成这个任务呢？在std::for_each中，我们可以指定一个可调用对象，它将应用于容器中的所有元素。在这个例子中，我们可以这样做：

1
2
3

int nums[] = {1, 2, 3, 4, 5};
std::string str = "hello";
std::for_each(std::begin(nums), std::end(nums), [=](int num) { printNumAndString(num, str); });

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

//编译器生成的代码
#include <iostream>
#include <algorithm>
using namespace std;
void printNumAndString(int num, const std::basic_string<char> & str)
{
  std::operator<<(std::operator<<(std::cout.operator<<(num), ": "), str).operator<<(std::endl);
}

int main()
{
  int nums[5] = {1, 2, 3, 4, 5};
  std::basic_string<char> str = std::basic_string<char>(std::basic_string<char>("hello", std::allocator<char>()));
  //这个表达式是一个Lambda表达式生成的闭包对象（closure object）的类型名称，其中`__lambda_12_49`是一个自动生成的类名，用于标识这个Lambda表达式的类型，而后面的`{str}`则是Lambda表达式的参数列表，表示捕获了一个名为`str`的变量。在C++中，Lambda表达式的类型是一个未命名的闭包类（closure class），它会根据Lambda表达式的内容和上下文自动创建，其中捕获的变量会作为类的成员变量，Lambda表达式的函数体则会转化为类的一个成员函数。在使用Lambda表达式时，编译器会自动生成一个闭包对象，其类型就是Lambda表达式的类型，这个闭包对象可以像普通函数一样被调用和使用。在这个例子中，`__lambda_12_49`就是自动生成的闭包类的类型名称，其中的`{str}`表示捕获了一个名为`str`的变量。
  class __lambda_12_49
  {
    public: 
    inline void operator()(int num) const
    {
      printNumAndString(num, str);
    }
    
    private: 
    std::basic_string<char> str;
    public: 
    // inline __lambda_12_49(__lambda_12_49 &&) noexcept = default;
    // inline __lambda_12_49 & operator=(const __lambda_12_49 &) /* noexcept */ = delete;
    __lambda_12_49(const std::basic_string<char> & _str)
    : str{_str}
    {}
    
  };
  
  std::for_each(std::begin(nums), std::end(nums), __lambda_12_49(__lambda_12_49{str}));
  return 0;
}
//在这个lambda表达式中，只捕获了`str`而没有捕获`nums`数组的原因是，lambda表达式中使用的`nums`数组是通过迭代器传递给`std::for_each`算法的，而不是直接作为lambda表达式的捕获变量。当lambda表达式使用`std::for_each`算法时，迭代器会逐一遍历数组中的元素，并将每个元素作为lambda表达式的参数进行调用，因此不需要在lambda表达式中捕获`nums`数组。而对于`str`变量，由于lambda表达式中调用了`printNumAndString`函数，需要将其作为参数传递给函数，因此需要捕获它。

在这个例子中，我们使用lambda表达式来定义一个可调用对象，它将接受一个整数作为参数，并调用printNumAndString函数来打印整数和字符串。但是在调用printNumAndString函数时，我们需要传递两个参数，而不是一个整数。这时候，我们可以使用std::bind函数来绑定第二个参数：

1
2
3

int nums[] = {1, 2, 3, 4, 5};
std::string str = "hello";
std::for_each(std::begin(nums), std::end(nums), std::bind(printNumAndString, std::placeholders::_1, str));

在这个例子中，我们使用std::bind函数来绑定第二个参数str，并使用std::placeholders::_1来表示第一个参数num。现在我们可以将std::bind返回的可调用对象传递给std::for_each，它将在容器的每个元素上调用该对象，而不必手动绑定第二个参数。

四、再探迭代器

1、插入迭代器

• 插入器是一种迭代器适配器，接受一个容器，生成一个迭代器，能实现向给定容器添加元素。
• 三种类型：
  • back_inserter：创建一个使用push_back的迭代器。
  • front_inserter：创建一个使用push_front的迭代器。
  • inserter创建一个使用insert的迭代器。接受第二个参数，即一个指向给定容器的迭代器，元素会被查到迭代器所指向的元素之前。

插入迭代器操作：

插入迭代器是 C++ STL 中的一种迭代器，它可以用来将元素插入到容器中。和普通迭代器一样，它也支持迭代器操作，如 ++、* 等。但是它有一个特殊的地方，它不是指向某个容器的迭代器，而是一个模板类，通过模板参数来指定要插入的容器类型。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <vector>
#include <iterator> // 包含插入迭代器头文件

int main() {
    std::vector<int> v1{1, 2, 3, 4};
    std::vector<int> v2{5, 6, 7, 8};

    // 创建插入迭代器，将元素插入到 v1 的末尾
    std::back_insert_iterator<std::vector<int>> inserter(v1);

    // 将 v2 中的元素插入到 v1 中
    std::copy(v2.begin(), v2.end(), inserter);

    // 输出 v1 中的元素
    for (const auto& elem : v1) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

2、iostream迭代器

C++中的iostream迭代器可以将输入输出流转换为迭代器，使得可以像操作容器迭代器一样操作输入输出流。 使用iostream迭代器需要包含头文件<iterator>和<iostream>。

• 流迭代器将它们对应的流当做一个特定类型的元素序列来处理通过使用流迭代器，我们可以用泛型算法对流对象读取数据以及向其写入数据。
• 迭代器可与输入或输出流绑定在一起，用于迭代遍历所关联的 IO 流。
• 通过使用流迭代器，我们可以用泛型算法从流对象中读取数据以及向其写入数据。

istream_iterator的操作：

1
2

istream_iterator<int> in(cin) ,eof;
cout << accumulate(in,eof,0)<<endl;

ostream_iterator的操作：

1
2
3
4
5
6

ostream_iterator<int> out_iter(cout," ");
for(auto e:vec)
{
	*out_iter++=e; //等价写法：out_iter=e;
}
cout<<endl;

下面是一些使用iostream迭代器的例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

//1.  从标准输入流中读取数据到容器中：
#include <iostream>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> v;
    std::copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(v));
    return 0;
}

这个例子中，std::istream_iterator<int>(std::cin)创建了一个输入流迭代器，表示从标准输入流中读取int类型的数据，std::istream_iterator<int>()创建了一个默认的输入流迭代器，表示输入流的结束。std::copy算法使用输入流迭代器和输出迭代器将数据从输入流复制到容器中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

//2.  将容器中的数据输出到标准输出流中：
#include <iostream>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> v {1, 2, 3, 4, 5};
    std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout, " "));
    return 0;
}

这个例子中，std::ostream_iterator<int>(std::cout, " ")创建了一个输出流迭代器，表示将int类型的数据输出到标准输出流中，每个数据之间用空格隔开。std::copy算法使用输入迭代器和输出流迭代器将数据从容器输出到标准输出流中。

3、反向迭代器

反向迭代器是一种特殊的迭代器，它可以从容器的末尾向前遍历容器的元素。C++标准库中提供了反向迭代器std::reverse_iterator，可以用来迭代双向迭代器或随机访问迭代器。

• 反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。
• 对于反向迭代器，递增和递减的操作含义会颠倒。
• 实现向后遍历，配合rbegin和rend
• reverse_iterator 的base成员

![[Pasted image 20220516175615.png]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> v {1, 2, 3, 4, 5};
    // 从容器尾部构造一个反向迭代器
    auto rit = v.rbegin();
    // 遍历容器的元素，从尾部开始
    while (rit != v.rend()) {
        std::cout << *rit << " ";
        ++rit;
    }
    std::cout << std::endl;
    // 使用std::for_each算法和反向迭代器遍历容器的元素，从尾部开始
    std::for_each(v.rbegin(), v.rend(), [](int i) { std::cout << i << " "; });
    std::cout << std::endl;
    return 0;
}

这个例子中，我们首先从容器尾部构造了一个反向迭代器，然后使用while循环遍历了容器的元素。在遍历时，我们通过*rit访问反向迭代器指向的元素，同时每次遍历完成后，通过++rit移动迭代器，直到反向迭代器指向容器的开头位置。 另外，我们还使用了std::for_each算法和反向迭代器来遍历容器的元素，从尾部开始。在这个例子中，我们使用了一个lambda表达式来输出遍历到的每个元素。

五、泛型算法结构

1、5类迭代器

2、算法的形参模式

• alg(beg, end, other args);
• alg(beg, end, dest, other args);
• alg(beg, end, beg2, other args);
• alg(beg, end, beg2, end2, other args);

其中，alg是算法名称，beg和end表示算法所操作的输入范围。dest、beg2、end2都是迭代器参数，是否使用要依赖于执行的操作。

3、算法命名规范

• 一些算法使用重载形式传递一个谓词。
• 接受一个元素值的算法通常有一个不同名的版本：加_if，接受一个谓词代替元素值。
• 区分拷贝元素的版本和不拷贝的版本：拷贝版本通常加_copy。

六、特定容器算法

对于list和forward_list，优先使用成员函数版本的算法而不是通用算法。

list和forward_list成员函数版本的算法：

• 上面的操作都返回void

list和forward_list的splice成员函数版本的参数：

• 使用lst.splice(args)或flst.splice_after(args)