======泛型算法======
C++ Primer 笔记 第十章\\
----
**泛型算法**（//Generic Algorithms//）是标准库提供的一系列的算法。与之前学到的针对于特定容器的操作相比，泛型算法有几个特点：
  * 不限定类型：可以应用到不同容器甚至 build-in 类型上
  * 主要使用迭代器操作
  * 实现的主要是算法的内容，比如排序、寻找等等
====概述====
泛型算法主要定义在两个头文件中：
  * ''<algorithm>'' 定义了绝大部分算法。
  * ''<numeric>'' 定义了一系列数值计算的算法。
泛型算法并不直接操作目标，而是主要通过维护**两个迭代器**（一首一尾）来进行对目标的遍历。比如使用 //find// 搜寻某个 //vector// 中的指定元素：
<code cpp>
int val = 42; // value we'll look for
// result will denote the element we want if it's in vec, or vec.cend() if not
auto result = find(vec.cbegin(), vec.cend(), val);
</code>
//find// 通过两个迭代器确定搜寻的范围，再通过 ''val'' 来确定要匹配的值，然后返回一个结果。由于操作的对象是迭代器，//find// 也可以用到别的容器上，比如 //list//：
<code cpp>
string val = "a value"; // value we'll look for
// this call to find looks through string elements in a list
auto result = find(lst.cbegin(), lst.cend(), val);
</code>
由于在 //build-in array// 中也可以通过 //begin()// 和 //end()// 函数实现类似于迭代器的功能，因此 find 也可以应用于 //build-in array//：
<code cpp>
int ia[] = {27, 210, 12, 47, 109, 83};
int val = 83;
int* result = find(begin(ia), end(ia), val);
</code>
==泛型算法如何工作==
泛型算法通过**迭代器**进行操作。比如之前的 //find// 的一个简单流程：
  - 访问第一个元素
  - 与目标值比较，如果匹配返回值说明找到，否则接着进行寻找
  - 如最终未能找到，返回指定值说明没有找到
我们发现这整个过程都没有任何与容器相关的操作。因此，只要是能使用迭代器访问元素的地方，//find// 就不需要依赖容器类型。

==算法、容器和迭代器的关系==

尽管泛型算法不依赖于容器，但是依赖于**容器元素类型**的操作。比如刚才 //find// 中比较元素的步骤，就必须根据元素指定的比较法则来进行。\\ \\ 
这意味着绝大多数的算法并没有对容器的直接操作；换句话说，泛型算法可能会改变容器元素的值，或者交换元素的位置，但**不会更改容器本身的大小**（不会**直接**做添删类操作）。

====初识泛型算法====
C++ 标准库中至少包含了 100 多种泛型算法。从体系上来看，绝大多数算法都是对一个“范围” 内的元素进行操作，而该范围一定是使用迭代器来表示。而真正体现算法差异性的是算法的内容。根据内容的不同，泛型算法可以分为三类：
  * 只读算法
  * 读/写算法
  * 元素重排序算法
===只读算法===


**只读算法**（//Read-Only Algorithms//）指读取但不会改变元素的算法。
==只读算法：accumulate==
//accumulate// 是一种常见的只读算法。该算法计算并返回**指定范围的元素之和**。该算法总共获取三个参数：
<code cpp>
accumulate(vec.cbegin(), vec.cend(), 0);
</code>
迭代器表示范围，第三个参数表示累加的**起始值**。需要注意的是，由于第三个参数参与了累加，因此隐含了两个条件：
  * 返回内的元素需要与第三个参数的类型必须相同，或是可以转化
  * 用于累积的元素定义了加法（可以相加）
基于这样的条件来判断，带有 //string// 的容器也能使用 //accumulate//：
<code cpp>
string sum = accumulate(v.cbegin(), v.cend(), string(""));
</code>
算法严格遵循这样的一致性。一个反例就是上例不能使用 literial 空字符串作为起始值，因为 ''const char*'' 类型并没有定义加法：
<code cpp>
string sum = accumulate(v.cbegin(), v.cend(), "");
</code>
<WRAP center round tip 100%>
除了需要使用算法返回的迭代器改变元素值的情况，只读算法都应该使用 //cbegin()// 与 //cend()// 表示范围。
</WRAP>

==只读算法：equal==
//equal// 是一种应用于两个序列的算法，用与比较连个序列是否相等。//equal// 获取的 parameter 为三个迭代器：前两个迭代器表示第一个序列的范围，第三个迭代器表示第二个序列的起始点：
<code cpp>
// roster2 should have at least as many elements as roster1
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
</code>
//equal// 通过对两个序列每个位置的对应元素进行比较来得出结果。其返回值为 ''bool''，序列相等则返回 ''true'' ，反之则为 ''false''。根据算法的特性，只要是可以进行 ''=='' 运算的元素序列，都可以使用 //equal// 进行比较。更详细的来说：
  * //equal// 可以比较不同类型的元素序列
  * //equal// 可以比较不同长度的元素序列
需要注意的是，由于 //equal// 算法从设计上来说需要查看第一个序列的所有元素，因此 //equal// 假定第二个序列的长度**不小于**第一个序列的长度。
===写算法===
写算法是 STL 中提供的，用于修改元素内容的算法。该类算法有个非常重要的使用前提：**确保被修改的容器足够大到装下算法需要修改的元素个数。**\\ \\ 
具体的来说，写算法大概分为三种：
  * 修改自身容器，即只接受一对迭代器。这种操作是安全的，因为可写的元素总是在范围内。
  * 使用一个序列修改另外一个序列：这种情况又可以细分为两种：
    * 接收**三个迭代器**的情况。头两个表示第一个序列的范围，第三个表示第二个序列的开头位置。这种情况下，算法会假定**第二个序列的长度大于等于第一个序列**；也就是我们必须确定第二序列足够的容量供修改。
    * 接收四个迭代器的情况：两个表示第一序列的范围，两个表示第二序列的范围。
==写算法：fill & fill_n==
fill 是一种常见的写算法，其所用是将范围类的元素全替换为指定值。它接收三个参数，前两个确定元素的范围，第三个数为指定值：
<code cpp>
fill(vec.begin(), vec.end(), 0); // reset each element to 0
</code>
//fill// 属于之前提到的修改当前序列本身的算法，因此操作是确认安全的。不过即便如此，我们也应该谨记**算法不会检查写操作**这个事实。 //fiil// 算法的另外一个变种 //fill_n//，使用迭代器 + 容器大小的形式表示输入范围；在这种情况下是需要用户来保证输入范围的合法性的：
<code cpp>
fill_n(vec.begin(), vec.size(), 0);
</code>
''vec.size()'' 在这里就是一个安全的值。但如果像下面这样的写就有问题了：
<code cpp>
vector<int> vec; // empty vector
// disaster: attempts to write to ten (nonexistent) elements in vec
fill_n(vec.begin(), 10, 0);
</code>
<WRAP center round important 100%>
总之需要谨记的是，算法不会检查容器本身，它只会假定容器具有写入的资格（足够大，并且可以容纳指定类型的元素）
</WRAP>

==确保被写容器拥有足够空间的手段：back_inserter==

我们可以用 //inserter// 类型的迭代器来来确保容器拥有足够的空间。与一般的迭代器不同，//inserter// 是一种用来**添加元素**到容器的迭代器。该类迭代器都定义在 ''<iterator>'' 头文件里面，以如下的方式向容器中添加元素：
  * 将迭代器绑定至容器中需要添加元素的位置
  * 向该迭代器指向的位置进行赋值
//back_inserter// 是 //insert_iterator// 的一种。它的作用是：
  * 获取容器的引用
  * 返回一个绑定到该容器的迭代器
  * 调用 //push_back()// 为该容器添加新元素
<code cpp>
vector<int> vec;
auto it = back_inserter(vec);
*it = 42;
</code>
该种类型的迭代器可以与写算法一起连用，达到循环新建容器元素并写入的效果：
<code cpp>
vector<int> vec;
fill_n(back_inserter(vec), 10, 0); //append 10 '0' to the end of vec
</code>
==写算法：copy & replace==
//copy// 是另一种常见的写算法，其功能是将源序列的内容复制到目标序列中。其接收三个迭代器（源序列范围 + 目标序列起始点），因此需要确保目标序列的容量足够大：
<code cpp>
int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)]; // a2 has the same size as a1
// ret points just past the last element copied into a2
auto ret = copy(begin(a1), end(a1), a2); // copy a1 into a2
</code>
//copy// 会返回一个迭代器，该迭代器指向**复制**结果的 //off-the-end// 位置，比如上例 ''ret'' 的值就是 ''a2'' 中最后一个元素的下一个位置。\\ \\ 
除此之外，其他某些算法也提供类似 copy 的功能，比如 //replace//，其功能是将指定范围内中的某个值替换为指定值：
<code cpp>
// replace any element with the value 0 with 42
replace(ilst.begin(), ilst.end(), 0, 42);
</code>
如果不想修改源序列的值，可以使用另外一个版本 //replace_copy()//。该算法会将替换的结果复制到一个新的容器中：
<code cpp>
// use back_inserter to grow destination as needed
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);
</code>
这里 使用了 //back_inserter()// 将复制的内容添加到 ''ivec'' 中。
===排序算法===
排序算法指改变容器内元素顺序的算法。
==排序算法：sort() & unique()==
常用的对容器元素排序的算法有：//sort()//, //unique()//。\\ \\ 

 <color #666>//**sort() 实现了什么功能？如何使用？**//</color> \\ \\ 
//sort()// 接收两个表示范围的迭代器，对范围内的元素按照 ''<'' 操作来排序（越小的越靠前）：
<code cpp>
sort(words.begin(), words.end());
</code>
 <color #666>//**unique() 实现了什么功能？如何使用？**//</color> \\ \\ 
//unique()// 接收两个表示范围的迭代器，返回一个迭代器：
<code cpp>
unique(words.begin(), words.end());
</code>
其机制稍微有些复杂：
  * 首先，其目的是**移除重复的元素**，创造一个不重复元素的序列
  * 其次，由于泛型算法的限制，//unique()// 使用了**移动元素**的方式来达到**移除重复元素**的效果。具体的实现办法就是将重复的元素都往序列**最后**的位置放；当确定了不重复序列时，返回一个指向该序列末位元素下一位的， "off-the-end" 迭代器。需要注意的是，**重复的元素并没有被删除**，只是从逻辑上来说他们已经不属于当前队列了。
  * 再次，//unique()// 移除重复元素的前提必须是**范围内相邻的重复元素**（//every consecutive group of equivalent elements//）。
可以看出 //unique()// 本身具有一定的局限性。比如想实现消除一个**无序**字符串序列里的**重复**元素，必须配合 //sort()// 和容器本身的 //erase()// 成员使用：
  * 首先通过排序，重复的元素会变得相邻。
  * 其次通过 //unique//  将重复的元素全移到末尾，并使用返回的 “off-the-end” 迭代器作为分界线，指定需要物理上删除的重复元素范围。
  * 最后通过 //earse()// 真正删除上述范围的元素。
<html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/unique.svg"  width="450"> </div> </html>\\ 
写成代码就是：
<code cpp>
vector<string> words; 
sort(words.begin(), words.end(); //sorting
end_unique = unique(words,begin(), words.end()); //move the dupilicated words to the end of the container, return a "boundary" sign 
words.erase(end_unique, words.end()); //use the sign to establish the range of the dupilicated elements, remove all of them in the range.
</code>
这种情况下，即使序列中一开始就没有重复元素（即 //unique()// 直接返回 ''word.end()'' 迭代器），//earse// 操作也是安全的，因为删除空范围是被允许的，不会造成任何影响。

====为算法定制比较策略====
某些比较算法采用默认的策略对元素进行比较，比如 ''=='' 或 ''<'' 这样的运算符。但某些情况下，由于元素不支持此类运算符（比如类元素），我们需要自行定制比较的策略。C++ 通过提供对应算法的特殊版本来解决这个问题。

===方式1：传递函数给算法===
这种特殊的版本以**传递函数的方式** 将定制的比较策略应用到算法中，其中函数即为我们制定的策略。以 //sort()// 为例。通常情况下, //sort()// 只拥有两个迭代器参数。而 //sort()// 的特殊版本则提供了第三个参数，我们称之为**谓词**（//predicates//）。
谓词如下的特性使其在这里实际上作为了定制策略的载体：
  * 它是一个**表达式**（可以是函数）
  * 它可以被算法调用
  * 它接收**元素**作为 argument（算法调用它对元素进行比较）
因此整个流程可以描述为：
  - 谓词装载定制的函数
  - 该函数接收元素作为 argument
  - 算法通过调用该函数完成定制策略下元素的比较：
<html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/predicate.svg"  width="400"> </div> </html>\\ \\ 
比如 //sort()//，如果我们想通过比较 //string// 元素长度的方式来比较大小，那么规则函数可以定义为：
<code cpp>
bool isShorter(const string &s1, const string &s2) {
    return s1.size() < s2.size();
}
</code>
接着直接通过带谓词的算法版本调用则可使用该规则完成排序：
<code cpp>
sort(words.begin(), words.end(), isShorter);
</code>
这里有两点需要注意：
  * 谓词可以接收的 parameter 是 1-2 个，parameter 的数量被称为**元**，即接收单个 parameter 的谓词被称为**一元谓词**（//unary predicate//），接收两个 parameter 的谓词被称为**二元谓词**（//binary predicate//）。
  * 由于谓词接收元素作为 argument，因此**元素的类型与谓词中函数 parameter 的类型需要匹配**。
==实例：谓词配合 stable_sort() 排序==
上例中，通过比较 //string// 长度得出来的结果很可能看起来不那么直观，因为规则只比较 //string// 的长度，因此长度相同的 //string// 会被无序的放在一起。如果希望结果看起来更直观，可以使用 //stable_sort()// 进行排序。 对于长度相等的 //string// 元素, //stable_sort()// 根据其开头字母，以字母表（//alphabet//）的顺序来进行排列。其用法与 //sort()// 相同：
<code cpp>
stable_sort(words.begin(), words.end(), isShorter);
</code>
===方式2：Lambda 表达式===

根据书中的实例：需要实现一个 ''biggies()'' 函数：该函数需要对所有长度大于 ''sz'' 的元素进行排序并输出：
<code cpp>
void biggies(vector<string> &words,
             vector<string>::size_type sz)
{
    elimDups(words); // put words in alphabetical order and remove duplicates
    // resort by length, maintaining alphabetical order among words of the same length
    stable_sort(words.begin(), words.end(), isShorter);
    // get an iterator to the first element whose size() is >= sz
    // compute the number of elements with size >= sz
    // print words of the given size or longer, each one followed by a space
}
</code>
例子中的另外一个要求是希望该函数可以作为自定义的策略提供给 //find_if()// 算法使用，用于定位所有满足条件 //string// 序列的头元素位置。
==find_if 简介==
//find_if()// 是一种排序算法。其功能是按指定条件对所有元素进行判断，并返回指向**第一个满足条件元素**的迭代器。通常情况下，该算法接收三个参数：一对表示范围的迭代器与一个**一元谓词**：
<code cpp>
find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
</code>
===Lambda 的基本概念===
==Lambda 表达式以及相关背景==
由于 //find_if()// 的谓词只能接收一个参数，因此拥有两个参数的 //biggies()// 不能直接作为自定义规则传递给该算法。C++ 提供了一个解决方案：**//Lambda//** 表达式，允许我们将拥有更多定制参数的规则传递给算法。有几个概念需要在了解 //Lambda// 之前熟悉一下：
 \\ \\ <color #666>//**算法可以接收的传递对象有什么特点？**//</color> \\ \\ 
总的来说，如果一个对象被称作**可调用对象**（//callable object//），那么它就是可以传递给算法的。
 \\ \\ <color #666>//**什么是可调用对象？**//</color> \\ \\
可调用对象是指可以对其使用调用运算符 ''()'' 的对象。该对象可以是对象，也可以是一个表达式。假设 ''e'' 是一个可调用的表达式，那么一个可调用的对象就可以表示为如下的形式：
<code cpp>
e(argment_list);
</code> 
加上本节的 //Lambda// 表达式，已知的可调用对象有四种：
  * 函数
  * 函数指针
  * //Lambda// 表达式
  * 重载了 ''()'' 运算符的类对象
==Lambda 表达式的组成与定义==

和函数相似，//Lambda// 表达式也是由一系列代码组成的代码单元。我们可以将其理解为一个 **//inline//** 的、**没有名字**的函数。//Lambda// 表达式 与函数有很多共同点：
  * 有 parameter list 与 返回值
  * 有函数体
但与函数稍微不同的是， //Lambda// 可以（通常）定义于函数的内部。其定义写法也采用了**尾置**的形式：
<code>[capture list] (parameter list) -> return type { function body }</code>

其中：
  *//Capture list// 表示需要使用的**函数局部变量**（多用于**规则函数的实参传递**，与 Lambda处于同一个作用域）
  *//Parameter list// 与普通函数相同。当被算法调用的时候，该 List 接收指定范围内的元素作为 parameter 。''()'' **可以省略**，代表不接收任何 argument
  *//Return type// 与普通函数相同，但必须用// trailing return// 的形式表示，**可以省略**
  *//Function body// 表示 //Lamaba// 表达式的内容。
需要注意的是，//Capture list// 与**函数体**在定义中是**不能省略**的。当位置的返回类型为**空**的时候，编译器通过函数体中的 ''return'' 语句来判断当前表达式的返回类型：
<code cpp>
auto f = [] { return 42; } //f returns an int
</code>
但如果这种情况下函数体中语句**不止一句**，则表达式的返回类型为 ''void''。\\ \\ 
除此之外，调用 lambda 表达式的方式与普通函数相同：
<code cpp>
cout << f() << endl; //print 42
</code>
==向 Lambda 传递参数==
lambda 表达式与普通函数接收 argument 的方式相同。唯一的区别是 lambda 表达式不能设置 default argument。因此 lambda 表达式接收的 argument 与自身的 parameter 永远相等。
\\ \\ 
之前见过的 //[[cs:programming:cpp:cpp_primer:10_algorithms#传递函数给算法|is_shorter()]]// ，与其功能完全一致的 lambda 如下所示：
<code cpp>
[](const string& s1, const string& s2) { return s1.size() < s2.size(); }
</code>
而之前使用 string 长度排序的 //stable_sort()// 就可以写成：
<code cpp>
stable_sort(word.begin(), word.end(), 
			[] (const string& s1, const string& s2) 
			{ return s1.size() < s2.size(); })
</code>
==使用 Capture list==
回到书中的例子。我们的目标是同时将上级函数 //biggie()// 的两个 parameter：一个 ''vector<string>&'' 类型的 ''word''、与长度 ''sz'' 传递给算法 //find_if()// 使用。在这里，我们使用 lambda 的 Capture list 对其所在函数中的变量进行**捕获**。\\ \\ 

捕获的意思是，当 lambda 想使用**上级函数**（//enclosing function//, or //surrounding function//）中的局部变量时，只需要将其添加到 ''[]'' 捕获列表中就可以：比如这里我们如果希望使用 ''sz''，则对应的规则 lambda 可以写成：
<code cpp>
[sz] (const string& s) { return s.size() >= sz; }
</code>
//Capture list// 允许我们捕获多个局部变量用于使用，只需要用 comma 隔开即可。需要注意的是，Capture list 遵循捕获后才能使用的原则；如果其为空，则意味着 lambda 无法使用任何上级函数的局部变量。
== lambda 与 find_if() 的连用==
此时我们的  lambda 只有一个参数 ''s''，因此满足 //find_if()// 需要一元谓词的条件。//find_if()// 会返回指向第一个满足条件元素的迭代器。该结果可以用与计算结果序列的长度，因此使用 ''wc'' 变量将其存储起来：
<code cpp>
auto wc = find_if(word.begin(), word.end(),
				 [sz] (const string& s)
				 { return s.size() >= sz; })
</code>
因为 ''word'' 是有序序列，使用 ''word.end() - wc'' 可以得到满足条件的序列有多长。使用之前定义的 //make_plural()// 函数可以对打印信息进行单双数的优化：
<code cpp>
cout << count << " " << make_plural(count, "word", "s") 
	 << "of length" << sz << " or longer" << endl;
</code>
==for_each() 简介==
//for_each()// 算法接收一个**可调用对象**，并使用序列中的**每个元素都调用该对象**。我们可以将该对象设置为打印功能的 lambda，来输出指定序列中所有的内容：
<code cpp>
for_each(wc, word.end(), [] (const string& s)
						 {cout << s << " "; })
cout << endl;
</code>
需要注意的是：
  * **只有上级函数中的局部变量，才需要捕获后使用**。除此之外，lambda 可以随意使用外部名字，比如这里的 ''cout''。
  * 只有 non-static 的局部变量需要经过 //Capture list// 捕获才能使用。local static varible，及其在函数外部的名字均可以直接被 lambda使用。 
==整个的 biggies 函数==
<code cpp>
void biggies(vector<string> &words, vector<string>::size_type sz) {
	
	//duplicates removed, the sequence in alphabetical order
	
	elim_dups(words); 
	
	//sort words by size, maintain the alphabetical order for words of the same length
	
	stable_sort(words.begin(), words.end(), 
			   [](const string& s1, const string& s2)
			   { return s1.size() < s2.size(); });

	//get the sequence range of the elements that has length >= sz

	auto wc = find_if(words.begin(), words.end(),
					 [sz](const string& s)
					 { return s.size() >= sz; });
	auto count = words.end() - wc;

	//print the additional info

	cout << count << " " << make_plural(count, "word", "s")
		 << " of length " << sz << " or longer " << endl;

	//print each element in the range

	for_each(wc, words.end(), 
			[](const string& s) { cout << s << endl; };
	cout << endl;

}
</code>
===Lambda 的捕获与返回===
在 lambda 被传递给算法的整个过程中，编译器主要做了两件事：
  * 当 lambda 被定义的时候，编译器生成了一个新的（没有名字）的 class type，这个 class type 对应被定义的 lambda。
  * 当传递 lambda 给算法时候，编译器创建了该 class type 的一个**对象**，并将该对象作为 argument 传递给算法。
捕获列表中的局部变量也是这个对象的一部分。根据参数的传递方式的不同，捕获列表中的变量也可以分为两种捕获方式：**值捕获**（//Capture by value//）与**引用捕获**（//Calture by reference//）。
==值捕获==
值捕获与值传递的方式一样，通过拷贝的方式传递参数；因此可以使用值捕获的变量**必须能被拷贝**。与函数不同的是，值捕获的变量在 lambda 被**创建**的时候就已经复制**初始化完毕**了，因此之后对原有变量的修改不会对 lambda 的捕获变量造成任何影响：
<code cpp>
/* caputure by value: change v1 doesn't not affect the capture list. */
void fcn1()
{
	size_t v1 = 42; // local variable
	// copies v1 into the callable object named f
	auto f = [v1] { return v1; };
	v1 = 0;
	auto j = f(); // j is 42; f stored a copy of v1 when we created it
}
</code>

==引用捕获==
另外一种方式是引用捕获，捕获列表中的元素是**上级函数中局部变量的引用**。由于捕获的是引用，因此通过该引用改变绑定的局部变量也会影响到 lambda：
<code cpp>
/* lambda captured a reference that refers to v1, changes v1 also changes the lambda.*/
void fcn2()
{
	size_t v1 = 42; // local variable
	// the object f2 contains a reference to v1
	auto f2 = [&v1] { return v1; };
	v1 = 0;
	auto j = f2(); // j is 0; f2 refers to v1; it doesn't store it
}
</code>
这种捕获方式也受传统引用传递方式规则的约束：
  * 该引用遵循任何一般变量引用的规则
  * 通过引用方式捕获的变量，在 lambda 执行的时候**必须存在**（特别需要注意上级函数的周期，因为引用的是局部变量）。
<color #666>//**哪些情况下一定会用到引用捕获？**//</color> \\ \\ 
在传递某些**不能被拷贝的参数**的情况下。比如我们想使用 //biggies()// 函数传递一个 ''ostream'' 对象给算法，就必须要用到引用捕获：
<code cpp>
void biggies(vector<string> &words, vector<string>::size_type size_type,
			 ostream& os = cout; char c = ' '){
	...
	//using fucntion parameter ostream and lambda to print
	for_each(words.begin(), words.end(), 
			[&os, c](const string& s) { os << s << c; };
	os << endl;
}
</code>
<color #666>//**哪些情况下不能使用引用捕获？**//</color> \\ \\
在函数**返回**自身 lambda 的情况下。通常，lambda 会作为一个对象返回。而此时，捕获列表中的局部变量会作为对象成员一起返回。由于局部变量的生命周期只到函数结束前，如果通过引用捕获获取变量，那返回的就是**指向不存在变量的引用**，这显然是不能被允许的。\\ \\ 
<color #666>//**使用捕获列表的建议？**//</color> \\ \\
一个总的原则是，尽可能的保证一个简单的捕获列表。只有在捕获间接访问对象（引用，指针）的时候，我们才需要确保其存在性（引用与存在的值绑定）和正确性（引用不修改绑定的值）。因此如果可能，尽可能避免**捕获间接访问对象**。
==隐藏捕获以及混用==
lambda 可以在不将变量写入捕获列表的情况下，通过符号 ''='' 或者 ''&'' 来指定对**所有局部变量**的捕获方式：
  * ''='' 代表使用值捕获
  * ''&'' 代表使用引用捕获
如果需要特殊指定某些变量的捕获方式，可以将需要指定的变量与上述符号混用，中间用逗号隔开：
<code cpp>
void biggies(vector<string> &words,
             vector<string>::size_type sz,
             ostream &os = cout, char c = ' ') 
{

    // os implicitly captured by reference; c explicitly captured by value
    for_each(words.begin(), words.end(),
	    	    [&, c](const string &s) { os << s << c; });
    // os explicitly captured by reference; c implicitly captured by value
    for_each(words.begin(), words.end(),
		    [=, &os](const string &s) { os << s << c; });
}
</code>
混用时需要注意几点：
  * 必须以符号 ''='' 或 ''&'' 开头
  * 列表中**显式捕获的变量**（逗号后的）必须形式上与隐式捕获的符号不同。比如以 ''='' 开头，后面的变量必须标注引用符号；反之则不能标注。

==Mutable Lambda==
<WRAP center round info 100%>
Mutable Lambda 只针对于**值捕获**，即捕获列表中的变量都是拷贝的情况。
</WRAP>

**在值捕获的情况下**，lambda 默认不能修改捕获列表中的变量拷贝。如果希望修改，可以使用关键字 ''mutable'' 定义 lambda： 
<code cpp>
void fcn3() {
	size_t v1 = 42;
	auto f = [v1] () mutable { return ++v1; };
	auto j = f(); //j = 43
}
</code>
需要注意这种情况下是不能省略参数列表的（本例中的 ''()''）。\\ \\ 
如果是**引用捕获**，那么是否能修改捕获的变量**只与引用的变量类型**有关系。如果引用的是 non-const 变量，那么就可以修改：
<code cpp>
void fcn4() {
	size_t v1 = 42; // local variable
	// v1 is a reference to a non const variable
	// we can change that variable through the reference inside f2
	auto f2 = [&v1] { return ++v1; };
	v1 = 0;
	auto j = f2(); // j is 1
}
</code>

==指定 Lambda 的返回类型==
lambda 在没有显式指定返回类型，且函数体中不单有 ''return'' 语句的情况下，默认返回形式为 ''void''。如果希望 lambda 返回期望的值，则必须显式指定返回类型：比如使用 //transfrom()// 对 vector 进行批量的修改。
\\ \\ 
先介绍一下 //transform()//。 //transform()// 是一种写算法。其作用是以可调用对象的结果**替换**目标序列中所有的元素。它接收 3 个迭代器与 1 个可调用对象：
  * 头两个对象指代输入序列的范围
  * 第三个迭代器指代源序列的起始点
  * 可调用对象代表要实施的操作
下列例子中，我们希望使用 lambda 对 ''vi'' 中的元素求绝对值。由于 lambda 的函数体不止一个语句，因此必须显式的指定返回类型：
<code cpp>
transform(vi.begin(), vi.end(), vi.begin(),
		 [](int i) -> int 
		 {if (i < 0) return -i; else return i; });
</code>
===方法3：参数绑定===
lambda 适合简单的规则；当需要大量重复使用规则，或是规则实现复杂时，函数是才是更好的选择。但当 lambda 使用捕获列表时，可传递的 parameter 并不受算法和谓词的限制；而函数本身无法替代该功能。\\ \\ 
为了解决这个问题，C++ 提供了 //bind()// 函数。该函数定义于 ''<functional>'' 头文件中，其作用是**适配**函数的 parameter 数量（//function apapter//）。//bind()// 会接收一个**可调用对象**，以及其对应的 parameter，然后返回一个**新的可调用对象**供算法调用。这个新的对象通过适配后，其 parameter 就能满足算法的要求。
==bind 与 placeholder==
以 //find_if()// 为例。该算法只能接收一元谓词，如果传递函数作为规则，则函数只能有一个 parameter。假设我们有一个 //check_size()// 的函数如下：
<code cpp>
bool check_size(const string &s, string::size_type sz) {
    return s.size() >= sz;
}
</code>
使用下面的写法可以得到一个新的函数 //check()//，该函数与 //check_size()// 功能相同，并且只有一个参数：
<code cpp>
auto check6 = bind(check_size, _1, 6); //check(s) call check_size(s, 6);
</code>
 <color #666>//**bind() 是如何达到函数适配的效果的？**//</color> \\ \\ 
实际上，//bind()// 通过接收一个可调用对象和一个 //argument list// 来产生新的可调用对象：
<code cpp>
auto newCallable = bind(callable, arg_list);
</code>
当调用 ''newCallable'' 的时候，我们实际上通过其调用了 ''callable''，并将绑定的参数同时传递给了 ''callable''。\\ \\ 
同时，之前的例子中存在 ''_1'' 这样的参数。该参数被称为 //Placeholder//，用于将源函数的某个 parameter 与新函数对应的 parameter **绑定**起来：比如我们希望在 //check6()// 中使用 //check_size()// 的 ''const string& s'' 参数，只需将 ''_1'' 添加到 //bind()// 参数列表中即可。
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/bind_mec_1.svg"  width="600"> </div> </html>\\ \\ 
''callable'' 中**没有被绑定的参数** 与 //placeholder// 绑定的参数共同组成 ''callable'' 的参数列表（//arg_list//），该部分将通过 //bind()// 一起传递给 ''newCallable'' 对象。比如上例中的 ''check6()'' 函数接受了两个参数，但自身的参数也只有被绑定的参数，也就是 ''s''，作为了自身的 parameter：
<code cpp>
string s = "hello";
bool b1 = check6(s);  // check6(s) calls check_size(s, 6)
</code>

比较一下这种写法与 lambda 的区别：
<code cpp>
auto wc = find_if(words.begin(), words.end(),
            [sz](const string &a);
            
auto wc = find_if(words.begin(), words.end(),
             bind(check_size, _1, sz));
</code>
很明显，没有被绑定的参数可以被视作接受**上级函数参数的载体**，比如：
<code cpp>
void biggies(vector<string> &words, vector<string>::size_type sz) {
    auto wc = find_if(words.begin(), words.end(),
             bind(check_size, _1, sz));
}
</code>
 ==参数绑定与 arguments==
需要注意的是，一旦确定 placeholder 的位置后，其与**被适配对象**和**新产生对象**中的 parameter 都会一一对应起来。利用 //bind()// 的这种功能，可以通过对 ''newCallable'' 中参数 (被绑定参数) 的重排序，来达到调整 ''callable'' 对象中被绑定参数位置的效果。比如 ''callable'' 对象为：
<code cpp>
auto g = bind(f,a, b, _2, c, _1));
</code>
由于 //placeholder// 与 ''newCallable'' 对象 ''g()'' 中的对应关系是按编号来排列的， 如果调用一个 ''g(X,Y)'' 的函数，实际上调用了：
<code cpp>
f(a,b,Y,c,X);
</code>
如果我们希望通过 ''g(X,Y)'' 调用的 ''f()'' 如下：
<code cpp>
f(a,b,X,c,Y);
</code>
那么需要替换 placeholder 在整个 argument list 中的位置即可：
<code cpp>
// g is a callable object that takes two arguments
auto g = bind(f, a, b, _1, c, _2)；
</code>
<html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/arg_binding.svg"  width="250"> </div> </html> \\ 
可以总结出来的是：
  * ''newCallable'' 中：placeholder 使用 **编号**与其参数对应，即 ''_1'' 对应 第一个参数，以此类推
  * ''callable'' 中：placeholder 与其绑定参数的**位置**对应。比如上例中 '' f(a,b,X,c,Y)''，如果将 ''X'' 与 ''Y'' 调换，那么对应的 placeholder 也需要调换位置。
==使用 bind 对参数重新排序==
在某些应用下，使用 //bind()// 重新安排参数顺序能达到改变函数本身功能的效果，比如： 
<code cpp>
// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);
// sort on word length, longest to shortest
sort(words.begin(), words.end(), bind(isShorter, _2, _1));
</code>
原本函数的功能是返回 ''A < B'' 的结果。经过 //bind()// 的参数交换后，函数定义的规则则变为了 ''B < A''，也就是我们实际调用的是 ''isShorter(B, A)''。
==使用 placeholder 的前提==
placeholder 定义于命名空间 ''placeholders'' 中。该命名空间定义于命名空间 ''std'' 中。因此，为了使用 placeholder，我们需要作出以下的声明：
<code cpp>
using std::placeholders::_1;
</code>
如果有多个 placeholder 存在，可以直接声明其所在命名空间来简化书写：
<code cpp>
using namespace std::placeholders;
</code>
这种写法可以允许我们使用 ''placeholders'' 空间中定义的所有名字。
==绑定引用 parameters==
lambda 通过捕获列表获取局部变量。//bind()// 中，对标捕获列表的变量是 argument list 中**没有被绑定的**变量；默认情况下，这些变量是通过**拷贝**的形式绑定到新函数中的。\\ \\ 
而某些对象是一定要通过引用传递的，比如之前提到的 ''ostream'' 对象。lambda 通过引用捕获传递该对象：
<code cpp>
//os is a local variable referring to an output stream
for_each(words.begin(), words.end(), [&os, c](const string &s) { os << s << c; });
</code>
如果我们希望在 bind 中以引用的形式传递该对象，那么需要使用库函数 //ref()//:
<code cpp>
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));
</code>
该函数还有传递 reference to const 的版本 //cref()//。这两个函数都被定义在 ''<functional>'' 头文件中。
<WRAP center round help 100%>
更早版本的 C++ 提供了 //bind1st()// 与 //bind2rd()// 两个函数实现绑定功能。由于其功能的局限性性（只能绑定第一个或者第二个参数），在 C++11 中已经被放弃了。现代 C++ 应该使用 bind() 替代。</WRAP>

====再探迭代器====
除了一般应用于容器的迭代器以外，STL 还额外定义了几种通用的迭代器：
  * 插入迭代器（//Inserter iterators//）：绑定容器并实现对该容器的元素插入操作。
  * 流迭代器（//Stream iterators//）：绑定 Stream 对象，并实现对该对象的遍历。
  * 反向迭代器（//Reverse iterators//）：从右往左移动的迭代器，除了 forward_list 都有该类迭代器。
  * 移动迭代器（//Move iterrators//）:  用移动元素取代拷贝元素的迭代器。
===插入迭代器===
插入迭代器拥有自身对应的**函数适配器**（//Inserter adoptor//）。这些适配器会接收一个容器对象，并**返回对应的插入迭代器**。元素的插入通过**向插入迭代器进行赋值**来进行，比如：
<code cpp>
it = 222; //it denotes the insert point
</code>
根据插入迭代器的不同，其插入的位置与调用的函数都有不同：
  * //front_inserter// 会创建调用 //c.push_front(val)// 的迭代器，在容器首部插入元素 ''val''
  * //back_inseter// 会创建调用 //c.push_back(val)// 的迭代器，在容器尾部插入元素 ''val''
  * //inserter// 会创建调用 //c.insert(val, pos)// 的迭代器，在迭代器 ''pos'' 指代的位置插入元素 ''val''
<WRAP center round important 100%>
使用插入迭代器的容器必须支持该迭代器对应的调用。
</WRAP>
<WRAP center round tip 100%>
插入迭代器支持 *，++, -- 等运算，但这些运算对其没有任何影响，统统会返回迭代器本身。
</WRAP>


==inserter==
成功 ''inserter(c, iter)'' 这种形式会得到一个迭代器。假设该迭代器为 ''it''，也就是：
<code cpp>
it = inserter(c, iter);
</code>
那么当我们在使用该迭代器进行插入操作的时候：
<code cpp>
it = 222;
</code>
实际上等同于：
<code cpp>
it = c.insert(it, 222);
++it;
</code>
这是因为 //inserter// 的插入操作，始终要保证插入的位置处于**初始插入点的前一位**。本例中，''iter'' 用于设定**第一次的**插入点，而 ''it'' 用于后期维护**本轮的**插入点。由于 //c.insert()// 会让 ''it'' 指向新插入的元素，为了**更新**插入点，每次插入结束后，''it'' 都会往后（右）移动一位，将当前位置重新指向**初始的插入点**，也就是由 ''iter'' 指定的初始位置：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/inserter_1.svg"  width="450"> </div> </html>
换句话说，插入的位置由 ''iter'' 决定。
==back_inserter==
//back_inserter// 的操作类似，只是因为 //back_inserter// 会调用 //push_back()//，因此**初始插入点已经被指定到了容器的尾部**：
<code cpp>
it = back_inserter(c);
it = 222;
it = 333;
//output
........, 222, 333
</code>
==front_inserter==
//front_inserter// 的使用方法与 //back_inserter// 一致。但由于 //push_front()// 的机制问题，导致**最后插入的元素永远在最开头**：
<code cpp>
it = back_inserter(c);
it = 222;
it = 333;
//output
333,222,.......
</code>
也就是插入的元素会以**倒序**的形式呈现。
<WRAP center round info 100%>
**插入迭代器** 也拥有 ++it, it++, *it 等操作。但与一般迭代器不同，这些操作对其均不构成任何影响，统统会返回 it。
</WRAP>
书中的一些例子：
<code cpp>
list<int> 1st = {1,2,3,4};
list<int> lst2, lst3;     // empty lists
// after copy  completes, 1st2 contains 4 3 2 1
copy(1st.cbegin(), lst.cend(), front_inserter(lst2));
// after copy completes, 1st3 contains 1 2 3 4
copy(1st.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));
</code>
===iostream 迭代器===
//iostream// 迭代器绑定一个 stream 对象，并将该 stream 视作一系列指定类型的元素进行读或写的操作。其中：
  * //istream_iterator//：读入 Input stream
  * //ostream_iterator//: 写 output stream
常见的操作如下表：
\\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer//stream_iterator_op.svg"  width="650"> </div> </html> \\ \\
==istream_iterator 的操作==
使用 //istream_iterator// 有两个前提：
  * 创建 istream_iterator 时需要指定其操作对象的**类型**
  * istream_iterator 使用 ''>>'' 运算符，因此被操作的对象必须**支持**该运算符
一些实例：
<code cpp>
istream_iterator<int> int_it(cin); //reads int from cin
istream_iterator<int> int_eof; //default init, end iterator value;
ifstrem in("file");
istream_iterator<string> str_it(in); //read string from "file"
</code>
通过 istream_iterator 可以将输入的内容存到 vector 中. 这里 vector 的创建可以直接使用  istream_iterator 表示范围：
<code cpp> 
vector<int> vec(ini_it, int_eof);
//read inputs into a vector
while(int_it != int_eof)
	vec.push_back(*int_it++);
</code>
==istream_iterator 与算法的配合使用==
某些算法可以使用一对 istream_iterator 作为参数来获取输入范围，比如 ''accumulate'': 
<code cpp>
istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof, 0) << endl;
</code>
该段代码实现了所有从输入端输入的值的累加。
==istream_iterator 与 lazy evaluation==
istream_iterator 读取数据采用的是 lazy evaluation 的机制；也就是说，我们不能保证 istream_iterator 对 stream 的读取是即时的。该读取过程会发生在对 istream_iterator 的解应用之前。通常情况该机制下没有什么影响，除了以下两种情况：
  * istream_iterator 创建后没被使用就被销毁了
  * 同时从两个 istream_iterator 读取同一段 stream
这两种情况下需要考虑该机制带来的影响。
==ostream_iterator 的操作==
ostream_iterator 可以绑定任意支持 ''<<'' 运算符的 stream 对象。 ostream_iterator 同时支持第二个 parameter。该 parameter 接收类型为 c-style string（或者字符）, 功能是为每个输出的元素后面都加上一段字符。这个参数在打印元素之间的空格时很方便：
<code cpp>
ostream_iterator<int> out_iter(cout, " ");
for (auto e : vec)
	*out_iter++ = e;
cout << endl;
</code>
当每次对 ostream_iterator 赋值时，写操作就会发生一次，同时还会附带上额外的空格字符。需要注意的是，由于解引用与自增对 ostream_iterator 无效，上述循环可以写成：
<code cpp>
for (auto e : vec)
	out_iter = e;
cout << endl;
</code>
但为了保证对迭代器使用的一致性，加上解引用与自增可以使代码的表意更加清楚。\\ \\ 
我们也可以使用 //copy// 算法来取代上述操作：
<code cpp>
copy(vec.begin(), vec.end(), out_iter);
cout << endl;
</code>
==stream 迭代器与 class type（实例）===
通过使用 stream 迭代器进行输入、输出与循环，之前 //Sales_data// 的合并打印书籍的程序可以改写成如下代码：
<code cpp>
istream_iterator<Sales_item> item_iter(cin), eof;
ostream_iterator<Sales_item> out_iter(cout, "\n");

//init the first book
Sales_item total = *item_iter;
//to the next input
++item_iter;

while(item_iter != eof) {
	//current book has the same isbn
	if(item_iter->isbn() == total.isbn())
		//accumulate
		total += *item_iter;
		//to the next input
		++item_iter;
	else {
		//print total for the current book
		out_iter = total;
		//start with the new book
		total = *item_iter;
		//to the next input
		++item_iter;
	}
}
//print the last book
out_iter = total;
</code>
几个要点：
  * 通过对 ''item_iter'' 的自增实现对整个 stream 内容的遍历
  * 通过对 ''item_iter'' 的解引用读入当前输入内容
  * 流迭代器也可以调用成员
  * ''out_iter'' 可以输出定义了 ''<<'' 操作的对象
===反向迭代器===
反向迭代器（//Reverse Iterators//）**从右往左**遍历整个容器。反向意味着自增自减操作与一般迭代器**相反**，比如反向迭代器的 ''++'' 意味着一般迭代器的 ''--''。\\ \\ 
除了 //forward_list//，所有的容器都有反向迭代器。反向迭代器写作 ''rbegin''，''rend''，以及其常量版本 ''crbegin'' & ''crend''。''rbegin'' 指代容器最后一个元素，而 ''rend'' 指代容器的 off-the-begin 元素：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/reverse_iter.svg"  width="250"> </div> </html>
==反向迭代器与其他迭代器的关系==
反向迭代器与一般迭代器的遍历过程正好相反。利用这一点可以方便我们进行做一些对容器末尾的操作。比如我们有一个 string ''line''，包含了几个 word, 中间以逗号隔开，找第一个被逗号隔开的 word 可以写成：
<code cpp>
// find the first element in a comma-separated list
auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;
</code>
如果想直接找最后一个被逗号隔开的 word, 则可以利用反向迭代器：
<code cpp>
auto rcomma = find(line.rcbegin(), line.rcend(), ",");
</code>
不过如果对其输出，返现这个 word 是反着输出的，比如
<code cpp>
//input
FIRST, MIDDLE, LAST
//output
TSAL
</code>
这是因为使用反向迭代器遍历容器时，是从右往左的。因此打印也是从右往左打印。不仅如此，由于 ''rcomma'' 也是反向迭代器，因此不能直接用于输出。正确的方式是以 ''rcomma'' 为起点，从左往右输出。这样做需要使用反向迭代器的成员 ''base'' 将其**转化为一般迭代器**：
<code cpp>
cout <<string(rcomma.base(), line.cend()) << endl;
</code>
同时需要注意的是，如果使用反向迭代器代表范围，那么该范围是一个**左闭右开**的区间，比如 $[crbegin(), rcomma)$ 在容器中表现的区间是 $(rcomma.base(), cend()]$。由于这样的原因，''rcomma'' 与 ''rcomma.base()'' 表示的实际上是**两个相邻的位置**：
\\ \\ \\ 
<html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/comma_base.svg"  width="400"> </div> </html> \\ \\
====泛型算法的结构====
根据算法要求的不同，迭代器可以分为如下五大类：
\\ \\ <html><div align="center"> <img src="/_media//programming/cpp/cpp_primer/iter_cate.svg"  width="400"> </div> </html> \\ \\
这五种类别的迭代器分别具有不同的读 / 写 / 遍历 / 随机访问属性。
===迭代器的五个类别===
 <color #666>//**迭代器通过什么进行分类？**//</color> \\ \\ 
迭代器按照其自身允许的操作来分类的。**高等级的迭代器支持低等级迭代器的所有操作**。
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/iter_hierarchy.svg"  width="600"> </div> </html>
\\ \\ <color #666>//**算法是如何选择迭代器的？**//</color> \\ \\ 
C++ 标准中指明了了每个算法对迭代器等级的最低要求。如果迭代器不满足该要求，则无法使用。比如 //find()// 算法对序列进行扫描和读取，因此至少要 //input iterator// 才能满足需求。\\ \\ 
但需要注意的是，很多编译器并不会对不满足要求的迭代器参数提出警告，因此使用之前一定要检查该参数是否满足要求。
==输入迭代器==
输入迭代器（//Input iterator//）:用于**读取**序列中的元素。其支持以下操作：
  * 比较**两个迭代器**相等性的操作（''=='', ''!=''）
  * **向前移动迭代器**的操作（''++'', prefix or postfix）
  * 迭代器**解应用**操作（''*it''），用于读取迭代器元素。该解引用操作只能在赋值操作的**右边**，也就是只能作为值赋值给别的对象。
  * 迭代器访问成员的操作（''it->mem''）
输入迭代器只能用于**顺序访问**。同时，输入迭代器只能**保证当前位置是有效**，因此当输入迭代器自增以后，其他指向同位置输入迭代器的有效性也不会再被保证，也就是 ''a = b'' 并不能确保 ''a++ = b++''。因此，输入迭代器只能用于 **single-pass** 的算法，比如 //find()//，//accumulate()// 等等。//istream_iterator// 也是输入迭代器。 
<WRAP center round tip 100%>
stream 是个很好的例子。对读取下一部分的 stream 内容会使之前部分的内容失效。如果我们通过某个迭代器控制读取，那么当该迭代器移位，其他所有的指向之前内容的迭代器都会失效。
</WRAP>
==输出迭代器==
输出迭代器（//Output Iteratrors//）用于向元素写入内容。它与输入迭代器的等级相同，唯一的区别是输出迭代器**只能写，不能读**。常见的使用的输出迭代器的算法有: //copy()//。//ostream_iterator// 也是输出迭代器。
==前向迭代器==
前向迭代器（//Forward iterators//）比输入 / 输出迭代器等级高。该迭代器同时支持对元素的读和写操作，并拥有所有输出 / 输出迭代器可进行的操作。\\ \\ 
除此之外，前向迭代器支持 //multi-pass// 的读写操作，也就是**可以对同一元素进行反复读写**。比如 //replace()//:
<code cpp>
template<class ForwardIt, class T>
void replace(ForwardIt first, ForwardIt last,
             const T& old_value, const T& new_value)
{
    for (; first != last; ++first) { 
        if (*first == old_value) {  //read ,1st r/w to iter "first"
            *first = new_value;  //write, 2rd r/w to iter "first"
        }
    }
}
</code>
可以看出 //replace()// 的实现中， //first// 迭代器支持对其指向元素的多次读写（多次读写意味着迭代器可以保存当前元素的状态）。同时，该算法的循环是单向的；因此 //replace()// 可以使用前向迭代器来完成算法的实现。\\ \\ 
其他常见的前向迭代器：//forward_list// 的成员迭代器。
==双向迭代器==
双向迭代器（//Bidirectional iterators//）的等级高于前向迭代器。其支持前向迭代器的所有操作，除此之外，双向迭代器支持对序列的**双向遍历**，也就是**同时支持迭代器的自增和自减操作**。使用双向迭代器的常见算法有 //reverse()//。除了 //forward_list// 以外的容器，都要求其**成员迭代器**的等级**不低于**双向得带器。
==随机访问迭代器==
随机访问迭代器（//Random-access iterators//）是迭代器类别中**等级最高**的迭代器。其不但支持之前所有迭代器支持的操作；并且还额外支持以下的操作：
  * 两个迭代器之前的**关系运算操作**（//<, <=, >, >=//），用于比较两个迭代器的相对位置
  * 单个迭代器的**移位**操作（//+, +=, -,-=//）
  * 两个迭代器的相减（''iter1 - iter2''），用于获取迭代器之间的**距离**
  * 下标操作（iter[n]），等同于移位再取对应元素的操作（''*(iter+n)''）
常见使用随机访问迭代器的例子有：//sort()// 算法，以及 //arrray//、//deque//、//string// 和 //vector// 的成员迭代器。
===算法形参的形式===
除开迭代器的分类以外，算法的 parameter 的形式也有助于算法的理解。通常情况下算法有如下四种形式的参数分布：
<code cpp>
alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);
</code>
一般的来说， ''beg/end'' 表示输入源， ''beg2/end2'' 代表算法额外的输入源，''dest'' 表示输出部分。
==使用 dest 参数的算法==
''dest'' parameter 指代的是某个**容器**，或是插入迭代器，或是输出迭代器：
  * ''dest'' 是**容器**：代表算法将会把得到的输出写到这个容器中的元素里
  * ''dest'' 是**插入**迭代器：添加元素到指定容器
  * ''dest'' 是**输出**迭代器：将得到的内容写到输出的 stream 中
采用 ''dest'' 参数的算法假定无论有多少数据，''dest'' 都具有足够的空间容纳这些输入。
==使用第二个输入源的算法==
有两种不同的形式用于指定第二个输入源：
  * ''beg2 / end2''，指代了第二个输入源的范围为 [beg2, end2)
  * ''beg2''，指代了第二个输入源的起始位置，并假定其范围不小于第一个输入源。
===算法的命名规范===
除开参数的规范，算法还遵循一系列命名和重载的规范。这些规范用于处理一些问题：
  * 如何替换默认的关系运算符 ''<'', ''==''
  * 决定算法结果写出的位置是其自身的输入范围，或是指定的 ''dest'' 对象。
==使用重载版本传递谓词的算法==
拥有重载版本的算法有如下的两个特点：
  * 使用额外的谓词参数来代替 ''<'' 或者 ''==''
  * 除此之外并没有额外的参数
比如：
<code cpp>
unique(beg, end); // uses the == operator to compare the elements
unique(beg, end, comp); // uses comp to compare the elements
</code>
==具有 if 版本的算法==
只接收**单个元素值**的算法通常都会有一个 ''_if'' 后缀的版本。该版本不属于重载，并且使用一个谓词来取代原版本中的元素值，比如：
<code cpp>
find(beg, end, val); // find the first instance of val in the input range
find_if(beg, end, pred); // find the first instance for which pred is true
</code>
提供 ''_if'' 是为了防止可能由重载带来的**歧义**。
==具有拷贝 / 不拷贝两种版本的算法==
这种算法多半存在于排序算法中。默认情况下，排序算法会将排序结果重新写入输入的序列中。不过这些算法往往会提供第二个版本，允许算法将结果写入到指定的位置。第二个版本往往以 ''_copy'' 的后缀结尾，比如：
<code cpp>
reverse(beg, end); // reverse the elements in the input range
reverse_copy(beg, end, dest);// copy elements in reverse order into dest
</code>
某些版本还会基于 ''_if'' 的版本提供 ''_copy'' 的版本，意味着该版本**会采取定制的策略，并将结果写到其他指定的位置**：
<code cpp>
// removes the odd elements from v1
remove_if(v1.begin(), v1.end(),
		 [](int i) { return i % 2; });
// copies only the even elements from v1 into v2; v1 is unchanged
remove_copy_if(v1.begin(), v1.end(), back_inserter(v2),
			  [](int i) { return i % 2; });
</code>
====容器专属的算法====
//List// 与 //Forward_list// 拥有专属的成员算法：//sort//、//merge//、//remove//、//reverse// 和 //unique//。特别是 //sort//，由于 泛型的 //sort// 算法需要随机访问迭代器, 而 //List// 和 //forward_list// 只能使用双向迭代器与前向迭代器，因此泛型 //sort// 算法不能应用与这两种容器上。\\ \\ 
除此之外，上述成员算法的泛型版本可以用于 //List// 类型，但代价太大。这是由于交换元素的方式不同：泛型版本需要通过输入序列来交换元素，而 //List// 只需要交换元素之间的**链接**即可完成元素的交换。因此，上述算法的专属版本**效率要高出很多**。\\ \\ 
//List// 专属的成员算法如下表所示。对于没有在列表中出现的算法，只要其需求的迭代器与 //List// 提**供的迭代器能正确匹配**，那么就不会存在效率上的差异。
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/list_algo_1.svg"  width="650"> </div> </html> 
==splice 成员==
//List// 与 //Forward_list// 都有其**独占**成员算法 //splice//。该算法为链表数据结构而专门设计，因此没有必要提供泛型版本：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/splice.svg"  width="650"> </div> </html>\\ \\ 
需要注意的是，在调用 //splice_after()// 的时候，如果希望从 ''flst2'' 移动全部的元素，需要使用：
<code cpp>
flst.splice_after(flst.begin(), flst2);
</code>
而不能使用
<code cpp>
flst.splice_after(flst.begin(), flst2, flst2.begin(), flst2.end());
</code>
第二种方法会丢失 ''flst2'' 中的第一位数。原因是 //forward_list// 中表示范围是从 ''flst.before_begin()'' 开始的。
==list 的成员算法会改变容器==
需要注意的是，即便 list 的成员算法与其泛型版本在功能上没有多大的区别，但一个重要的不同是 list 的成员算法会**修改对应的容器**。比如 //list.remove()// 会移除指定的元素，//list.unique()// 会将重复的元素真正的移除掉，而不是将其放到序列的末尾。 \\ \\ 
同样，//merge// 与 //splice// 也会删除其 argument。泛型版本的 //merge// 会将要合并的两个序列组合到一个新的目标序列中，而并不会改变两个源序列；而 List 版本的 //merge// 则会直接将新序列写入调用 //merge// 的 list 中。