第十章 泛型算法

泛型算法

• 因为它们实现共同的操作，所以称之为“算法”；而“泛型”、指的是它们可以操作在多种容器类型上。
• 泛型算法本身不执行容器操作，只是单独依赖迭代器和迭代器操作实现。
• 头文件： #include <algorithm>或者 #include <numeric>(算数相关)
• 大多数算法是通过遍历两个迭代器标记的一段元素来实现其功能。

• 必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但不能直接添加或者删除元素。

  find

• vector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value);

• 输入：两个标记范围的迭代器和目标查找值。返回：如果找到，返回对应的迭代器，否则返回第二个参数，即标记结尾的迭代器。

  初识泛型算法

• 标准库提供了超过100个算法，但这些算法有一致的结构。

• 理解算法的最基本的方法是了解它们是否读取元素、改变元素、重排元素顺序。

  只读算法

• 只读取范围中的元素，不改变元素。

• 如 find和 accumulate（在numeric中定义，求和）。
• find_first_of，输入：两对迭代器标记两段范围，在第一段中找第二段中任意元素，返回第一个匹配的元素，找不到返回第一段的end迭代器。
• 通常最好使用cbegin和cend。

• equal：确定两个序列是否保存相同的值。

  写容器元素的算法

• 一些算法将新值赋予序列中的元素。

• 算法不检查写操作。
• 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时必须保证目标目的序列至少要包含与输入序列一样多的元素。

  重排容器元素的算法

• 这些算法会重排容器中元素的顺序。

• 排序算法sort：
  • 接受两个迭代器，表示要排序的元素范围。

• 消除重复unique：

  • 之前要先调用sort
  • 返回的迭代器指向最后一个不重复元素之后的位置。
  • 顺序会变，重复的元素被“删除”。
  • 并没有真正删除，真正删除必须使用容器操作。

    定制操作

    向算法传递函数：

• 谓词（predicate）：

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

• 例子：

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

      lambda表达式

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

• lambda表达式表示一个可调用的代码单元，可以理解成是一个未命名的内联函数。
  
• 形式：[capture list](parameter list) -> return type {function body}。
  • 其中capture list捕获列表是一个lambda所在函数定义的局部变量的列表（通常为空）。不可忽略。
  • return type是返回类型。可忽略。
  • parameter是参数列表。可忽略。
  • function body是函数体。不可忽略。
  • auto f = [] {return 42;}

• 例子：

  • 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 << " ";})

      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捕获列表：

参数绑定

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

• 标准库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函数。

    再探迭代器

    插入迭代器

• 插入器是一种迭代器适配器，接受一个容器，生成一个迭代器，能实现向给定容器添加元素。

• 三种类型：
  • back_inserter：创建一个使用push_back的迭代器。
  • front_inserter创建一个使用push_front的迭代器。
  • inserter创建一个使用insert的迭代器。接受第二个参数，即一个指向给定容器的迭代器，元素会被查到迭代器所指向的元素之前。

插入迭代器操作：

iostream迭代器

• 迭代器可与输入或输出流绑定在一起，用于迭代遍历所关联的 IO 流。
• 通过使用流迭代器，我们可以用泛型算法从流对象中读取数据以及向其写入数据。

istream_iterator的操作：

ostream_iterator的操作：

反向迭代器

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

  泛型算法结构

  5类迭代器

  | 迭代器类别 | 解释 | 支持的操作 | | —- | —- | —- | | 输入迭代器 | 只读，不写；单遍扫描，只能递增 | ==,!=,++,*,-> | | 输出迭代器 | 只写，不读；单遍扫描，只能递增 | ++,* | | 前向迭代器 | 可读写；多遍扫描，只能递增 | ==,!=,++,*,-> | | 双向迭代器 | 可读写；多遍扫描，可递增递减 | ==,!=,++,--,*,-> | | 随机访问迭代器 | 可读写，多遍扫描，支持全部迭代器运算 | ==,!=,<,<=,>,>=,++,--,+,+=,-,-=,*,->,iter[n]==*(iter[n]) |

算法的形参模式

• 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都是迭代器参数，是否使用要依赖于执行的操作。

算法命名规范

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

• 区分拷贝元素的版本和不拷贝的版本：拷贝版本通常加_copy。

  特定容器算法

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

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

• 上面的操作都返回void

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

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