C++ Primer 迭代器

专栏简介：本专栏主要面向C++初学者，解释C++的一些基本概念和基础语言特性，涉及C++标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级程序设计技术。希望对读者有帮助！

3.4迭代器介绍

我们已经知道可以使用下标运算符来访问string对象的字符或vector对象的元素,还有另外一种更通用的机制也可以实现同样的目的,这就是迭代器(iterator)。除了vector之外,标准库还定义了其他几种容器。所有标准库容器都可以使用逄代器,但是其中只有少数几种才同时支持下标运算符。严格来说,string对象不属于容器类型,但是string支持很多与容器类型类似的操作。vector支持下标运算符,这点和string一样;string支持迭代器,这也和vector是一样的。

类似于指针类型,迭代器也提供了对对象的间接访问。就迭代器而言,其对象是容器中的元素或者string对象中的字符。使用迭代器可以访问某个元素,迭代器也能从一个元素移动到另外一个元素。迭代器有有效和无效之分,这一点和指针差不多。有效的迭代器或者指向某个元素,或者指向容器中尾元素的下一位置;其他所有情况都属于无效。

使用迭代器

和指针不一样的是,获取迭代器不是使用取地址符,有迭代器的类型同时拥有返回迭代器的成员。比如,这些类型都拥有名为begin和end的成员,其中begin成员负责返回指向第一个元素(或第一个字符)的迭代器。如有下述语句:

//由编译器决定b和e的类型;
//b表示v的第一个元素,e表示y尾元素的下一位置
auto b=v.begin(),e=v.end();//b和e的类型相同

end成员则负责返回指向容器(或string对象)尾元素的下一位置(one past the end) 的迭代器,也就是说,该迭代器指示的是容器的一个本不存在的“尾后(off the end)“元
素。这样的迭代器没什么实际含义,仅是个标记而己,表示我们已经处理完了容器中的所有元素。end成员返回的迭代器常被称作尾后迭代器(off-the-end iterator)或者简称为尾
迭代器(end iterator)。特殊情况下如果容器为空,则begin和end返回的是同一个迭代器。

如果容器为空,则begin和end返回的是同一个迭代嚣,都是尾后迭代器

一般来说,我们不清楚(不在意)迭代器准确的类型到底是什么。在上面的例子中,使用auto关键字定义变量b和e(参见2.5.2节,第61页),这两个变量的类型也就是begin和end的返回值类型,第97页将对相关内容做更详细的介绍。

迭代器运算符

表3.6列举了迭代器支持的一些运算。使用==和!=来比较两个合法的迭代器是否相等,如果两个迭代器指向的元素相同或者都是同一个容器的尾后迭代器,则它们相等;否则就说这两个迭代器不相等。

表3.6:标准容器迭代器的运算符

和指针类似,也能通过解引用迭代器来获取它所指示的元素,执行解引用的选代器必须合法并确实指示着树个元素。试图解引用一个非法迢代器或者尾后迭代器都是未被定义的行为。
举个例子,程序利用下标运算符把string对象的第一个字母改为了大写形式:

strings(“some string“);
if(s.begin()!s.end())〔//确保s非空
   auto it=s.begin();//it表示s的第一个字符
   *it= toupper(*it);//将当前字符改成大写形式
)

本例首先检查s是否为空,显然通过检查begin和end返回的结果是否一致就能做到这一点。如果返回的结果一样,说明s为空;如果返回的结果不一样,说明s不为空,此时s中至少包含一个字符。

我们在i内部,声明了一个迭代器变量it并把begin返回的结果赋给它,这样就得到了指示s中第一个字符的迭代器,接下来通过解引用运算符将第一个字符更改为大写形式。和原来的程序一样,输出结果将是:

Some string

将迭代器从一个元素移动到另外一个元素

迭代器使用递增(++)运算符来从一个元素移动到下一个元素。从逻辑上来说,迭代器的递增和整数的递增类似,整数的递增是在整数值上“加1迭代器的递增则是将迭代器“向前移动一个位置“。

因为end 返回的迭代器并不实际指示某个元素，所以不能对其进行递增或解引用操作。

之前有一个程序把string对象中第一个单词改写为大写形式,现在利用迭代器及其递增运算符可以实现相同的功能:

//依次处理s的字符直至我们处理完全部字符或者遥到空白
for(auto it=s.begin();it!=s.end()&&!isspace(*it);++it)
    *it=toupper(*it);//将当前字符改成大写形式

上面的循环遍历s的字符直到遇到空白字符为止。

循环首先用s.begin的返回值来初始化it,意味着it指示的是s中的第一个字符(如果有的话)。条件部分检查是否已到达s的尾部,如果尚未到达,则将it解引用的结果传入isspace函数检查是否遇到了空白。每次迭代的最后,执行++it令迭代器前移-个位置以访问s的下一个字符。

循环体内部和上一个程序if语句内的最后一句话一样,先解引用it,然后将结果传入toupper函数得到该字母对应的大写形式,再把这个大写字母重新赋值给it所指示的字符。

迭代器类型

就像不知道string和vector的size_type成员到底是什么类型一样,一般来说我们也不知道(其实是无须知道)迭代器的精确类型。而实际上,那些拥有迭代器的标准库类型使用iterator和const iterator来表示迭代器的类型:

vector<int>::iterator it;//it能读写vector<itnt>的元素
string::iterator it2;//it2能读写string对象中的字符

vector<int>::const_iterator it3;//it3只能读元素,不能写元素
string::const_iterator it4;//it4只能读字符,不能写字符

const_iterator和常量指针差不多,能读取但不能修改它所指的元素值。相反,iterator的对象可读可写。如果vector对象或string对象是一个常量,只能使const iterator;如果vector对象或string对象不是常量, 那么既能使用iterator也能使用const_iterator。

begin和end运算符

begin和end返回的具体类型由对象是否是常量决定,如果对象是常量,begin和end返回const_iterator;如果对象不是常量,返回iterator:

vector<int> v;
const vector<int> cv;
auto it1 = v.begin();//it1的类型是vector<int>::tterator
auto it2 = cv.begin();//it2的类型是vector<int>::const_iterator

有时候这种默认的行为些非我们所要。如果对象只需读操作而无须写操作的话最好使用常量类型(比如const_iterator)。为了便于专门得到const_iterator类型的返回值,C++11新标准引入了两个新函数,分别是cbegin：

auto it3 = v.cpegin();//it3的类型是vector<int>::const_tterator

类似于begin和end,上述两个新函数也分别返回指示容器第一个元素或最后元素下一位置的迭代器。有所不同的是,不论vector对象(或string对象)本身是否是常量,返回值都是const_iterator。

结合解引用和成员访问操作

解引用迭代器可获得迭代器所指的对象,如果该对象的类型恰好是类,就有可能希望进一步访问它的成员。例如,对于一个由字符串组成的vector对象来说,要想检查其元素是否为空,令it是该vector对象的迭代器,只需检查it所指宇符串是否为空就可以了,其代码如下所示:

(*it).empty()

注意,(*it).empty()中的圆括号必不可少,该表达式的含义是先对it解引用,然后解引用的结果再执行点运算符。如果不加圆括号,点运算符将由it来执行,而非it解引用的结果:

(*it).empty() //解引用it,然后调用结果对象的empty成员
*it.empty()// 错误:试图访问it的名为empty的成员,但it是个选代器,
// 没有empty成员

上面第二个表达式的含义是从名为it的对象中寻找其empty成员,显然it是一个迭代器,它没有哪个成员是叫empty的,所以第二个表达式将发生错误。

为了简化上述表达式,C++语言定义了箭头运算符(->)。箭头运算符把解引用和成员访问两个操作结合在一起,也就是说,it->mem和(*it).mem表达的意思相同。

例如,假设用一个名为text的字符串向量存放文本文件中的数据,其中的元素或者是一句话或者是一个用于表示段落分隔的空字符串。如果要输出text中第一段的内容,可以利用迭代器写一个循环令其遍历text,直到遇到穿字符串的元素为止:

//依次输出text的每一行直至遇到第一个空白行为止
for(auto it=text.cbegin();
    it != text.cend()&& it->empty();++it)
cout<< *it << endl;

我们首先初始化it令其指向text的第一个元素,循环重复执行直至处理完了text的所有元素或者发现某个元素为空。每次迭代时只要发现还有元素并且尚未遇到空元素,就输
出当前正在处理的元素。值得注意的是,因为循环从头到尾只是读取text的元素而未向其中写值,所以使用了cbegin和cend来控制整个迭代过程。

某些对vector对象的操作会使迭代器失效
虽然vector对象可以动态地增长,但是也会有些副作用。已知的一个限制是不能在范围for循环中向vector对象添加元素。另外一个限制是任何一种可能改变vector对象容量的操作,比如push_back,都会使该vector对象的迭代器失效。

迭代器运算

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

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(1+10)。已知下标从0开始,则迭代器所指的元素是vi[10],也就是从首元素开始向前相隔10个位置的那个元素。

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

只要两个迭代器指向的是同一个容器中的元素或者尾元素的下一位置,就能将其相减,所得结果是两个迭代器的距离。所谓距离指的是右侧的迭代器向前移动多少位置就能追上左侧的迭代器,其类型是名为adifference_type的带符号整型数。string和vector都定义了adifference_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的全部范围。

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

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