Effective STL~4 迭代器

目录

第26条:iterator优先于const_iterator、reverse_iterator以及const_revserse_iterator

STL标准容器提供4种不同的迭代器类型:iterator、const_iterator、reverse_iterator、const_reverse_iterator。
对于容器类container而言,iterator类型相当于T,const_iterator相当于const T
对于一个iterator或const_iterator进行递增,则可以移动到容器中的下一个元素,从而可以实现从容器头部遍历到尾部。

reverse_iterator、const_reverse_iterator分别对应于T、const T,区别在于这2个迭代器递增的效果是从容器的尾部反向遍历到头部。

注意:原文提到vector的insert和erase函数原型中,迭代器参数都是iterator类型的。然而,时至C++11以后,不论GCC,还是MSVC的STL实现,都已经改成const_iterator,而且对重载函数支持的参数类型也做了扩充。

// GCC关于vector容器的insert、erase函数原型
iterator insert(const_iterator __position, const value_type& __x);
iterator insert(const_iterator __position, value_type&& __x);
iterator insert(const_iterator __position, initializer_list<value_type> __l);
iterator insert(const_iterator __position, size_type __n, const value_type& __x);
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last);

iterator erase(const_iterator __position);
iterator erase(const_iterator __first, const_iterator __last)

iterator和const_iterator关系

因为iterator到const_iterator之间存在隐式转换,通过调用iterator的base成员函数,可以将iterator转换为const_iterator,反过来则不行。而得到const_iterator,意味着很难将这类迭代器与容器的某些成员函数一起使用,因为无法通过const_iterator修改所指向的内容。

reverse_iterator与const_reverse_iterator之间,也存在类似关系。

当然,这并不意味着const_iterator一无是处。有许多算法并不关心所面对的是什么类型的迭代器,通常只关心这些迭代器属于何种类别(category)。

为什么应尽可能使用iterator,而避免使用const或reverse型迭代器?

因为,

  • 有些版本insert和erase函数要求使用iterator。如果要调用这些函数,那就必须使用iterator。const和reverse型迭代器则不行。
  • 要想隐式地将一个const_iterator转换成iterator是不可能的。这种技术不普遍,且效率无法保证,见条款27.
  • 从reverse_iterator转换而来的iterator在使用前可能需要相应的调整。见条款28。

2个iterator之间混合使用

// OK
typedef deque<int> IntDeque; // typedef极大简化STL容器类和iterator类型的用法
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;

Iter i;
ConstIter ci;
// ...
if (i == ci) // 使ci和i指向同一容器,然后比较一个iterator和一个const_iterator
{
       // ...
}

2个迭代器之间比较if (i == ic) ,应该没有问题,一个对象类型iterator,另一个是const_iterator。比较时,i转换成const_iterator类型。

然而,有些STL实现并没有将operator==实现为iterator的成员函数,就会导致上面的比较无法通过编译。解决办法是交换i和ci的位置。
类似地,如果试图在2个随机访问迭代器之间做减法操作:

if (i - ci >= 3) ... // 如果i和ci之间至少有3个元素

if (ci + 3 <= i) ... // 以上if语句无法编译通过时,可以这样转换解决

避免这种问题最简单的办法就是:减少混用不同类型的迭代器的机会,尽量使用iterator来代替const_iterator,避免卷入const_iterator的麻烦中。

[======]

第27条:使用distance和advance将容器的const_iterator转换成iterator

有些容器类的成员函数仅仅接受iterator作为参数,const_iterator不能作为其参数。那么,如果手上有一个const_iterator,如何转换为iterator呢?
如条款26所述,const_iterator到iterator之间并没有隐式转换。我们可能会考虑到类型转换。
下面的代码,试图把一个const_iterator强制转换为iterator:

typedef deque<int> IntDeque;                      // 类型定义,简化代码
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;

ConstIter ci;
...
Iter i(ci);  // 编译错误:从const_iterator到iterator没有隐式转换
              
Iter i(const_cast<Iter>(ci));  // 编译错误:不能将const_iterator强制转换为iterator

示例是针对deque,然而对于其他容器类(list、set、multiset、map、multimap等)得到的结果也一样。不过,也许在vector或string类的情形下,强制转换的代码能通过编译,但这属于特殊情况。

为什么包含显式类型转换的代码不能通过编译?
因为对于这些容器类型,iterator和const_iterator是完全不同的类,它们之间的关系很远。试图将一种类型转换为另一种类型是毫无意义的,这是const_cast转换被拒绝的原因。不仅如此,reinterpret_cast、static_cast,甚至C风格类型转换也不行。

为什么对于vector和string容器,或许可以通过编译?
不过,对于vector和string容器,上面包含const_cast的代码也许能通过编译。这是因为,大多数STL实现都会利用指针作为vector和string的迭代器。对于这样的实现,vector::iterator和vector::const_iterator分别被(通过类型定义)定义为T和const T,string::iterator和string::const_iterator则分别被定义为char和const char。因此,在这样的实现中,const_iterator到iterator的const_cast转换被解释为从const T到T的转换,因而可以通过编译,而且结果正确。
然而,reverse_iterator和const_reverse_iterator仍然是真正的类(而非T和const T),所以你不能直接通过const_cast强制转换成reverse_iterator。
而且,如条款50,STL实现为了便于调试,通常只会在Release模式下,才使用指针来表示vector和string的迭代器。
综上,即便对于vector和string,将const迭代器强制转换成迭代器也是不可取的,因为移植性将是一个问题。

advance+distance将const_iterator转换成iterator
将上面代码稍作修改,使用advance和distance就能将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()); // 使得i指向d的其实位置
advance(i, distance(i, ci)); // 编译错误:需要修改才能编译。移动i,使它指向ci所指的位置

distance和advance都是声明在中的2个函数模板:
distance用来取得(同一个容器的)2个迭代器之间的距离;advance用来将一个迭代器移动指定的距离。

也就是说,代码试图将i从容器d的起始位置开始,移动distance距离,而distance距离是容器d起始位置到迭代器ci的距离,从而将const_iterator类型的ci,转换成同位置的iterator类型的i。
然而,问题在于distance函数模板接受的参数必须是同一种类型:

template<class InputInterator>
typename iterator_traits<InputInterator>::difference_type distance(InputInterator _First, InputInterator _Last);

我们给distance同时传递iterator类型迭代器和const_iterator类型迭代器,编译器无法同时实例化为两种类型。要想让distance编译通过,需要排除这里的二义性。

advance(i, distance<ConstIter>(i, ci)); // OK:将i和ci都当做const_iterator,计算出它们之间的距离,然后将i移动这段距离

advance+distance转换const_iterator为iterator效率问题
既然advance和distance能将const_iterator转换为iterator,那么效率如何?
效率取决于你所使用的迭代器。
对于随机访问的迭代器(如vector、string、deque产生的迭代器),是常数时间的操作;
对于双向迭代器(所有其他标准容器的迭代器,以及某些哈希容器实现(条款25)的迭代器),是线性操作时间。

因为迭代器转换可能需要线性操作时间,所有尽量避免转换。如果需要,尽量用iterator替代const或reverse型的迭代器。

[======]

第28条:正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

由reverse_iterator的base()成员函数,能得到与之对应的iterator,但没有说明真正的含义。
看一个例子:把1~5放进一个vector,然后将一个reverse_iterator指向值3,并通过其base()成员函数初始化一个iterator。

vector<int> v;
v.reserve(5);
for (size_t i = 0; i <= 5; i++)
{
       v.push_back(i);
}
vector<int>::reverse_iterator ri = find(v.rbegin(), v.rend(), 3);
vector<int>::iterator i(ri.base());

cout << *ri << ", " << distance(v.rbegin(), ri) << endl;
cout << *i << ", " << distance(v.begin(), i) << endl;

执行上面代码,该vector和相应迭代器状态:
Effective STL~4 迭代器

可以知道,reverse_iterator与base()产生的iterator之间存在偏差:ir指向3,i指向4。
然而,容器类的有些成员函数仅接受iterator作为迭代器参数,如insert函数不接受reverse_iterator参数,如果要插入(insert)元素,就要先通过base成员函数将其转化为iterator,然后用iterator来完成插入。删除(erase)元素也存在类似的问题。

对于插入操作
ri和ri.base()是等价的。

例如,插入元素99之前,ri指向3,i指向4。考虑insert与遍历方向的关系,用i进行insert操作,结果跟用ri来指定插入位置得到的结果相同。

Effective STL~4 迭代器

对于删除操作
ri和ri.base()是不等价的。

在插入99之前,ri和i指向不同的元素,如果要删除,就必须删除i前面的元素。

vector<int> v;
...
v.erase(--ri.base()); // 删除ri所指元素:试图删除ri.base()前一个元素,对于有的STL vector和string实现,编译可能不通过

v.erase((++ri).base()); // 同上,删除ri所指元素

综上,通过base()成员函数,将reverse_iterator转换为iterator后,用iterator对容器进行插入、删除操作时,一定要清楚差别。

[======]

第29条:对于逐个字符的输入请考虑使用istreambuf_iterator

保留空白字符
假设我们想把文本文件"interestingData.txt"的所有内容拷贝到一个string对象中,可以用如下代码:

// 存在某些问题:不会保留空白字符
ifstream inputFile("interestingData.txt");
string fileData((istream_iterator<char>(inputFile)), istream_iterator<char>());

cout << fileData << endl;

然而,这段代码并没有把文件中的空白字符拷贝到string对象中。这是因为ifstream使用operator>>来完成读操作的,而operator>>默认情况下会跳过空白字符。
如果想要保留空白字符,那么就要修改默认行为,只需要清除输入流的skipws标志即可:

// OK:达到了保留空白字符的效果
ifstream inputFile("interestingData.txt");
inputFile.unsetf(ios::skipws); // 添加了这一行:禁止忽略inputFile中的空格
string fileData((istream_iterator<char>(inputFile)), istream_iterator<char>());

cout << fileData << endl;

提高ifstream读取字符的效率
istream_iterator内部使用operator>>会执行格式化输入,每调用一次,就会执行许多附加操作,导致效率低下。如果只是想从输入流读出下一个字符,完全没必要进行这些附加操作。

解决办法就是使用istreambuf_iterator。其用法类同istream_iterator,但istream_iterator对象operator>>从输入流读取单个字符,而istreambuf_iterator>>则直接从流的缓冲区中读取下一个字符。

使用istreambuf_iterator读取字符后,不再需要清除输入流skipws标志,因为istreambuf_iterator不会跳过任何字符,只是简单的取回流缓冲区的下一个字符(不论是什么字符)。

// OK
ifstream inputFile("interestingData.txt");
string fileData((istreambuf_iterator<char>(inputFile)),  istreambuf_iterator<char>());

cout << fileData << endl;

综上
1)如果你需要从一个输入流逐个读取字符,那么可不必使用格式化输入;如果关心的是读取流的时间开销,那么使用istreambuf_iterator取代istream_iterator,可以有效改善性能。对于非格式化的逐个字符的输入过程,总是应该考虑使用istreambuf_iterator。
2)对于非格式化的逐个字符输出过程,也应该考虑使用outtreambuf_iterator,从而改善性能。

[======]

上一篇:习题6-6 使用函数输出一个整数的逆序数


下一篇:【设计模式】笔记之【适配器模式】