Difference between Java iterator and iterator in Gang of Four

[Hendrik Maryns]

Hi,

I just read through the Design Patterns book of Gamma et al., also known
as the GoF, and noticed that they define a method Start in their
iterator, which does nothing but set the index to zero. I would find
this possibility rather useful, as I want to recycle some iterators.
Right now I have to recreate them at the end of the loop every time.
This seems rather inefficient to me.

Why didn´t Sun include this method in the Iterator interface? Do they
have good reasons for this?

H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org

 

[Chris Smith]

I just read through the Design Patterns book of Gamma et al., also known
as the GoF, and noticed that they define a method Start in their
iterator, which does nothing but set the index to zero. I would find
this possibility rather useful, as I want to recycle some iterators.
Right now I have to recreate them at the end of the loop every time.
This seems rather inefficient to me.

Why didn=3Ft Sun include this method in the Iterator interface? Do they
have good reasons for this?

If this seems rather inefficient, I'd suggest you re-evaluate your ideas
of performance. It could be nice if iterators had some kind of a reset
method... but recreating an iterator from an existing collection is
hardly expensive.

My best guess as to why it wasn't included is that Iterator is intended
for any Collection... not necessarily one that's in memory all the time
or that even has a defined order; I can conceive of such a structure for
which there is not easy way to start over without performing a
significant amount of work... or for which it's not even possible at
all. (Of course, in the world of optional methods -- the Collections
API -- it almost seems unusual that something would be omitted just
because it may not apply.)

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[VisionSet]

I want to recycle some iterators.
Right now I have to recreate them at the end of the loop every time.
This seems rather inefficient to me.

An Iterator is extremely light weight, it is nothing more than a reference
structure for pointing at the original collection, but I guess you know that
if you've read GOF.
Take a look at the sun source (eg AbstractList) for their various
implementations they have just a couple of int index/cursor attributes.
It is very normal to create them on any whim. It is the choice method to
access collections, so much so there's now the for/each language
augmentation to support it.

 

[ricky.clarkson]

It's better to keep the interface as minimal as possible, to keep the
limitations on where it can be used to a minimum, and to keep the
effort required in implementing it to a minimum.

Creating another Iterator is very cheap, for all collections I've known
about.

Use a profiler to examine performance, don't guess.

Oh, when you reimplement List, feel free to make your own
RestartableIterator for these purposes.

 

[Googmeister]

See Roedy's reply. It may be that the iteration can't be repeated at
all, in any order. (Again, there's no consistent justification, though,
for leaving this out while including other optional operations... except
that someone didn't think this was as useful.)

Yes. I don't understand why remove() is part of the Iterator
interface, while being optional. Wouldn't it be better design
to have a separate interface, say, RemovableIterator, for
those times when you also want to support remove()?
Moveover, the remove() method mutates the underlying
collection, whereas the simpler interface without remove()
could guarantee never to change it.

Any insight into why remove() is part of Iterator?

 

[Roedy Green]

Yes. I don't understand why remove() is part of the Iterator
interface, while being optional. Wouldn't it be better design
to have a separate interface, say, RemovableIterator, for
those times when you also want to support remove()?

I agree. I think that was just an error. They did not realise until it
was too late that forcing you to support remove was too onerous and
the code would likely never be used.

 

[Chris Smith]

I agree. I think that was just an error. They did not realise until it
was too late that forcing you to support remove was too onerous and
the code would likely never be used.

Au contraire. From the beginning, it was very carefully considered and
decided that remove() should be provided and made into an optional
operation. Optional operations were quite deliberately designed into
the collections API. The goal was to reduce the number of public
interfaces. Careful before you dismiss this. Mutable versus immutable
is only one possible distinction. Arrays.asList creates a List
implementation that supports only that mutation which does not change
the length. The danger was that different operations might be legal in
different contexts, and there might be a combinatoric explosion of
superinterfaces if the API walked that road.

Whether this was a good idea or not is another matter. I believe that
it was not. However, it was a deliberate decision made in response to
real challenges. It was a conscious decision for simplicity over
safety.

(How that decision meshes with the later decision to add generics to the
type system is a question for a different thread. Clearly, these value
judgements are made differently by different people at Sun.)

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Roedy Green]

Au contraire. From the beginning, it was very carefully considered and
decided that remove() should be provided and made into an optional
operation.

How do you know this?

 

[Chris Smith]

How do you know this?

Mostly I deduced this from common sense. Though I hardly think Sun is
immune from making mistakes, the level of mistake which you suggest --
to forget about the possibility of immutable collections when designing
a general-purpose collections API -- would be phenomenally negligent and
require that they employ only complete morons. That's clearly not true.

Incidentally, Google confirms my thoughts on the matter. This
information is out there for the finding. See, for example:

http://java.sun.com/j2se/1.4.2/docs/guide/collections/designfaq.html

Of course, no one wrote that text to defend against this specific
outrageous charge of idiocy, but "We would have supported it if we
believed it were feasible" implies that, in fact, they thought about it
and decided it wasn't feasible... not that they forgot and then never
bothered to fix it.

You'll also probably recall that the design team at Sun went out of
their way to ask Doug Lea for input based on the experience he had with
his then-popular third-party collections framework. Since Doug's
framework did provide compile-time checking for immutable iterators and
collections via interface hierarchies, it's doubly unlikely that the
idea never occurred to Sun's design team even while they read his
existing code to implement it.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Dimitri Maziuk]

Hendrik Maryns sez:
[ iterators ]

start your iteration again, for example, in (Hash)Set, there is no order
guarantee at all. But as indeed they are only a lightweight wrapper of
indexes, and with what I read about the differences in object creating
between Java and C++, I can see why they left this out.

Errm, they aren't lightweight wrappers for indexes. Recall that
Java has no separate RandomAccess and SequentialAccess lists,
there's only one List and it's implicitly sequential access.

Which means that rewinding an iterator is O(n) -- creating a
new one will be much faster in most cases.

Also, every index-based access is O(n), giving you O(n) for
for( Iterator i = l.iterator(); i.hasNext(); )
e = i.next();
and O(n^2) for
for( int i = 0; i < l.size(); i++ )
e = l.get( i );

What's beyond me is why they didn't make Iterator.next()
return a boolean or void, and Iterator.get() for getting
to the element: either
while( i.next() )
or
for( Iterator i = l.iterator(); i.hasNext(); i.next() )
would be much better than what we have now.

Dima

 

[Eric Sosman]

Dimitri Maziuk wrote On 12/20/05 12:20,:

Hendrik Maryns sez:
[ iterators ]

start your iteration again, for example, in (Hash)Set, there is no order
guarantee at all. But as indeed they are only a lightweight wrapper of
indexes, and with what I read about the differences in object creating
between Java and C++, I can see why they left this out.

Errm, they aren't lightweight wrappers for indexes. Recall that
Java has no separate RandomAccess and SequentialAccess lists,
there's only one List and it's implicitly sequential access.

There is only one java.util.List, but there's no implication
of an access pattern. Various methods of List take a position
argument, and there is no requirement or even suggestion that
successive calls to the methods should use adjacent indices.

True, some particular implementations of List cannot provide
efficient random access -- but that's not a characteristic of
List, but of (for example) LinkedList. Implementations like
ArrayList most definitely do support efficient random access.

Which means that rewinding an iterator is O(n) -- creating a
new one will be much faster in most cases.

Even a half-clever programmer can do better than that. If
there's an efficient way to start a brand-new Iterator at the
beginning of the List, a hypothetical Iterator.rewind() method
could use it.

Also, every index-based access is O(n), giving you O(n) for
for( Iterator i = l.iterator(); i.hasNext(); )
e = i.next();
and O(n^2) for
for( int i = 0; i < l.size(); i++ )
e = l.get( i );

True for LinkedList, but not true for ArrayList or Vector.

What's beyond me is why they didn't make Iterator.next()
return a boolean or void, and Iterator.get() for getting
to the element:

Ah, but "they" did exactly what you ask! They used
different names: hasNext() for your next() and next() for
your get(), but the same[*] functionality is provided.
Is it just the choice of names that bothers you?

[*] "The same" for "return a boolean." I confess I
do not understand what you mean by "return a [...] void,"
since the only use of `void' in Java is to indicate that
a method returns nothing at all, not ever.

either
while( i.next() )
or
for( Iterator i = l.iterator(); i.hasNext(); i.next() )
would be much better than what we have now.

The first is "what we have now," with a change of name.
The second is *exactly* "what we have how," so I don't see
how it "would be much better" than what it already is ...?

 

[Thomas Hawtin]

What's beyond me is why they didn't make Iterator.next()
return a boolean or void, and Iterator.get() for getting
to the element: either
while( i.next() )
or
for( Iterator i = l.iterator(); i.hasNext(); i.next() )
would be much better than what we have now.

Quite. Try writing an iterator filter with strong exception guarantees.
It ain't pretty. You can't quite do it if removes are permitted.

Tom Hawtin

 

[Thomas Hawtin]

Yes. I don't understand why remove() is part of the Iterator
interface, while being optional. Wouldn't it be better design
to have a separate interface, say, RemovableIterator, for
those times when you also want to support remove()?
Moveover, the remove() method mutates the underlying
collection, whereas the simpler interface without remove()
could guarantee never to change it.

Alpha versions of 1.5 had a SimpleIterator (or ReadOnlyIterator).
Iterator extended SimpleIterator. Iterable.iterator returned an
SimpleIterator. As now, Collection extended Iterable.

Unfortunately having bridging botched by javac rather than implemented
by the JVM gives slightly different semantics. (In class files, methods
override if name, parameters and return type match, and the overridden
method is accessible. Bridge methods override the old method, forwarding
to the new, narrower typed method.) Old classes directly implementing
Collection did not have the bridge method, so would throw an
AbstractMethodError if used through the Iterable interface (e.g. in the
enhanced for loop).

Tom Hawtin

 

[Dimitri Maziuk]

Eric Sosman sez:

Dimitri Maziuk wrote On 12/20/05 12:20,: ....
There is only one java.util.List, but there's no implication
of an access pattern. Various methods of List take a position
argument, and there is no requirement or even suggestion that
successive calls to the methods should use adjacent indices.

RTF Javadoc for java.util.List, spec. where it says

"Note that these operations may execute in time proportional to
the index value for some implementations (the LinkedList class,
for example). Thus, iterating over the elements in a list is
typically preferable to indexing through it if the caller does not
know the implementation."

True, some particular implementations of List cannot provide
efficient random access -- but that's not a characteristic of
List, but of (for example) LinkedList. Implementations like
ArrayList most definitely do support efficient random access.

Again, RTFM. Iterator is part of Collection that does not
guarantee anything, esp. wrt. underlying storage -- so there *is*
no guarantee of efficient random access. Cf.
java.util.Iterator<foo>
Vector::iterator<foo>
-- the latter form is "iterator over random access container",
the former is "iterator over any collection".

Besides, it's not "some particular implementations", it's 50%
of existing implementations of List that don't provide efficient
random access.

Even a half-clever programmer can do better than that. If
there's an efficient way to start a brand-new Iterator at the
beginning of the List, a hypothetical Iterator.rewind() method
could use it.

Sure, if it could repoint "this" to the brand-new iterator.
....

[*] "The same" for "return a boolean." I confess I
do not understand what you mean by "return a [...] void,"
since the only use of `void' in Java is to indicate that
a method returns nothing at all, not ever.

You don't seem to understand much, do you? Cf.

while( i.hasNext() ) {
name = i.next().getName();
num = i.next().getNumber();
}

// boolean next()
while( i.next() ) {
name = i.get().getName();
num = i.get().getNumber();
}

// void next()
for( i = l.iterator(); i.hasNext(); i.next() ) {
name = i.get().getName();
num = i.get().getNumber();
}

RTF JLS # 8.4 where it says "void" is a method result type.

Dima

 

[Eric Sosman]

Dimitri Maziuk wrote On 12/20/05 19:07,:

Eric Sosman sez:


RTF Javadoc for java.util.List, spec. where it says

"Note that these operations may execute in time proportional to
the index value for some implementations (the LinkedList class,
for example). Thus, iterating over the elements in a list is
typically preferable to indexing through it if the caller does not
know the implementation."

I draw your attention to the word "may" and to the
phrase "some implementations." In your earlier posting
you stated as fact that every List required O(n) time to
access the n'th element. This is true only of some List
implementations, definitely not of all.

Again, RTFM. Iterator is part of Collection that does not
guarantee anything, esp. wrt. underlying storage -- so there *is*
no guarantee of efficient random access. Cf.
java.util.Iterator<foo>
Vector::iterator<foo>
-- the latter form is "iterator over random access container",
the former is "iterator over any collection".

Iterator has nothing to do with random access, and
Iterator is not "part of Collection." There seems to be
a communication problem here.

Besides, it's not "some particular implementations", it's 50%
of existing implementations of List that don't provide efficient
random access.


Sure, if it could repoint "this" to the brand-new iterator.
...

No such magic (and it would indeed need to be magical)
is needed. My claim is that if List.iterator() has an
efficient way to initialize a new Iterator properly, then
the same initialization technique is available to the
hypothetical Iterator.rewind().

[*] "The same" for "return a boolean." I confess I
do not understand what you mean by "return a [...] void,"
since the only use of `void' in Java is to indicate that
a method returns nothing at all, not ever.

You don't seem to understand much, do you? Cf.

Was that called for?

while( i.hasNext() ) {
name = i.next().getName();
num = i.next().getNumber();
}

// boolean next()
while( i.next() ) {
name = i.get().getName();
num = i.get().getNumber();
}

// void next()
for( i = l.iterator(); i.hasNext(); i.next() ) {
name = i.get().getName();
num = i.get().getNumber();
}

Aha! Now I see what you were after; it certainly wasn't
apparent in your earlier posting. You want a get() method
that does not advance the "current position" of the Iterator.
I'm not sure why you want such a thing, but if you really
want it you can easily wrap the Iterator in a helper class.

RTF JLS # 8.4 where it says "void" is a method result type.

I'm aware that `void' is a method result type, but you
expressed a desire for Iterator.next to "return a boolean
or void." Not even a `void' method can "return a void."

 

[Dimitri Maziuk]

Eric Sosman sez:

Dimitri Maziuk wrote On 12/20/05 19:07,: ....

I love how they phrased it: "some implementations". Until
they come up with quantum subspace memory, there's only
two and half of them is sequential access.

I draw your attention to the word "may" and to the
phrase "some implementations." In your earlier posting
you stated as fact that every List required O(n) time to
access the n'th element. This is true only of some List
implementations, definitely not of all.

I draw you attention to "does not know the implementation".
If all you have is "a List" then it's O(n). Similarly, if
all you have is "a Collection", then it's O(n) -- see below.

....

Iterator has nothing to do with random access, and
Iterator is not "part of Collection." There seems to be
a communication problem here.

Riight. Let me try this again in words of one syllable or
less: Iterator is part of Collections API, it's an iterator
over "a Collection". Since "a Collection" has no guarantees
wrt underlying storage (unlike c++ Containers), designers
of iterator must assume the worst case scenario where cost
of rewinding the iterator is proportional to number of
elements in the collection. Creating a new iterator, on
the other hand, is presumed to be O(1).

Again, note how Java Iterator is "an iterator", not
c++-style "ArrayList::Iterator" or "LinkedList::Iterator".

No such magic (and it would indeed need to be magical)
is needed. My claim is that if List.iterator() has an
efficient way to initialize a new Iterator properly, then
the same initialization technique is available to the
hypothetical Iterator.rewind().

Que?

Iterator foo = bar.iterator();
while( foo.hasNext() ) {
do stuff
}
foo.rewind();
while( foo.hasNext() ) {
do more stuff
}

Explain to me how this works if foo.rewind() initializes
a new bar.iterator() "properly".

I'm aware that `void' is a method result type, but you
expressed a desire for Iterator.next to "return a boolean
or void." Not even a `void' method can "return a void."

"(return a boolean) or void". Get it now?

Dima

 

[Monique Y. Mudama]

Riight. Let me try this again in words of one syllable or less:

Must you be such a jackhole? Do you really think you look clever or
admirable by putting down other people?

Iterator is part of Collections API, it's an iterator over "a
Collection". Since "a Collection" has no guarantees wrt underlying
storage (unlike c++ Containers), designers of iterator must assume
the worst case scenario where cost of rewinding the iterator is
proportional to number of elements in the collection. Creating a new
iterator, on the other hand, is presumed to be O(1).

PS you're not very good at counting, are you?

 

[Dimitri Maziuk]

Monique Y. Mudama sez:

Must you be such a jackhole? Do you really think you look clever or
admirable by putting down other people?

public boolean giveafuck() { return false; }

PS you're not very good at counting, are you?

Nah, I've computers for that.

HTH,HAND
Dima

 

[castillo.bryan]

Dimitri,

Here is a list you can use in all of your code that will give you that
great sequential access you want.

import java.util.*;

public class MyList<T> extends ArrayList<T> {

Random rand = new Random();

public T get(int index) {
while (rand.nextInt(index+1) != index) {
System.out.println("Damn! where did I put that thing again?");
}
return super.get(index);
}

}