iterators and views of lists

[Brendan Miller]

On Thu, Dec 17, 2009 at 6:44 PM, Steven D'Aprano
<steve at remove-this-cybersource.com.au> wrote:
> On Thu, 17 Dec 2009 12:07:59 -0800, Brendan Miller wrote:
>
>> I was thinking it would be cool to make python more usable in
>> programming competitions by giving it its own port of the STL's
>> algorithm library, which needs something along the lines of C++'s more
>> powerful iterators.
>
> For the benefit of those of us who aren't C++ programmers, what do its
> iterators do that Python's don't?

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.

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)

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).

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.