STL iterator 基本原则     有效使用STL迭代器的三条基本原则



STL迭代器的概念看上去似乎已经足够直观了,然而,你会很快发现容器类(Container)实际上提供了四种不同的迭代器类型:iterator、const_iterator、reverse_iterator和const_reverse_iterator。进而,你会注意到容器类的insert和erase方法仅接受这四种类型中的一种作为参数。问题来了:为什么需要四种不同的迭代器呢?它们之间存在何种联系?它们是否可以相互转换?是否可以在STL算法(Algorithm)和其他工具函数中混合使用不同类型的迭代器? 这些迭代器与相应的容器类及其方法之间又是什么关系?
这篇从新近出版的《Effective STL》中摘录的文章将会通过迭代器使用的三条基本原则来回答上述问题,它们能够帮助你更为有效的使用STL迭代器。

原则一:尽量使用iterator取代const_iterator、reverse_iterator和const_reverse_iterator

STL中的所有标准容器类都提供四种不同的迭代器类型。对于容器类container<T>而言,iterator的功用相当于T*,而const_iterator则相当于const T*(可能你也见到过T const *这样的写法,它们具有相同的语义[2])。累加一个iterator或者const_iterator可以由首至尾的遍历一个容器内的所有元素。reverse_iterator与const_reverse_iterator同样分别对应于T*和const T*,所不同的是,累加reverse_iterator或者const_reverse_iterator所产生的是由容器的尾端开始的反向遍历。

让我们先来看一下vector<T>容器insert和erase方法的样式:
iterator insert(iterator position, const T& x);
iterator erase(iterator position);
iterator erase(iterator rangeBegin, iterator rangeEnd);

不同容器的insert和erase方法虽然可能具有截然不同的返回类型,但它们的参数形式却大都与此类似。需要注意的是:这些方法仅接受iterator类型的参数,而不是const_iterator、reverse_iterator或者const_reverse_iterator。虽然容器类支持四种不同的迭代器类型,但其中iterator似乎有更为广泛的应用[3]。

下图清晰的表明了不同类型的迭代器之间的转换关系:

如图所示,你可以隐式的将iterator转换成const_iterator或者reverse_iterator,也可以隐式的将reverse_iterator转换成const_reverse_iterator。并且,reverse_iterator可以通过调用其base()成员函数转换为iterator。const_reverse_iterator也可以类似的通过base()转换成为const_iterator。然而,一个图中无法显示的事实是:通过base()得到的也许并非你所期待的iterator,我们将会在原则三中详细讨论这一点。
很显然,我们没有办法从一个const_iterator转换得到一个iterator,也无法从const_reverse_iterator得到reverse_iterator。这一点非常重要,因为这意味着当你仅仅得到一个const_iterator或者const_reverse_iterator,你会在调用容器类的一些成员函数时遇到麻烦。这些成员函数要求iterator作为参数,而你无法从const类型的迭代器中直接得到iterator。当需要指出插入或者删除的位置时,const类型的迭代器总是显得那么力不从心。
千万不要傻乎乎的宣称const类型的迭代器一无是处,它们仍然可以在特定的场合使用。比如,const类型的迭代器可以与STL算法默契配合——因为STL算法通常只关心迭代器属于何种概念范畴(Category),而对其类型(Type)没有限制。很多容器类的成员方法也接受const类型的迭代器,只有insert和erase显得有些吹毛求疵。

即便是在需要插入或删除操作的时候,面对const类型的迭代器你也并非走投无路。一般情况下仍然有办法通过const类型的迭代器取得一个iterator,但这种方法并不总是行得通。而且就算可行,它也显得复杂而缺乏效率。原则二中将会提及这种转换的方法。


现在,我们已经有足够的理由相信应该尽量使用iterator取代const或者reverse类型的迭代器:
·大多数insert和erase方法要求使用iterator。如果你需要调用这些方法,你就必须使用iterator。
·没有一条简单有效的途径可以将const_iterator转换成iterator,我们将会在原则二中讨论的技术并不普遍适用,而且效率不彰。
·从reverse_iterator转换而来的iterator在使用之前可能需要相应的调整,在原则三种我们会讨论何时需要调整以及调整的原因。
由此可见,尽量使用iterator而不是const或reverse类型的迭代器,可以使得容器的使用更为简单而有效,并且可以避免潜在的问题。
在实践中,你可能会更多的面临iterator与const_iterator之间的选择,因为iterator与reverse_iterator之间的选择结果显而易见——依赖于顺序或者逆序的的遍历。而且,即使你选择了reverse_iterator,当需要iterator的时候,你仍然可以通过base()方法得到相应的iterator(可能需要一些调整,我们会在条款三中讨论)。
而在iterator和const_iterator之间举棋不定的时候,你有更充分的理由选择iterator,即使const_iterator同样可行,即使你并不需要调用容器类的任何成员函数。其中的缘由包括iterator与const_iterator之间的比较,如下代码所示:
typedef deque<int> IntDeque;   //typedef可以极大的简化
typedef IntDeque::iteratorIter;   //STL容器类和iterator
typedef IntDeque::const_iteratorConstIter;//的操作。

Iter  i;
ConstIter ci;
...  //使ci和i指向同一容器。
if (i == ci) ...  //比较iterator和const_iterator

我们所做的只是同一个容器中两个iterator之间的比较,这是STL中最为简单而常用的动作。唯一的变化是等号的一边是iterator,而另一边是const_iterator。这应该不是问题,因为iterator应该在比较之前隐式的转换成const_iterator,真正的比较应该在两个const_iterator之间进行。
对于设计良好的STL实现而言,情况确实如此。但对于其它一些实现,这段代码甚至无法通过编译。原因在于,这些STL实现将const_iterator的等于操作符(operator==)作为const_iterator的一个成员函数而不是友元函数。而问题的解决之道显得非常有趣:只要交换两个iterator的位置,就万事大吉了。
if (ci==i)...//问题的解决方法

不仅是比较是否相等,只要你在同一个表达式中混用iterator和const_iterator(或者reverse_iterator和const_reverse_iterator),这样的问题就会出现。例如,当你试图在两个随机存取迭代器之间进行减法操作时:
if (i-ci >= 3) ...//i与ci之间有至少三个元素

如果迭代器的类型不同,你的完全正确的代码可能会被无理的拒绝。你可以想见解决的方法(交换i和ci的位置),但这次,不仅仅是互换位置了:
if (ci+3 <= i) ...//问题的解决方法

避免类似问题的最简单的方法是减少混用不同类型的迭代器的机会,尽量以iterator取代const_iterator。从const correctness的角度来看,仅仅为了避免一些可能存在的STL实现的弊端(而且,这些弊端都有较为直接的解决途径)而抛弃const_iterator显得有欠公允。但综合考虑到iterator与容器类成员函数的粘连关系,得出iterator较之const_iterator更为实用的结论也就不足为奇了。更何况,从实践的角度来看,并不总是值得卷入const_iterator的麻烦当中去。


原则二:使用distance和advance将const_iterator转换成iterator

原则一中指出容器类的部分方法仅接受iterator作为参数,而不是const_iterator。那么,如何在一个const_iterator指出的容器位置上插入新元素呢?换言之,如何通过一个const_iterator得到指向容器中相同位置的iterator呢?由于并不存在从const_iterator到iterator之间的隐式转换,你必须自己找到一条转换的途径。
嗨,我知道你在想什么!“每当无路可走的时候,就祭起强制类型转换的大旗!”。在C++的世界里,强制类型转换似乎总是最后的杀手锏。老实说,这恐怕算不上什么好主意——真不知道你是哪儿学来的。



让我们看看当你想把一个const_iterator强制转换为iterator时会发生什么:
typedef deque<int> IntDeque;//typedef, 简化代码。
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;

ConstIter ci;//const_iterator
Iter i(ci);//编译错误!
//没有隐式转换途径!
Iter i(const_cast<Iter>(ci));//编译错误!
//转换不能成立!

这里只是以的deque为例,但是用其它容器类(list, set, multiset, map, multimap甚至非标准STL的基于hash表的容器[4])产生的代码大同小异。也许vector或string类的代码能够顺利编译,但这是非常特殊的情形。
包含显式类型转换的代码不能通过编译的原因在于,对于这些容器而言,iterator和const_iterator是完全不同的类。它们之间并不比string和complex<float>具有更多的血缘关系。编译器无法在两个毫无关联的类之间进行const_cast转换。reinterpret_cast、static_cast甚至C语言风格的类型转换也不能胜任。
不过,对于vector和string容器来说,包含const_cast的代码也许能够通过编译。因为通常情况下STL的大多数实现都会采用真实的指针作为vector和string容器的迭代器。就这种实现而言,vector<T>::iterator和vector<T>::const_iterator分别被定义为T*和const T*,string::iterator和string::const_iterator则被定义为char*和const char*。因此,const_iterator与iterator之间的const_cast转换被最终解释成const T*到T*的转换。当然,这样的类型转换没有问题。但是,即便在这种STL的实现当中,reverse_iterator和const_reverse_iterator仍然是实在的类,所以仍然不能直接将const_reverse_iterator强制转换成reverse_iterator。而且,这些STL实现为了方便调试通常只会在Release模式时才使用指针表示vector和string的迭代器[5]。所有这些事实表明,出于可移植性的考虑,这样的强制类型转换即使是对vector和string来说也不可取。

如果你得到一个const_iterator并且可以访问它所指向的容器,那么这里有一条安全、可移植的途径将它转换成iterator,而且,用不着搅乱类型系统的强制转换。下面是基本的解决思路,称之为“思路”是因为还要稍作修改才能让这段代码通过编译。
typedef deque<int> IntDeque;
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;

IntDeque  d;
ConstIter ci;
...//ci指向d。
Iter i(d.begin());//指向d的起始位置。
advance(i, distance(i, ci));//调整i,指向ci位置。

这种方法看上去非常简单,也很直观:要得到与const_iterator指向同一位置的iterator,首先将iterator指向容器的起始位置,并且取得const_iterator距离容器起始位置的偏移量,然后将iterator向后移动相同的偏移即可。这些动作是通过<iterator>中声明的两个算法函数实现的:distance用以取得两个指向同一个容器的iterator之间的距离;advance则用于将一个iterator移动制定的距离。如果ci和i指向同一个容器,并且i指向容器的器时位置,表达式advance(i, distance(i, ci))会将i移动到与ci相同的位置上。
如果这段代码能够通过编译,它就能完成这种转换任务。但似乎事情并不那么顺利。先来看看distance的定义:
template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
不必为长达56个字符的返回类型操心,也不用理会difference_type是什么东西。仔细看看调用的参数!编译器需要推断出它所遇到的distance调用的参数类型。再来看看我们的distance调用:
advance(i, distance(i, ci));//调整i,指向ci位置。

i和ci分别是distance函数的两个参数,它们的类型分别是deque<int>::iterator和deque<int>::const_iterator,而distance函数需要一种确定的参数类型,所以调用失败。也许相应的错误信息会告诉你编译器无法推断出InputIterator的类型。
要顺利的通过编译,你需要排除distance调用的歧义性。最简单的办法就是显式的指明distance调用的模版参数类型,从而避免编译器为此大伤脑筋。
advance(i, distance<ConstIter>(i, ci));





这样,我们就可以通过advance和distance将一个const_iterator转换成iterator了。但另一个值的考虑的问题是,这样做的效率如何?答案在于你所转换的究竟是什么样的迭代器。对于随机存取的迭代器(如vector, string和deque)而言,这种转换只需要一个与容器中元素个数无关的常数时间;对于双向迭代器(其它容器,包括基于hash表的非标准容器的一些实现[6])而言,这种转换是与容器元素个数相关的线性时间操作。

这种从const_iterator到iterator的转换可能需要线性的时间代价,并且需要访问const_iterator所属的容器。从这个角度出发,也许你需要重新审视你的设计:是否真的需要从const_iterator到iterator的转换呢?

原则三:正确理解如何使用通过base()得到的iterator

调用reverse_iterator的base()方法可以得到“与之相对应的”iterator。这句话也许有些辞不达意。还是先来看一下这段代码,我们首先把从1到5的5个数放进一个vector中,然后产生一个指向3的reverse_iterator,并且通过其base()函数取得一个iterator。
vector<int> v;
 
  for(int i = 0;i < 5; ++ i) {//插入1到5
v.push_back(i);
}

vector<int>::reverse_iterator ri =//使ri指向3
find(v.rbegin(), v.rend(), 3);
vector<int>::iterator i(ri.base());//取得i.






下图表示了执行上述代码之后的i和ci迭代器位置:











如图所示,rbegin()与end()、rend()与begin()之间存在一个元素的偏移,并且ri与i之间仍然保留了这种偏移。但这还远远不够,针对你所要进行的特定操作,你还需要知道一些技术细节。
原则一指出容器类的部分成员函数仅接受iterator类型的参数。上面的例子中,你并不能直接在ri所指出的位置上插入元素,因为insert方法不接受reverse_iterator作为参数。如果你要删除ri位置上的元素,erase方法也有同样的问题。为了完成这种插入/删除操作,你必须首先用base方法将reverse_iterator转换成iterator,然后用iterator调用insert或erase方法。
先让我们假设你要在ri指出的位置上进行插入操作,并且假设你要插入的值是99。由于ri遍历vector的顺序是自右向左,而insert操作会将新元素插入到ri位置,并且将原先ri位置的元素移到遍历过程的“下一个”位置,插入操作之后,3应该出现在99的左侧,如下图所示:


当然,这些只是我们的假设而已。insert实际上并不接受reverse_iterator类型的参数,所以我们必须用i取代ri。如上所述,在插入操作之前,ri指向元素3而通过base()得到的i指向元素4。考虑到insert与遍历方向的关系,直接使用i进行insert操作,我们会得到与上述假设完全相同的结果。
·如果要在一个reverse_iterator指出的位置上插入新元素,只需通过base()得到相应的iterator然后调用insert方法即可。对于insert操作而言,reverse_iterator与通过其base()方法得到的iterator是完全等价的。

现在再来考虑删除元素的情况,先来回顾一下最初(没有进行insert操作)的vector的状态以及i与ri的位置:

如果你要删除ri指向的元素,你恐怕不能直接使用i了。这时i与ri分别指向不同的位置,因此,你需要删除的是i所指向元素的前一个元素。
·如果要删除一个reverse_iterator指向的元素,需要通过base()得到相应的iterator,并且删除此iterator所指向的前一位值的元素。对于erase操作而言,reverse_iterator与通过其base()方法得到的iterator并非完全等价。

我们还是有必要看看erase操作的实际代码:
vector<int> v;
... //插入1到5,同上
vecot<int>::reverse_iterator ri =
find(v.rbegin(), v.rend(), 3); //ri指向3
v.erase(--ri.base()); //vector编译不通过。

这段代码并不存在什么设计问题,表达式--ri.base()确实能够指出我们需要删除的元素。而且,它们能够处理除了vector和string之外的其他所有容器。但问题是,对于vector和string,--ri.base()可能会无法通过编译。这是因为vector和string容器的iterator和const_iterator通常会采用真实的指针来实现,而ri.base()会返回一个内建指针。
C和C++都加强了对指针类型返回值的限制,你不能直接修改函数返回的指针。如果vector和string选用真实的指针作为iterator,你也就不能修改base()的返回值,所以--ri.base()无法通过编译。出于通用性和可移植性的考虑,应该避免直接修改base()的返回值。当然,我们只需要先增加ri的值,然后再调用base()方法:
...//同上
v.erase((++ri).base());//这下编译没问题了!

当你需要删除一个由reverse_iterator指出的元素时,应该首选这种更为通用而可移植的方法。
由此可见,通过base()方法可以取得一个与reverse_iterator“相对应的”iterator的说法并不准确。对于insert而言,这种对应关系确实存在;但是对于erase操作,情况并非如此简单。当你需要将reverse_iterator转换成iterator的时候,你必须根据所要进行的操作对base()的返回值进行相应的调整。

总结:
STL容器提供了四种不同的迭代器类型,但在实践当中,iterator比其它三种迭代器更为实用。如果你有一个const_iterator,并且可以访问它所指向的容器,你就可以通过advance和distance得到与值相应的iterator。如果你有一个reverse_iterator,你可以通过base()方法得到“相对应的”iterator,但在你进行删除操作之前,必须首先调整iterator的值。

备注与参考:
[1]Scott Meyers, Effective STL: 50 specific ways to improve your use of standard template library. Addison-Wesley, 2001. ISBN 0-201-749629. 本文摘录了Effective STL中的条款26至28。
[2] Const T vs. T Const. Dan Saks. Embedded Systems Programming,1999二月。
[3] 很难弄清为什么iterator会比其它三种迭代器更为特殊。HP公司的最初的STL实现中使用了iterator作为insert和erase的参数,而STL标准化过程中对此也未作改动。这种情况可能在STL的未来版本中有所改变。C++类库工作小组的180号备注中提到:“这个问题应该成为重新审视C++标准中的const问题时的一个主要部分”(http://anubis.dkuug.dk/jtc1/sc-22/wg21/docs/lwg-defects.html)。
[4] 有两个较为常用的STL实现中包含了基于hash表的容器,Dinkumware STL和SGISTL。你可以在1998年12月版CUJ上找到P.J.Plauger的栏目“hash table”,它介绍了Dinkumware STL的实现。就我所知,只有Effective STL的条款25涉及SGISTL中hash类型容器的实现。你可以在http://www.sgi.com/tech/stl/HashAssociative-Containers.html找到SGI版本的调用界面。
[5]STLPort再Debug模式下就是如此。你可以在http://www.stlport.org找到相关资料。
[6]Dinkumware STL实现的hash容器提供双向迭代器,除此以外,SGISTL、STLPort和Metrowerk的hash容器实现都仅提供单向迭代器。

作者简介:
Scott Meyers,C++程序设计领域著名作家,Effective STL是他的第三本C++专著。Brown大学计算机科学博士,NumeriX LLC和Info Cruiser顾问委员会成员。提供计算机科学领域的教学和咨询服务,网址:http://www.aristeia.com
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐