Iterator

Iterator是一个非常重要的概念。

wikipedia Iterator

In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterator are fixed, iterators are often implemented in terms of the structures underlying a container implementation and are often tightly coupled to the container to enable the operational semantics of the iterator. An iterator performs traversal and also gives access to data elements in a container, but does not itself perform iteration (i.e., not without some significant liberty taken with that concept or with trivial use of the terminology). An iterator is behaviorally similar to a database cursor.

NOTE:请思考iterator和iteration之间关系？我们往往是通过for，while语句来实现iteration。iterator则相当于与一个pointer。

Description

NOTE: 原文的这一段非常值得一读

Internal Iterators

Internal iterators are higher order functions (often taking anonymous functions) such as map, reduce etc., implementing the traversal across a container, applying the given function to every element in turn.

NOTE: 其实这属于functional programming paradigm，结合python的Functional Programming Modules¶、Functional Programming HOWTO¶来理解是非常好理解的。所谓的internal iterator是指使用map等 higher order function（这些函数接收一个函数作为参数），这些函数在内部执行iteration操作，所以对于使用者而言，它就无需显式地使用for、while等循环语句了，这就是所谓的“Internal Iterators”。

External iterators and the iterator pattern

An external iterator may be thought of as a type of pointer that has two primary operations: referencing one particular element in the object collection (called element access), and modifying itself so it points to the next element (called element traversal). There must also be a way to create an iterator so it points to some first element as well as some way to determine when the iterator has exhausted all of the elements in the container. Depending on the language and intended use, iterators may also provide additional operations or exhibit different behaviors.

NOTE: 将iterator比作pointer，是非常容易理解的。

The primary purpose of an iterator is to allow a user to process every element of a container while isolating the user from the internal structure of the container. This allows the container to store elements in any manner it wishes while allowing the user to treat it as if it were a simple sequence or list. An iterator class is usually designed in tight coordination with the corresponding container class. Usually, the container provides the methods for creating iterators.

NOTE:

1、separation of algorithm and structure

2、iterator is an good abstraction and is an abstract language

A loop counter is sometimes also referred to as a loop iterator. A loop counter, however, only provides the traversal functionality and not the element access functionality.

Implicit iterators

Some object-oriented languages such as C#, C++ (later versions), Delphi (later versions), Go, Java (later versions), Lua, Perl, Python, Ruby provide an intrinsic way of iterating through the elements of a container object without the introduction of an explicit iterator object. An actual iterator object may exist in reality, but if it does it is not exposed within the source code of the language.

Implicit iterators are often manifested by a "foreach" statement (or equivalent), such as in the following Python example:

for value in iterable:
    print(value)

NOTE: c++中将此称为range-for

Contrasting with indexing

NOTE: 原文这一段总结的非常好。

Iterator VS pointer

我觉得，最最能够说明iterator VS pointer的是Iterator pattern，在维基百科Iterator pattern#Overview中说明了我们为什么要使用iterator pattern，其实就是iterator pattern相比于pointer的优势所在，iterator更加地抽象，我们依赖于抽象，而不是依赖于具体。

Separation of algorithm and structure principle

本节标题的含义是: 容器与算法的分离。iterator是实现它的一种方式，在下面文章中对此进行了描述:

1、wikipedia Iterator pattern

The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled.

2、 wikipedia Iterator

The primary purpose of an iterator is to allow a user to process every element of a container while isolating the user from the internal structure of the container. This allows the container to store elements in any manner it wishes while allowing the user to treat it as if it were a simple sequence or list. An iterator class is usually designed in tight coordination with the corresponding container class. Usually, the container provides the methods for creating iterators.

iteration and algorithm

在algorithm中，最最常使用的就是iteration了，而iterator pattern正是将两者进行分离。visitor pattern感觉就是运用算法。

Application of iterator

Generic programming

参见Theory\Programming-paradigm\Generic-programming，典型例子就是STL，其中使用iterator来作为container的抽象描述。