C++中的前向迭代器
在浏览了各种STL算法的模板定义,如std::search,std::search_n,std::lower_bound之后,您必须已经发现它们的模板定义由类型为 前向迭代器 的对象组成。那么它们是什么,为什么要使用它们?
前向迭代器 是C++标准库中五种主要迭代器类型之一,其他类型包括 输入迭代器 、 输出迭代器 、 双向迭代器 和 随机访问迭代器 。
前向迭代器被认为是 输入和输出迭代器的组合 。它提供了对两者功能的支持。它允许对值进行访问和修改。
需要注意的一件重要事情是, 双向 和 随机访问 迭代器也是有效的前向迭代器,如上面的迭代器层次结构所示。
显著特点
- 可用性 (Usability): 对可取消引用的前向迭代器执行操作不会使其迭代器值不可取消引用,因此允许使用使用此类别的迭代器的算法使用多个迭代器的副本以通过相同的迭代器值多次传递,因此,它“可以用于多遍算法”。
- 相等 / 不相等比较 (Equality / Inequality Comparison): 可以将前向迭代器与另一个迭代器进行比较。由于迭代器指向某个位置,因此仅当它们指向相同位置时,这两个迭代器才相等,否则它们不匹配。
因此,如果 A 和 B 是前向迭代器,则以下两个表达式是有效的:
A == B // 检查相等性
A != B // 检查不相等性
- 取消引用 (Dereferencing): 因为输入迭代器可以通过 * 运算符和 -> 作为右值进行取消引用,输出迭代器可以作为左值进行取消引用,因此前向迭代器可用于两个目的。
// C++ program to demonstrate forward iterator
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v1 = { 1, 2, 3, 4, 5 };
// Declaring an iterator
vector<int>::iterator i1;
for (i1 = v1.begin(); i1 != v1.end(); ++i1) {
// Assigning values to locations pointed by iterator
*i1 = 1;
}
for (i1 = v1.begin(); i1 != v1.end(); ++i1) {
// Accessing values at locations pointed by iterator
cout << (*i1) << " ";
}
return 0;
}
输出结果如下:
1 1 1 1 1
因此,我们可以在迭代器上访问和分配值,因此迭代器至少是前向迭代器(它在层次结构中可能更高)。
- 可递增性 (Incrementable): 可以对前向迭代器进行增加,从而使用 operator ++() 引用下一个序列中的元素。
注意: 我们可以使用前向迭代器与增量运算符的事实并不意味着也可以使用 operator – -()。请记住,前向迭代器是单向的,只能向前移动。
因此,如果 A 是前向迭代器,则以下两个表达式是有效的:
A++ // 使用后增运算符
++A // 使用前增运算符
- 交换 (Swappable): 可交换或交换这些迭代器指向的值。
实际应用
理解其特定后,非常重要的是了解其实际实现。如前所述,前向迭代器既可在访问元素时使用,也可在将元素分配给它们时使用,因为它是输入迭代器和输出迭代器的组合。以下两个 STL 算法可以说明这一事实:
- std::replace: 众所周知,该算法用于将范围内所有等于特定值的元素替换为新值。因此,让我们看看它的内部工作(不要深入细节,只需查看可以使用前向迭代器的地方和不可以使用的地方):
// Definition of std::replace()
template void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value)
{
while (first != last) {
if (*first == old_value) // L1
*first = new_value; // L2
++first;
}
}
在这里,我们可以看到我们已经使用了前向迭代器,因为我们需要使用输入迭代器和输出迭代器的特性。在L1中,我们需要将迭代器first作为rvalue(输入迭代器)进行解引用,在L2中,我们需要将first作为lvalue(输出迭代器)进行解引用,因此为了完成这两个任务,我们使用了前向迭代器。
- std::reverse_copy: 正如名称所示,该算法用于将范围中的元素以相反顺序复制到另一个范围中。关于访问元素和指定元素的问题,前向迭代器是可以的, 但是一旦我们必须将迭代器递减,则不能使用这些前向迭代器 进行此操作。
// Definition of std::reverse_copy()
template OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last,
OutputIterator result)
{
while (first != last)
*result++ = *--last;
return result;
}
在这里,我们可以看到,我们已将last声明为双向迭代器,而不是前向迭代器,因为我们无法像last一样对前向迭代器进行递减,因此在此情况下无法使用它。
注意: 如我们所知,前向迭代器是输入和输出迭代器的组合,因此,如果任何算法涉及任何这两种迭代器的使用,则我们也可以在它们的位置使用前向迭代器,而不影响程序。
因此,上述两个示例非常清楚地展示了前向迭代器在实践中是如何、在何处、为何以及如何使用的。
限制
在研究突出特点之后,人们必须也要了解它的缺陷,尽管它的缺陷不像输入或输出迭代器那样多,因为它在层次结构中处于更高的位置。
- 无法递减: 正如我们可以使用前向迭代器的运算符++()来对它们进行增量操作一样,我们不能对它们进行递减操作。虽然它在层次结构中高于输入和输出迭代器,但仍然无法克服这个缺陷。
这就是为什么它的名字是前向迭代器,它只能朝一个方向移动。
如果A是前向迭代器,则
A-- // 不允许使用前向迭代器进行递减操作
- 关系运算符: 虽然前向迭代器可以与相等运算符(==)一起使用,但无法与其他关系运算符(如=)一起使用。
如果A和B是前向迭代器,则
A == B // 允许
A <= B // 不允许
- 算术运算符: 类似于关系运算符,它们也不能与算术运算符(+、-等)一起使用。这意味着前向运算符只能向一个方向移动,而且只能按顺序移动。
如果A和B是前向迭代器,则
A + 1 // 不允许
B - 2 // 不允许
- 使用偏移解引用运算符([ ]): 前向迭代器不支持偏移解引用运算符([ ]),该运算符用于随机访问。
如果A是前向迭代器,则
A[3] // 不允许