What & How & Why

您在这里: start » cs » programming » cpp » cpp_primer » 10_algorithms

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:programming:cpp:cpp_primer:10_algorithms [2024/01/14 13:46] – 移除 - 外部编辑 (未知日期) 127.0.0.1cs:programming:cpp:cpp_primer:10_algorithms [2024/01/14 13:47] (当前版本) – ↷ 链接因页面移动而自动修正 codinghare
行 1: 行 1:
 + ======泛型算法======
 +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 中。