[C++ 面试基础知识总结] 泛型算法
参考书籍：《C++ Primer》
目录
基础泛型算法
泛型算法本身运行于迭代器之上，不会执行容器的操作，可以改变容器中保存元素的值，也可以在容器内移动元素，但永远不会直接添加或删除元素。插入迭代器是一种特殊的迭代器，当算法操作插入迭代器时，迭代器可以向容器添加元素，但算法本身永远不会做这样的事。
只读算法
只读算法只会读取其输入范围内的元素，而从不改变元素。
vector<int> v = {1,2,3,4,5,4,3,2,1};
string s1 = "Summer love C++";
string s2 = "Summer love Swift";
auto f = find(v.begin(), v.end(), 2); //find函数是查找给定值在给定范围内的位置
cout << (f != v.end()) << endl; //如果查找到，返回第一个等于给定值元素的迭代器，否则返回尾后迭代器
auto c = count(v.begin(), v.end(), 2); //count函数返回的是给定值在给定范围内的出现次数
auto sum = accumulate(v.begin(), v.end(), 0); //accumulate函数是将给定范围内的所有元素相加，最后一个参数为初始值
auto sSum = accumulate(s1.begin(), s1.end(), string("Hello:")); // 字符串字面值不能执行+运算，所以最后一个参数不能写成"Hello:"
auto isEuqal = equal(s1.begin(),s1.end() - 3,s2.begin());//isEqual函数是比较两个序列是否相等，前两个参数表示第一个序列的范围，最后一个参数表示第二个序列的起始位置（两个序列长度相等）写容器算法
vector<int> v = {1,2,3,4,5};
vector<int> v2;
fill(v.begin(), v.end(), 0); //将给定范围内的元素全部替换为0
fill_n(v.begin(), 3, -1); //将给定位置开始的3个元素全部替换为-1
fill_n(back_inserter(v), 5, 1); //使用插入迭代器在容器尾部添加5个值为1的元素
replace(v.begin(), v.end(), 0, 1); //将给定范围内所有值为0的元素替换为1
replace_copy(v.begin(), v.end(), back_inserter(v2), -1, 1); //将给定范围内的所有元素拷贝出来，再将所有为-1的元素替换为1后有插入迭代器添加在v2尾部，v1中的元素没有变化重排容器元素算法
vector<int> v = {1,2,3,4,5,4,3,2,1};
sort(v.begin(), v.end()); //按大小重排v中的元素 {1，1，2，2，3，3，4，4，5}
auto end_unique = unique(v.begin(), v.end()); //将不重复的元素覆盖到容器前部，后部不动 {1，2，3，4，5，3，4，4，5}，并返回不重复区域之后第一个位置的迭代器
v.erase(end_unique,v.end()); // 可利用上面返回的迭代器删除重复元素定制操作
向算法传递函数
可以使用自定义的条件来给容器中的元素排序。下面以给几个两位数排序为例。
//自定义排序规则为按照各位数字的大小来排序
bool isSmaller(const int &i1, const int &i2){
return i1%10 < i2%10;
} vector<int> v = {15,24,33,42,51,41,32,23,14};
//在sort函数后增加第三个参数，自定义的谓词，排序结果：51 41 42 32 33 23 24 14 15
sort(v.begin(), v.end(),isSmaller);如果希望个位数字大小相同的数字，再按十位数字大小来排序，可以用稳定排序
vector<int> v = {15,24,33,42,51,41,32,23,14};
//先按照两位数大小进行排序，顺便按十位数字大小排序
sort(v.begin(), v.end());
//采用稳定排序的函数按照个位数字大小，再对容器进行排序，由于是稳定排序，不会改变相同个位数字大小的元素之间的原有顺序。排序结果：41 51 32 42 23 33 14 24 15
stable_sort(v.begin(), v.end(), isSmaller);lambda表达式
调用普通函数：
int func(){
return 1;
}auto f = func();调用lambda表达式可以得到同样结果
// 中括号内为捕获列表，小括号内为参数列表，->后为返回类型，花括号内为函数体
auto f = []() -> int{return 1;};lambda表达式还可以省略参数列表和返回类型
auto f = []{return 1;};用lambda表达式可以简化之前的排序的代码：
vector<int> v = {15,24,33,42,51,41,32,23,14};
sort(v.begin(), v.end());
//第三个参数传入一个与isSmaller函数等价的lambda表达式
stable_sort(v.begin(), v.end(), [](const int &i1, const int &i2){return i1%10 < i2%10;});在上述vector的基础上，输出所有两位数四舍五入后的值
int n = 5;
//采用find_if函数找到第一个复合条件的位置，这里lambda表达式需要使用局部变量n，需要在捕获列表中加入n，函数体才能使用n
auto pos = find_if(v.begin(), v.end(), [n](const int &i){return i%10 >= n;});
//for_each函数是对所有序列中的元素分别调用一次lambda表达式
for_each(v.begin(), pos, [](const int &i){cout << (i/10)*10 <<" ";});
for_each(pos, v.end(), [](const int &i){cout << (i/10+1)*10<<" ";});lambda表达式可以采取值捕获和引用捕获两种方式。
auto v1 = 1, v2 = 2;
auto f1 = [v1] { return v1;}; //值捕获，之后改变v1的值不会影响f1()的值
auto f2 = [&v2] { return v2;}; //引用捕获，之后改变v2的值会改变f2()的值
auto f3 = [=]{return v1 + v2;}; //对所有变量采用值捕获
auto f4 = [&]{return v1 + v2;}; //对所有变量采用引用捕获
auto f5 = [=,&v2]{return v1 + v2;}; //对除v2外的所有变量采用值捕获
auto f6 = [&,v1]{return v1 + v2;}; //对除v1外的所有变量采用引用捕获
auto f7 = [v1] () mutable {return ++v1;}; //加上mutable关键字可以在函数体内改变捕获变量的值如果lambda函数体包含了除return以外的任何语句，则编译器会假定lambda返回void，如果要返回其他类型，需要显示指定出来。
auto f = [v1] () mutable ->int{ ++v1 ; return v1;};参数绑定
bool checkNumber(const int &i, int n){
return i%10 >= n;
}由于函数有两个参数，而find_if只接受一元谓词，不能写成如下形式：
auto pos = find_if(v.begin(), v.end(), checkNumber);这个时候就需要用到bind函数
// _1表示第一个生成的可调用对象中参数的位置，依次类推_2表示第二个，使用这些占位符时需要声明使用命名空间 using namespace std::placeholders;
auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,n));等价于
auto pos = find_if(v.begin(), v.end(), [n](const int &i){return i%10 >= n;});占位符的顺序是传递参数的顺序，例如之前的
sort(v.begin(), v.end(),isSmaller);如果改写为
sort(v.begin(), v.end(),bind(isSmaller, _2, _1));则相当于颠倒了两个参数的顺序，最终得到的序列将会是从大到小的。
在bind函数中，非占位符参数是引用的时候，需要用ref函数或cref函数（常量）保护起来，写成以下形式
int x =5;
int &n = x;
auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,ref(n)));
const int &m = 5;
auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,cref(m)));
特殊迭代器
插入迭代器
插入迭代器是一种迭代器适配器，它接收一个容器，生成一个迭代器，能实现给定容器添加元素。该迭代器调用容器操作来向给定容器的指定位置插入一个元素。插入迭代器有3种类型，只是插入位置存在差异。
list<int> l = {1,2,3,4,5};
list<int> l1,l2,l3;
copy(l.begin(), l.end(), front_inserter(l1)); //在头部插入，copy函数执行完成后结果为5 4 3 2 1
copy(l.begin(), l.end(), back_inserter(l2)); //在尾部插入，copy函数执行完成后结果为1 2 3 4 5
copy(l.begin(), l.end(), inserter(l3, l3.begin())); //在指定位置插入，copy函数执行完成后结果为1 2 3 4 5 需要注意的是，front_inserter会将插入元素序列颠倒过来，类似数据结果中链表的头插法。
iostream迭代器
通过流迭代器，可以用泛型算法从流对象读取数据以及向其写入数据。
// 定义两个输入流迭代器in，eof，in与cin绑定，eof为空，相当于尾后迭代器
istream_iterator<int> in(cin), eof;
// 用accumulate函数对输入的整数求和
cout << accumulate(in, eof, 0) << endl;
vector<int> v = {1,2,3,4,5};
// 定义一个输出流迭代器out,与cout绑定，每个值后面都输出一个" "
ostream_iterator<int> out(cout," ");
// 将vector拷贝到输出流迭代器
copy(v.begin(), v.end(), out);
cout << endl;反向迭代器
反向迭代器是在容器中从尾元素向首元素反向移动的迭代器，rbegin函数返回的指向容器尾元素的迭代器，rend函数返回指向容器首元素之前位置的迭代器。crbegin和crend为相应的const型反向迭代器。
string s = "C++,Objective-C,Swift";
// 反向查找最后一个单词，找到逗号为止
auto last = find(s.crbegin(), s.crend(), ',');
// 输出结果为 tfiwS ，因为构造string的两个迭代器为反向迭代器
cout << string(s.crbegin(),last) << endl;
// 输出结果为 Swift，调用base函数可以将反向迭代器转换为普通迭代器
cout << string(last.base(),s.cend()) << endl;5类迭代器
算法所要求的迭代器操作可以分为5个类别，每个算法都会对它的每个迭代器参数指明须提供哪类迭代器。
输入迭代器：只读不写，单遍扫描，只能递增，find和accumulate要求输入迭代器，istream_iterator是输入迭代器
输出迭代器：只写不读，单遍扫描，只能递增，copy的第三个参数和ostream_iterator就是输出迭代器
前向迭代器：可读写，多遍扫描，只能递增，replace要求前向迭代器，forward_list上的迭代器也是前向迭代器
双向迭代器：可读写，多遍扫描，可递增递减，reverse要求双向迭代器，list上的迭代器也支持双向迭代器
随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算，sort要求随机访问迭代器，array，deque，string，vector的迭代器和内置数组的指针都是随机访问迭代器。
链表的特定容器算法
由于链表类型不支持要求随机访问迭代器的通用算法，所以定义了一些类似的算法。
// 用于提供比较个位数字大小谓词的函数
bool isSmaller(const int &i1, const int &i2){
return i1%10 < i2%10;
}
// 用于提供判定各位数字是否相等谓词的函数
bool isEuqal(const int &i1, const int &i2){
return i1%10 == i2%10;
}
int main(int argc, const char * argv[]) {
list<int>l {15,24,33,42,51};
list<int>l2 {41,32,23,14};
// 将l2的元素全部合并到l中，合并后l2为空。l和l2都必须有序，合并后会自动排序。合并后的l： 14 15 23 24 32 33 41 42 51
l.merge(l2);
// 根据个位数字大小排序 排序后的l：41 51 32 42 23 33 14 24 15
l.sort(isSmaller);
// 删除个位数字重复的元素 删除后的l：41 32 23 14 15
l.unique(isEuqal);
return 0;
}链表还定义了splice算法，以下2种写法等价，都是将l2所有元素移动到l尾部，并从l2中删除
l.splice(l.end(), l2);
l.splice(l.end(), l2, l2.begin(),l2.end());如果只移动一个元素可以写成如下形式
l.splice(l.end(), l2, l2.begin());注意：多数链表特有算法与其通用版本很相似，但不完全相同，链表特有版本的一个至关重要的区别是会改变底层的容器。例如merge算法将l2合并到l中后，会将l2的全部元素从l2列表中删除。但这些删除的元素依旧存在，只是存在于l中了。
