C++ primer 第十章
10.1 泛型算法概述
泛型：可以用于不同类型的容器和不同类型的元素
容器定义的操作非常有限，其它操作（例如：查找特定元素，替换或删除某一个元素，排序等）都是通过一组泛型算法实现的
大多数算法都定义在头文件 algorithm 中，头文件 numeric 还定义了一组算法
int val =42; //将查找的值 //如果在vec中找到想要的元素,则返回结果指向它 //否则返回结果为 vec.end() std::vector<int> vec; auto result = std::find(vec.begin(), vec.end(), val); //打印结果 std::cout << "值:" << val << (result == vec.cend() ? "不存在":"存在") << std::endl; std::list<std::string> list1; std::string s1 ="val"; auto result = std::find(list1.begin(), list1.end(), s1); //由于指针就像内置数组上的迭代器一样,所以也可以在数组中查找 int ia[] = { 27, 210, 12, 47, 109, 83 }; int val =83; int* result = std::find(std::begin(ia), std::end(ia), val); //从ia[1]开始,直至(但不包含)ia[4]范围内查找元素 auto result = std::find(ia+1, ia+4, s1);
泛型算法本身不会执行容器操作，它们只会运用于迭代器上
Find 函数的执行步骤
以下步骤不依赖容器保存的元素类型，也不依赖容器类型，只用迭代器访问元素
1、访问序列的首元素
2、比较此元素与查找值
3、如果此元素与查找值匹配，find 返回标识此元素值
4、否则，前进至下一个元素，重复步骤 2 和 3
5、若至序列尾，则 Find 停止，返回一个元素未找到的值
10.2 初识泛型算法
标准库提供了超过 100 个算法
只读算法
读取输入范围内的元素，而不改变元素，如 accumulate ，equal
std::vector<int> vec; //对vec中的元素求和,和初值为 0 (第三个参数决定了返回类型) int sum = std::accumulate(vec.begin(),vec.end(),0); std::vector<std::string> vec1; //string定义了 + 方法 std::string sum1 = std::accumulate(vec1.begin(), vec1.end(), std::string("")); //错误,const char* 没有定义 + 方法 std::string sum1 = std::accumulate(vec1.begin(), vec1.end(), ""); /* 所有接受单一迭代器来表示第二个序列的算法,都认为第二个序列至少与第一个一样长 */ std::vector<const char*> roster1; //容器内的类型能比较即可 std::vector<const char*> roster2; //roster2元素个数至少要和roster1一样多 std::equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
写容器元素算法
std::vector<int> vec; std::fill(vec.begin(), vec.end(), 0); //将每个元素重置为 0std::fill(vec.begin(), vec.begin() + vec.size()/2, 10); //将容器一个子序列置为 0//算法不检查写操作,可能会触发灾难性错误 std::fill_n(vec.begin(), vec.end(), 0); //将每个元素重置为 0//修改 vec 10 个(不存在)的元素 std::fill_n(vec.begin(),10, 1); //dest指向一个元素,从dest开始至少要包含n个元素
插入迭代器
back_inserter 是定在头文件 iterator 中的一个函数，接受指向容器的引用
实质，返回的就是尾后迭代器
std::vector<int> vec; //空向量 auto it = std::back_inserter(vec); //通过它赋值会将元素添加到vec中 *it =42; //vec中现有一个元素,值为42 std::vector<int> vec2; //正确,back_inserter 会创建一个插入迭代器,可用来向 vec2 插入元素 std::fill_n(std::back_inserter(vec2), 10, 0); //添加10个元素到vec
拷贝算法
//#include <algorithm>int a1[] = { 0, 1, 2, 3, 4, 5, 6 }; int a2[sizeof(a1) / sizeof(*a1)]; //a2 和 a1 大小一样 //ret 指向拷贝到 a2 尾元素之后的位置 auto ret = std::copy(std::begin(a1), std::end(a1), a2);//把a1的内容拷贝给a2 //将所有值为0的元素改为42 std::replace(std::begin(a2), std::end(a2), 0, 42); //如果需原序列不变,可使用replace_copy std::vector<int> vec; //vec包含a2的一份拷贝,且将vec所有值为0的元素改为42 std::replace_copy(std::begin(a2), std::end(a2), std::back_inserter(vec), 0, 42);
重排容器元素算法
void elimDups(std::vector<std::string>& words){ //按字典顺序排序words,以便查找重复单词 std::sort(words.begin(), words.end()); //unique消除相邻的重复项 //排列在范围的前部,返回指向不重复区域之后一个位置的迭代器 auto end_unique = std::unique(words.begin(), words.end()); words.erase(end_unique, words.end()); //消除多余 } int main(){ std::vector<std::string> words = { "the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle" }; elimDups(words); }
SORT 默认使用元素类型的 < 运算符
//比较函数,用来按长度排序单词 bool isShorter(const std::string& s1, const std::string& s2){ return s1.size() < s2.size(); } //按长度由短至长排序words,sort可以接受一个二元谓词参数(两个参数) std::sort(words.begin(), words.end(),isShorter); //第三个参数是谓词(可调用的表达式,返回结果是一个能用做条件的值,谓词分为一元和二元)
10.3.1 定制操作 lambda 表达式
可调用的代码单元 : 一个未命名的内联函数
int main(){ auto f = []{return 42; }; f(); //lambda和普通函数调用方式相同,都是使用调用运算符 system("pause"); return 0; }
lambda 表达式，可用来解决函数参数限制多元谓词的场景
void biggies(std::vector<std::string>& words, std::vector<std::string>::size_type sz){ //elimDups(words); //将words按字典顺序排序,删除重复元素 //按长度排序,长度相同的单词维持字典序 std::stable_sort(words.begin(), words.end(), [sz](const std::string& a){return a.size() >= sz; }); //获取一个迭代器,指向第一个满足size() >= sz的元素 auto wc= std::find_if(words.begin(), words.end(), [sz](const std::string& a){return a.size() >= sz; }); }
lambda 捕获和返回
向函数传递 lambda 时，同时定义了一个（未命名的）新类型和该类型的一个对象
默认情况下，新类型包含了捕获的变量，作为数据成员
//值捕获 void fcn1(){ size_t v1 =42;//局部变量 //将v1拷贝到名为f的可调用对象 auto f = [v1]{return v1; }; v1 =0; auto j = f();//j为42 f是一个拷贝,当创建v1时 } //引用捕获 : 当以引用方式捕获一个变量时，必须保证 lambda 执行时变量存在 void fcn2(){ size_t v1 =42;//局部变量 //将v1拷贝到名为f的可调用对象 auto f = [&v1]{return v1; }; v1 =0; auto j = f();//j为0 }
隐式捕获 : 让编译器根据 lambda 表达式体中的代码来推断需要使用哪些变量
//隐式捕获 auto wc= std::find_if(words.begin(), words.end(), [=](const std::string& a){return a.size() >= sz; }); std::ostream& os = std::cout; char c =' '; //os隐式引用捕获,c显式值捕获 std::for_each(words.begin(), words.end(), [&, c](const std::string& s){os << s << c; }); //os显式引用捕获,c隐式值捕获 std::for_each(words.begin(), words.end(), [=, &os](const std::string& s){os << s << c; });
可变 lambda
void fcn3(){ size_t v1 =42;//局部变量 //对于值拷贝的变量,如果需要修改,必须使用关键字mutable auto f = [v1]() mutable {return ++v1; }; v1 =0; auto j = f();//j为43 } void fcn4(){ size_t v1 =42;//局部变量 //对于非const变量的引用,可以通过f中的引用修改 auto f = [&v1]{return v1; }; v1 =0; auto j = f();//j为1 }
10.3.2 定制操作 绑定参数
参数绑定 ：定义在 functional 头文件中，调用 bind 的一般形式为
auto newCallable = bind(callable,arg_list);
_1 定义在 std::placeholders 中
#include <functional>using namespace std::placeholders; std::vector<std::string> words = { "string1", "abcd" }; bool check_size(const std::string& s,std::string::size_type sz){ return s.size() >= sz; } int main(){ auto check1 = std::bind(check_size, _1, 6); std::string str ="abc"; bool b1 = check1(str); auto wc= std::find_if(words.begin(), words.end(), std::bind(check_size, _1, 6)); auto wc2 = std::find_if(words.begin(), words.end(), check1); system("pause"); return 0; }
bind 的参数
//g是一个有两个参数的可调用对象 auto g = bind(f,a,b,_2,c,_1); //g(x,y) 的调用会映射到 f(a,b,y,c,x);
用 bind 重排参数顺序
//按单词长度由短至长排序 sort(words.begin(), words.end(),isShorter); //按单词长度由长至短排序 sort(words.begin(), words.end(),bind(isShorter,_2,_1)); //当sort需要比较两个元素A和B时,调用isShorter(A,B) //当sort需要比较两个元素时,就好像调用了isShorter(B,A)一样
绑定引用参数 : 默认情况下，bind 的那些不是占位符的参数会被拷贝
//错误 : 不能拷贝os for_each(words.begin(), words.end(),bind(print,os,_1,'')); //对于os对象,不能拷贝;必须使用标准库ref函数包含给定的引用 for_each(words.begin(), words.end(),bind(print,ref(os),_1,''));
