泛型算法

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

初识泛型算法

• 除少数例外，标准库算法都对一个范围内的元素进行操作，称为“输入范围”；
• 接受输入范围的算法总是使用前连个参数来表示此范围，两个参数为 要处理的第一个元素 和 尾元素之后位置 的迭代器；
• 理解算法的最基本的方法是了解它们是否读取元素、改变元素、重排元素顺序。

只读算法

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

find

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

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

count

• 类似find()，接受一对标记范围的迭代器和一个值作为参数；
• count() 返回给定值在序列中出现的次数。

accumulate

• 头文件 #include <numeric>；
• 接受三个参数，前两个指出需要求和的元素的范围，第三个参数是求和的初始值；
• 第三个参数的类型决定了函数中使用哪个加法运算符及返回值的类型。

equal

• 用于确定两个序列是否保存相同的值；
• 接受三个迭代器：前两个表示第一个序列中的元素范围，第三个表示第二个序列的首元素；
• 可以比较两个不同类型的容器，甚至元素类型也不必一样而只要能用==来比较即可；
• 但需要保证第二个序列不比第一个序列短，从而第一个序列中每一个元素在第二个序列中都有与之对应的。

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

写容器元素的算法

• 一些算法将新值赋予序列中的元素。
• 算法不检查写操作，必须确保序列大小不小于算法将要写入(更改)的元素数目。

插入迭代器back_inserter

• 一种保证算法有足够元素空间来容纳输出数据的方法。

• #include <iterator>

• 对插入迭代器解引用并赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中：

  vector<int> vec;  //空向量
  auto it = back_intserter(vec);  //通过它赋值会将元素添加到vec中
  *it = 42;  //vec 中现在又一个元素了，值为42

fill

• fill：接受一对“输入范围”，还接受一个值作为第三个参数，fill 将给定的这个值赋给输入序列中的每一个元素； fill(vec.begin(), vec.end(), 0); 将每个元素重置为 0
• fill_n：接受一个“单迭代器”、一个计数值和一个值，fill_n 将从迭代器指向位置开始为指定个数的元素赋值为指定值； fill_n(vec.begin(), vec.size(), 0);若vec是一个int型容器，fill_n将所有元素重置为 0。请确保vec 不是一个空容器，即已初始化，且从vec.begin()开始元素个数不少于vec.size()

copy

auto ret = copy(vec.begin(), vec.end(), cp_vec.begin());

• 输入：前两个参数指定输入范围，第三个指向目标序列的起始位置。
• 返回：返回其目的位置迭代器(第三个参数)递增后的值，即ret指向cp_vec中最后拷贝的元素的下一个位置。
• copy时必须保证目标目的序列至少要包含与输入序列一样多的元素。
• copy (ilst.begin(), ilst.end(), back_inserter(ivec));

replace

• 修改指定值。

• 输入：接受 4 个参数，前两个是输入范围，第三个是要搜索的值，第四个是要替换的新值。

// 将所有值为0的元素改为42
replace(ilst.begin(), ilst.end(), 0, 42);

• replace_copy：replace的copy版本。对指定序列执行replace后保存到另一位置，而原序列不变。额外接受第三个迭代器参数，指出调整后序列的保存位置：

  //list并未改变，ivec包含ilst的一份拷贝，但在原来ilst中值为0的元素在ivec中为42
  //使用back_inserter按需要增长目标序列
  replace_copy(ilst.cbegin(), ilst.cend(),
  			 back_inserter(ivec), 0, 42);

重排容器元素的算法

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

sort

• 接受两个迭代器，表示要排序的元素范围。
• 利用元素类型的<运算符实现排序，因此默认从小到大排。

unique

• 重排输入序列，将相邻的重复项“消除”。

• 之前要先调用sort
• 并没有真正删除，只是在遇到相邻的重复元素时，将其后所有元素都向前移，覆盖重复元素，容器大小依然不变；
• 返回的迭代器指向最后一个不重复元素之后的位置，此位置之后的元素依然存在，但不知道值是什么；
• 真正删除必须使用容器操作：words.erase(end_unique, words.end())

定制操作

向算法传递函数：

• 谓词（predicate）：
  • 是一个可调用的表达式，返回结果是一个能用作条件的值
  • 一元谓词：接受一个参数
  • 二元谓词：接受两个参数
• 接受谓词参数的算法对输入序列中的元素调用谓词，因此元素类型必须能转换为谓词的参数类型

带谓词的 sort

// 比较函数，用来按长度排序单词
bool isShorter(const string &s1, const string &s2){
	return s1.size() < s2.size();
}

// 按长度由短至长排序words
sort(words.begin(), words.end(), isShorter);
// 按长度排序，长度相同的单词维持原来的相对位置
stable_sort(words.begin(), words.end(), isShorter);

• stable_sort：保留相等元素的原始相对位置。

lambda 表达式

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

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

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

  • capture list（捕获列表）是一个lambda所在函数中定义的局部变量的列表（通常为空），一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。不可忽略

  • return type是返回类型。可忽略，根据函数体中代码推断返回类型

  • parameter list是参数列表，通常是输入序列中元素的引用。可忽略

  • function body是函数体。不可忽略

  • 定义一个可调用对象f，他不接受参数，返回 42：

    // 可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体
    auto f = [] {return 42;}
    // 调用 f，打印42
    cout << f() << endl;

find_if

• 接受一对表示范围的迭代器和一个谓词，对输入序列中每个元素调用给定的谓词。返回一个迭代器，指向第一个使谓词返回非 0 值的元素，如不存在则返回尾后迭代器

• 接受一个谓词的find_if：

  // sort接受二元谓词，而find_if接受一元谓词
  // 传递给find_if的函数，即谓词参数所表示的函数cmp，只能接受一个参数
  // 因此意味着只能将输入序列中的元素和一个固定的值5比较
  bool cmp(const string &a){
      return a.size() > 5;
  }
  // 找出第一个长度大于5的字符串
  auto wc = find_if(words.begin(), words.end(), cmp);

• 使用lambda，接受一个调用对象的find_if：

  // 找出第一个满足 size()>=sz 的元素位置
  // sz 是lambda所在函数中定义的局部变量
  auto wc = find_if(words.begin(), words.end(),
               [sz](const string &a)
                    { return a.size() >= sz; });
  
  // 打印长度大于sz的单词，words已按元素长度排过序
  for_each(wc, words.end(),
          [](const string &s){ cout << s << " "; });

  • for_each：接受一个可调用对象，并对序列中每个元素调用此对象。

只有局部非 static 变量才需要在捕获列表中写出，对于局部 static 变量以及lambda所在函数之外声明的变量lambda可以直接使用

lambda 捕获和返回

• 定义lambda时会生成一个新的类类型和该类型的一个对象。
• 默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员，在lambda对象创建时被初始化。
• 值捕获：前提是变量可以拷贝。捕获的变量的值在lambda创建时而非调用时拷贝；
• 引用捕获：必须保证在lambda执行时，变量是存在的。引用的变量是调用时引用；
• 尽量减少捕获的数据量，尽可能避免捕获指针或引用。
• 隐式捕获：让编译器推断捕获列表，在捕获列表中写一个&（引用捕获）或=（值捕获）来告诉编译器采用哪种捕获方式。

size_t v1 = 42;
auto f = [v1] { return v1; };  //值捕获
auto f2 = [&v1] { return v1; };//引用捕获
v1 = 0; auto j = f(); // j为42
auto j2 = f2(); // j2为0

// sz为隐式捕获，值捕获方式
auto f3 = [=] { return sz; };

lambda 捕获列表：

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

可变 lambda

• 默认情况下，不能在 lambda 中改变值捕获的变量，需要在参数列表首加上关键字mutable
• 引用捕获的变量，如果此引用指向的是一个非const类型，则可改变

size_t v1 = 42;
auto f = [v1] () mutable { return ++v1; };//创建时拷贝
auto f2 = [&v1] { return ++v1; };		  //调用时引用
v1 = 0;
auto j = f() + f2(); // j的值为43+1

lambda 的返回类型

• 若只包含单一的return语句，可以不指明返回类型，由编译器推断；若包含除此之外的其他语句，编译器假定返回void

• 若除return外有其他语句，又确实有返回值，使用尾置返回类型来定义：

  // transform对输入序列中每个元素调用可调用对象，
  // 并将结果写到目的位置vi.begin()。
  // 将输入序列vi中每一个元素求绝对值并放回原位置
  transform(vi.begin(), vi.end(), vi.begin(),
           [](int i) -> int
            { if(i < 0) return -i; else return i; });

参数绑定

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

bind

• 定义在头文件functional中，可以看做为一个通用的函数适配器。

• auto newCallable = bind(callable, arg_list);

• 我们再调用newCallable的时候，newCallable会调用callable并传递给它arg_list中的参数。

• _n代表第 n 个位置的参数。定义在placeholders的命名空间中。using std::placeholder::_1;

• 调用g时，将第一个参数与_1绑定，第二个参数与_2绑定，然后再将bind中后面的参数a,b,_2,c,_1作为f的参数列表，调用f：

  // g是一个有两个参数的可调用对象
  auto g = bind(f, a, b, _2, c, _1);
  // 等价于 f(a, b, y, c, x)
  g(x, y)

auto wc = find_if(words.begin(), words.end(),
             [sz](const string &a)
                   { return a.size() >= sz; });
// 等价于下面版本：
bool check_size(const strings &s, int sz){
    return s.size() >= sz;
}
auto wc = find_if(words.begin(), words.end(),
                 bind(check_size, _1, sz));

再探迭代器

插入迭代器

• 插入器是一种迭代器适配器，接受一个容器，生成一个迭代器，能实现向给定容器添加元素。
• 三种类型：
  • back_inserter：创建一个使用push_back的迭代器。
  • front_inserter创建一个使用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++	使用元素类型所定义的>>运算符从流中读取下一个值。前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值。

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，接受一个谓词代替元素值：

  // 查找输入范围中val第一次出现的位置
  find(beg, end, val);
  
  // 查找第一个使得pred返回非零值的元素的位置
  find_if(beg, end, pred);

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

  // 反转输入范围中元素的顺序
  reverse(beg, end);
  
  // 将元素按逆序拷贝到dest中
  reverse_copy(beg, end, dest);

特定容器算法

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

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

操作	解释
lst.merge(lst2)	将来自lst2的元素合并入lst，二者都必须是有序的，元素将从lst2中删除。合并之后，合并之后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)	同上，但使用给定的二元谓词。

• 上面的操作都返回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)
• 通用算法永远不能执行容器的操作，不能添加或删除元素；而链表特有的操作会改变底层的容器。