迭代器与算法

C++算法库定义了一系列函数，用于查找、排序、技术和操纵某个范围（range），这个范围是按照左闭右开的方式给出的，也就是容器迭代器中的[first,last)。从算法要求角度迭代器可以分为五类，分别是输入、输出、单向、双向和随机；迭代器的来源有两个地方：

• 通过调用容器成员（begin()、 end()之类的）
• 标准库iterator处理得到的

对于后者，可以分为插入、流、反向和移动四种。

一、迭代器方法及分类

迭代器是类模板，它定义了遍历容器的操作。那么这些操作有哪些呢？

1.1 迭代器方法

迭代器的基本操作：自增自减解引用返成员及判等，如果一个类重载了上述操作，那么就符合迭代器的概念。

在vector和string中，我们既可以通过下标访问其中的元素，也可以通过迭代器。之所以说迭代器更加通用，是因为不是所有的标准库都支持下标操作，但都支持迭代器操作。所以指针和迭代器有什么不一样？获取方式不同。指针通过取地址方式，迭代器通过成员函数（begin和end之类的）。对于不同容器，迭代器支持的操作可能不同。

所有迭代器都有的操作（自增自减解引用返成员及判等）：

操作含义*iter返回迭代器所指元素的引用（解引用）iter->mem解引用并返回mem成员++iter迭代器指向下一个元素–iter迭代器指向上一个元素iter1==iter2判断两个迭代器是否相等，如果解引用相同，则为真iter1!=iter2判断两个迭代器是否不等，如果解引用不同，则为真

有些迭代器可能支持额外的操作：

string和vector支持的额外操作含义iter+n迭代器加一个整数值仍为迭代器，和原位置相比向前移动了若干个元素。结果可能是容器内或尾部迭代器iter-n迭代器减一个整数值仍为迭代器，和原位置相比向后移动了若干个元素。结果可能是容器内或尾部迭代器iter1+=n迭代器复合加法语句，iter1+n的结果赋给iter1自身iter1-=n迭代器复合减法语句，iter1-n的结果赋给iter1自身iter1-iter2右侧迭代器向前移动若干个元素的得到左侧的迭代器，必须保证是同一个容器，结果是迭代器之间的距离（可正可负）>、>=、 5; }, 0);

注意：虽然名字似乎和forward_list相关（都是前向），这是最低要求，事实上所有标准库（string vector list forward_list deque）都能满足。

2.4 双向迭代器（bidirectional iterator）

双向迭代器与前向迭代器相比，多了一个方向，也就是反向扫描（--）。除了forward_list都有满足要求的双向迭代器（begin end），双向扫描。

2.5 随机访问迭代器（random-access iterator）

随机访问迭代器是可以在常数时间内访问到容器中的任意元素的能力。除了链表类的容器，都具有随机访问能力。

三、算法对迭代器的要求

算法内部可能对迭代器进行如下操作：

• 改写迭代器所指向的值
• 正反扫描容器中的值
• 解引用、访问某个数据成员

对应到迭代器就有：

• 读写要求
• 扫描方向要求
• 访问要求

我们在使用算法时只需要传递正确的迭代器进去即可。什么叫做不正确的！传递一个能力比较差的迭代器进去，如前面提到的fill_n，显然我们是需要改写迭代器的值的，就不能只传递一个输入迭代器。一般来说，使用算法如果你不是传递一个cend()和cbegin()之类的const迭代器，就不需要考虑读写之类的问题；如果你使用的不是链表之类的容器，那你总能使用所有的算法，毕竟除了链表，剩下的全是随机访问能力的容器了，已经算法最高要求了。

四、算法参数形式

绝大部分算法参数形式都属于以下形式中的一种：

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

可以看出，几乎所有算法都接受一个输入范围，是否有其他参数取决于要执行的操作。比较常见的参数就dest和beg2 end2两种，两者都是迭代器参数：

• dest 目标迭代器，算法假定了其需要写入参数，不管写多少都是安全的
• beg2 end2 它可以是完整的迭代器范围[beg2 end2 )；也可以是只指定[beg2， + ∞ +\infin +∞）也就是结束位置不确定，假定至少和完整迭代器一样大。

五、算法命名规范

除了参数规范外，算法还遵循一套命名和重载规范。当然，谓词也有一定的规范，如定义< ==以及拷贝原序列还是覆盖原序列。

5.1 重载，增加谓词

unique(beg,end);
unique(beg,end,comp);//comp定义了什么是unique

谓词丰富了算法的使用范围，将解释的权力交给程序员。

5.2 _if假设版本

相对于非if版本，_if版本将值换成了谓词。将value切确的值变成了模糊的、满足一定条件的元素。

find(beg,end,val);
find(beg,end,pred);//不再是切确的val,而是模糊的pred(如大于某个值)

5.3 _copy拷贝版本

相对于非copy版本，_copy不是直接"污染"源序列，而是给定一个新的迭代器（或迭代器范围），完全不改变原序列地完成算法结果的输出。

reverse(beg,end);
reverse(beg,end,dest);//不再是直接输出到原序列，而是输出在dest

5.4 _copy_if 拷贝假设版本

如：

remove_if(v1.begin(),v1.end(),[](int i){return i%2;});
remove_copy_if(v1.begin(),v1.end(),back_inserter(v2),[](int i){return i%2;});

5.5 特定容器算法

因为某些容器具备某些特征，通用算法可能需要独特定制。如list和forward_list，他们就针对其容器特点，定制了更加高效、合适的算法版本，不过他们是以成员函数的形式给出的。

//都返回void
lst.merge(lst2);//有序链表lst2 lst合并,使用