Duplicate Collections For Modification Safety

This is one of the JavaIdioms.

Problem

You want to use the new collections library and and iterators. But the collection is occasionally modified and you are worried about the IteratorInvalidationProblem. In particular, suppose you have a collection which has three extant iterators. If you modify the collection, the iterators will now throw a comodification exception (to let you know that the data you are iterating over has changed). Catching this exception everywhere you use iterators is a pain in the butt.

Solution

Notice that, frequently, it doesn't strongly affect program correctness if the existing iterators use a slightly out of date version of the collection. Therefore, when making a change to the colleciton observers, replace it with a copy like so

   public void addFrameListener(FrameListener foo)
   {
       _listenerList = new ArrayList(_listenerList);
       _listenerList.add(foo);

   }

Now, in the example scenario, the three iterators won't fail (because the collection they point to hasn't changed), but new iterators will iterate over the updated collection. And, eventually, the old colleciton will be garbage collected (after all the iterators over it are garbage collected).

In addition, use java.util.unmodifiable...() methods to wrap your collections whenever you hand them out to som other part of the code that is not at all supposed to modify the collection (available since Java 1.2). In the example scenario, the three iterators should get unmodifiable versions (or one unmodifiable version) of the collection.

If you use such collections, you only need to make a copy when modifying the collection, rather than when iterating over it. This is more efficient if iteration is more common than modification, which is often the case in GUI components.

Examples

I began to use this for custom listeners in GUI code (using the 1.1 Event model). Recent conversations around the lab suggest it's a common trick to avoid comodification exceptions.

Originally by WilliamGrosso. Refactored with contributions from NatPryce, ThomasWeidenfeller.

It should be noted that if you only copy when you modify as Nat suggests, you can absorb most of the cost of duplicating the collection -- which can be considerable. -- RobertDiFalco

Smalltalk has #copyWith:, which does the copy and append in a single step. It is optimised so that the copy allows room for the extra element. -- AnonymousDonor

If you assume that, given a writable copy you will at some point need to grow the underlying data-structure (such as for indexed collections), you will already be creating a copy. I'd like to explore the idea of doing this on a less granular basis. Something like toMutable and toImmutable. I dunno. -- RobertDiFalco

Basically, you would want a CopyOnWrite that would copy on the first modification for owner a but not for the second or third modification. This is fairly easy to do with CeePlusPlus because you can overload the assignment operators. In Java or SmallTalk, it is difficult to determine the boundaries of ownership. I want to avoid having to perform #copyWith on each modification. -- RobertDiFalco

Does ownership matter? We can do an implicit toMutable on add, and an implicit toImmutable on getEnumeration. We only need the copy when switching from immutable to mutable. Two adds by different people can (and should) use the same growable collection, so ownership doesn't matter. -- AnonymousDonor

(Refactored slightly - please correct any misattributions etc and DeleteMe)

This is a well-known Smalltalk idiom. I learned it and started teaching it in the late 80's. It is described on page 261 of the DesignPatternsBook, where it is said to be "too expensive to do in general", which is true, but irrelevant, since the special case of it not being too expensive happens 95% of the time. -RalphJohnson

True enough, I've also noticed that in some SmallTalk enumerator implementations, they will create a copy and iterate over that if the enumerator does something that could change the order of elements -- like #removeSuchThat. i.e. make a copy, an enumerate over the copy but actually remove the elements from self. -- rad

CategoryJava CategoryCollections

EditText of this page (last edited June 16, 2005)
FindPage by browsing or searching

This page mirrored in JavaIdioms as of April 29, 2006