iterators and views of lists

[Terry Reedy]

On 12/18/2009 1:00 AM, Brendan Miller wrote:

>> For the benefit of those of us who aren't C++ programmers, what do its
>> iterators do that Python's don't?

It depends on what one means by 'iterator'. Python iterators do not fit 
in the STL hierarchy. On the other hand, Python indexes are a form of 
random access iterator, the top of the hierarchy.

> Python iterators basically only have one operation:

> next(), which returns the next element or throws StopIteration.
>
> In C++ terminology this is a Input iterator. It is good for writing
> "for each" loops or map reduce operations.
>
> An input iterator can't mutate the data it points to.

For that, Python uses indexes. Random access 'iterators' are a 
generalization of sequence indexes.

> C++ also has progressively stronger iterators:
> http://www.sgi.com/tech/stl/Iterators.html
>
> InputIterator<- read only, one direction, single pass
> ForwardIterator<- read/write, one direction, multi pass
> BidirectionalIterator<- read/write, can move in either direction
> RandomAccessIterator<- read/write, can move in either direction by an
> arbitrary amount in constant time (as powerful as a pointer)

An index can be incremented or decremented an arbitrary amount. Note 
that Python indexes are object pointers, not memory byte pointers, so 
that index + 1 points to the next object, not the next byte of memory in 
possibly the same object. They are, however, much safer than pointers in 
that x[i] can only retrieve objects of x and never, surprise, surprise, 
of some other collection.

> Each only adds extra operations over the one before. So a
> RandomAccessIterator can be used anywhere a InputIterator can, but not
> vice versa.
>
> Also, this is a duck typing relationship, not a formal class
> inheritance. Anything that quacks like a RandomAccessIterator is a
> RandomAccessIterator, but there is no actual RandomAccessIterator
> class.
>
> So, for instance stl sort function takes pair of random access
> iterator delimiting a range, and can sort any datastructure that can
> provide that powerful of an iterator (arrays, vectors, deques).

Python, traditionally, only came with one mutable builtin sequence type, 
so the sort function was made a method of that type. There is also the 
importable array module. Apparently, there has been little demand for a 
generic array.sort method as there is none. One could easily write a 
function that took an array or other seqeunce and two indexes as args.

The generic reversed() builtin function by default uses sequence indexes 
in the obvious manner to return a reversed version of *any* sequence, 
mutable or not.

> http://www.sgi.com/tech/stl/sort.html
>
> MyCollection stuff;
> // put some stuff in stuff
>
> sort(stuff.begin(), stuff.end());
>
> Where begin() and end() by convention return iterators pointing to the
> beginning and end of the sequence.

start,stop = 0, len(seq)

Terry Jan Reedy