我正在学习 Koenig & Moo 的《Accelerated C++》一书。
练习 8-2 要求我自己实现一些模板化函数<algorithm>
and <numeric>
,并指定我的实现需要哪种迭代器。
当尝试实施时std::search
,我确定我只需要“输入”迭代器。
到目前为止,这是我的代码:
template <class In1, class In2>
In1 search(In1 b, In1 e, In2 b2, In2 e2)
{
if (b2 != e2) {
while (b != e) {
if (*b == *b2) {
In1 bc = b;
In2 b2c = b2;
while (bc != e && b2c != e2 && *bc == *b2c) {
++bc;
++b2c;
}
if (b2c == e2)
return b;
}
++b;
}
}
return e;
}
然而,纵观实施std::search
用我的编译器安装后,我可以看到它们使用“前向”迭代器,但我无法理解为什么,因为不需要写入,只需读取,并且输入迭代器满足要求。
这里有人可以帮助我理解这一点吗?为什么我需要使用“前向”迭代器来实现std::search
?
使用输入迭代器,您只能通过该范围一次。也就是说,一旦取消引用并递增迭代器,就无法返回并再次取消引用它。
此类迭代器对于很多事情都非常有用。例如,如果您正在从某种流中读取内容,那么一旦您从流中读取了某些内容,您就无法返回并再次读取该内容;您无法存储迭代器的副本,继续使用原始迭代器进行迭代,然后返回并开始使用副本进行迭代并假设您会得到相同的结果。
在您的算法中,您多次遍历该范围(请参阅此处源代码中的注释):
template <class In1, class In2>
In1 search(In1 b, In1 e, In2 b2, In2 e2)
{
if (b2 != e2) {
while (b != e) {
if (*b == *b2) {
In1 bc = b; // copy iterator b
In2 b2c = b2;
while (bc != e && b2c != e2 && *bc == *b2c) {
++bc; // increment the copy of iterator b
++b2c;
}
if (b2c == e2)
return b;
}
++b; // increment the original b
}
}
return e;
}
ForwardIterator
是可用于多遍算法的最基本类型的迭代器,因为它保证您可以多次迭代某个范围。
迭代器是可变的还是不可变的(即是否可以修改其类型的迭代器引用的元素)与迭代器的类别无关:ForwardIterator
可能是不可变的。例如,任何迭代器类别的 const 迭代器都是不可变的(或者,对于一个具体示例,std::forward_list<int>::const_iterator
在 C++0x 中是一个不可变的前向迭代器)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)