• Index

迭代器库

Reads: 25

初识迭代器

本部分教程将讲解迭代器的使用,这样就可以更灵活地使用C++的容器库和算法库。设计迭代器将留到高级教程中讲解。

在前面排序的教程中,曾经使用过迭代器,迭代器为算法库和容器库之间的操作提供了通用的方案,使得我们使用它们的时候非常方便。

我们熟悉的字符串类和std::vector都有很多成员函数需要或者返回迭代器。例如前面排序用到的成员函数begin()end()就是返回第一个位置和最后一个位置的迭代器,然后给std::sort()函数调用;还有就是std::vectorinsert()erase()都是必须以迭代器作为参数来操作。

简述迭代器的作用和操作

如果指针保存静态数组地址,那么这个指针也算是一个迭代器,例如下面的指针p

int array[10]{};
int *p = array + 4;

像上面的指针p保存了array[4]的地址。因为指针保存了这个数组中某个元素的地址,我们知道静态数组中的地址是连续的,也就是说这个指针相当于保存了这个数组的某个元素的位置,然后可以通过*对地址代表的内存进行操作。

接着这个指针还可以通过++来移动到下个元素的位置,也可以通过--来移动到上个元素的位置。

int array[10]{};
int *p = array + 4;
++p; // 移动到下一个元素, 就是array[5]的位置
++p; // 移动到下一个元素, 就是array[6]的位置
++p; // 移动到下一个元素, 就是array[7]的位置
--p; // 移动到上一个元素, 就是array[6]的位置
*p = 666; // 给当前位置的元素赋值为666

像这样,可以逐个元素按顺序地移动指针就是迭代,这就是迭代器(英文:Iterator)这个名称的由来。

而我们使用的迭代器大部分都是类,这些迭代器类的用法,会尽量保持和指针一样的操作,所以我们可以像指针那样使用迭代器。更具体的用法在接下来的教程中慢慢讲解,这里不需要太深入了解,只要看了后面讲解的使用方法,就会很容易明白迭代器是什么了。

简述迭代器的设计原则

迭代器基本上都是专用的,如std::vector的迭代器不能用来保存std::string的元素位置,如下,去掉最后两行开头注释将会编译报错:

std::vector<int>::iterator iter1; // std::vector<int>的迭代器
std::vector<long long>::iterator iter2; // std::vector<long long>的迭代器
std::string::iterator iter3; // std::string的迭代器
// iter1 = iter2; // std::vector<int>和std::vector<long long>不是同一种类型
// iter1 = iter3; // std::vector<int>和std::string不是同一种类型

但是所有的迭代器都会统一操作,屏蔽了这些操作的细节,使得我们每次都可以用相同的方法操作迭代器。例如我们使用迭代器的时候使用++,就会使迭代器指向下一个元素,但是迭代器类内部的代码不一定是写了++,有可能是其他。

因为迭代器统一了操作,所以算法库就可以很轻松地操作各种不同的容器了。

简述迭代器的分类

标准迭代器有五种:

  • 输入迭代器Input Iterator
  • 输出迭代器Output Iterator
  • 前向迭代器Forward Iterator
  • 双向迭代器Bidirectional Iterator
  • 随机访问迭代器Random Access Iterator

程序经常会用到容器,而使用容器基本上离不开使用迭代器。只是使用迭代器的话,暂时不需要精通迭代器,但是基本的规则是要知道的。

std::list<int>::iterator iter1; // std::list的迭代器是双向迭代器
std::vector<int>::iterator iter2; // std::vector的迭代器是随机访问迭代器
iter2 += 4; // 允许随机访问任何的元素, 这里是直接跳到这个元素后的第四个元素的位置
++iter1; // 双向迭代器只支持++和--操作
// iter1 += 4; // 双向迭代器不支持随机访问, 也就是不能跳着访问其他元素

容器std::vector使用的是随机访问迭代器,例如上面的iter2 += 4;就是从当前位置跳到它后面的第四个元素的位置上,也可以跳到其他位置,这就是随机访问。而std::list的迭代器是双向迭代器,它只提供了++--操作,所以iter1 += 4;是会编译报错的,如果需要iter1移动到它后面的第四个元素的位置,只能使用四次的++iter1;

在说明文档中,都会说明容器的迭代器的种类。如果知道迭代器种类,但不知道这个种类的迭代器怎么用就很尴尬了。以下列出所有迭代器种类对应的必须提供的操作(假设X是迭代器数据类型,ab是迭代器变量,n是整数,t是值,m是成员):

种类 属性 示例
所有种类 可复制构造、可复制赋值并且可以析构 X b(a);
b = a;
可以递增 ++a
a++
随机访问 双向 前向 输入 支持相等和不相等的比较操作 a == b
a != b
可以解引用成一个右值 *a
a->m
输出 可以解引用成一个左值
(前提是允许修改内容的迭代器数据类型)
*a = t
*a++ = t
可以默认构造 X a;
X()
无论是解引用还是自增,都不能影响解引用的行为 { b=a; *a++; *b; }
可以递减 --a
a--
*a--
支持算术操作符 +- a + n
n + a
a - n
a - b
支持 <><=>= 这些比较操作 a < b
a > b
a <= b
a >= b
支持 +=-= 操作 a += n
a -= n
支持偏移解引用操作([] a[n]

Comments

Make a comment

  • Index

WARNING: You are using an old browser that does not support HTML5. Please choose a modern browser (Chrome / Microsoft Edge / Firefox / Sarafi) to get a good experience.