How are Iterators Created?

Question

A common approach to create an Iterator is :

Iterator iter = myarray.iterator(); 

Can anybody tell me how iter is created without new operator? I know Iterator is an interface, so who implements it?

Answer 1

The collection classes from the standard library that implement Iterable interface usually have an inner class that extends Iterator, though that's not an requirement. You can subclass and instantiate Iterator anywhere you want, just like any other classes.

Here is an example from my utils where I have written a method that provides an Iterable instance for the given array.

public static Iterable<A> asIterable(final A[] xs) {
  return new Iterable<A>() {
    @Override
    public Iterator<A> iterator() {
      return new Iterator<A>() {
        private int i = 0;

        @Override
        public boolean hasNext() {
          return i < xs.length;
        }

        @Override
        public A next() {
          A x = xs[i];
          i++;
          return x;
        }

        @Override
        public void remove() {
          throw new UnsupportedOperationException(
            "Cannot remove an element from an array.");
        }
      };
    }
  };
}

Answer 2

Iterator is an interface and it already implemented with every implementation of List interface like ArrayList, Vector, LinkedList and others you do not need to worry about its implementation just use it.

Answer 3

First of all class of object from myarray reference must implement interface Iterable. It means that class must add implementation to Iterator iterator() method.

To make things easy iterator() method returns object of private inner class implementing Iterator interface. It is done this way because inner classes have acces to all fieldss of outer classes (even private).

Here is example of reverse array iterator

class ReverseArray implements Iterable{
    private Object[] data;// some data to iterate
    public ReverseArray(Object[] data) {
        this.data=data;
    }
    private class ReverseIterator implements Iterator {
        int counter = data.length;

        public boolean hasNext() {
            if(counter>0)
                return true;
            else
                return false;
        }

        public Object next() {
            return data[--counter];
        }

        public void remove() {
            //TODO Auto-generated method stub
        }
    }

    public Iterator<Integer> iterator() {
        return new ReverseIterator();
    }
}

Lets test it

    public static void main(String[] args) {
        ReverseArray reverseArray=new ReverseArray(new Integer[]{1,2,3,4,5});
        for(Object i:reverseArray)
            System.out.print(i+"; ");
        //OUT: 5; 4; 3; 2; 1;  
    }

Answer 4

You haven't shown what myarray is, but that's the key to finding the implementation. For example, if myarray refers to an ArrayList at execution time, then it'll call ArrayList.iterator() which will return an instance of the private ArrayList.Itr class. (At least in the JRE implementation I happened to look at.)

Answer 5

An iterator is generally implemented as a private inner class of a data structure so that its methods can be written to suitably iterate over that structure's data. So the iterator will only be accessible through a method provided by the data structure class, in your case

myarray.iterator();

Answer 6

myarray.iterator is a function. The new operator only applies to types. As Mr. Skeet stated in his answer, the return value is likely an inner class that implements Iterator and the implementation of the iterator() method calls new on the inner class.

Answer 7

Here's the code snippet from the ArrayList class for that part. As you can see, there is an internal private class that implements the interface Iterator and an instance of this class is returned.

  766       /**
  767        * Returns an iterator over the elements in this list in proper sequence.
  768        *
  769        * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
  770        *
  771        * @return an iterator over the elements in this list in proper sequence
  772        */
  773       public Iterator<E> iterator() {
  774           return new Itr();
  775       }
  776   
  777       /**
  778        * An optimized version of AbstractList.Itr
  779        */
  780       private class Itr implements Iterator<E> {
  781           int cursor;       // index of next element to return
  782           int lastRet = -1; // index of last element returned; -1 if no such
  783           int expectedModCount = modCount;
  784   
  785           public boolean hasNext() {
  786               return cursor != size;
  787           }
  788   
  789           @SuppressWarnings("unchecked")
  790           public E next() {
  791               checkForComodification();
  792               int i = cursor;
  793               if (i >= size)
  794                   throw new NoSuchElementException();
  795               Object[] elementData = ArrayList.this.elementData;
  796               if (i >= elementData.length)
  797                   throw new ConcurrentModificationException();
  798               cursor = i + 1;
  799               return (E) elementData[lastRet = i];
  800           }
  801   
  802           public void remove() {
  803               if (lastRet < 0)
  804                   throw new IllegalStateException();
  805               checkForComodification();
  806   
  807               try {
  808                   ArrayList.this.remove(lastRet);
  809                   cursor = lastRet;
  810                   lastRet = -1;
  811                   expectedModCount = modCount;
  812               } catch (IndexOutOfBoundsException ex) {
  813                   throw new ConcurrentModificationException();
  814               }
  815           }
  816   
  817           final void checkForComodification() {
  818               if (modCount != expectedModCount)
  819                   throw new ConcurrentModificationException();
  820           }
  821       }

Answer 8

If you look inside the implementation of iterator(), there'll be a new inside there, somewhere. For example, this is the iterator() method from OpenJDK's ArrayList:

public Iterator<E> iterator() {
    return new Itr();
}

In turn, Itr refers to a private inner class that implements the Iterator interface:

private class Itr implements Iterator<E> {
    // implementation details
}