迭代器和算法结构 | 彩潭有鲤的札记

type

status

date

slug

summary

iterator

除了定义在每个容器中的迭代器，标准库还在iterator 头文件中定义了几种别的迭代器：

插入迭代器（Insert iterators）：这些迭代器绑定到容器上，并且可用于往容器中插入元素

流迭代器（Stream iterators）：这些迭代器绑定到输入输出流上，并可用于迭代相关的 IO 流

反向迭代器（Reverse iterators）：这些迭代器向后移动而不是向前移动，除了 forward_list 之外都提供反向迭代器

移动迭代器（Move iterators）：特殊的迭代器用于移动元素而不是拷贝

插入迭代器

插入器（inserter）是一个迭代器适配器，以一个容器为参数，生成一个可以插入元素的迭代器。当通过插入迭代器赋值时，迭代器将调用容器的操作添加一个元素到指定的位置。这些迭代器支持的操作包括：

有三种不同种类的插入器，区别在于元素插入到哪个位置：

back_inserter() 这个迭代器调用容器的 push_back

front_inserter() 这个迭代器调用容器的 push_front

inserter() 这个迭代器调用 insert，inserter 有第二个参数，并且这个参数必须是容器中的迭代器。元素被插入到给定迭代器所表示的元素前面

只有容器有 push_front 函数时才能用 front_inserter ，同样只有容器有 push_back 时才能用 back_inserter。

当调用 inserter(c, iter) 时，如果连续向其赋值会把元素顺序的插入到这个迭代器所表示的元素之前。而 front_inserter 生成的迭代器的行为与 inserter 生成的迭代器有很大的不同。当使用 front_inserter 时，元素总是被插入到首元素之前，意味着后面插入的元素在前面插入的元素之前。而 inserter 生成的迭代器刚好相反，后面插入的元素在前面插入的元素之后：

iostream 迭代器

尽管 iostream 类型不是容器，依然可以在 IO 类型上使用迭代器。istream_iterator 读取输入流，ostream_iterator 写输出流。这些迭代器将其对应的流当作特定类型元素的序列。使用流迭代器，可以使用通用算法对流对象进行读写。

以下是 istream_iterator 的操作：

当创建流迭代器时，需要指定元素的类型。istream_iterator 使用 >> 读取流。因而这个元素类型必须要有 >> 操作符才行。在创建 istream_iterator 时可以将其绑定到一个流上，或者当默认初始化时，创建的迭代器被当作尾后值：

只有当要给迭代器绑定的流到达了文件尾部或者遇到了 IO 错误时才会等于 end 迭代器。以下是利用 istream_iterator 读取流中的数据并存储到 vector 中：

以及用 istream_iterator 用于初始化 vector：

将流迭代器用于算法

由于算法是在迭代器上进行的，并且流迭代器支持一些迭代器操作。算法是按照迭代器分类决定哪些迭代器是可以用于此算法的。如 accumulate 可以用于一对 istream_iterator：

istream_iterator 允许延迟计算

当将 istream_iterator 绑定到流时，并没有说会立即读取这个流。实现会推迟到使用迭代器时才读取流。标准库保证当第一次解引用迭代器前，流是被读取了的。对于大部分程序来说，是立即读取还是延迟读取是没有关系的。然而，如果在同一个流上同时绑定了两个迭代器，此时就要当心了。

以下是 ostream_iterator 的操作：

ostream_iterator 可以定义在任何有 << 操作符的元素类型。创建 ostream_iterator 时可以提供第二参数是一个字符串，这个字符串必须是 C 风格字符串，它将在任何元素打印之前先打印。ostream_iterator 必须与特定的流绑定，并且没有尾后迭代器。

使用 ostream_iterator 写入一系列的值：

每次赋值给 out_iter 时都会提交一个写入操作。需要注意的是其实我们可以省略解引用和自增操作，这两个操作并没有什么作用。但是现在这种写法是更好的，原因是更符合习惯，并且可以很容器的替换为别的迭代器类型。

除了自己写循环之外，还可以调用 copy 算法：

反向迭代器

反向迭代器是一种反向遍历容器的迭代器。反向迭代器反转了自增和自减的含义。自增一个反向迭代器会将迭代器移动到前一个元素；自减则会将迭代器移动到下一个元素。

除了 forward_list 的容器都有反向迭代器。通过调用 rbegin，rend，crbegin 和 crend 成员函数来获取反向迭代器。这些成员返回指向最后一个元素和首前位置的迭代器。与正常的迭代器一样，反向迭代器分为 const和非 const 的。

在反向迭代器上调用 sort 将容器中的元素按照相反的顺序排序：

反向迭代器需要自减操作符

只有同时支持自减和自增操作符的迭代器才能定义反向迭代器。毕竟反向迭代器的目的就是为了让迭代器反向移动。除了 forward_list ，所有标准容器的迭代器都同时支持自减和自增操作。流迭代器不支持自减操作，毕竟它不能反向移动。

反向迭代器和其它迭代器之间的关系

reverse_iterator 有一个 base 成员，返回其对应的正常迭代器。反向迭代器的正常迭代器指向的位置与反向迭代器本身是不一样的，正常迭代器指向的位置是下一个位置。

5类迭代器

算法的基本特性是它对于迭代器的要求。有些算法如 find 只需要能够通过迭代器进行元素访问、自增迭代以及比较两个迭代器相等性。有些算法如 sort 需要可以进行读、写和随机访问元素。算法要求的迭代器操作被分类为五种迭代器类别（iterator categories），每个算法都说明了其每个迭代器参数所属的类别：

另一种对算法进行分类的方法是他们是否对元素进行读，写或者重排序。算法还共享一组参数传递规范和明明规范。

容器	对应的迭代器类型
array	随机访问迭代器
vector	随机访问迭代器
deque	随机访问迭代器
list	双向迭代器
set / multiset	双向迭代器
map / multimap	双向迭代器
forward_list	前向迭代器
unordered_map / unordered_multimap	前向迭代器
unordered_set / unordered_multiset	前向迭代器
stack	不支持迭代器
queue	不支持迭代器

与容器一样，迭代器定义一组公共操作。一些操作是所有迭代器都会提供的；其它一些操作则只有特定种类的迭代器会提供。如 ostream_iterator 只能进行递增，解引用和赋值。vector，string 和 deque 的迭代器除了支持这些操作外，还支持递减、关系和算术运算。

迭代器按照他们提供的操作进行分类，并且组成了某种形式的层级。除了输出迭代器，如果一个迭代器处于更高的层级那么它将提供低层级迭代器的所有操作。

C++标准说明了通用和数字算法对迭代器参数所要求的最低层级。如 find 最低要求需要输入迭代器。replace 函数需要一对迭代器至少是前向迭代器。同样，replace_copy 要求其前两个迭代器至少得是前向迭代器。其第三个迭代器至少得是输出迭代器。对于每个迭代器，至少得是要求的最低层级，传递更低层级的迭代器是一种错误。注：大多数迭代器在我们传递错误的迭代器类别时并不会识别这个错误。

输入迭代器（Input iterators）：可以读取序列中的元素。输入迭代器必须提供：

相等和不等操作符（==，!=）用于比较两个迭代器

前置和后置递增操作符（++）用于推进迭代器

用于读取元素的解引用运算符（*），解引用只能出现在赋值运算符的右边

箭头运算符（->）等价于 (*it).member ，意味着解引用迭代器，并从底层对象中获取一个成员

输入迭代器只能用于顺序访问。*it++ 保证是有效的，但是递增输入迭代器可能会导致流中的所有其它迭代器失效。结果就是，不能保证输入迭代器的状态可以保存，并且用于测试一个元素。输入迭代器因而只能用于单遍扫面算法，就是对元素值只访问一次，而不能多次访问。如果需要多次访问就要使用前向迭代器。find 和 accumulate 算法只要求输入迭代器；istream_iterator 是输入迭代器；

输出迭代器（Output iterators）：可以被认为是输入迭代器的补集，只能写不能读元素。输出迭代器必须提供：

用于推进迭代器的前置和后置递增运算符（++）

解引用运算符（*），只能出现在赋值操作符的左侧（给输出迭代器赋值是将内容写入到底层元素）

我们只能给输出迭代器写入给定值一次。与输入迭代器一样，输出迭代器只能被用于单遍扫描算法。用于目的迭代器基本都是输出迭代器。如 copy 的第三个参数是输出迭代器。ostream_iterator 是输出迭代器。

前向迭代器（Forward iterators）：可以读写给定序列。它们只能在序列的一个方向上移动。前向迭代器支持输入和输出迭代器的所有操作。而且，可以多次读写同一个元素。因此，可以保存前向迭代器的状态。使用前向迭代器的算法可以多次扫描序列。replace算法需要一个前向迭代器；forward_list 上的迭代器就是前向迭代器；

双向迭代器（Bidirectional iterators）：可以正向和反向读写序列中的元素。除了支持前向迭代器中的所有操作，双向迭代器还支持前置和后置递减操作符（--)。reverse 算法需要双向迭代器，除了 forward_list 外的标准库容器都提供符合双向迭代器要求的迭代器。

随机访问迭代器（Random-access iterators）：提供固定时间内访问序列中任何位置的能力。这些迭代器双向迭代器的所有操作。除此之外，随机访问迭代器还支持：

关系操作符（< <= >= >）用于比较两个迭代器的相对位置

加法和减法操作符（+ += - -=）用于迭代器和整数。结果是推进或回退给定整数个元素的位置

减法操作符运用于两个迭代器，将返回两者之间的距离

下标操作符（iter[n]）与 *(iter+n) 同义

sort 算法要求随机访问迭代器。array ，deque，string 和 vector 中的迭代器是随机访问迭代器，用于访问内置数组元素的指针也是。

算法形参模式

算法的参数有自己的规范，理解这些规范对于理解算法本身很有帮助。绝大部分算法的参数形式是以下四种之一：

其中 algorithm 就是算法的名字，beg 和 end 表示输入范围。尽管几乎所有的算法都有一个输入范围，其它参数的出现则依赖于算法所做的工作。dest ，beg2 和 end2 都是迭代器，它们在算法中的角色是类似的。除了这些迭代器参数，有些算法还有额外的非迭代器参数。

接受单个目标迭代器的算法

dest 参数表示一个目的位置的迭代器，这样算法可以将输出写入到这个 dest 所表示的元素中。算法总是假设能够写入足量的元素，保证目的迭代器能够容纳算法的输出是程序员自己的责任。如果 dest 直接指向容器中的元素，那么算法将其输出写入到容器中已经存在的元素中去。更为一般的是，dest 是一个插入迭代器或者 ostream_iterator。插入迭代器往容器中添加元素，因此可以保证容器中有足够的容量。ostream_iterator 将内容写入到输出流中，同样不用管需要写入多少个元素。

接受第二个输入序列的算法

接受单独的 beg2 或者 beg2 和 end2 参数的算法将这些迭代器当作第二个输入范围。这些算法将第二个范围内的元素与第一个范围内的元素联合起来进行运算。

如果一个算法的参数是 beg2 和 end2，那么这些参数有两个完全确定的范围：第一个输入范围 [beg, end) 和第二个输入范围 [beg2, end2) 。

如果算法只有一个 beg2 ，那么将 beg2 当作第二个输入范围的首元素。这个范围的尾部没有指定，相反，算法假定第二个范围从 beg2 开始，并且至少跟第一个输入范围一样大，保证这个条件成立是程序员自己的责任。

算法命名规范

除了参数规范，算法的名字和重载也有自己的规范。这些规范用于处理怎样提供操作以替代默认 < 或 == 操作符，以及算法是将输出写入到其输入序列还是一个独立的目的地。

有些算法使用重载来传递谓词

使用谓词来替换 < 或 == 操作符的算法，以及没有这个谓词参数的算法是重载的。其中一个版本使用元素的操作进行比较；另一个版本则有一个额外的参数表示谓词，如：

两个调用都会移除相邻的重复元素。第一个使用元素的 == 操作符以检查重复元素；第二个使用 comp 决定两个元素是否相等。由于两个函数的参数数目不一样，调用哪个函数不存在模糊性。

_if 的算法版本

有一个元素值的算法通常会有第二个名字（而不是重载），第二个版本的参数是一个谓词而不是元素值。以谓词为参数的算法的后缀是 _if：

这两个算法都是查找一个特定元素在输入序列中出现的位置。find查找特定的值，find_if 查找使得 pred 为真的元素值；

这些算法提供要给额外的名字，而不是进行重载的原因是两个版本都具有相同数目的参数。重载可能会导致模糊性。

_copy 的算法版本

默认情况下，会调整元素的算法将调整后的元素写回到给定的输入范围中。这些算法提供了第二个版本将元素写入到给定的输出目的地，这样的版本以 _copy 为后缀：

一些算法同时提供了 _copy 和 _if 版本。这些版本有一个目的迭代器和谓词：

两个调用都用 lambda 来判断一个元素是否为偶数。第一个版本，直接在输入序列中移除。第二个版本，将符合条件的值拷贝到v2 中。