[C++ 面试基础知识总结] 泛型算法
基础泛型算法
泛型算法本身运行于迭代器之上,不会执行容器的操作,可以改变容器中保存元素的值,也可以在容器内移动元素,但永远不会直接添加或删除元素。插入迭代器是一种特殊的迭代器,当算法操作插入迭代器时,迭代器可以向容器添加元素,但算法本身永远不会做这样的事。
只读算法
只读算法只会读取其输入范围内的元素,而从不改变元素。
vector 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 v = {1,2,3,4,5}; vector 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 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 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 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 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 l = {1,2,3,4,5}; list 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 in(cin), eof; // 用accumulate函数对输入的整数求和 cout << accumulate(in, eof, 0) << endl; vector v = {1,2,3,4,5}; // 定义一个输出流迭代器out,与cout绑定,每个值后面都输出一个" " ostream_iterator 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[]) { listl {15,24,33,42,51}; listl2 {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中了。