What is the difference between an Iterator and a Generator?

Question

What is the difference between an Iterator and a Generator?

Answer 1

Generators are iterators, but not all iterators are generators.

An iterator is typically something that has a next method to get the next element from a stream. A generator is an iterator that is tied to a function.

For example a generator in python:

def genCountingNumbers():
  n = 0
  while True:
    yield n
    n = n + 1

This has the advantage that you don't need to store infinite numbers in memory to iterate over them.

You'd use this as you would any iterator:

for i in genCountingNumbers():
  print i
  if i > 20: break  # Avoid infinite loop

You could also iterate over an array:

for i in ['a', 'b', 'c']:
  print i

Answer 2

A generator is an implementation of an iterator. It is typically a routine that yields multiple values to its caller as opposed to just one.

In c#

// yield-example.cs
using System;
using System.Collections;
public class List
{
    public static IEnumerable Power(int number, int exponent)
    {
        int counter = 0;
        int result = 1;
        while (counter++ < exponent)
       {
            result = result * number;
            yield return result;
    }
}

static void Main()
{
    // Display powers of 2 up to the exponent 8:
    foreach (int i in Power(2, 8))
    {
        Console.Write("{0} ", i);
    }
}
}

See Wikipedia's entry

Answer 3

An iterator traverses a collection one at a time.

A generator generates a sequence, one item at a time.

You might for example, iterate over the result of a generator...

Answer 4

Iterators walk over an existing sequence (such as an array or list). Generators calculate a new value upon every request.

Answer 5

An iterator is commonly used to move through a collection of items. Often having MoveNext() and Current() methods. MoveNext() would shift the pointer to the next collection item (if possible) and return true/false based on success. Current() would provide the actual value.

A generator is an implementation of iterator, but instead of pointing to a pre-existing collection, it creates new items on each MoveNext() call.

Answer 6

An iterator is used to iterate over the objects in a collection, be that an array, linked list, tree, hash map, whatever. You've got a bunch of objects and you want to do something with each one of them.

A generator doesn't just return the items from some finite collection of objects. Instead, it generates them on the fly. You could conceptualize it as an iterator over a collection that is created while you are iterating over it and may not have finite size.

For instance, you could have a generator that spits out prime numbers from 2 to infinity. There's no way you could have a collection of "all prime numbers" and iterate over it with an iterator. You need a generator.

Or you could have a generator that takes an integer and yields the factors of that number one at a time. A generator would benefit you here as you could examine the factors one by one without allocating memory for all of the factors upfront. It would also allow you to use them as they are generated rather than having to generate the entire list up front, which might be slower than you like. Here's an example of such a generator in Python:

def factors(n):
    for i in xrange(1, n+1):
        if n % i == 0:
            yield i

for n in factors(1234567890):
    print n

If you run this you can see the factors printed as they are calculated. We don't need to actually maintain an entire list of all factors in memory.

Answer 7

A Generator is a special function that can behave as an Iterator, returning a value each time it is called. Because it is a function, it can compute each value on demand. And because it is special, it can remember its state from the last time it was called, so the resulting code looks pretty simple.

For example, this generator in python will produce a sequence of integers

def integers():
    int n = 0
    while True:
        yield n
        n += 1

The important thing in this example is the yield n statement. The function will return the value, and the next time it is called, it will continue from that point.

This link has a longer explanation of generators in python: link text

Answer 8

There's too much Python here, and too many people saying generators are the only way to implement an infinite iterator. Here's the example I mentioned (squares of all natural numbers) implemented in C#. ExplicitSquares explicitly implements an iterator (called IEnumerator in C#). ImplicitSquares uses a generator to do the same thing. Both are infinite iterators and have no backing collection. The only difference is whether the state machine is spelled out, or alternatively a generator is used.

using System.Collections;
using System.Collections.Generic;
using System;

class ExplicitSquares : IEnumerable<int>
{
    private class ExplicitSquaresEnumerator : IEnumerator<int>
    {
        private int counter = 0;

        public void Reset()
        {
            counter = 0;
        }

        public int Current { get { return counter * counter; }}

        public bool MoveNext()
        {
            counter++;
            return true;
        }

        object IEnumerator.Current { get { return Current; } }

        public void Dispose(){}
    }

    public IEnumerator<int> GetEnumerator()
    {
        return new ExplicitSquaresEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

class ImplicitSquares : IEnumerable<int>
{
    public IEnumerator<int> GetEnumerator()
    {
        int counter = 1;
        while(true)
        {
            int square = counter * counter;
            yield return square;
            counter++;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public class AllSquares
{
    private static readonly int MAX = 10;

    public static void Main()
    {
        int i = 0;
        foreach(int square in new ExplicitSquares())
        {
            i++;
            if(i >= MAX)
                break;
            Console.WriteLine(square);
        }

        Console.WriteLine();

        int j = 0;
        foreach(int square in new ImplicitSquares())
        {
            j++;
            if(j >= MAX)
                break;
            Console.WriteLine(square);
        }
    }
}