nested iteration

Discussion in 'Java' started by Sharp, Mar 5, 2005.

  1. Sharp

    Sharp Guest

    Hi

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

    Cheers
    Sharp
     
    Sharp, Mar 5, 2005
    #1
    1. Advertising

  2. Sharp

    marcus Guest

    " 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 wrote:
    > Hi
    >
    > How does one perform nested iteration through an ArrayList without causing
    > concurrent modification error?
    >
    > Cheers
    > Sharp
    >
    >
     
    marcus, Mar 5, 2005
    #2
    1. Advertising

  3. Sharp

    Sharp Guest

    Are there any datastructures besides Vector that is synchronised?

    Cheers
    Sharp

    > 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 wrote:
    > > Hi
    > >
    > > How does one perform nested iteration through an ArrayList without

    causing
    > > concurrent modification error?
    > >
    > > Cheers
    > > Sharp
     
    Sharp, Mar 5, 2005
    #3
  4. Sharp

    marcus Guest

    yes

    Sharp wrote:
    > Are there any datastructures besides Vector that is synchronised?
    >
    > Cheers
    > Sharp
    >
    >
    >>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 wrote:
    >>
    >>>Hi
    >>>
    >>>How does one perform nested iteration through an ArrayList without

    >>

    > causing
    >
    >>>concurrent modification error?
    >>>
    >>>Cheers
    >>>Sharp

    >>

    >
    >
    >
     
    marcus, Mar 5, 2005
    #4
  5. Sharp

    John McGrath Guest

    On 3/5/2005 at 4:01:50 AM, Sharp wrote:

    > 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,

    --
    Regards,

    John McGrath
     
    John McGrath, Mar 5, 2005
    #5
  6. marcus coughed up:
    >
    > Sharp wrote:
    >> Hi
    >>
    >> How does one perform nested iteration through an ArrayList without
    >> causing concurrent modification error?
    >>
    >> Cheers
    >> Sharp

    >
    > " 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.



    --
    "So I just, uh... I just cut them up like regular chickens?"
    "Sure, just cut them up like regular chickens."
     
    Thomas G. Marshall, Mar 5, 2005
    #6
  7. Sharp

    Dotty Guest

    "Sharp" <> wrote in message
    news:0EdWd.185062$...
    > Hi
    >
    > How does one perform nested iteration through an ArrayList without causing
    > concurrent modification error?
    >
    > Cheers
    > Sharp
    >

    What is "nested iteration?"
     
    Dotty, Mar 6, 2005
    #7
  8. Sharp

    marcus Guest

    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.

    Thomas G. Marshall wrote:
    > marcus coughed up:
    >
    >>Sharp wrote:
    >>
    >>>Hi
    >>>
    >>>How does one perform nested iteration through an ArrayList without
    >>>causing concurrent modification error?
    >>>
    >>>Cheers
    >>>Sharp

    >>
    >>" 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.
    >
    >
    >
     
    marcus, Mar 6, 2005
    #8
  9. Dotty <> scribbled the following:
    > "Sharp" <> wrote in message
    > news:0EdWd.185062$...
    >> Hi
    >>
    >> How does one perform nested iteration through an ArrayList without causing
    >> concurrent modification error?

    >
    > 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.

    --
    /-- Joona Palaste () ------------- Finland --------\
    \-------------------------------------------------------- rules! --------/
    "We're women. We've got double standards to live up to."
    - Ally McBeal
     
    Joona I Palaste, Mar 6, 2005
    #9
  10. wrote in comp.lang.java.programmer:
    > Dotty <> scribbled the following:
    >> "Sharp" <> wrote in message
    >> news:0EdWd.185062$...
    >>> How does one perform nested iteration through an ArrayList without causing
    >>> concurrent modification error?

    >>
    >> 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.


    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.

    --
    Antti S. Brax Rullalautailu pitää lapset poissa ladulta
    http://www.iki.fi/asb/ http://www.cs.helsinki.fi/u/abrax/hlb/
    "Disconnect this cable to shorten, re-connect to lengthen."
    -- Instructions on Logitech's USB mouse extension cord.
     
    Antti S. Brax, Mar 6, 2005
    #10
  11. marcus coughed up:
    >
    > Thomas G. Marshall wrote:
    >> marcus coughed up:
    >>
    >>> Sharp wrote:
    >>>
    >>>> Hi
    >>>>
    >>>> How does one perform nested iteration through an ArrayList without
    >>>> causing concurrent modification error?
    >>>>
    >>>> Cheers
    >>>> Sharp
    >>>
    >>> " 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.

    >
    > 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.



    --
    Forgetthesong,I'dratherhavethefrontallobotomy...
     
    Thomas G. Marshall, Mar 7, 2005
    #11
  12. Antti S. Brax coughed up:
    > wrote in comp.lang.java.programmer:
    >> Dotty <> scribbled the following:
    >>> "Sharp" <> wrote in message
    >>> news:0EdWd.185062$...
    >>>> How does one perform nested iteration through an ArrayList without
    >>>> causing concurrent modification error?
    >>>
    >>> 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.

    >
    > 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 :)


    > 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.




    --
    Forgetthesong,I'dratherhavethefrontallobotomy...
     
    Thomas G. Marshall, Mar 7, 2005
    #12
  13. marcus wrote:

    > " 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.

    --
    John Bollinger
     
    John C. Bollinger, Mar 7, 2005
    #13
  14. John C. Bollinger coughed up:
    > marcus wrote:
    >
    >> " 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.



    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.



    > 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.




    --
    Onedoctortoanother:"Ifthisismyrectalthermometer,wherethehell'smypen???"
     
    Thomas G. Marshall, Mar 7, 2005
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Russ Perry Jr
    Replies:
    2
    Views:
    4,159
    Russ Perry Jr
    Aug 20, 2004
  2. Chad E. Dollins
    Replies:
    3
    Views:
    661
    Kai-Uwe Bux
    Nov 8, 2005
  3. request@no_spam.com
    Replies:
    5
    Views:
    434
  4. Rudi
    Replies:
    5
    Views:
    5,042
  5. Roy Smith

    Nested iteration?

    Roy Smith, Apr 23, 2013, in forum: Python
    Replies:
    13
    Views:
    135
    Oscar Benjamin
    Apr 23, 2013
Loading...

Share This Page