首页 > 代码库 > Chapter10：泛型算法
Chapter10：泛型算法
泛型算法的基础是迭代器。
迭代器令算法不依赖于容器，但是算法依赖于元素类型的操作。也即：算法永远不会执行容器的操作。
那么，如果想向容器中添加元素或者执行其他的一些操作呢？标准库提供了插入迭代器来完成。但算法自身永远不会做这样的操作。
- 理解算法最基本的方法是：了解它们是否读取元素、改变元素、或是重排元素。
只读算法
1 int sum = accumulate(vec.cbegin(), vec.cend(),0);2 //第三个参数类型决定了函数中使用哪个加法运算符及返回值类型
这里面蕴含着一个编程假定：将元素类型加到和的类型上的操作是可行的。
1 string sum = accumulate(v.cbegin(), v.cend(), string(""));2 //错误：string无法转换为const char*3 string sum = accumulate(v.cbegin(), v.cend(), "");
Best Practice：对于只读算法，最好使用cbegin（）和cend（）。
写算法
算法不会执行检查操作，不会检查写算法。
重排容器的算法
1 //消除重复单词2 void elimDups(vector<string> &words)3 {4 sort(words.begin(), words.end());5 auto end_unique = unique(words.begin(), words.end());6 words.erase(end_unique, words.end());//使用容器操作来删除元素7 }
- 定制操作——谓词
谓词是一个可调用表达式，其返回一个能用作条件的值。到目前为止，我们仅用过两种可调用对象：函数和函数指针。还有其他两种可调用对象：重载了函数调用运算符的类和lambda表达式。
lambda表达式：
具有一个返回类型、一个参数列表、一个函数体。
1 [capture list] (parameter list) -> return type {function body}
表达式格式说明：
「我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体。
忽略参数列表，等价于一个空参数列表；忽略返回类型，如果函数体只有一个return语句，则从返回的表达式推断函数类型，否则，返回类型为void。
虽然一个lambda可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。
一个lambda可以直接使用定义在当前函数之外的名字。即：捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和在它所在函数之外声明的名字。」
1 void biggies(vector<string> &words, vector<string>::size_type sz) 2 { 3 elimDups(words); 4 //按长度稳定排序 5 stable_sort(words.begin(), words.end(), [](const string& a, const string& b) {return a.size() < b.size(); }); 6 //获取第一个size大于sz的元素 7 auto wc = find_if(words.begin(), words.end(), [sz](const string &a) {return a.size() >= sz; }); 8 //size大于sz的元素数目 9 auto count = words.end() - wc;10 cout << count;11 //打印这些单词12 for_each(wc, words.end(), [](const string &s) {cout << s << " "; });13 cout << endl; 14 }
当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此未命名对象。
捕获分为值捕获和引用捕获：
被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝；
如果lambda可能在函数结束后执行，捕获的引用指向的局部变量已经消失；
确保lambda每次执行的时候，信息都有预期的意义，是程序员的责任；一般来说，我们应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题，而且，如果可能的话，应该避免捕获指针和引用。
捕获分为隐式捕获和显式捕获。
如果混合使用隐式捕获和显式捕获，显式捕获必须使用与隐式捕获不同的方式：如果隐式捕获使用引用方式（&），则显示捕获使用值方式；反之亦然。
可变lambda：
如果我们希望能改变一个被捕获的变量的值，就必须在参数列表首加上关键字mutable。
对于那种只在一两个地方使用的简单操作，lambda表达式是最有用的；如果我们需要在很多地方使用相同的操作，通常应该定义一个函数，而不是多次编写相同的lambda表达式。
- 参数绑定
如果lambda的捕获列表为空，可以用函数来替代它。但是，对于捕获局部变量的lambda，用函数来替换它就不是那么容易了。我们必须解决这一问题。
1 auto newCallable = bind(callable, arg_list);1 bool check_size(const string &s, string::size_type sz)2 {3 return s.size() >= sz;4 }5 6 auto check6 = bind(check_size, placeholders::_1, 6);
以check6为例：只有一个占位符：表示check6只接受一个参数。占位符出现在arg_list的第一个位置，表示check6此参数对应到check_size的第一个参数。
最后一个问题：
1 for_each(words.begin(), words.end(), bind(print, os, _1, ‘ ‘));//错误，os不能拷贝2 for_each(words.begin(), words.end(), bind(print, ref(os), _1, ‘ ‘));
其他迭代器：流迭代器、插入迭代器、反向迭代器、移动迭代器。
算法形参的4种模式：
1 alg(beg, end, other args);2 alg(beg, end, dest, other args);3 alg(beg, end, beg2, other args);4 alg(beg, end, beg2, end2, other args);
list和forward_list使用自己的算法会比较好。
Chapter10：泛型算法