和C#中的IEnumerable接口类似,在C++中,遍历标准容器库比如vector、deque、list等,都需要用到迭代器对象(iterator),根据容器的类型不同以及访问时是否需要读写,迭代器分为可读写迭代器iterator,只读迭代器const_iterator以及反向迭代器reverse_itertaor。

调用容器类型成员的begin和end方法(或者cbegin、cend,rbegin、rend)方法,可以分别返回指向容器首元素的迭代器,以及尾元素之后的(one past the last element),简称尾后迭代器。

这里面有一个容易误解的地方在于,end方法返回的迭代器,从来都不会指向容器的最后一个元素,而是指向最后一个元素之后的元素。调用容器v的.begin()和.end()返回的迭代器范围(iterator range)实际上为:

[begin, end)

这在数学上称为左闭合区间(left-inclusive interval)

C++的迭代器范围为什么要这么设计? 为什么区间要包含第一个元素,而不把最后一个元素end也包含进来?

恰好,前几天我看到一个对“计算机中数组下标要从0开始,而不是1?”的解答,这个解答对为什么C++的迭代器要这么设计有帮助,那就从计算机中的数组下标从0而不是1开始这个问题展开。

计算机中数组下标要从0开始


大部分的编程语言中,数组或集合的下标都是从0开始,0表示数组或者集合里面的第1个元素 (但也有例外,比如FORTRAN,比如三大m语言MATLAB、mathematica、maple中数组下标都是1开始的😂)。为什么在计算机的世界要把0作为第一个元素的下标,而不是日常生活中更加直观的1呢?

这个问题1972年图领奖获得者Dijkstra,在1982年已经解答过。没错,如果你是地理信息系统专业,或者了解空间分析,Dijkstra的最短路径算法你一定听说过。原文在此 https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html 。我这里对这篇简短的文章简单翻译理解了一下。

连续自然数序列的表示方法


他举了一个例子,比如如果要表示一个连续的自然数序列 [2,3,4,5,6,7,8,9,10,11,12],假设 i 表示一个整数,那么可以有如下4种表示方法:

a)	2 ≤ i < 13
b)	1 < i ≤ 12
c)	2 ≤ i ≤ 12
d)	1 < i < 13

上面4个不等式都满足要求,有什么理由该选择其中的一个而不是其它?Dijkstra从三个不同方面给出了解答:

  • 首先,Dijkstra 说有,应该选 a 和 b,因为这2个不等式有个很突出的优点,就是不等式边界的差(不等式右边 - 左边)正好等于连续序列的长度(13-2=11,12-1=11,序列正好有11个元素)并且如果两个序列邻近,就意味着一个序列的上边界等于另外一个序列的下边界。比如如果A序列为[1,2,3,4 ],B序列为[5,6,7,8]。如果用a和b的不等式形式来表示:
    a)A:1 ≤ i < 5 B:5 ≤ i < 9  
    b)A:0 < i ≤ 4 B:4 < i ≤ 8
    可以看到,要判断序列A和B是否邻近,只需要判断,序列A的上标是否等于B的下标或者A的下标是否等于B的上标即可。所以a和b更好。
  • 其次,从另外一个角度来看,Dijkstra 接着说,我们有最小的自然数0,b和d都排除了序列中的最小元素,它使得要表示自然数序列,可能会使得最小的下标为-1,而-1是一个非自然数,用一个包含非自然数的表达式来表示自然数序列,这很不优雅 (负数在计算机中的表示比正整数更加复杂,涉及到补码、反码)。比如我们要表示[0,1,2,3]这个序列,如果按照b和d的表示方法,则为:
    b) -1 < i ≤ 3
    d) -1 < i < 4
    下标为-1,是一个非自然数,因此a和c是更好的选择。
  • 再次,假设我们有一个序列的起始值为0,如果包含上标,那么当我们要表示一个只有最新值0的序列[ 0 ],就会显得很ugly。比如如果要表示一个空序列,如果按照b和c,则:
    b)  0 < i ≤ 0
    c)  0 ≤ i ≤ 0
    所以,从这个角度,a和d更好。

综合上面三点,可以看出,使用不等式a,即左闭合区间更好。不仅从理论上如此,Dijkstra还以Mesa这个在Xerox PARC开发出来的编程语言为例,说明了使用其它三种集合的表示方法更容易出错,并且强烈建议不要使用后面这三种集合的表示方法,而坚持值选择左闭合区间来表示连续的自然数序列。

下标从0开始


选择左闭合区间来表示N个自然数的数列之后,接下来考虑下标的问题,按照表达式a的表示方法:

  • 如果下标从1开始,则为 1 ≤ i < N+1
  • 如果下标从0开始,则为 0 ≤ i < N

Dijkstra 认为:下标从0 开始能够给出更好的不等式,因为元素的下标就等于序列中它前面的元素个数(或者说 “偏移量”)。

C++中的迭代器


从上面Dijkstra对自然数序列的表示,尤其是序列以左闭和区间的形式更优雅也更不容易出错的解释,这对C++中的迭代器为什么设计成左闭包有帮助。

C++的标准库使用左闭合区间范围有三种方便的性质,假定begin和end表示一个合法的迭代器范围:

  • 如果begin和end相等,则范围为空
  • 如果begin和end不等,则范围至少包含一个元素,且begin指向范围中的第一个元素,begin-end等于范围内元素的个数
  • 可以递增begin若干次,使得begin==end

可以使用迭代器来实现一个二分查找的算法:

#include <vector>
#include <iterator>
bool find(std::vector<int> &vector, int findnum)
{
    auto begin = vector.cbegin();//std::vector<int>::const_iterator
    auto end = vector.cend();
    auto middle = begin + (end - begin) / 2;
    while (middle != end && (*middle) != findnum)
    {
        if (findnum < *middle)
        {
            end = middle;
        }
        else
        {
            begin = middle + 1;
        }
        middle = begin + (end - begin) / 2;
    }
    return middle != end;
}

代码中,调用vector容器类的cbegin和cend方法,分别获取了容器的首元素迭代器,和尾后迭代器,然后对迭代器进行运算,获取了指向容器中间的迭代器middle。迭代器之间的减法运算表示两个元素之间的距离。将一个迭代器与一个整数相加,表示将该迭代器往前移动若干个元素。需要注意的是,这里的获取容器中间的迭代器middle的写法为:

auto middle = begin + (end - begin) / 2;

begin是一个首元素迭代器,end-begin表示end和begin之间的距离,除以2,表示距离的一半,它是一个std::ptrdiff_t的long long长整型类型。迭代器之间相减、一个迭代器与整型的加减,都是合法的运算,都有意义

迭代器之间的加法运算是没有意义的,所以下面这个取集合中间迭代器的算法,是错误的。

auto n = (begin + end) / 2;
编译器会报错:
no match for 'operator+' (operand types are '__gnu_cxx::__normal_iterator<const int*, std::vector<int> >' and '__gnu_cxx::__normal_iterator<const int*, std::vector<int> >')

迭代器上没有加法运算器。