频道栏目
读书频道 > 软件开发 > C++ > C++ Primer中文版(第5版)
3.4.2 迭代器运算
2013-09-09 09:40:35     我来说两句
收藏   我要投稿

本文所属图书 > C++ Primer中文版(第5版)

这本久负盛名的 C++经典教程,时隔八年之久,终迎来史无前例的重大升级。除令全球无数程序员从中受益,甚至为之迷醉的——C++ 大师 Stanley B. Lippman 的丰富实践经验,C++标准委员会原负责人 Jos&eacut...  立即去当当网订购

迭代器的递增运算令迭代器每次移动一个元素,所有的标准库容器都有支持递增运算的迭代器。类似的,也能用==和!=对任意标准库类型的两个有效迭代器(参见3.4节,第106页)进行比较。

string和vector的迭代器提供了更多额外的运算符,一方面可使得迭代器的每次移动跨过多个元素,另外也支持迭代器进行关系运算。所有这些运算被称作迭代器运算(iterator arithmetic),其细节由表3.7列出。


表3.7:vector和string迭代器支持的运算
iter + n 迭代器加上一个整数值仍得一个迭代器,迭代器指示的新位置与原来相比向前移动了若干个元素。结果迭代器或者指示容器内的一个元素,或者指示容器尾元素的下一位置
iter - n 迭代器减去一个整数值仍得一个迭代器,迭代器指示的新位置与原来相比向后移动了若干个元素。结果迭代器或者指示容器内的一个元素,或者指示容器尾元素的下一位置
iter1 += n 迭代器加法的复合赋值语句,将iter1n的结果赋给iter1
iter1 -= n 迭代器减法的复合赋值语句,将iter1n的结果赋给iter1
iter1 - iter2 两个迭代器相减的结果是它们之间的距离,也就是说,将运算符右侧的迭代器向前移动差值个元素后将得到左侧的迭代器。参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置
> >= < <= 迭代器的关系运算符,如果某迭代器指向的容器位置在另一个迭代器所指位置之前,则说前者小于后者。参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置

迭代器的算术运算

可以令迭代器和一个整数值相加(或相减),其返回值是向前(或向后)移动了若干个位置的迭代器。执行这样的操作时,结果迭代器或者指示原vector对象(或string对象)内的一个元素,或者指示原vector对象(或string对象)尾元素的下一位置。举个例子,下面的代码得到一个迭代器,它指向某vector对象中间位置的元素:

// 计算得到最接近vi中间元素的一个迭代器

auto mid = vi.begin() + vi.size() / 2;

如果vi有20个元素,vi.size()/2得10,此例中即令mid等于vi.begin()+10。已知下标从0开始,则迭代器所指的元素是vi[10],也就是从首元素开始向前相隔10个位置的那个元素。

对于string或vector的迭代器来说,除了判断是否相等,还能使用关系运算符(<、<=、>、>=)对其进行比较。参与比较的两个迭代器必须合法而且指向的是同一个容器的元素(或者尾元素的下一位置)。例如,假设it和mid是同一个vector对象的两个迭代器,可以用下面的代码来比较它们所指的位置孰前孰后:

if (it < mid)

    // 处理vi前半部分的元素

只要两个迭代器指向的是同一个容器中的元素或者尾元素的下一位置,就能将其相减,所得结果是两个迭代器的距离。所谓距离指的是右侧的迭代器向前移动多少位置就能追上左侧的迭代器,其类型是名为difference_type的带符号整型数。string和vector都定义了difference_type,因为这个距离可正可负,所以difference_type是带符号类型的。

使用迭代器运算

使用迭代器运算的一个经典算法是二分搜索。二分搜索从有序序列中寻找某个给定的值。二分搜索从序列中间的位置开始搜索,如果中间位置的元素正好就是要找的元素,搜索完成;如果不是,假如该元素小于要找的元素,则在序列的后半部分继续搜素;假如该元素大于要找的元素,则在序列的前半部分继续搜索。在缩小的范围中计算一个新的中间元素并重复之前的过程,直至最终找到目标或者没有元素可供继续搜索。

下面的程序使用迭代器完成了二分搜索:

// text必须是有序的

// beg 和 end表示我们搜索的范围

auto beg = text.begin(), end = text.end();

auto mid = text.begin() + (end - beg)/2; // 初始状态下的中间点

// 当还有元素尚未检查并且我们还没有找到sought时执行循环

while (mid != end && *mid != sought) {

    if (sought < *mid)  // 我们要找的元素在前半部分吗?

        end = mid;       // 如果是,调整搜索范围使得忽略掉后半部分

    else                 // 我们要找的元素在后半部分

        beg = mid + 1;   // 在mid之后寻找

    mid = beg + (end - beg)/2; // 新的中间点

}

程序的一开始定义了三个迭代器:beg指向搜索范围内的第一个元素、end指向尾元素的下一位置、mid指向中间的那个元素。初始状态下,搜索范围是名为text的vector<string>的全部范围。

循环部分先检查搜索范围是否为空,如果mid和end的当前值相等,说明已经找遍了所有元素。此时条件不满足,循环终止。当搜索范围不为空时,可知mid指向了某个元素,检查该元素是否就是我们所要搜索的,如果是,也终止循环。

当进入到循环体内部后,程序通过某种规则移动beg或者end来缩小搜索的范围。如果mid所指的元素比要找的元素sought大,可推测若text含有sought,则必出现在mid所指元素的前面。此时,可以忽略mid后面的元素不再查找,并把mid赋给end即可。另一种情况,如果*mid比sought小,则要找的元素必出现在mid所指元素的后面。此时,通过令beg指向mid的下一个位置即可改变搜索范围。因为已经验证过mid不是我们要找的对象,所以在接下来的搜索中不必考虑它。

循环过程终止时,mid或者等于end或者指向要找的元素。如果mid等于end,说明text中没有我们要找的元素。

您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:3.4.1节练习
下一篇:3.4.2节练习
相关文章
图文推荐
排行
热门
最新书评
特别推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站