3.4.2  迭代器运算

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

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

表3.7：vector和string迭代器支持的运算

迭代器的算术运算

可以令迭代器和一个整数值相加（或相减），其返回值是向前（或向后）移动了若干个位置的迭代器。执行这样的操作时，结果迭代器或者指示原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.2节练习

练习3.24：请使用迭代器重做3.3.3节（第105页）的最后一个练习。

练习3.25：3.3.3节（第104页）划分分数段的程序是使用下标运算符实现的，请利用迭代器改写该程序并实现完全相同的功能。

练习3.26：在112页的二分搜索程序中，为什么用的是mid = beg + (end - beg) / 2，而非mid = (beg + end) /2;？