了解 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.
相关文章