第十章 泛型算法

泛型算法

  • 因为它们实现共同的操作，所以称之为“算法”；而“泛型”、指的是它们可以操作在多种容器类型上。
  • 泛型算法本身不执行容器操作，只是单独依赖迭代器和迭代器操作实现。
  • 头文件： #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);这里必须先定义后修改，也就是vec大小必须大于10.

  • 插入迭代器back_inserter：接收一个指向容器的引用，返回一个与容器绑定的插入迭代器。

    • 用来确保算法有足够的空间存储数据。
    • #include <iterator>
    • back_inserter(vec)

  • 拷贝算法copy：

  • 输入：前两个参数指定输入范围，第三个指向目标序列。

  • copy (ilst.begin(), ilst.end(), back_inserter(ivec));将ilst的内容拷贝到ivec中

  • copy时必须保证目标目的序列至少要包含与输入序列一样多的元素。

  • replace(ilst.begin(), ilst.end(), 0, 42);将序列中的所有0都替换为42.

  • replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(vec), 0, 42);

    ilst拷贝到vec中，0都替换为42.

back_inserter 是插入迭代器，在 iterator.h 头文件中，不是标准库的算法。

重排容器元素的算法

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

int fun(...){...}等价于auto fun(...)->int{...}

算法不改变容器大小的原因是什么？

  • 将算法和容器的成员函数区分开。
  • 算法的参数是迭代器，不是容器本身。

定制操作

向算法传递函数：

  • 谓词（predicate）：

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

  • 例子：

    • stable_sort：
      • 保留相等元素的原始相对位置。
      • stable_sort(words.begin(), words.end(), isShorter);需要定义一个bool类型的isshorter函数。
    1
    2
    3
    4
     bool is_shorter(std::string const& lhs, std::string const& rhs)
    {
        return  lhs.size() < rhs.size();
    }

lambda表达式

  • 有时可能希望操作可以接受更多的参数。
  • lambda表达式表示一个可调用的代码单元，可以理解成是一个未命名的内联函数。
  • 形式：[capture list](parameter list) -> return type {function body}。
    • 其中capture list捕获列表是一个lambda所在函数定义的局部变量的列表（通常为空）。不可忽略。
    • return type是返回类型。可忽略。
    • parameter是参数列表。可忽略。
    • function body是函数体。不可忽略。
    • auto f = [] {return 42;}
1
2
auto f = [](int i, int j) { return i + j; };
stable_sort(words.begin(), words.end(), [](const string &a, const string &b) {return a.size() < b.size()});
  • 例子：
    • find_if:
      • 接受一对表示范围的迭代器和一个谓词，用来查找第一个满足特定要求的元素。返回第一个使谓词返回非0值的元素。
      • auto wc = find_if(words.begin(), words.end(), [sz](const string &a){return a.size() >= sz;});查找长度大于等于sz的元素，返回值是一个迭代器
    • for_each：
      • 接受一个可调用对象，并对序列中每个元素调用此对象。
      • for_each(wc, words.end(), [](const string &s){cout << s << " ";})打印wc到words.end()的所有元素

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不能使用所在函数中的变量。一个lambda只有在捕获变量后才能使用它们。
[names] names是一个逗号分隔的名字列表，这些名字都是在lambda所在函数的局部变量，捕获列表中的变量都被拷贝，名字前如果使用了&，则采用引用捕获方式。
[&] 隐式捕获列表，采用引用捕获方式。lambda体中所使用的来自所在函数的实体都采用引用方式使用。
[=] 隐式捕获列表，采用值捕获方式。
[&, identifier_list] identifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。identifier_list中的名字前面不能使用&
[=, identifier_list] identifier_list中的变量采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。identifier_list中的名字不能包括this，且前面必须使用&

参数绑定

  • 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的迭代器，只有容器支持push_back才能用。
    • front_inserter创建一个使用push_front的迭代器，只有容器支持push_front才能用。
    • inserter创建一个使用insert的迭代器。接受第二个参数，即一个指向给定容器的迭代器，元素会被查到迭代器所指向的元素之前。

插入迭代器操作：

操作 解释
it=t 在it指定的当前位置插入值t。假定c是it绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用c.push_back(t)、c.push_front(t)、c.insert(t, p)，其中p是传递给inserter的迭代器位置
*it, ++it, it++ 这些操作虽然存在，但不会对it做任何事情，每个操作都返回it

iostream迭代器

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

istream_iterator的操作：

操作 解释
istream_iterator<T> in(is); in从输入流is读取类型为T的值
istream_iterator<T> end; 读取类型是T的值的istream_iterator迭代器，表示尾后位置
in1 == in2 in1和in2必须读取相同类型。如果他们都是尾后迭代器，或绑定到相同的输入，则两者相等。
in1 != in2 类似上条
*in 返回从流中读取的值
in->mem 与*(in).mem含义相同
++in, in++ 使用元素类型所定义的>>运算符从流中读取下一个值。前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iterator>
using std::string;
int main()
{
    std::ifstream ifs("../data/book.txt");
    std::istream_iterator<string> in(ifs), eof;
    std::vector<string> vec;
    std::copy(in, eof, back_inserter(vec));
    // output
    std::copy(vec.cbegin(), vec.cend(), std::ostream_iterator<string>(std::cout, "\n"));
}

ostream_iterator的操作：

操作 解释
ostream_iterator<T> out(os); out将类型为T的值写到输出流os中
ostream_iterator<T> out(os, d); out将类型为T的值写到输出流os中，每个值后面都输出一个d。d指向一个空字符结尾的字符数组。
out = val 用<<运算符将val写入到out所绑定的ostream中。val的类型必须和out可写的类型兼容。
*out, ++out, out++ 这些运算符是存在的，但不对out做任何事情。每个运算符都返回out。

反向迭代器

  • 反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。
  • 对于反向迭代器，递增和递减的操作含义会颠倒。
  • 实现向后遍历，配合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成员函数版本的算法：

操作 解释
lst.merge(lst2) 将来自lst2的元素合并入lst，二者都必须是有序的，元素将从lst2中删除。
lst.merge(lst2, comp) 同上，给定比较操作。
lst.remove(val) 调用erase删除掉与给定值相等(==)的每个元素
lst.remove_if(pred) 调用erase删除掉令一元谓词为真的每个元素
lst.reverse() 反转lst中元素的顺序
lst.sort() 使用<排序元素
lst.sort(comp) 使用给定比较操作排序元素
lst.unique() 调用erase删除同一个值的连续拷贝。使用==。
lst.unique(pred) 调用erase删除同一个值的连续拷贝。使用给定的二元谓词。
  • 上面的操作都返回void

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

参数 解释
(p, lst2) p是一个指向lst中元素的迭代器，或者一个指向flst首前位置的迭代器。函数将lst2中的所有元素移动到lst中p之前的位置或是flst中p之后的位置。将元素从lst2中删除。lst2的类型必须和lst相同，而且不能是同一个链表。
(p, lst2, p2) 同上，p2是一个指向lst2中位置的有效的迭代器，将p2指向的元素移动到lst中，或将p2之后的元素移动到flst中。lst2可以是于lst或flst相同的链表。
(p, lst2, b, e) b和e表示lst2中的合法范围。将给定范围中的元素从lst2移动到lst或first中。lst2与lst可以使相同的链表，但p不能指向给定范围中的元素。
  • 使用lst.splice(args)或flst.splice_after(args)

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊