Recap

If you have a Collection (List or Set) you can use a for-each loop to visit every element in the collection. For example, you can sum the values of all of the elements in a Set:

/*
Set<Double> someNumbers = ...
*/

double sum = 0.0;
for (Double d : someNumbers)
{
   sum += d;
}
double average = sum / someNumbers.size();

The code fragment above has a potential problem; do you see it?

Iterators

An Iterator is an object that lets the client traverse a collection. Iterator is actually an interface:

public interface Iterator<E> 
{
   boolean hasNext();
   E next();
   void remove(); //optional
}

Every class that implements Collection has a method named iterator that returns an iterator for the elements in the collection.

Iterator Traversal

Traversing a collection using an iterator uses a method similar to the chained traversal method. Suppose you have collection of elements that we can label e0, e1, and so on.

Note that the order of the elements is determined by the container.

Iterator Traversal: Step 1

The first thing we need to do is to get an iterator for the collection by calling the collection's iterator method. This creates an iterator object that points not at the first element e0, but at a position immediately before e0.

/*
Set<Double> someNumbers = ...
*/

double sum = 0.0;
Iterator<Double> iter = someNumbers.iterator();

Iterator Traversal: Step 2a

Inside the loop, you use the iterator to access the current element in the traversal using the method next. next returns the next element in the traversal, and throws an exception if there are no more elements in the traversal.

double sum = 0.0;
Iterator<Double> iter = someNumbers.iterator();
while (???)
{
   sum = sum + iter.next();
}

Iterator Traversal: Step 2b

Invoking next has the side-effect of moving the iterator to a position just before the next element in the collection.

Iterator Traversal: Step 3

The loop body should execute only if next will succeed (not throw an exception). The iterator method hasNext returns true if next will succeed, and false otherwise.

double sum = 0.0;
Iterator<Double> iter = someNumbers.iterator();
while ( iter.hasNext() )
{
   sum = sum + iter.next();
}

Iterator Traversal: Step 4

Eventually, the loop will cause the iterator to move past the last element. At this point, hasNext will return false and the loop will stop.

Why Iterators?

For-each loops are really iterator loops that the compiler hides from the programmer.

For-each loops are the preferred method of traversing a collection, but it has limitations. One limitation is that you cannot remove elements from a collection using a for-each loop.

Why Iterators?

Suppose you want to remove all the numbers greater than some value from a collection (of numbers). You might try something using a for-each loop like this:

import java.util.*;

public class ForEachFail
{
   public static void main(String[] args)
   {
      // Create list of numbers from 0-9
      List<Double> numbers = new ArrayList<Double>();
      for (int i = 0; i < 10; i++)
      {
         numbers.add((double)i);
      }
      
      // Remove 5-9 ?
      final double THRESHOLD = 5.0;
      for (Double d : numbers)
      {
         if (d >= THRESHOLD)
         {
            numbers.remove(d);
         }
      }
      System.out.println(numbers);
   }
}

If you compile and run the program you will find that a ConcurrentModificationException exception is thrown. If a collection is modified while an iterator is visiting the collection, the iterator will probably throw a ConcurrentModificationException the next time next is invoked.

Using Iterator remove

The only safe way to remove an element from a collection during an iterator-based traversal is to create an iterator and invoke its remove method:

// Remove 5-9
final double THRESHOLD = 5.0;
Iterator<Double> iter = numbers.iterator();
while (iter.hasNext())
{
   if (iter.next() >= THRESHOLD)
   {
      // Remove the element previously
      // returned by next
      iter.remove();
   }
}

Note that you can only invoke remove once each time you invoke next.

Using Iterator remove with Map

Suppose you have a Map holding the prices of some items:

$539.95 Bose SoundDock 10 Digital Music System
$359.95 Bose SoundDock Portable Digital Music System
$269.95 Bose SoundDock Series II Digital Music System
$499.95 Boston Acoustics i-DS3 plus Speaker System for iPhone/iPod
$299.95 Creative ZiiSound D5 Wireless Bluetooth Speakers
$299.95 Geneva Sound S Speaker System for iPod and iPhone
$299.95 Harman Kardon Go + Play Micro Portable Loudspeaker Dock for iPod and iPhone
$199.95 JAMBOX by Jawbone Wireless Speaker - Blue
$229.95 JBL On Stage 400P Loudspeaker for iPhone and iPod
$199.95 Philips Fidelio DS8500 Tabletop Speaker Dock
$299.95 Philips Fidelio DS8550 Portable Speaker Dock
$499.95 Philips Fidelio DS9000 Premium Speaker Dock with Remote
$199.95 XtremeMac Tango TRX with Dock 2.1 Wireless Audio System
$299.95 iHome iP1 Studio Series Audio System for iPod/iPhone

The keys are the item names and the values are the prices.

Using Iterator remove with Map

If you are gift shopping for Christmas and looking for a good gift, then you might be interested only in items above a certain price point (assuming price is related to quality/desirability), say $300:

// Map<String, String> prices = ...
// dollar amounts are held as Strings in the map

double THRESHOLD = 300;

Iterator<String> iter = prices.values().iterator();
while (iter.hasNext())
{
   double price = Double.parseDouble(iter.next());
   if (price < THRESHOLD)
   {
      iter.remove();
   }
}

Notice that we are removing elements from the values of the map...

Using Iterator remove with Map

If you read the documentation for Map.values you will see that the collection returned by Map.values is backed by the map, so changes to the map are reflected in the collection, and vice-versa. If you print out the entries in the modified map you get:

$539.95 Bose SoundDock 10 Digital Music System
$359.95 Bose SoundDock Portable Digital Music System
$499.95 Boston Acoustics i-DS3 plus Speaker System for iPhone/iPod
$499.95 Philips Fidelio DS9000 Premium Speaker Dock with Remote

which are indeed the items with price greater than $300.

Download the program here: Prices.java