C++Primer——第10章(泛型算法)

10.2 初识泛型算法

int main() {
	std::vector<int> vec1{ 1,2,3,4 };
	std::vector<int> vec2{ 1,2,3,4 };
	std::vector<int> vec3{ 1,2,3 };

	int counts = std::accumulate(vec1.begin(), vec1.end(), 5);			    // 15

	bool result = std::equal(vec1.begin(), vec1.end(), vec2.begin());      // true
	bool result1 = std::equal(vec1.begin(), vec1.end(), vec3.begin());     // 错误: equal只传递一个迭代器vec3.begin()来表示 比较的第二个范围，但此算法要处理第一个序列中的每个元素，它假定每个元素在第二个序列中都有一个与之对应的元素。
}

int main() {
	
	std::vector<int> vec1{ 1,2,3,4 };
	std::vector<int> vec2{ 1,2,3,4 };
	std::vector<int> vec3{ 1,2,3,4 };
	std::vector<int> vec4{ 0,0,0,0 };
	std::vector<int> vec5{ 0,0,0,0 };
	std::vector<int> vec6{ 0,0,0,0 };

	std::fill(vec2.begin(), vec2.begin() + 2, 0);         // vec2={0,0,3,4} （范围内两个元素 被替换成0）
	std::fill_n(vec3.begin(), 2, 0);                      // vec3={0,0,3,4} （从vec.begin()开始的两个元素 被替换成0）
	std::copy(vec1.begin(), vec1.end(), vec4.begin());    // vec4={1,2,3,4} （范围内的元素 复制到另一个范围）
	std::replace(vec5.begin(), vec5.end(), 0, 1);         // vec5={1,1,1,1} （范围内的元素 值为0的都被替换成1）
	std::replace_copy(vec1.begin(), vec1.end(), vec6.begin(), 2, 1);     // vec5={1,1,3,4} （范围内的元素被 复制到从vec6.begin()起始的范围，复制过程中 原范围内元素 值为2的都替换成1后，再复制到新范围。注:原范围内的值不变）
}

int main() {
	vector<int> vec;

	std::fill_n(vec.begin(), 5, 0);                   // 错误: vec容器大小为0，不允许复制数据
	std::fill_n(std::back_inserter(vec), 5, 1);       // 正确: back_inserter为vec容器创建一个 尾部插入迭代器，可用于在容器vec尾部插入元素
}

int main() {
	vector<int> vec1{ 1,3,2,4 };
	vector<int> vec2{ 4,3,2,3,1,1 };

	std::sort(vec1.begin(), vec1.end());      // vec1={1,2,3,4}（范围内元素进行排序）

	std::sort(vec2.begin(), vec2.end());      // vec2={1,2,3,3,4}（注: 使用unique之前的序列一定要是有序的!，否则没有作用，所以要先调用sort排序）
	auto end_unique = std::unique(vec2.begin(), vec2.end());      // vec2={1,2,3,4,3,4} （注: 实际只有前面{1,2,3,4}是有效的，后面{3,4}是无效的。end_unique为指向{1,2,3,4}中最后一个元素(4)的下一个元素(3)的迭代器）
	cout << *end_unique;      // 3
	vec2.erase(end_unique, vec2.end());       // vec2={1,2,3,4}（使用unique后通常会 调用容器的erase方法，它擦除未指定值{3,4}并减小容器的物理大小，以匹配其新的逻辑大小）
}

• unique只对有序序列操作，所以调用unique之前 先调用sort；
• 调用unique后，重复的元素并未被真正删除，真正删除必须使用 容器自身的删除操作。(如：vec2.erase(end_unique, vec2.end())；)
• 标准库算法 对迭代器而不是容器 进行操作。因此算法不能(直接) 添加或删除元素。

bool isShorter(const string& s1, const string& s2) {
	return s1.size() < s2.size();
}

int main() {
	vector<string> vec{ "aaad","aaac","aab","aaa","aaab" };

	std::sort(vec.begin(), vec.end(),isShorter);               // vec={"aab","aaa","aaad","aaac","aaab"}（按长度排是正确的，但按字典序是错误的!）

	// 希望将vec按大小排序的同时，还希望 具有相同长度的元素按字典序排列
	std::sort(vec.begin(), vec.end());                         // vec={"aaa","aaab","aaac,"aaad","aab"}（按字典序排序）
	std::stable_sort(vec.begin(), vec.end(), isShorter);       // vec={"aaa","aab","aaab","aaac","aaad"} (按长度排序，但又能够保持相同元素(长度相对的元素) 的原本相对次序，因此也就保持了字典序)
}

• 带有 ”stable“ 前缀的函数 可保证相同元素的原本相对次序 在排序之后保持不变。
• stable_sort内部实现是 归并排序，稳定； sort的内部实现是 快速排序，不稳定。

// 练习 10.13
int main() {
	std::vector<string> vec = { "aaaa","aaaa1","bbbb1","bbbb","cccc","cccc1","dddddd" };

	auto end_position = std::partition(vec.begin(), vec.end(), compare);       // vec={"dddddd","aaaa1","bbbb1","cccc1","cccc","bbbb","aaaa"}（满足条件 "str.size()>5" 的为前四个元素{"dddddd","aaaa1","bbbb1","cccc1"}）
	vec.erase(end_position, vec.end());          // vec={"dddddd","aaaa1","bbbb1","cccc1"}，删除不满足条件的元素（即后面三个元素{"cccc","bbbb","aaaa"}）
	

	// partition只能接受一元谓词，则说明作为谓词的compare函数 只能有一个参数，所以必须将 "长度5" 硬编码到compare函数体内。如果条件长度改为6，则需要额外编写一个函数。
	// 使用lambda表达式就可以巧妙解决这一点，通过捕获列表捕获 局部变量len，因此可以不受参数数量的限制的影响
	size_t len = 6;
	auto end_position = std::partition(vec.begin(), vec.end(), [len](const string& str) {return str.size() >= len; });   
	vec.erase(end_position, vec.end());          // vec={"dddddd"}
}

int main() {
	vector<string> vec = { "aaa","bbb","ccc" };

	auto target_itr = std::find_if(vec.begin(), vec.end(), [](const string& str)-> bool { return str == "ccc"; });      // *target_itr="ccc"（lambar表达式的返回类型 "->bool" 可以省略，编译器会根据返回语句自动推导）

	std::for_each(vec.begin(), vec.end(), [](const string& str) {cout << str << " "; });      // 输出{"aaa","bbb","ccc"}（之所以可以不用捕获 而直接使用cout，是因为cout是定义在当前所在函数(main)之外的名字）
}

• 值捕获：前提是变量可以拷贝。（如：cout不可拷贝）
• 引用捕获：必须保证在lambda执行时，变量是存在的。（如：函数返回一个lambda，该lambda不能包含引用捕获）
• 隐式捕获：让编译器推断捕获列表，在捕获列表中写一个 &(引用方式) 或 =(值方式)。auto f3 = [=] {return v1;}
• 混合使用隐式捕获和显示捕获：捕获列表中的第一个元素必须是一个 &或=。此符号指定了 默认捕获方式 为引用或值。

int main() {
	
	// 被捕获的变量的值 是在lambda"创建时"拷贝，而不是调用时拷贝:
	int a = 1;
	auto f0 = [a] {return a; };
	a = 0;
	int j = f0();   // j为1，f0保存了我们创建它时 a的拷贝


	// 值捕获: 前提是变量可以拷贝
	int b = 1;
	auto f1 = [b] {return b; };           // 正确
	auto f2 = [cout] {cout << "a"; };     // 错误: cout不可以拷贝


	// 引用捕获: 必须保证在lambda执行时，变量是存在的
	int c = 1;
	auto f3 = [&c] {return c; };


	// 隐式捕获：让编译器推断捕获列表，在捕获列表中写一个 &(引用方式) 或 =(值方式)
	int d = 1;
	auto f4 = [=] {return d; };
	auto f5 = [&] {return d; };


	// 混合使用隐式捕获和显示捕获：捕获列表中的第一个元素必须是一个 &或=。此符号指定了 默认捕获方式为引用或值。
	int e = 1, f = 1;
	auto f6 = [&, f] {return e + f; };     // f为显式捕获，值捕获方式; e为隐式捕获，引用捕获方式
	auto f7 = [=, &e] {return e + f; };    // f为隐式捕获，值捕获方式; e为显式捕获，引用捕获方式
	auto f8 = [=, f] {return e + f; };     // 错误: 不能同时存在隐式和显式的 值捕获
	auto f9 = [&, &f] {return e + f};      // 错误: 不能同时存在隐式和显式的 引用捕获
	auto f10 = [&, =] {return e + f};      // 错误: 不能同时存在两种隐式捕获


	// 默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果我们希望能改变一个被捕获的变量的值，就必须在参数列表尾加上关键字mutable。
	int g = 1;
	auto f11 = [g]() {return ++g; };              // 错误: 捕获的变量g不可修改
	auto f12 = [g]()mutable { return ++g; };      // 正确: 捕获的变量g，它在刚开始被捕获的初始值是1
	cout << f12();;    // 调用一次f12之后，变成了2
	cout << f12();     // 调用一次f12之后，变成了3
	cout << g;         // 1（由于是值捕获，所以局部变量g的值一直不会变，最终还将输出1）   

	
	// 如果lambda体不只有单一的return语句，编译器将不能推断lambda的返回类型，必须显式指定lambda返回类型。(然而VS-2019下编译器不需要显式返回类型也能推断，但为了移植性，最好按标准写)
	vector<int> vec1{ 1,-1,-1 };
	vector<int> vec2{ 4,4,4 };
	auto f13 = [](int i) {if (i < 0)return -i; else return i; };       // 作用: 返回i的绝对值 （正确: VS-2019下的编译器不需要显式返回类型也能推断）
	std::transform(vec1.begin(), vec1.end(), vec2.begin(), f13);       // vec2={1,1,1}，将第一个范围内的元素的"绝对值"，覆盖到第二个范围内的元素
}

• 我们调用newCallable的时候，newCallable会调用callable 并传递给它arg_list中的参数。
• arg_ list中的参数可能包含形如 _n 的名字，其中n是一个整数。这些参数是“占位符"，表示newCallable的参数。(如：_1为newCallable的第一个参数，_2 为第二个参数)
• 名字 _n 都定义在一个名为placeholders的命名空间中，而这个命名空间本身 定义在std命名空间中。(使用这些名字，两个命名空间都要写，如：std::placeholders::_1)

using namespace std::placeholders;      // 为了方便使用_n，直接声明命名空间placeholders

void print_s(std::ostream& os,const string &s) {
	os << s << " ";
}

bool isShorter(const string& str1, const string& str2) {
	return str1.size() < str2.size();
}

void print(int a, int b,int c) {
	cout << a << " " << b << " " << c << endl;
}

int main() {
	// 理解bind函数的使用:
	int a = 1, b = 2, c = 3;
	
	auto cpre = std::bind(print, _1,_2,c);
	cpre(a, b);         // 输出: 1,2,3 （_1对应a，_2对应b。分别为可调用对象cpre的第1,2个参数。调用cpre时将调用cpre(_1,_2)，映射为print(_1,_2,c)，即print(a,b,c)）
	
	auto cpre1 = std::bind(print, _2, _1, c);
	cpre1(a, b);        // 输出: 2,1,3 （_1对应a，_2对应b。分别为可调用对象cpre的第1,2个参数。调用cpre时将调用cpre(_1,_2)，映射为print(_2,_1,c)，即print(b,a,c)）

	
	// 应用: 用bind参数"重排参数顺序":
	vector<string> vec{"a", "ccc", "bb"};
	std::sort(vec.begin(), vec.end(), isShorter);                    // vec={"a","bb","ccc"} （根据isShorter函数，实现从短到长排序）
	std::sort(vec.begin(), vec.end(), bind(isShorter, _2, _1));      // vec={"ccc","bb","a"} （在不改变isShorter函数 或不另外定义一个函数的条件下，实现从长到短排序）


	// 绑定引用参数
	vector<string> vec1{ "aaa","bbb","ccc" };
	std::for_each(vec1.begin(), vec1.end(), bind(print_s, ref(cout), _1));      // 输出: {"aaa","bbb","ccc"}  注: cout不能拷贝!（bind拷贝其参数，而我们不能拷贝一个ostream。如果我们希望传递给bind一个对象而又不拷贝它，就必须使用标准库ref函数）
	std::for_each(vec1.begin(), vec1.end(), bind(print_s, cout, _1));           // 错误: 默认情况下，cout被bind拷贝到 bind返回的可调用对象中，但是cout不允许拷贝
	std::for_each(vec1.begin(), vec1.end(), bind(print_s, &cout, _1));          // 错误: 必须使用ref函数（ref返回一个对象，包含给定的引用，此对象可以拷贝）
}

10.4 再探迭代器

(1) 插入迭代器：

1. back_inserter：创建一个使用 push_back的迭代器。
2. front_inserter：创建一个使用 push_front的迭代器。
3. inserter：创建一个使用 insert的迭代器。（除了接受一个容器，还接受一个 指向给定容器的迭代器，元素会被插入到 给定迭代器所指向的元素之前）

int main() {
	list<int> lst{ 1,2,3 };
	list<int> lst1{ 1,2,3 };

	auto inserter_iter=std::inserter(lst, lst.begin());      // 返回插入迭代器，该插入迭代器与lst绑定，值永远插在 迭代器lst.begin()指向的元素 之前（也就是插在1之前）
	inserter_iter = 4;        // lst={4,1,2,3} （4插在1之前）
	inserter_iter = 5;        // lst={4,5,1,2,3} （5插在1之前）

	// 其效果与上面代码一样
	auto iter = lst1.insert(lst1.begin(), 4);    // lst1={4,1,2,3} （iter指向新插入的值4）
	iter++;                                      // 通过递增使iter再次指向1
	iter = lst1.insert(iter, 5);                 // lst1={4,5,1,2,3} （注: 传给intsert的第一个参数不能是lst1.begin()，此时lst1.begin()指向4而不是1）


	// front_ inserter生成的迭代器 会将插入的元素序列 的顺序颠倒过来，而inserter和back_ inserter则不会
	list<int> lst2{ 1,2,3,4 };
	list<int> lst3, lst4, lst5;
	std::copy(lst2.begin(), lst2.end(), std::inserter(lst3, lst3.begin()));      // lst3={1,2,3,4}（每次插入的位置 都是在inserter返回的插入迭代器inserter_iter之前，而inserter_iter指向的位置是不变的。最终效果是顺序的）
	std::copy(lst2.begin(), lst2.end(), std::front_inserter(lst4));              // lst4={4,3,2,1}（每次插入的位置 都是在lst4.begin()之前，也就是当前插入元素 永远为lst4的第一个元素。最终效果是逆袭的）
	std::copy(lst2.begin(), lst2.end(), std::back_inserter(lst5));               // lst4={1,2,3,4}（每次插入的位置 都是在lst5.end()之前，也就是当前插入元素 永远为lst5的最后一个元素。最终效果是顺序的）
}

• front_ inserter生成的迭代器 会将插入的元素序列 的顺序颠倒过来，而inserter和back_ inserter则不会。
• 只有在容器支持push_front的情况下，我们才可以使用front_inserter；只有在容器支持push_back的情况下，我们才能使用back_inserter。

int main() {
	// 从cin对象中读取内容，并输出到"屏幕"上(要通过cout):
	std::istream_iterator<int> is_iter_int(cin);         // 从cin中读取int 到is_iter_int指向的流对象
	cout << *is_iter_int;                                // 返回is_iter_int指向的流对象中 读取的值，并输出


	// 从文件中读取内容，并输出到"屏幕"上(要通过cout):
	std::ifstream in_f("aaa.txt");                            // in_f从 当前项目所在文件夹中的 "aaa.txt"文本文件 中读取数据  （手动去创建这样的一个文件夹，并写入内容。代码创建并写也可以，去看第八章内容，为了方便，不再赘述）
	std::istream_iterator<string> is_iter_string(in_f);       // 从in_f对象中读取string
	cout << *is_iter_string;                                  // 输出的内容为 "aaa.txt"文本文件 中的内容
	in_f.close();

	
	// 使用istream_iterator 从标准输入中读取数据，存入一个vector: (方法一)
	vector<int> vec;
	std::istream_iterator<int> is_end;                   // 相当于istream尾后迭代器 （默认初始化的迭代器，相对于创建一个可以当作 尾后值 使用的迭代器）
	std::istream_iterator<int> is_iter_int1(cin);        // 从cin中读取int 到is_iter_int1指向的流对象 （这里触发第一次cin输入，作用是 初始化is_iter_int1指向的istream对象）

	while (is_iter_int1 != is_end) {          // 按Ctrl+z、Ctrl+d、输入EOF 都能退出循环（Ctrl+z一般用于string; Ctrl+d、输入EOF一般用于int）
		vec.push_back(*is_iter_int1++);       // 后置递增运算 "读取流"，返回迭代器的旧值; 解引用迭代器，获得从流读取的前一个值 （后置运算符的优先级 比解引用高）
	}                                         // 每一次递增运算都会触发"读取流"，也就触发输入cin，因为读取流和cin绑定（不用纠结为什么会触发，应该是重载了"运算符++"）
	

	// 使用istream_iterator 从标准输入中读取数据，存入一个vector: (方法二)
	std::istream_iterator<int> is_end1;            // 相当于istream尾后迭代器
	std::istream_iterator<int> is_iter_int2(cin);

	vector<int> vec1(is_iter_int2, is_end1);       // 我们用 一对表示元素范围的迭代器 来构造vec1（范围构造过程 需要肯定移动迭代器，就会自增，自增就会触发"读取流"。输入EOF后之后，is_iter_int2的值就与尾后迭代器相等，也就退出了"循环"）
	

	// 使用算法操作流迭代器:
	std::istream_iterator<int> is_iter_int3(cin), is_end2;

	int counts = std::accumulate(is_iter_int3, is_end2, 0);    // 该调用会计算出 从标准输入读取的值 的和。（原理和上例解释一样）
}

• 默认初始化的迭代器，相对于创建一个可以当作 尾后值 使用的迭代器。
• 对于一个绑定到流的迭代器，一旦其关联的流 遇到文件尾或遇到IO错误，迭代器的值就与 尾后迭代器相等。

int main() {
	vector<int> vec{ 1,2,3,4,5 };
	std::ostream_iterator<int>os_iter_int(cout, " ");        // 输出流迭代器os_iter_int 绑定到了cout对象。并且每次使用os_iter_int 向cout写入int值时，后面都会追加一个" "
															 // 特别注意: 也就是因为可以用"<<运算符"实现 cout<<int类型值，要是cout没有对输出的类型 定义<<运算符，就不允许!)
															
	// 用ostream_ iterator来输出值的序列: (推荐写法)												
	for (auto x : vec)	           // 输出: {1 2 3 4 5 }
		*os_iter_int++ = x;        // "我的理解"为: os_iter_int是指向cout对象的迭代器(相当于指针)，*os_iter_int=x 就相当于给cout赋值一样(但此时调用cout定义的"<<运算符" 将x写入cout对象，也就是写到屏幕)
		                           // 先调用后置递增，再解引用*，但是解引用* 用的是递增前的旧值。递增就相当于 往后移动更新cout, 接着再次往cout中写入一个值。（注意: 这只是站在 指针角度 去思考问题，指针和迭代器是有差异的，但是迭代器又在模仿指针行为）
									 


	// 等价方式: (但不推荐)
	for (auto x : vec)             // 输出: {1 2 3 4 5 }        
		os_iter_int = x;           // 作用在ostream_iterator上的 *、++运算符 虽然存在，但是返回值都是 迭代器本身 (相当于 *、++ 不做任何事情)。说明这么做是为了 模仿指针行为，
	                               // 好处: (1)在这种写法中，流迭代器的使用与其他迭代器的使用保持一致。 (2)如果想将此循环 改为操作其他迭代器类型，修改起来非常容易。(3)对于读者来说，此循环的行为也更为清晰。


	// 再次优化: (使用泛型算法copy 比循环更简洁)
	std::copy(vec.begin(), vec.end(), os_iter_int);        // 输出: {1 2 3 4 5 }
	                                                       // 总结: 流迭代器就相当于 流对象指针，在对流对象循环操作时 多利用流迭代器使用泛型算法。（"流思想": 不要把 用cout来输出内容 仅仅看作输出到窗口。是内容写入了cout流对象，只不过是因为cout绑定了窗口，才最终写到窗口）
} 

(3) 反向迭代器：

int main() {
	string line{ "abc,def,ghi" };

	// 打印字符串line中的 第一个单词:
	auto comma = find(line.cbegin(), line.cend(), ',');          // comma是指向字符串line中 第一个','的正向迭代器（从前往后找）
	cout << string(line.cbegin(), comma);                        // 输出: "aaa" （打印字符串line中 第一个','之前的内容，即第一个单词"aaa"）


	//  打印字符串line中的 最后一个单词:
	auto rcomma = find(line.crbegin(), line.crend(), ',');       // rcomma是指向字符串line中 最后一个','的反向迭代器（从后往前找）

	cout << string(line.crbegin(), rcomma);                      // 错误输出: "ihg" （逆向打印）
	cout << string(rcomma.base(), line.cend());                  // 正确输出: "ghi" （反向迭代器rcomma 通过调用base()成员函数，转换成相应 正向迭代器，从而实现正向打印）        
}                                       

• 不可能从一个 forward_list或流迭代器 创建反向迭代器。
• 反向迭代器通过调用 base()成员函数 获得相应的正向迭代器。（转换后的正向迭代器 和原反向迭代器 指向的并不是同一元素）

10.5 泛型算法结构

• 一些算法使用重载形式传递一个谓词。
• 接受一个元素值的算法 通常有一个不同名的版本。（如：加_if，接受一个谓词代替元素值）
• 区分拷贝元素的版本和不拷贝的版本：拷贝版本通常加_copy。

nique(beg, end);                     // 使用==运算符比较元素
unique(beg, end, comp);              // 使用comp比较元素

find(beg, end, val);                 // 查找输入范围中 val第一次出现的位置
find_if(beg, end, pred);             // 查找第一个 令pred为真的元素


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

remove_if(v1.begin(), v1.end(), [](int i){ return i%2; });                                 // 从v1中删除 奇数元素
remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), [](int i){ return i%2; });         // 将偶数元素 从vl拷贝到v2，v1不变

10.6 特定容器算法