nested iteration

[Sharp]

Hi

How does one perform nested iteration through an ArrayList without causing
concurrent modification error?

Cheers
Sharp

 

[marcus]

" Note that this implementation is not synchronized. If multiple threads
access an ArrayList instance concurrently, and at least one of the
threads modifies the list structurally, it must be synchronized externally."

try vector instead, it is syncronized

 

[Sharp]

Are there any datastructures besides Vector that is synchronised?

Cheers
Sharp

 

[marcus]

yes

Are there any datastructures besides Vector that is synchronised?

Cheers
Sharp

 

[John McGrath]

Are there any datastructures besides Vector that is synchronised?

HashTable is also synchronized.

In addition to that, you can synchronize any of the collections data
structures using the synchronizedXxxxxx() methods in the Collections
class,

 

[Thomas G. Marshall]

marcus coughed up:

" Note that this implementation is not synchronized. If multiple
threads access an ArrayList instance concurrently, and at least one
of the threads modifies the list structurally, it must be synchronized
externally."
try vector instead, it is syncronized

The question was about "nested iteration", not multiple thread access.

 

[Dotty]

Hi

How does one perform nested iteration through an ArrayList without causing
concurrent modification error?

Cheers
Sharp

What is "nested iteration?"

 

[marcus]

The question was about "concurrent modification" exception, which is
thrown when an object like ArrayList is, hmm, accessed concurrently,
which is avoided when access to the object is, hmm, syncronized.

 

[Joona I Palaste]

What is "nested iteration?"

Nested iteration happens when you iterate through a Collection with an
Iterator, and inside the iteration loop, you iterate again through the
same Collection with another Iterator.

 

[Antti S. Brax]

Nested iteration happens when you iterate through a Collection with an
Iterator, and inside the iteration loop, you iterate again through the
same Collection with another Iterator.

The Iterator implementation for ArrayLists is implemented so
that if there are two iterators created for one array list
then _any_ modification on the list will cause a concurrent
modification exception to at least one of the iterators. One
has to write a new implementation of ArrayList if one wants to
circumvent the fail-fast functionality (I believe overriding
the iterator() and listIterator() methods should be enough).

A lot of care should be taken when doing this though. Consider
what happens when an element is removed from the beginning of
the list when there exists N iterators that have passed that
element. Instead of overriding iterator() and breaking the
fail-fast functionality one might extend ArrayList to provide
a nestedIterator() method.

In situations where I would have needed nested iterators I have
created a copy of the list, iterated it and made modifications
to the original list.

 

[Thomas G. Marshall]

marcus coughed up:

The question was about "concurrent modification" exception, which is
thrown when an object like ArrayList is, hmm, accessed concurrently,
which is avoided when access to the object is, hmm, syncronized.

Synchronization does not help you here unless there are multiple threads.
That's what synchronization does: it blocks the re-entrance to a method if
another thread is in it already.

And concurrent modification does not necessitate multiple threads. It only
means that the collection that is being iterated over is being modified by
something other than the iterator's own add() or remove() methods mid
looping or any time after the creation of the iteration (and before it
completes).

It can easily be in the same thread, and synchronized methods do not help
here.

 

[Thomas G. Marshall]

Antti S. Brax coughed up:

The Iterator implementation for ArrayLists is implemented so
that if there are two iterators created for one array list
then _any_ modification on the list will cause a concurrent
modification exception to at least one of the iterators. One
has to write a new implementation of ArrayList if one wants to
circumvent the fail-fast functionality (I believe overriding
the iterator() and listIterator() methods should be enough).

That would be ok if your interators were always going to be "read-only".

Not sure that's enough for modifications. You would have to be excedingly
careful here anyway, even when using the iterator's add() and remove(), and
I believe that using one iterator's add() and remove() would always violate
the sensibilites of the other iterator. Which makes sense to me.

Imagine the following:

collection C
Iterator 1 (I1)
Iterator 2 (I2)

I1.add() and I1.remove() know how to modify C and maintain their own
iteration properly, but they do /not/ know how to keep I2 from frigging up.
The only way around this would be a redesign where the iterators were
themselves listeners for changes, in which case /any/ modification would
result in a "change event" being fired and the iterators being notified.

A lot of care should be taken when doing this though. Consider
what happens when an element is removed from the beginning of
the list when there exists N iterators that have passed that
element. Instead of overriding iterator() and breaking the
fail-fast functionality one might extend ArrayList to provide
a nestedIterator() method.

Yes. And gross, by the way

 

[John C. Bollinger]

" Note that this implementation is not synchronized. If multiple threads
access an ArrayList instance concurrently, and at least one of the
threads modifies the list structurally, it must be synchronized
externally."

try vector instead, it is syncronized

Vector is synchronized, but synchronization is not really the problem.
A fail-fast iterator, such as all provided by the standard Collections,
throws ConcurrentModificationException if a method is invoked on it when
the underlying collection has been modified since the Iterator's
creation (by means other than the Iterator itself). That does not
require multiple threads to accomplish, and Vector's synchronization is
in any case too narrow in scope to protect instances from this issue in
a multi-threaded scenario.

The _only_ reason to ever use the Vector class is if you need to
interface with an external API that requires it. Otherwise use
ArrayList instead. For multi-threaded programming you generally need to
provide the same degree of external synchronization for a Vector as you
do for an ArrayList, but with ArrayList you don't run into extra
synchronization barriers. If you think you want a List with per-method
synchronization (like Vector has), then you can run any List you want
through Collections.synchronizedList(List) to get one.

 

[Thomas G. Marshall]

John C. Bollinger coughed up:

Vector is synchronized, but synchronization is not really the problem.
A fail-fast iterator, such as all provided by the standard
Collections, throws ConcurrentModificationException if a method is
invoked on it when the underlying collection has been modified since
the Iterator's creation (by means other than the Iterator itself). That
does not require multiple threads to accomplish, and Vector's
synchronization is in any case too narrow in scope to protect
instances from this issue in a multi-threaded scenario.

The _only_ reason to ever use the Vector class is if you need to
interface with an external API that requires it.

Uh.....almost.

There's a less than nifty reason to use it. If you wanted to extend
ArrayList into something, say, SmedlyList, *and* you wanted SmedlyList to be
synchronized, you would *have to* wrap every single method in ArrayList in
order to make them synchronized.

Why is this? Because for terrible reasons sun decided that the following
inner class:

Collections.SynchronizedList

is defined to have package scope, and is not public, and hence cannot be
extened by anything you write (outside of java.util). You can only get at
this class programmatically, which is a mistake IMO.