Java collection to allow adding and removing while iterating

Question

I am interested if there is any framework that implements a collection that would have the following behavior.

---

Suppose it initially contains: [1, 2, 3]

• I iterate it (using an iterator) and reach element 2, now I add 4 to the end (the collection will now be [1, 2, 3, 4]).
• now I create a new iterator and iterate the collection, resulting in [1, 2, 3, 4]
• I continue iterating with the first iterator and it will give me just 3 and return
• now resetting the first iterator will give me [1, 2, 3, 4] (similar to creating a new one).

Same should apply for removal of elements. If I remove 3 instead of adding, the second iterator should give me [1, 2] while the first one will still give me 3 and the end.

---

So when I get and iterator I want it to give me the collection I had when I created the iterator (even if I iterate it later, on I iterate a bit and continue later), when I reset the iterator, it gets garbage collected it will update to the latest versions and I should be able to have multiple iterator instances created at different times that will give different versions depending on the contents of the array when the iterator was created.

I would need it to work well with multiple threads and preferable have an efficient implementation.

Does anyone know of any implementation of such a collection, or do I have to implement it myself?

Answer 1

java.util.concurrent.CopyOnWriteArrayList will behave like this, except that no Java collection has "resetting" of iterators -- but getting a new iterator instead of resetting has the effect you request here.

Answer 2

What you describe looks very similar to how CopyOnWriteArrayList works:

• once you start iterating, you can change the collection (including from another thread) without affecting the iteration
• if you create a new iterator it will be based on the collection at the creation time
• it is thread safe

Simple example below with the following output:

Iterator 1 - 1
4 has been added
Iterator 2 - 1
Iterator 2 - 2
Iterator 2 - 3
Iterator 2 - 4
Iterator 1 - 2
Iterator 1 - 3

public static void main(String[] args) throws InterruptedException {
    final List<Integer> list = new CopyOnWriteArrayList<Integer>();
    list.addAll(Arrays.asList(1, 2, 3));
    new Thread(new Runnable() {

        @Override
        public void run() {
            for (Integer i : list) {
                System.out.println("Iterator 1 - " + i);
                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {}
            }
        }
    }).start();
    Thread.sleep(10);
    list.add(4);
    System.out.println("4 has been added");
    for (Integer i : list) {
        System.out.println("Iterator 2 - " + i);
    }

}

Answer 3

You can use the ImmutableCollections from the guava library.

The returned ImmutableList is frequently -- not always, but frequently -- a constant-overhead view, rather than an explicit copy. That said, it's often smarter than your average List -- for example, it'll use the efficient contains methods of the backing collection.

Answer 4

You could make use of java.util.concurrent.CopyOnWriteArrayList<E>

According documentation:

A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.

Its costly, but thread safe.

This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created.

As the iteration occurs over a kind of snapshot, the operations (remove, set, and add) on Iterator itself are not supported.