I'm thinking, in part, about how one might translate some of the C++ standard-library algorithms into Python. If that translation requires that the user always supply the original container, rather than using iterators only, then some algorithms become harder to express or less ueful.
Indeed. There's a whole slew of interesting things you can do with iterators that means you won't have a container, only an iterator.
For example, you can define "iterator algebra" functions that take iterators and return iterators. A simple example is this generator, which yields alternating elements of a given iterator.
def alternating(it): while 1: yield it.next() it.next()
The nice thing is that you can combine these easily. For example alternating(alternating(it)) would yield every 4th element.
It would be a pity if the results of iterator algebra operations would not be acceptable to Andrew's proposed algorithm library.
--Guido van Rossum (home page: http://www.python.org/~guido/)