type
status
date
slug
summary
tags
category
icon
password
Property
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
中。