理解 STL 中的迭代器
C++ STL 中的迭代器到底是什么?
What exactly are iterators in the C++ STL?
就我而言，我使用的是 list，我不明白你为什么要制作迭代器 std::list <int>::const_iterator iElementLocator; 以解引用运算符显示列表内容:
<代码>cout <<*iElementLocator; 在将其分配给也许 list.begin() 之后.
In my case, I'm using a list, and I don't understand why you have to make an iterator std::list <int>::const_iterator iElementLocator; to display contents of the list by the derefrence operator:
cout << *iElementLocator; after assigning it to maybe list.begin().
请解释迭代器到底是什么以及为什么我必须取消引用或使用它.
Please explain what exactly an iterator is and why I have to dereference or use it.
推荐答案
STL 中包含三个构建块:
There are three building blocks in the STL:
- 容器
- 算法
- 迭代器
在概念层面，容器保存数据.这本身并不是很有用，因为您想对数据做一些事情；你想对它操作，操纵它，查询它，玩它.算法正是这样做的.但是算法不保存数据，它们没有数据――它们需要一个容器来完成这项任务.给算法一个容器，你就有了一个动作.
At the conceptual level containers hold data. That by itself isn't very useful, because you want to do something with the data; you want to operate on it, manipulate it, query it, play with it. Algorithms do exactly that. But algorithms don't hold data, they have no data -- they need a container for this task. Give a container to an algorithm and you have an action going on.
从技术角度来看，唯一需要解决的问题是算法如何遍历容器.从技术上讲，容器可以是链表，也可以是数组、二叉树或任何其他可以保存数据的数据结构.但是遍历数组与遍历二叉树的方式不同.尽管从概念上讲，算法想要一次从容器中获取"一个元素，然后处理该元素，但从容器中获取下一个元素的操作在技术上是非常容器的――具体.
The only problem left to solve is how does an algorithm traverse a container, from a technical point of view. Technically a container can be a linked list, or it can be an array, or a binary tree, or any other data structure that can hold data. But traversing an array is done differently than traversing a binary tree. Even though conceptually all an algorithm wants is to "get" one element at a time from a container, and then work on that element, the operation of getting the next element from a container is technically very container-specific.
看起来好像您需要为每个容器编写相同的算法，以便算法的每个版本都有正确的代码来遍历容器.但是有一个更好的解决方案:让容器返回一个可以遍历容器的对象.该对象将有一个接口算法知道.当算法要求对象获取下一个元素"时，对象会遵守.因为对象直接来自容器，所以它知道如何访问容器的数据.并且因为对象有一个算法知道的接口，所以我们不需要为每个容器复制一个算法.
It appears as if you'd need to write the same algorithm for each container, so that each version of the algorithm has the correct code for traversing the container. But there's a better solution: ask the container to return an object that can traverse over the container. The object would have an interface algorithms know. When an algorithm asks the object to "get the next element" the object would comply. Because the object came directly from the container it knows how to access the container's data. And because the object has an interface the algorithm knows, we need not duplicate an algorithm for each container.
这是迭代器.
这里的迭代器粘合算法到容器，而不将两者耦合.迭代器与容器耦合，算法与迭代器的接口耦合.这里的神奇之处在于真正的模板编程.考虑标准的 copy() 算法:
The iterator here glues the algorithm to the container, without coupling the two. An iterator is coupled to a container, and an algorithm is coupled to the iterator's interface. The source of the magic here is really template programming. Consider the standard copy() algorithm:
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 的函数功能.
The copy() algorithm takes as parameters two iterators templated on the type In and one iterator of type Out. It copies the elements starting at position first and ending just before position last, into res. The algorithm knows that to get the next element it needs to say ++first or ++res. It knows that to read an element it needs to say x = *first and to write an element it needs to say *res = x. That's part of the interface algorithms assume and iterators commit to. If by mistake an iterator doesn't comply with the interface then the compiler would emit an error for calling a function over type In or Out, when the type doesn't define the function.
相关文章