注册 登录
LUPA开源社区 返回首页

fandaozhang的个人空间 http://www.lupaworld.com/?381944 [收藏] [复制] [分享] [RSS]

我的博客

迭代器分类

热度 1已有 1663 次阅读2011-6-13 11:07 |系统分类:IT技术|

Categories

分类

An iterator category is a set of requirements that defines a certain type of behavior. A category is an interface, though not in any mechanical sense, i.e. it is not an abstract base class.

迭代器的分类需要定义某种类型的行为。一种分法是接口,尽管不是机械的理解。例如,它并不是一个抽象的基类。

 

Since an iterator is just a collection of requirements, and not a class hierarchy, expressing different kinds of iterators is a little unusual in this object-oriented world we live in.

一个迭代器仅仅是满足了一些标准,不是类的继承。描述不同的迭代器和描述我们的物质世界是不一样的。

 

The way the standard describes it, there are five sets of requirements that define five different categories of iterators: input, output, forward, bidirectional, and random access.

规范的描述,有5种需求集对应了5种类型的迭代器:输入、输出、前向、双向、随机访问。

 

The requirements for each category are little more than the list of member functions each iterator category supports and their associated semantics, with a few footnotes about behavior.

对每个迭代器类型的需求比它的成员函数列表所支持要多,对它们的行为说明很少。(这里翻译比较牵强)

 

Table 2 shows which member functions are supported by each iterator category. Assume that Iter is the iterator type, and x and y are variables of type Iter.

2显示了每种迭代器支持的成员函数。约定:iter是迭代器类型,x  y是迭代器类型的变量。

 

 

 

 

 

Table 2. Iterator categories and required member functions

Member Function

Input     

Output

       Forward      

Bidirectional

Random Access

 

 

Iter x(y)

Y

Y

Y

Y

Y

 

Iter x = y

Y

Y

Y

Y

Y

 

x == y

Y

N    

Y

Y

Y

 

x != y

Y

N

Y

Y

Y

 

x++, ++x

Y

Y

Y

Y

Y

 

x--, --x

N

N

N

Y

Y

 

*x

As lvalue

As lvalue

Y

Y

Y

 

(*x).f

Y

N

Y

Y

Y

 

x->f

Y

N

Y

Y

Y

 

x + n

N

N

N

N

Y

 

x += n

N

N

N

N

Y

 

x - n

N

N

N

N

Y

 

X -= n

N

N

N

N

Y

 

X[n]

N

N

N

N

Y

 

 

In Table 2, the categories become more functional as you move from left to right. Input and output iterators permit relatively few operations, while random access iterators do everything.

在表2里,从左到右,类别的功能越来越多,输入输出迭代器省略了一些相关的操作,随机迭代器最全面。

 

The most basic iterator categories are input and output iterators.

最基础的迭代器是输入输出迭代器。

 

Input iterators are generally for reading elements from some collection in a single pass, such as an input stream.

输入迭代器一般是用于单向的读取元素,比如:输入流。

 

The idea is that the input iterator refers to a range of elements that can be read from, but not written to.

输入迭代器指的是读取,而不是去写入。

 

As a result, the dereference operator yields rvalues.

结果,(这里不好翻译)

An output iterator is just the opposite, where you write elements to a collection that will only be traversed once.

一个输出迭代器仅仅是和输入迭代器相反,当你写入一个元素时需要遍历所有元素。

 

 

The biggest difference between the two is that dereferencing an output iterator yields an lvalue, so you can write to it, but you cannot read from it. And output iterators do not support testing for equality.

输入输出迭代器最大的区别就是:你不可以解引用一个输出迭代器,因为它是一个逻辑值,你可以写它,但是不可以通过它读取。输出迭代器也不支持相等判断。

 

A forward iterator can do everything an input or output iterator can do, which means you can read from a dereferenced value or write to it, but since it is a "forward" iterator, not surprisingly, you can only go forward using a prefix or postfix ++ operator; for example, ++p or p++.

一个前向迭代器可以做输入输出迭代器可以做的事情,也就是说,你可以读也可以写元素。当然,作为一个前向迭代器,你只能这样用:++p p++

 

Bidirectional and random access iterators do what their name implies.

双向迭代器和随机迭代器的功能如他们的名字那样。

 

With a bidirectional iterator, you can advance forward or backward with the ++ or -- operators.

一个双向迭代器,你可以++也可以--

 

A random access iterator can do everything any other iterator can do, and it can advance a given number of places a la pointer arithmetic.

随机迭代器能做其他迭代器可以做的事情,它能递增一段距离就像指针那样。

 

For example, the standard container vector supports random access iterators, which means that the following code will move the iterator around in various ways:

例如:标准容器:vector支持随机迭代器,这就意味着可以写如下代码(在该文的评论里,有人指出这段代码是有问题的。)

vector<string> v;

// Fill up v with some data

vector<string>::iterator p = v.begin();

p += 5;  // Now p refers to the 5th element

p[5];    // Now p refers to the 10th element

p -= 10; // Back to the beginning...

 

Different standard containers offer different types of iterators, depending on what can be efficiently supported, based on the type of data structure that is used by the container.

不同的标准容器提供不同的迭代器,因为效率、数据结构类型的原因。

 

For example, a list (declared in the <list> header) provides bidirectional iterators because lists are usually implemented as a doubly-linked list, which makes it efficient to iterate forward and backward one element at a time. list does not provide random access iterators, though, not because it's impossible to implement, but because it can't be implemented efficiently. Random access in a list would require linear complexity for advancing forward or backward more than one element.

例如,一个list类提供双向迭代器因为列表的思想是一个双向链表,所以,向前或向后移动元素是高效的。List没有提供随机访代器,不是因为不能实现,而是效率比高,随机访问元素需要从头开始移动迭代器。

 

Each standard container supports the category of iterator it can implement efficiently.

每一种标准容器提供的迭代器类型都是高效实现的。

 

Standard algorithms advertise their requirements for an iterator by the category of iterator each requires.

泛型算法建议什么样的迭代器才是需要的。

 

This declaration of iterator categories by algorithms and containers is what determines which algorithms will work with which containers.

算法和容器对迭代器的声明决定了算法如何同容器一同工作。

 

Table 3 contains a list of the standard containers and the category of iterator each supports.

3包含了标准容器和它所支持的迭代器类型。

 

Table 3. Iterator categories for standard containers

3  标准容器支持的迭代器类型

Container

Iterator Category

basic_string

Random access

deque

Random access

list

Bidirectional

map, multimap

Bidirectional

Setmultiset

Bidirectional

vector

Random access

 

basic_string isn't a standard container proper, but it supports most of the same operations as a container, so I included it in the table.

Basic_string 不是标准容器,但是多容器有的它也有,所以上表我多算它一个。

 

If the name basic_string doesn't look familiar to you, it might be because you've been using its typedef'd shortcut: string or wstring.

如果basic_string你不熟悉是因为你用的是简写stringwstring

 

Right now, if you glance back up at Table 2 you might say, "What happened to the input, output, and forward iterators?"

现在,如果你回头看看表2,你可能会问:“输入输出前向迭代器为什么不一样了。”

And you'd be making a good point, if perhaps whining a little. Those categories aren't supplied by the containers; they're used for other things.

你会指出或者是发牢骚:这些类型不是容器支持的。它们用于别的事情(到底什么事情?)

 

In particular, input and output iterators are used with input and output stream iterators (which I will describe in the second part of this article).

实际上,输入输出迭代器用于输入输出流(iostream那种),本文的第二部分我会专门讲。

 

Forward iterators, even if they aren't supplied by any container, allow algorithms to make it clear that they only require the iterators to go forward.

对于前向迭代器,没有哪个容器支持。前向迭代器让算法可以向前访问元素。

 

Consider the remove standard algorithm. It operates on a range, but only needs to go forward, so its declaration looks like this:

考虑remove标准算法,它操作一个区间但是不需要前向的操作,它的声明就像下面这样:

 

template<typename Fwd, typename Val>

Fwd remove(Fwd start, Fwd end, const Val& val)

 

The Fwd template parameter is supposed to let you know that its type is a forward iterator. Val is the type of elements in the range.

通过Fwd 模板的参数,你可以看到它的类型是前向迭代器。Val是区间里的元素类型。

 

(All elements that are equal to val are moved to the end of the range and an iterator to the first one of these elements is returned so you can erase them with the container's erase member function.)

(所有和val相等的元素都被移动东结尾而且一个迭代器返回第一个元素这样你就可以擦除他们通过容器的erase()成员函数。)

 

Recap

 

The C++ standard library contains iterators for the standard containers that implement the iterator pattern, although not literally.

C++的标准库为标准容器实现了迭代器模式,虽然不是全部实现。

 

Using iterators (or const iterators) is the preferred method of traversing elements in a container.

使用iterators或者const iterators是遍历容器元素的首选方法。

 

 

The exact type of an iterator is implementation-defined, but that doesn't matter to you because regardless of exactly what it is, it still supports the interface its category requires.

迭代器实际的类型是“实现定义”,但是并不妨碍你,因为实际类型是忽略了的,这个类型的需求它是实现了的。

 

And finally, iterator categories define groups of requirements that each container or algorithm (standard or otherwise) can supply or require.

最后,迭代器类型定义了每个容器或者算法(标准或者非标准)支持的或者需要的功能,

 

In part two of this article, I'll describe some more flavors of iterator (namely reverse iterators and stream iterators), and show you how to write an iterator for your own class.

 

作者简介()

错误纠正:

p[5] will return the 10th element (which is not used), but p itself will still refer to the 5th element after doing this. Hence the subsequent statement "p -= 10" is a bug: p will point before v.begin(). I verified this by running a simple test program compiled with g++ 4.2.1 through valgrind. It did report an access violation when dereferencing p after the last statement.

刚表态过的朋友 (0 人)

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 注册
验证问答 换一个 验证码 换一个

关于LUPA|人才芯片工程|人才招聘|LUPA认证|LUPA教育|LUPA开源社区 ( 浙B2-20090187 浙公网安备 33010602006705号   

返回顶部