理解STL中的迭代器

Question

理解STL中的迭代器

13

C++ STL中的迭代器是什么？

在我的情况下，我正在使用一个list，我不理解为什么你必须制定一个迭代器std::list <int>::const_iterator iElementLocator;，然后通过取消引用运算符来显示列表的内容：
在将其分配给list.begin()之后，cout << *iElementLocator;.

请解释一下迭代器到底是什么以及为什么我需要对它进行解引用或使用它。

- Griffin

6个回答

7

我有点懒，所以不想描述迭代器是什么以及它们如何使用，尤其是当已经有很多在线文章可以自行阅读时。

以下是一些我可以引用的文章，提供完整文章的链接：

MSDN说：

迭代器是指针的一般化，以一种抽象的方式摆脱了指针的要求，使C++程序能够以统一的方式处理不同的数据结构。迭代器充当容器和通用算法之间的中介。算法被定义为在由迭代器类型指定的范围上操作，而不是在特定数据类型上操作。然后，任何满足迭代器要求的数据结构都可以被算法操作。有五种类型或类别的迭代器[...]

顺便说一下，似乎MSDN从C++标准本身中取得了粗体文本，具体来说是从第§24.1/1节中取得的，该节说：

迭代器是指针的一般化，允许C++程序以统一的方式处理不同类型的数据结构（容器）。为了能够构造在不同类型的数据结构上正确高效地工作的模板算法，库不仅形式化了迭代器的接口，还形式化了其语义和复杂性假设。所有迭代器i支持表达式*i，产生某个类、枚举或内置类型T的值，称为迭代器的值类型。对于所有支持表达式(*i).m定义良好的迭代器i，支持表达式i->m，其语义与(*i).m相同。对于每种定义了等号的迭代器类型X，都有一种相应的带符号整数类型，称为迭代器的差异类型。

cplusplus说：

在C++中，迭代器是指向一些元素（例如数组或容器）中的某个元素的任何对象，具有使用一组运算符（至少是增量（++）和解引用（*）运算符）迭代该范围中的元素的能力。

最明显的迭代器形式是指针[...]

你也可以阅读这些文章：

耐心阅读所有内容，希望您有一些关于在C++中迭代器的概念。学习C++需要耐心和时间。

- Nawaz

3

一个迭代器不同于容器本身。迭代器指的是容器中的单个项目，同时提供了到达其他项目的方式。

考虑设计自己的容器而不使用迭代器。它可以有一个 `size` 函数来获取它包含的项目数，并可以重载 `[]` 运算符以允许您按位置获取或设置项目。

但这种“随机访问”在某些类型的容器上实现起来并不容易。如果您获取第一百万个项目：`c[1000000]` 并且容器内部使用链接列表，则必须扫描一百万个项目才能找到您想要的项目。

相反，您可能决定允许集合记住“当前”项目。它可以拥有像 `start`、`more` 和 `next` 这样的函数，以允许您循环遍历内容。

c.start();
while (c.more()) 
{
    item_t item = c.next();

    // use the item somehow
}

但是这样会将“迭代状态”放在容器内部，这是一个严重的限制。如果您想将容器中的每个项与其他每个项进行比较，那就需要两个嵌套循环，两个循环都需要遍历所有项。如果容器本身存储了迭代的位置，那么您无法嵌套两个这样的迭代 - 内部循环将破坏外部循环的工作。

因此，迭代器是迭代状态的独立副本。您可以开始一次迭代：

container_t::iterator i = c.begin();

那个迭代器i是一个单独的对象，它表示容器中的位置。您可以获取该位置存储的任何内容：

item_t item = *i;

您可以移动到下一个项目：

i++;

有些迭代器可以跳过多个元素：

i += 1000;

或者获取相对于迭代器所标识的位置的某个项目：

item_t item = i[1000];

有些迭代器可以向后移动。

你可以通过将迭代器与 end 进行比较来发现是否已经超出了容器的内容范围:

while (i != c.end())

你可以将end视为返回一个迭代器，该迭代器表示容器中最后一个位置之后的位置。

需要注意的一点是，在迭代器（以及C++中通常）中，它们可能会失效。例如，如果您清空了一个容器，则任何指向该容器中位置的迭代器现在都已失效。在这种情况下，对它们进行的大多数操作都是未定义的 - 任何事情都可能发生！

- Daniel Earwicker

2

迭代器是与STL容器相对应的指针。您可以将它们视为STL容器的指针对象。作为指针，您可以使用指针符号（例如*iElementLocator，iElementLocator++）。作为对象，它们将具有自己的属性和方法（http://www.cplusplus.com/reference/std/iterator）。

- rturrado

-1

已经有很多很好的迭代器解释了。只要Google一下。

一个示例。

如果您有任何具体不理解的地方，请回来问。

- ronag

6

Stack Overflow的问题通常会成为谷歌搜索结果的首选，这时那些回答“为什么不自己谷歌一下呢”的回复看起来就显得有些短视了。http://meta.stackexchange.com/questions/5280/embrace-the-non-googlers - Daniel Earwicker

-1

我建议你先阅读有关 C++ 中运算符重载的内容。这将告诉你为什么 * 和 -> 可以表示任何东西。只有在此之后，你才应该去了解迭代器。否则，这可能会让你感到非常困惑。

- julx

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wilhelmtell · Accepted Answer

标准模板库(STL)中有三个基本部分：

容器（Containers）
算法（Algorithms）
迭代器（Iterators）

在概念上，容器保存数据。这本身并不是非常有用，因为您希望对数据进行操作，操纵它，查询它，玩弄它等等。算法正是做这件事的。但是算法不持有数据，它们没有数据 - 它们需要一个容器来完成任务。将容器提供给算法，就可以开始执行操作了。

从技术角度来看，唯一剩下的问题是算法如何遍历容器。从技术上讲，容器可以是链表、数组、二叉树或任何其他可以保存数据的数据结构。但是，遍历数组与遍历二叉树的方式不同。即使从概念上讲，算法只想从容器中“获取”一个元素，然后对该元素进行操作，但是从容器中获取下一个元素的操作在技术上是非常特定于容器的。

似乎需要为每个容器编写相同的算法，以便每个算法版本都具有正确的遍历容器的代码。但有一个更好的解决方案：要求容器返回一个可以遍历容器的对象。该对象将具有算法所知道的接口。当算法要求对象“获取下一个元素”时，对象将遵从请求。因为对象直接来自容器，它知道如何访问容器的数据。并且因为对象具有算法所知道的接口，我们不需要为每个容器复制一个算法。

这就是迭代器。

在这里，迭代器将算法与容器“粘合”在一起，而不耦合两者。迭代器与容器耦合，而算法与迭代器的接口耦合。这里的魔术源于模板编程。考虑标准的copy()算法：

template<class In, class Out>
Out copy(In first, In last, Out res)
{
    while( first != last ) {
        *res = *first;
        ++first;
        ++res;
    }
    return res;
}

copy()算法接受两个泛型类型为In的迭代器和一个类型为Out的迭代器作为参数。它将从位置first开始，直到位置last之前的元素复制到res中。该算法知道如何获取下一个元素，需要使用++first或++res命令。它知道要读取一个元素时需要使用x = *first，并且要写入一个元素时需要使用*res = x。这是算法接口假定的一部分，并且迭代器已经承诺遵守此接口。如果迭代器出现错误，没有遵守接口，那么编译器在调用类型为In或Out的函数时会生成错误。