# Chapter 10 Generic Algorithms

# Overview

# 泛型算法

因为它们实现共同的操作，所以称之为 “算法”；而 “泛型”、指的是它们可以操作在多种容器类型上。
泛型算法本身不执行容器操作，只是单独依赖迭代器和迭代器操作实现。
头文件： #include <algorithm> 或者 #include <numeric> (算数相关)
大多数算法是通过遍历两个迭代器标记的一段元素来实现其功能。
必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但不能直接添加或者删除元素。

# find

vector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value);
输入：两个标记范围的迭代器和目标查找值。返回：如果找到，返回对应的迭代器，否则返回第二个参数，即标记结尾的迭代器。

# Exercise 10.1

头文件 algorithm 中定义了一个名为 count 的函数，它类似 find ，接受一对迭代器和一个值作为参数。 count 返回给定值在序列中出现的次数。编写程序，读取 int 序列存入 vector 中，打印有多少个元素的值等于给定值。

解：

见下题

# Exercise 10.2

重做上一题，但读取 string 序列存入 list 中。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <list>


	int main()
	{
	// 10.1
	std::vector<int> v = { 1, 2, 3, 4, 5, 6, 6, 6, 2 };
	std::cout << "ex 10.01: " << std::count(v.cbegin(), v.cend(), 6) << std::endl;

	// 10.2
	std::list<std::string> l = { "aa", "aaa", "aa", "cc" };
	std::cout << "ex 10.02: " << std::count(l.cbegin(), l.cend(), "aa") << std::endl;

	return 0;
	}

# A First Look at the Algorithms

# 初识泛型算法

标准库提供了超过 100 个算法，但这些算法有一致的结构。
理解算法的最基本的方法是了解它们是否读取元素、改变元素、重排元素顺序。

# 只读算法

只读取范围中的元素，不改变元素。
如 find 和 accumulate （在 numeric 中定义，求和）。
find_first_of ，输入：两对迭代器标记两段范围，在第一段中找第二段中任意元素，返回第一个匹配的元素，找不到返回第一段的 end 迭代器。
通常最好使用 cbegin 和 cend 。
equal ：确定两个序列是否保存相同的值。

# 写容器元素的算法

一些算法将新值赋予序列中的元素。
算法不检查写操作。
fill ： fill(vec.begin(), vec.end(), 0); 将每个元素重置为 0
fill_n ： fill_n(vec.begin(), 10, 0);
插入迭代器 back_inserter ：
- 用来确保算法有足够的空间存储数据。
- #include <iterator>
- back_inserter(vec)
拷贝算法 copy ：
输入：前两个参数指定输入范围，第三个指向目标序列。
copy (ilst.begin(), ilst.end(), back_inserter(ivec));
copy 时必须保证目标目的序列至少要包含与输入序列一样多的元素。

# 重排容器元素的算法

这些算法会重排容器中元素的顺序。
排序算法 sort ：
- 接受两个迭代器，表示要排序的元素范围。
消除重复 unique ：
- 之前要先调用 sort
- 返回的迭代器指向最后一个不重复元素之后的位置。
- 顺序会变，重复的元素被 “删除”。
- 并没有真正删除，真正删除必须使用容器操作。

# Exercise 10.3

用 accumulate 求一个 vector<int> 中元素之和。

解：

见下题。

# Exercise 10.4

假定 v 是一个 vector<double> ，那么调用 accumulate(v.cbegin(),v.cend(),0) 有何错误（如果存在的话）？

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <numeric>

	int main()
	{
	// Exercise 10.3
	std::vector<int> v = { 1, 2, 3, 4 };
	std::cout << "ex 10.03: " << std::accumulate(v.cbegin(), v.cend(), 0) << std::endl;

	// Exercise 10.4
	std::vector<double> vd = { 1.1, 0.5, 3.3 };
	std::cout << "ex 10.04: "
	<< std::accumulate(vd.cbegin(), vd.cend(), 0)
	<< std::endl; // ^<-- note here.
	// @attention
	//
	// The ouput is 4 rather than 4.9 as expected.
	// The reason is std::accumulate is a template function. The third parameter is _Tp __init
	// When "0" , an integer, had been specified here, the compiler deduced _Tp as
	// interger.As a result , when the following statments were being excuted :
	// for (; __first != __last; ++__first)
	// __init = __init + *__first;
	// return __init;
	// all calculation would be converted to integer.

	return 0;
	}

结果会是 int 类型。

# Exercise 10.5

在本节对名册（ roster ）调用 equal 的例子中，如果两个名册中保存的都是 C 风格字符串而不是 string ，会发生什么？

C 风格字符串是用指向字符的指针表示的，因此会比较两个指针的值（地址），而不会比较这两个字符串的内容。

# Exercise 10.6

编写程序，使用 fill_n 将一个序列中的 int 值都设置为 0。

解：

	#include <iostream>
	#include <vector>
	#include <algorithm>

	using std::vector; using std::cout; using std::endl; using std::fill_n;

	int main()
	{
	vector<int> vec{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	fill_n(vec.begin(), vec.size(), 0);

	for (auto i : vec)
	cout << i << " ";
	cout << endl;
	}

# Exercise 10.7

下面程序是否有错误？如果有，请改正：

	(a) vector<int> vec; list<int> lst; int i;
	while (cin >> i)
	lst.push_back(i);
	copy(lst.cbegin(), lst.cend(), vec.begin());
	(b) vector<int> vec;
	vec.reserve(10);
	fill_n(vec.begin(), 10, 0);

解：

(a) 应该加一条语句 vec.resize(lst.size()) 。 copy 时必须保证目标目的序列至少要包含与输入序列一样多的元素。
(b) reserve 分配了足够的空间，但是不会创建新元素。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，永远不会直接添加和删除元素 (c++ priemr 中文版第五版 P338)，所以此处应该改为 resize (10)。

# Exercise 10.8

本节提到过，标准库算法不会改变它们所操作的容器的大小。为什么使用 back_inserter 不会使这一断言失效？

back_inserter 是插入迭代器，在 iterator.h 头文件中，不是标准库的算法。

# Exercise 10.9

实现你自己的 elimDups 。分别在读取输入后、调用 unique 后以及调用 erase 后打印 vector 的内容。

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>

	// print containers like vector, deque, list, etc.
	template<typename Sequence>
	auto println(Sequence const& seq) -> std::ostream&
	{
	for (auto const& elem : seq)
	std::cout << elem << " ";
	return std::cout << std::endl;
	}

	auto eliminate_duplicates(std::vector<std::string> &vs) -> std::vector<std::string>&
	{
	std::sort(vs.begin(), vs.end());
	println(vs);

	auto new_end = std::unique(vs.begin(), vs.end());
	println(vs);

	vs.erase(new_end, vs.end());
	return vs;
	}

	int main()
	{
	std::vector<std::string> vs{ "a", "v", "a", "s", "v", "a", "a" };
	println(vs);
	println(eliminate_duplicates(vs));

	return 0;
	}

# Exercise 10.10

你认为算法不改变容器大小的原因是什么？

解：

将算法和容器的成员函数区分开。
算法的参数是迭代器，不是容器本身。

# Customizing Operations

# 定制操作

# 向算法传递函数：

谓词（ predicate ）：
- 是一个可调用的表达式，返回结果是一个能用作条件的值
- 一元谓词：接受一个参数
- 二元谓词：接受两个参数
例子：
- stable_sort ：
  - 保留相等元素的原始相对位置。
  - stable_sort(words.begin(), words.end(), isShorter);

# lambda 表达式

有时可能希望操作可以接受更多的参数。
lambda 表达式表示一个可调用的代码单元，可以理解成是一个未命名的内联函数。
形式： [capture list](parameter list) -> return type {function body} 。
- 其中 capture list 捕获列表是一个 lambda 所在函数定义的局部变量的列表（通常为空）。不可忽略。
- return type 是返回类型。可忽略。
- parameter 是参数列表。可忽略。
- function body 是函数体。不可忽略。
- auto f = [] {return 42;}
例子：
- find_if :
  - 接受一对表示范围的迭代器和一个谓词，用来查找第一个满足特定要求的元素。返回第一个使谓词返回非 0 值的元素。
  - auto wc = find_if(words.begin(), words.end(), [sz](const string &a){return a.size() >= sz;});
- for_each ：
  - 接受一个可调用对象，并对序列中每个元素调用此对象。
  - for_each(wc, words.end(), [](const string &s){cout << s << " ";})

# lambda 捕获和返回

定义 lambda 时会生成一个新的类类型和该类型的一个对象。
默认情况下，从 lambda 生成的类都包含一个对应该 lambda 所捕获的变量的数据成员，在 lambda 对象创建时被初始化。
值捕获：前提是变量可以拷贝， size_t v1 = 42; auto f = [v1] {return v1;}; 。
引用捕获：必须保证在 lambda 执行时，变量是存在的， auto f2 = [&v1] {return v1;};
尽量减少捕获的数据量，尽可能避免捕获指针或引用。
隐式捕获：让编译器推断捕获列表，在捕获列表中写一个 & （引用方式）或 = （值方式）。 auto f3 = [=] {return v1;}

lambda 捕获列表：

捕获列表	解释
`[]`	空捕获列表。 `lambda` 不能使用所在函数中的变量。一个 `lambda` 只有在捕获变量后才能使用它们。
`[names]`	`names` 是一个逗号分隔的名字列表，这些名字都是在 `lambda` 所在函数的局部变量，捕获列表中的变量都被拷贝，名字前如果使用了 `&` ，则采用引用捕获方式。
`[&]`	隐式捕获列表，采用引用捕获方式。 `lambda` 体中所使用的来自所在函数的实体都采用引用方式使用。
`[=]`	隐式捕获列表，采用值捕获方式。
`[&, identifier_list]`	`identifier_list` 是一个逗号分隔的列表，包含 0 个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。 `identifier_list` 中的名字前面不能使用 `&`
`[=, identifier_list]`	`identifier_list` 中的变量采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。 `identifier_list` 中的名字不能包括 `this` ，且前面必须使用 `&`

# 参数绑定

lambda 表达式更适合在一两个地方使用的简单操作。
如果是很多地方使用相同的操作，还是需要定义函数。
函数如何包装成一元谓词？使用参数绑定。
标准库 bind 函数：
- 定义在头文件 functional 中，可以看做为一个通用的函数适配器。
- auto newCallable = bind(callable, arg_list);
- 我们再调用 newCallable 的时候， newCallable 会调用 callable 并传递给它 arg_list 中的参数。
- _n 代表第 n 个位置的参数。定义在 placeholders 的命名空间中。 using std::placeholder::_1;
- auto g = bind(f, a, b, _2, c, _1); ，调用 g(_1, _2) 实际上调用 f(a, b, _2, c, _1)
- 非占位符的参数要使用引用传参，必须使用标准库 ref 函数或者 cref 函数。

# Exercise 10.11

编写程序，使用 stable_sort 和 isShorter 将传递给你的 elimDups 版本的 vector 排序。打印 vector 的内容，验证你的程序的正确性。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <numeric>
	#include <list>

	// print a container like vector, deque, list, etc.
	template<typename Sequence>
	inline std::ostream& println(Sequence const& seq)
	{
	for(auto const& elem : seq) std::cout << elem << " ";
	std::cout << std::endl;

	return std::cout;
	}


	inline bool
	is_shorter(std::string const& lhs, std::string const& rhs)
	{
	return lhs.size() < rhs.size();
	}


	void elimdups(std::vector<std::string> &vs)
	{
	std::sort(vs.begin(), vs.end());
	auto new_end = std::unique(vs.begin(), vs.end());
	vs.erase(new_end, vs.end());
	}


	int main()
	{
	std::vector<std::string> v{
	"1234", "1234", "1234", "Hi", "alan", "wang"
	};
	elimdups(v);
	std::stable_sort(v.begin(), v.end(), is_shorter);
	std::cout << "ex10.11 :\n";
	println(v);

	return 0;
	}

# Exercise 10.12

编写名为 compareIsbn 的函数，比较两个 Sales_data 对象的 isbn() 成员。使用这个函数排序一个保存 Sales_data 对象的 vector 。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include "../ch07/ex7_26.h" // Sales_data class.

	inline bool compareIsbn(const Sales_data &sd1, const Sales_data &sd2)
	{
	return sd1.isbn().size() < sd2.isbn().size();
	}

	int main()
	{
	Sales_data d1("aa"), d2("aaaa"), d3("aaa"), d4("z"), d5("aaaaz");
	std::vector<Sales_data> v{ d1, d2, d3, d4, d5 };

	// @note the elements the iterators pointing to
	// must match the parameters of the predicate.
	std::sort(v.begin(), v.end(), compareIsbn);

	for(const auto &element : v)
	std::cout << element.isbn() << " ";
	std::cout << std::endl;

	return 0;
	}

# Exercise 10.13

标准库定义了名为 partition 的算法，它接受一个谓词，对容器内容进行划分，使得谓词为 true 的值会排在容器的前半部分，而使得谓词为 false 的值会排在后半部分。算法返回一个迭代器，指向最后一个使谓词为 true 的元素之后的位置。编写函数，接受一个 string ，返回一个 bool 值，指出 string 是否有 5 个或更多字符。使用此函数划分 words 。打印出长度大于等于 5 的元素。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>

	bool predicate(const std::string &s)
	{
	return s.size() >= 5;
	}

	int main()
	{
	auto v = std::vector<std::string>{ "a", "as", "aasss", "aaaaassaa", "aaaaaabba", "aaa" };
	auto pivot = std::partition(v.begin(), v.end(), predicate);

	for (auto it = v.cbegin(); it != pivot; ++it)
	std::cout << *it << " ";
	std::cout << std::endl;

	return 0;
	}

# Exercise 10.14

编写一个 lambda ，接受两个 int ，返回它们的和。

auto f = [](int i, int j) { return i + j; };

# Exercise 10.15

编写一个 lambda ，捕获它所在函数的 int ，并接受一个 int 参数。 lambda 应该返回捕获的 int 和 int 参数的和。

解：

	int x = 10;
	auto f = [x](int i) { i + x; };

# Exercise 10.16

使用 lambda 编写你自己版本的 biggies 。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>

	// from ex 10.9
	void elimdups(std::vector<std::string> &vs)
	{
	std::sort(vs.begin(), vs.end());
	auto new_end = std::unique(vs.begin(), vs.end());
	vs.erase(new_end, vs.end());
	}

	void biggies(std::vector<std::string> &vs, std::size_t sz)
	{
	using std::string;

	elimdups(vs);

	// sort by size, but maintain alphabetical order for same size.
	std::stable_sort(vs.begin(), vs.end(), [](string const& lhs, string const& rhs){
	return lhs.size() < rhs.size();
	});

	// get an iterator to the first one whose size() is >= sz
	auto wc = std::find_if(vs.begin(), vs.end(), [sz](string const& s){
	return s.size() >= sz;
	});

	// print the biggies
	std::for_each(wc, vs.end(), [](const string &s){
	std::cout << s << " ";
	});
	}

	int main()
	{
	// ex10.16
	std::vector<std::string> v
	{
	"1234","1234","1234","hi~", "alan", "alan", "cp"
	};
	std::cout << "ex10.16: ";
	biggies(v, 3);
	std::cout << std::endl;

	return 0;
	}

# Exercise 10.17

重写 10.3.1 节练习 10.12 的程序，在对 sort 的调用中使用 lambda 来代替函数 compareIsbn 。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include "../ch07/ex7_26.h" // Sales_data class.

	int main()
	{
	Sales_data d1("aa"), d2("aaaa"), d3("aaa"), d4("z"), d5("aaaaz");
	std::vector<Sales_data> v{ d1, d2, d3, d4, d5 };

	std::sort(v.begin(), v.end(), [](const Sales_data &sd1, const Sales_data &sd2){
	return sd1.isbn().size() < sd2.isbn().size();
	});

	for(const auto &element : v)
	std::cout << element.isbn() << " ";
	std::cout << std::endl;

	return 0;
	}

# Exercise 10.18

重写 biggies ，用 partition 代替 find_if 。我们在 10.3.1 节练习 10.13 中介绍了 partition 算法。

解：

见下题

# Exercise 10.19

用 stable_partition 重写前一题的程序，与 stable_sort 类似，在划分后的序列中维持原有元素的顺序。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>

	// from ex 10.9
	void elimdups(std::vector<std::string> &vs)
	{
	std::sort(vs.begin(), vs.end());
	auto new_end = std::unique(vs.begin(), vs.end());
	vs.erase(new_end, vs.end());
	}


	// ex10.18
	void biggies_partition(std::vector<std::string> &vs, std::size_t sz)
	{
	elimdups(vs);

	auto pivot = partition(vs.begin(), vs.end(), [sz](const std::string &s){
	return s.size() >= sz;}
	);

	for(auto it = vs.cbegin(); it != pivot; ++it)
	std::cout << *it << " ";
	}


	// ex10.19
	void biggies_stable_partition(std::vector<std::string> &vs, std::size_t sz)
	{
	elimdups(vs);

	auto pivot = stable_partition(vs.begin(), vs.end(), [sz](const std::string& s){
	return s.size() >= sz;
	});

	for(auto it = vs.cbegin(); it != pivot; ++it)
	std::cout << *it << " ";
	}


	int main()
	{
	// ex10.18
	std::vector<std::string> v{
	"the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle"
	};

	std::cout << "ex10.18: ";
	std::vector<std::string> v1(v);
	biggies_partition(v1, 4);
	std::cout << std::endl;

	// ex10.19
	std::cout << "ex10.19: ";
	std::vector<std::string> v2(v);
	biggies_stable_partition(v2, 4);
	std::cout << std::endl;

	return 0;
	}

# Exercise 10.20

标准库定义了一个名为 count_if 的算法。类似 find_if ，此函数接受一对迭代器，表示一个输入范围，还接受一个谓词，会对输入范围中每个元素执行。 count_if 返回一个计数值，表示谓词有多少次为真。使用 count_if 重写我们程序中统计有多少单词长度超过 6 的部分。

解：

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>


	using std::vector;
	using std::count_if;
	using std::string;


	// Exercise 10.20
	std::size_t bigerThan6(vector<string> const& v)
	{
	return count_if(v.cbegin(), v.cend(), [](string const& s){
	return s.size() > 6;
	});
	}


	int main()
	{
	// ex10.20
	vector<string> v{
	"alan","moophy","1234567","1234567","1234567","1234567"
	};
	std::cout << "ex10.20: " << bigerThan6(v) << std::endl;

	// ex10.21
	int i = 7;
	auto check_and_decrement = [&i]() { return i > 0 ? !--i : !i; };
	std::cout << "ex10.21: ";
	while(!check_and_decrement())
	std::cout << i << " ";
	std::cout << i << std::endl;

	return 0;
	}

# Exercise 10.21

编写一个 lambda ，捕获一个局部 int 变量，并递减变量值，直至它变为 0。一旦变量变为 0，再调用 lambda 应该不再递减变量。 lambda 应该返回一个 bool 值，指出捕获的变量是否为 0。

解：

	int i = 10;
	auto f = [&i]() -> bool { return (i == 0 ? true : !(i--)); };
	while (!f()) cout << i << endl;

# Exercise 10.22

重写统计长度小于等于 6 的单词数量的程序，使用函数代替 lambda 。

	#include <iostream>
	#include <vector>
	#include <string>
	#include <algorithm>
	#include <functional>

	using std::string;
	using namespace std::placeholders;

	bool isLesserThanOrEqualTo6(const string &s, string::size_type sz)
	{
	return s.size() <= sz;
	}

	int main()
	{
	std::vector<string> authors{ "Mooophy", "pezy", "Queequeg90", "shbling", "evan617" };
	std::cout << count_if(authors.cbegin(), authors.cend(), bind(isLesserThanOrEqualTo6, _1, 6));
	}

# Exercise 10.23

bind 接受几个参数？

假设被绑定的函数接受 n 个参数，那么 bind 接受 n + 1 个参数。

# Exercise 10.24

给定一个 string ，使用 bind 和 check_size 在一个 int 的 vector 中查找第一个大于 string 长度的值。

解：

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <functional>


	using std::cout;
	using std::endl;
	using std::string;
	using std::vector;
	using std::find_if;
	using std::bind;
	using std::size_t;

	auto check_size(string const& str, size_t sz)
	{
	return str.size() < sz;
	}

	int main()
	{
	vector<int> vec{ 0, 1, 2, 3, 4, 5, 6, 7 };
	string str("123456");
	auto result = find_if(vec.begin(), vec.end(), bind(check_size, str, std::placeholders::_1));
	if (result != vec.end())
	cout << *result << endl;
	else
	cout << "Not found" << endl;

	return 0;
	}

# Exercise 10.25

在 10.3.2 节的练习中，编写了一个使用 partition 的 biggies 版本。使用 check_size 和 bind 重写此函数。

解：

	#include <iostream>
	#include <vector>
	#include <string>
	#include <algorithm>
	#include <functional>

	using std::string; using std::vector;
	using namespace std::placeholders;

	void elimdups(vector<string> &vs)
	{
	std::sort(vs.begin(), vs.end());
	vs.erase(unique(vs.begin(), vs.end()), vs.end());
	}

	bool check_size(const string &s, string::size_type sz)
	{
	return s.size() >= sz;
	}

	void biggies(vector<string> &words, vector<string>::size_type sz)
	{
	elimdups(words);
	auto iter = std::stable_partition(words.begin(), words.end(), bind(check_size, _1, sz));
	for_each(words.begin(), iter, [](const string &s){ std::cout << s << " "; });
	}

	int main()
	{
	std::vector<std::string> v{
	"the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle"
	};
	biggies(v, 4);
	}

# Revisiting Iterators

# 再探迭代器

# 插入迭代器

插入器是一种迭代器适配器，接受一个容器，生成一个迭代器，能实现向给定容器添加元素。
三种类型：
- back_inserter ：创建一个使用 push_back 的迭代器。
- front_inserter 创建一个使用 push_front 的迭代器。
- inserter 创建一个使用 insert 的迭代器。接受第二个参数，即一个指向给定容器的迭代器，元素会被查到迭代器所指向的元素之前。

插入迭代器操作：

操作	解释
`it=t`	在 `it` 指定的当前位置插入值 `t` 。假定 `c` 是 `it` 绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用 `c.push_back(t)` 、 `c.push_front(t)` 、 `c.insert(t, p)` ，其中 `p` 是传递给 `inserter` 的迭代器位置
`*it, ++it, it++`	这些操作虽然存在，但不会对 `it` 做任何事情，每个操作都返回 `it`

# iostream 迭代器

迭代器可与输入或输出流绑定在一起，用于迭代遍历所关联的 IO 流。
通过使用流迭代器，我们可以用泛型算法从流对象中读取数据以及向其写入数据。

istream_iterator 的操作：

操作	解释
`istream_iterator<T> in(is);`	`in` 从输入流 `is` 读取类型为 `T` 的值
`istream_iterator<T> end;`	读取类型是 `T` 的值的 `istream_iterator` 迭代器，表示尾后位置
`in1 == in2`	`in1` 和 `in2` 必须读取相同类型。如果他们都是尾后迭代器，或绑定到相同的输入，则两者相等。
`in1 != in2`	类似上条
`*in`	返回从流中读取的值
`in->mem`	与 `*(in).mem` 含义相同
`++in, in++`	使用元素类型所定义的 `>>` 运算符从流中读取下一个值。前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值。

ostream_iterator 的操作：

操作	解释
`ostream_iterator<T> out(os);`	`out` 将类型为 `T` 的值写到输出流 `os` 中
`ostream_iterator<T> out(os, d);`	`out` 将类型为 `T` 的值写到输出流 `os` 中，每个值后面都输出一个 `d` 。 `d` 指向一个空字符结尾的字符数组。
`out = val`	用 `<<` 运算符将 `val` 写入到 `out` 所绑定的 `ostream` 中。 `val` 的类型必须和 `out` 可写的类型兼容。
`*out, ++out, out++`	这些运算符是存在的，但不对 `out` 做任何事情。每个运算符都返回 `out` 。

# 反向迭代器

反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。
对于反向迭代器，递增和递减的操作含义会颠倒。
实现向后遍历，配合 rbegin 和 rend 。

# Exercise 10.26

解释三种插入迭代器的不同之处。

解：

back_inserter 使用 push_back 。
front_inserter 使用 push_front 。
inserter 使用 insert ，此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

# Exercise 10.27

除了 unique 之外，标准库还定义了名为 unique_copy 的函数，它接受第三个迭代器，表示拷贝不重复元素的目的位置。编写一个程序，使用 unique_copy 将一个 vector 中不重复的元素拷贝到一个初始化为空的 list 中。

解：

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <iterator>

	int main()
	{
	std::vector<int> vec{ 1, 1, 3, 3, 5, 5, 7, 7, 9 };
	std::list<int> lst;

	std::unique_copy(vec.begin(), vec.end(), back_inserter(lst));
	for (auto i : lst)
	std::cout << i << " ";
	std::cout << std::endl;
	}

# Exercise 10.28

一个 vector 中保存 1 到 9，将其拷贝到三个其他容器中。分别使用 inserter 、 back_inserter 和 front_inserter 将元素添加到三个容器中。对每种 inserter ，估计输出序列是怎样的，运行程序验证你的估计是否正确。

解：

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <iterator>
	using std::list; using std::copy; using std::cout; using std::endl;

	template<typename Sequence>
	void print(Sequence const& seq)
	{
	for (const auto& i : seq)
	std::cout << i << " ";
	std::cout << std::endl;
	}

	int main()
	{
	std::vector<int> vec{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	// uses inserter
	list<int> lst1;
	copy(vec.cbegin(), vec.cend(), inserter(lst1, lst1.begin()));
	print(lst1);

	// uses back_inserter
	list<int> lit2;
	copy(vec.cbegin(), vec.cend(), back_inserter(lit2));
	print(lit2);

	// uses front_inserter
	list<int> lst3;
	copy(vec.cbegin(), vec.cend(), front_inserter(lst3));
	print(lst3);
	}

前两种为正序，第三种为逆序，输出和预计一样。

# Exercise 10.29

编写程序，使用流迭代器读取一个文本文件，存入一个 vector 中的 string 里。

解：

	#include <iostream>
	#include <fstream>
	#include <vector>
	#include <string>
	#include <iterator>

	using std::string;

	int main()
	{
	std::ifstream ifs("../data/book.txt");
	std::istream_iterator<string> in(ifs), eof;
	std::vector<string> vec;
	std::copy(in, eof, back_inserter(vec));

	// output
	std::copy(vec.cbegin(), vec.cend(), std::ostream_iterator<string>(std::cout, "\n"));
	}

# Exercise 10.30

使用流迭代器、 sort 和 copy 从标准输入读取一个整数序列，将其排序，并将结果写到标准输出。

解：

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <iterator>

	using namespace std;

	int main()
	{
	vector<int> v;
	istream_iterator<int> int_it(cin), int_eof;

	copy(int_it, int_eof, back_inserter(v));
	sort(v.begin(), v.end());

	copy(v.begin(), v.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	return 0;
	}

# Exercise 10.31

修改前一题的程序，使其只打印不重复的元素。你的程序应该使用 unique_copy 。

解：

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <iterator>

	using namespace std;

	int main()
	{
	vector<int> v;
	istream_iterator<int> int_it(cin), int_eof;

	copy(int_it, int_eof, back_inserter(v));
	sort(v.begin(), v.end());
	unique(v.begin(), v.end());
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	return 0;
	}

# Exercise 10.32

重写 1.6 节中的书店程序，使用一个 vector 保存交易记录，使用不同算法完成处理。使用 sort 和 10.3.1 节中的 compareIsbn 函数来排序交易记录，然后使用 find 和 accumulate 求和。

解：

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <iterator>
	#include <numeric>
	#include "../include/Sales_item.h"

	int main()
	{
	std::istream_iterator<Sales_item> in_iter(std::cin), in_eof;
	std::vector<Sales_item> vec;

	while (in_iter != in_eof)
	vec.push_back(*in_iter++);
	sort(vec.begin(), vec.end(), compareIsbn);
	for (auto beg = vec.cbegin(), end = beg; beg != vec.cend(); beg = end) {
	end = find_if(beg, vec.cend(), [beg](const Sales_item &item){ return item.isbn() != beg->isbn(); });
	std::cout << std::accumulate(beg, end, Sales_item(beg->isbn())) << std::endl;
	}
	}

# Exercise 10.33

编写程序，接受三个参数：一个输入文件和两个输出文件的文件名。输入文件保存的应该是整数。使用 istream_iterator 读取输入文件。使用 ostream_iterator 将奇数写入第一个输入文件，每个值后面都跟一个空格。将偶数写入第二个输出文件，每个值都独占一行。

解：

	#include <fstream>
	#include <iterator>
	#include <algorithm>

	int main(int argc, char **argv)
	{
	if (argc != 4) return -1;

	std::ifstream ifs(argv[1]);
	std::ofstream ofs_odd(argv[2]), ofs_even(argv[3]);

	std::istream_iterator<int> in(ifs), in_eof;
	std::ostream_iterator<int> out_odd(ofs_odd, " "), out_even(ofs_even, "\n");

	std::for_each(in, in_eof, [&out_odd, &out_even](const int i)
	{
	*(i & 0x1 ? out_odd : out_even)++ = i;
	});

	return 0;
	}

# Exercise 10.34

使用 reverse_iterator 逆序打印一个 vector 。

解：

	#include <iostream>
	#include <vector>

	using namespace std;

	int main()
	{
	vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	for (auto it = v.crbegin(); it != v.crend(); ++it)
	{
	cout << *it << endl;
	}

	return 0;
	}

# Exercise 10.35

使用普通迭代器逆序打印一个 vector 。

解：

	#include <iostream>
	#include <vector>

	using namespace std;

	int main()
	{
	vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	for (auto it = std::prev(v.cend()); true; --it)
	{
	std::cout << *it << " ";
	if (it == v.cbegin()) break;
	}
	std::cout << std::endl;

	return 0;
	}

# Exercise 10.36

使用 find 在一个 int 的 list 中查找最后一个值为 0 的元素。

解：

	#include <iostream>
	#include <list>
	#include <algorithm>

	using namespace std;

	int main()
	{
	list<int> l = { 1, 2, 0, 4, 5, 6, 7, 0, 9 };
	auto it = find(l.crbegin(), l.crend(), 0);

	cout << distance(it, l.crend()) << endl;
	return 0;
	}

# Exercise 10.37

给定一个包含 10 个元素的 vector ，将位置 3 到 7 之间的元素按逆序拷贝到一个 list 中。

解：

	#include <iostream>
	#include <list>
	#include <algorithm>
	#include <vector>
	#include <iterator>

	using namespace std;

	int main()
	{
	vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	list<int> l;

	copy(v.crbegin() + 3, v.crbegin() + 8, back_inserter(l));

	for (auto i : l) std::cout << i << " ";
	cout << endl;
	return 0;
	}

# Structure of Generic Algorithms

# 泛型算法结构

# 5 类迭代器

迭代器类别	解释	支持的操作
输入迭代器	只读，不写；单遍扫描，只能递增	`==` , `!=` , `++` , `*` , `->`
输出迭代器	只写，不读；单遍扫描，只能递增	`++` , `*`
前向迭代器	可读写；多遍扫描，只能递增	`==` , `!=` , `++` , `*` , `->`
双向迭代器	可读写；多遍扫描，可递增递减	`==` , `!=` , `++` , `--` , `*` , `->`
随机访问迭代器	可读写，多遍扫描，支持全部迭代器运算	`==` , `!=` , `<` , `<=` , `>` , `>=` , `++` , `--` , `+` , `+=` , `-` , `-=` , `` , `->` , `iter[n]` == `(iter[n])`

# 算法的形参模式

alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);

其中， alg 是算法名称， beg 和 end 表示算法所操作的输入范围。 dest 、 beg2 、 end2 都是迭代器参数，是否使用要依赖于执行的操作。

# 算法命名规范

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

# Exercise 10.38

列出 5 个迭代器类别，以及每类迭代器所支持的操作。

输入迭代器 : == , != , ++ , * , ->
输出迭代器 : ++ , *
前向迭代器 : == , != , ++ , * , ->
双向迭代器 : == , != , ++ , -- , * , ->
随机访问迭代器 : == , != , < , <= , > , >= , ++ , -- , + , += , - , -= , * , -> , iter[n] == *(iter+n)

# Exercise 10.39

list 上的迭代器属于哪类？ vector 呢？

list 上的迭代器是 双向迭代器
vector 上的迭代器是 随机访问迭代器

# Exercise 10.40

你认为 copy 要求哪类迭代器？ reverse 和 unique 呢？

copy 需要两个输入迭代器，一个输出迭代器
reverse 需要双向迭代器
unique 需要随机访问迭代器

# Exercise 10.41

仅根据算法和参数的名字，描述下面每个标准库算法执行什么操作：

	replace(beg, end, old_val, new_val);
	replace_if(beg, end, pred, new_val);
	replace_copy(beg, end, dest, old_val, new_val);
	replace_copy_if(beg, end, dest, pred, new_val);

解：

replace 在迭代器范围内用新值替换所有原来的旧值。
replace_if 在迭代器范围内，满足谓词条件的元素用新值替换。
replace_copy 复制迭代器范围内的元素到目标迭代器位置，如果元素等于某个旧值，则用新值替换
replace_copy_if 复制迭代器范围内的元素到目标迭代器位置，满足谓词条件的元素用新值替换

# Container-Specific Algorithms

# 特定容器算法

对于 list 和 forward_list ，优先使用成员函数版本的算法而不是通用算法。

list 和 forward_list 成员函数版本的算法：

操作	解释
`lst.merge(lst2)`	将来自 `lst2` 的元素合并入 `lst` ，二者都必须是有序的，元素将从 `lst2` 中删除。
`lst.merge(lst2, comp)`	同上，给定比较操作。
`lst.remove(val)`	调用 `erase` 删除掉与给定值相等 (==) 的每个元素
`lst.remove_if(pred)`	调用 `erase` 删除掉令一元谓词为真的每个元素
`lst.reverse()`	反转 `lst` 中元素的顺序
`lst.sort()`	使用 `<` 排序元素
`lst.sort(comp)`	使用给定比较操作排序元素
`lst.unique()`	调用 `erase` 删除同一个值的连续拷贝。使用 `==` 。
`lst.unique(pred)`	调用 `erase` 删除同一个值的连续拷贝。使用给定的二元谓词。

上面的操作都返回 void

list 和 forward_list 的 splice 成员函数版本的参数：

参数	解释
`(p, lst2)`	`p` 是一个指向 `lst` 中元素的迭代器，或者一个指向 `flst` 首前位置的迭代器。函数将 `lst2` 中的所有元素移动到 `lst` 中 `p` 之前的位置或是 `flst` 中 `p` 之后的位置。将元素从 `lst2` 中删除。 `lst2` 的类型必须和 `lst` 相同，而且不能是同一个链表。
`(p, lst2, p2)`	同上， `p2` 是一个指向 `lst2` 中位置的有效的迭代器，将 `p2` 指向的元素移动到 `lst` 中，或将 `p2` 之后的元素移动到 `flst` 中。 `lst2` 可以是于 `lst` 或 `flst` 相同的链表。
`(p, lst2, b, e)`	`b` 和 `e` 表示 `lst2` 中的合法范围。将给定范围中的元素从 `lst2` 移动到 `lst` 或 `first` 中。 `lst2` 与 `lst` 可以使相同的链表，但 `p` 不能指向给定范围中的元素。

使用 lst.splice(args) 或 flst.splice_after(args)

# Exercise 10.42

使用 list 代替 vector 重新实现 10.2.3 节中的去除重复单词的程序。

解：

	#include <iostream>
	#include <string>
	#include <list>

	using std::string; using std::list;

	void elimDups(list<string> &words)
	{
	words.sort();
	words.unique();
	}

	int main()
	{
	list<string> l = { "aa", "aa", "aa", "aa", "aasss", "aa" };
	elimDups(l);
	for (const auto& e : l)
	std::cout << e << " ";
	std::cout << std::endl;
	}

# Chapter Summary

🍓：）