输入迭代器只能一直自增, 并通过这样的方式遍历容器. 不过输入迭代器比迭代器的基础定义多了一个功能: 判等. 但是有些丧病的是在这个迭代器自增之后, 原来指向的元素可能失效. 这种情况可能发生在你试图复制一个迭代器作为备份, 并将原来的迭代器自增, 则自增后这个备份所指向的内容不保证合法性. 而且不保证可以根据这个迭代器合法地向这个迭代器所指向的内容进行写入.
2.2.2 向前迭代器向前迭代器和输入迭代器一样也只能进行自增且可以判等, 但是向前迭代器比输入迭代器多了一层保证: 迭代器自增后原位置依然合法.
严格来说这个东西叫做多趟保证, 具体定义摘一下:
多趟保证
给定 a 和 b ，类型 It 的可解引用迭代器
2.2.3 双向迭代器双向迭代器首先满足向前迭代器作为前置条件, 然后如字面意思所言, 双向迭代器不仅可以支持单方向的自增操作, 还支持反方向定位的自减操作. 上面所述的三种迭代器都是一次只能定位一个元素的距离.
2.2.4 随机访问迭代器随机访问迭代器是自由度最大的, 可以指定整数偏移量来任意移动定位迭代器并访问元素. 而且对于两个随机访问迭代器还可以相减求二者之间相距的元素个数, 判断两个迭代器的前后位置关系(大于/小于/等于/不大于/不小于等运算符)
2.2.5 输出迭代器输出迭代器的概念其实只要满足是迭代器而且这个迭代器所指向的内容可以写入数据即可.
2.2.6 迭代器综述虽然不同类型的迭代器有不同的限制, 但是这些限制并不是没有理由的, 比如对于 std::set , 它的内部实现是一棵平衡树, 而且没有实现名次树的功能, 所以能保证时间复杂度为 $O(log(n))$ 的操作只有查询该迭代器的前驱与后继. 所以它的迭代器是一个双向迭代器. 而 std::vector 由于它连续存储的特性所以可以支持随机定位, 比如位置 $+5$ 或者 $-7$ .
其实与其说不同种类的迭代器有不同的限制, 不如说不同种类的迭代器提供了自己对某种操作是否支持的保证. 比如需要用到二分查找的函数需要随机访问迭代器作为参数, 因为只有这样才能取到最中间的元素位置, 当传入的迭代器不满足随机访问迭代器的要求时查找就会退化为线性时间复杂度; 而像 std::for_each 这样的函数则只需要一个满足前向迭代器的输出迭代器就行了. (不过二分查找好像不必是输出迭代器233)
附:迭代器使用示例:
1 #include <vector> 2 #include <iostream> main(){ 5 std::vector<int> v={1,9,2,4,7,5,6,8}; 6 for(std::vector<int>::iterator i=v.begin();i!=v.end();++i){ 7 std::cout<<*i<<std::endl; 8 } ; 10 }
2.3 算法库
C++算法库中提供大量用途的函数(例如查找、排序、计数、操作),它们在元素范围上操作. 虽然算法库中的很多函数都可以比较快地手写出来, 但是有时候正确使用C++算法库可以大幅精简OI代码并减少在这些基础部分的无意义低错(而这些错误常常需要很长时间的debug才能发现.), 而且算法库中的算法往往进行过一些特殊优化使得库函数常常比手写快(STL和编译器可能有不为人知的py交易). 注意范围定义为左闭右开区间 [first, last) , 其中 last 指向要查询或修改的最后元素的后一个元素.
库函数大多都能吊打手写, 就算你自以为用了一些卡常的奇技淫巧也依然没有任何卵用. (毕竟人家有交易嘛(大雾))
多数涉及比较或者判定的库函数都支持自定义比较函数或者判定函数, 一般应该选择传const引用或者传值. 传值因为要复制所以一般有额外开销, 建议使用const引用.
下面仅介绍算法库中的部分OI常用函数(不然太多根本没法写QAQ)
1. std::for_each
接受三个参数: 两个迭代器用于指定操作区间, 最后一个函数对象用于执行操作. FP专属操作的味道
2. std::count std::count_if
分别接受三个参数, 前两个都是两个迭代器用于指定区间, 前者的第三个参数为一个值, 返回该值在指定区间内出现的次数; 后者的第三个参数为一个函数对象, 接受一个对应的值并返回 bool 值. count_if 对于指定区间内令指定函数返回 true 的值进行计数.
3. std::fill
三个参数, 前两个迭代器划分左闭右开区间, 第三个为一个类型对应的值. 作用为将指定区间内的对象全部设置为指定值. 据说内部有多路优化所以比自己写循环要快而且似乎不会像memset一样破坏STL及其他类的数据结构?
4. std::fill_n
三个参数, 第一个为一个迭代器指定区间左端, 第二个为要修改的元素数目, 第三个为要修改的值. 与 std::fill 功能类似.
5. std::transform
将一个或两个区间内的值分别传给一个指定的函数并将计算结果保存在另一个区间内的对应位置.
两个重载, 分别对应一元函数与二元函数. 先是两个迭代器指定参数区间, 二元函数还要再加一个迭代器指定第二个参数的区间左端. 然后是一个迭代器指定要保存结果的区间的左端, 最后是函数对象.
6. std::generate
用一个函数的返回值填充一个区间. 先是两个迭代器划分区间, 第三个参数为一个函数. 函数的返回值将被用于一个一个地写入指定区间内.
7. std::generate_n
与 std::generate 功能类似, 不同的是由两个迭代器划分区间改为由一个迭代器和一个计数器划分区间.
8. std::remove std::remove_if
相关文章
精彩导读
热门资讯
关注我们
