Iterators in Java and C++
Erik Wikström
A few days ago some expressed the opinion (in a post I can't find, but
it was probably in one of Razii's threads) that Java's iterators were
better than C++ iterators, or at least that the Java iterator concept
was better (or something to that effect). I would be interested to hear
about why whoever wrote it feels that way.
--
Erik Wikström
lbon...@yahoo.com
> This is a little bit off topic but I hop you'll forgive me.
>
> A few days ago some expressed the opinion (in a post I can't find, but
> it was probably in one of Razii's threads) that Java's iterators were
> better than C++ iterators,
You mean this?
Razii
<Erik-w...@telia.com> wrote:
>A few days ago some expressed the opinion (in a post I can't find, but
>it was probably in one of Razii's threads) that Java's iterators were
>better than C++ iterators, or at least that the Java iterator concept
>was better (or something to that effect). I would be interested to hear
>about why whoever wrote it feels that way.
For fun, I sent the blog page
(http://razi2.blogspot.com/2008/04/why-is-c-slower-than-java.html )
to the author of
http://bruscy.multicon.pl/pages/przemek/java_not_really_faster_than_cpp.html
his email response was:
-- quote--
see explanation to hash.cpp and hash2.cpp on my webpage.
If you use standard library as defined in 1998, you can't make the C++
faster. You either have to use original SGI STL map or unordered_map
from C++ 0x . (Or any hashmap from less standard sources like Boost).
With any of these solutions, C++ beats Java hands down.
There are other performance problems in the code, like this line:
std::string input( buffer.str() );
which needlessly copies the whole 40MB for the second time, but the
performance impact of that is insignificant in comparison to the
impact of using tree based map.
-- end quote ---
I am not sure what that really means but I am still waiting for C++
version that is faster and would compile on GCC.
Razii
Onn Thu, 03 Apr 2008 19:12:27 GMT, Erik Wikström..
<Erik-w...@telia.com> wrote:
(http://razi2.blogspot.com/2008/04/why-is-c-slower-than-java.html )
his email response was:
version that is faster and would compile on GCC..
James Kanze
That was me, and the reason is simply: you don't need two of
them. Try chaining functions which use iterators, for example.
Or writing a filtering iterator.
Not that Java's iterators are perfect, either. The merge access
and incrementing---as did the USL iterators. By the time Java
was being developed, we'd already established that this wasn't a
good idea, so it's hard to understand why they did it.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Erik Wikström
Relevance?
--
Erik Wikström
Erik Wikström
Yes, thanks.
James, can you explain what you meant by "... for most everyday jobs
like this, in fact, the Java collections library (and especially the
concept of iterators in Java) is far superior to the STL."?
While it was some time ago since I last used Java (before generics) I've
always liked the way the STL iterators, it is a quite simple concept but
still very powerful. To my knowledge there is not easy way to perform
operations on a subset of a container using Java's iterators.
--
Erik Wikström
Razii
<Erik-w...@telia.com> wrote:
>Relevance?
You have Iterators only when you have containers, like map or vector
:)
Razii
<james...@gmail.com> wrote:
>Not that Java's iterators are perfect, either. The merge access
>and incrementing---as did the USL iterators. By the time Java
>was being developed, we'd already established that this wasn't a
>good idea, so it's hard to understand why they did it.
I am not sure what you mean but with with 1.5, the syntax changed from
for(Iterator lineup = list.iterator() ; lineup.hasNext() ; ) {
Object thatThing = lineup.next();
myMonster.eat(thatThing);
}
to
for(Object thatThing : list) {
myMonster.eat(thatThing);
}
Erik Wikström
And?
Read my post again and tell me how your response is relevant.
--
Erik Wikström
Sam
This is stupid. This is like saying that apples are better than oranges.
Some people like apples more than oranges, other people like oranges more
than apples. There is no quantifiable way to compare apples and oranges on
some nebulous, global, "better" scale.
Lloyd Bonafide
news:cone.1207267138....@commodore.email-scan.com:
Right, there is no quantifiable way to compare the taste of apples and
oranges, nor is there a way to convince someone that one is better than
another. With programming constructs or paradigms, however, there are
often tradeoffs in choosing one over another, and reasons for choosing
one over another can be concrete.
James Kanze
> On 2008-04-03 21:38, lbonaf...@yahoo.com wrote:
[...]
> James, can you explain what you meant by "... for most everyday jobs
> like this, in fact, the Java collections library (and especially the
> concept of iterators in Java) is far superior to the STL."?
> While it was some time ago since I last used Java (before generics) I've
> always liked the way the STL iterators, it is a quite simple concept but
> still very powerful. To my knowledge there is not easy way to perform
> operations on a subset of a container using Java's iterators.
It's easier with Java's iterators than with those of C++. Try
it sometime: call std::transform with some function which should
only be applied to every third element. In Java, you simply
create a filtering iterator (using an anonymous class, if you
wish). In C++, you use boost::filtering_iterator, of course,
it's still more awkward (since you need to create two of them),
and from a purely STL point of view, you should take a look at
the hoops boost::filtering_iterator has to jump through.
Of course, the real problem comes when you want to call a
function to operate on a subset determined by another function.
In Java, that would simply be f( g( collection ), operation ),
where g( collection ) returns a filtering iterator, and f takes
an iterator (any iterator of the correct type), and the
functional operation object. In C++, g must return a pair of
iterators, and you need to store them somewhere, and then call
f() in a separate statement.
Projection and filtering iterators, and function chaining, are
some of the most fundamental concepts, which I used to use
everywhere, in pre-STL days.
The iterator pattern in the GoF was established and standard
practice as early as 1990. Neither Java nor the STL have the
excuse of not knowing the flaws in their iterator idiom by the
time they were developing them. In the case of Java, they
adopted existing practice (e.g. the USL library) known to be
somewhat flawed (next and accessing the element should be two
separate operations); in the case of the STL, the authors
decided to ignore all existing practice, and invented something
far less usable.
(There are few special cases where the two iterator model is
useful. It works well for tokenizing an input stream, for
example. The problem with this is that every time I've wanted
to tokenize an input stream, I've either had input
iterators---which don't allow establishing a sub-range using a
previously saved iterator---or a random access container, in
which case, I could just as easily use indexes, rather than
iterators. In fact, my ParserSource class is modeled more on
C++'s other iterators, streambuf, than it is on STL iterators.
But it really could be just a GoF iterator as well.)
James Kanze
> On Thu, 03 Apr 2008 21:03:29 GMT, Erik Wikström
> <Erik-wikst...@telia.com> wrote:
> >Relevance?
> You have Iterators only when you have containers, like map or
> vector :)
Since when? C++ has istream_iterator in the standard, and Boost
has a lot of iterators which don't depend on an underlying
container. And you can easily do the same thing in Java---much
more easily, in fact. (The fact that they are so easy to
implement may account for why no one felt it necessary to
provide them as standard, or as part of a widely used library.)
James Kanze
> On Thu, 3 Apr 2008 14:02:01 -0700 (PDT), James Kanze
>
> >Not that Java's iterators are perfect, either. The merge
> >access and incrementing---as did the USL iterators. By the
> >time Java was being developed, we'd already established that
> >this wasn't a good idea, so it's hard to understand why they
> >did it.
> I am not sure what you mean but with with 1.5, the syntax
> changed from
> for(Iterator lineup = list.iterator() ; lineup.hasNext() ; ) {
> Object thatThing = lineup.next();
And that's the problem. You should be able to access the object
without advancing the iterator. Most logically, advancing the
iterator should be the third part of the if.
The standard "pattern" is:
for ( Iterator iter( someInitializationArguments ) ;
! iter.isDone() ;
iter.next() ) {
doSomethingWith( iter.element() ) ;
}
In a well written iterator, doSomethingWith should encompass
deleting the element from the container, if the iterator is
based on a container. (IIRC, Java supports this; C++ definitely
doesn't.)
> myMonster.eat(thatThing);
> }
> to
> for(Object thatThing : list) {
> myMonster.eat(thatThing);
> }
Interesting. But isn't it just a cosmetic fix? Suppose that my
doSomethingWith, above, was actually to remove the element from
the underlying container, g.e.:
for ( Iterator i = list.iterator() ; list.hasNext() ; ) {
Object o = iter.next() ;
if ( condition( o ) ) {
iter.remove() ;
}
}
Try writing a filtering iterator in Java which supports that,
and you'll see why merging advance and access is a bad idea.
(Of course, from a design point of view, it's very ugly.
Separation of concerns should be an important guiding
principle.)
James Kanze
> Erik Wikström writes:
> > This is a little bit off topic but I hop you'll forgive me.
> > A few days ago some expressed the opinion (in a post I can't find, but
> > it was probably in one of Razii's threads) that Java's iterators were
> > better than C++ iterators, or at least that the Java iterator concept
> > was better (or something to that effect). I would be interested to hear
> > about why whoever wrote it feels that way.
> This is stupid. This is like saying that apples are better
> than oranges.
No. You're not comparing things in an absolute. If you call
something an "iterator", it is because it fulfills a specific
purpose. Implicit in the statement is that "Java iterators are
better iterators than C++ iterators". Sort of like "oranges are
a better source of vitamin C than apples".
Razii
<james...@gmail.com> wrote:
>And that's the problem. You should be able to access the object
>without advancing the iterator. Most logically, advancing the
>iterator should be the third part of the if.
>
>The standard "pattern" is:
>
> for ( Iterator iter( someInitializationArguments ) ;
> ! iter.isDone() ;
> iter.next() ) {
> doSomethingWith( iter.element() ) ;
> }
If the problem is that "You should be able to access the object
without advancing the iterator", where am I calling next in this
syntax.
int[] nums = { 1, 2, 3, 4, 5, 6 };
for(int n : nums) {
System.out.println(n);
}
Or
List list = getList();
for (Object element : list) {
out.println(element);
// Do something else with this element
}
Sam
> On Apr 4, 1:58 am, Sam <s...@email-scan.com> wrote:
>> Erik Wikström writes:
>> > This is a little bit off topic but I hop you'll forgive me.
>
>> > A few days ago some expressed the opinion (in a post I can't find, but
>> > it was probably in one of Razii's threads) that Java's iterators were
>> > better than C++ iterators, or at least that the Java iterator concept
>> > was better (or something to that effect). I would be interested to hear
>> > about why whoever wrote it feels that way.
>
>> This is stupid. This is like saying that apples are better
>> than oranges.
>
> No. You're not comparing things in an absolute. If you call
> something an "iterator", it is because it fulfills a specific
> purpose. Implicit in the statement is that "Java iterators are
> better iterators than C++ iterators". Sort of like "oranges are
> a better source of vitamin C than apples".
Except that there is no common denominator between Java and C++ iterators
that can be used as a measuring stick. A better analogy would be saying that
because both apples and oranges are fruits, one of them is a better fruit
than the other.
Totally meaningless.
Markus Moll
Razii wrote:
> If the problem is that "You should be able to access the object
> without advancing the iterator", where am I calling next in this
> syntax.
Easy...
> int[] nums = { 1, 2, 3, 4, 5, 6 };
>
> for(int n : nums) {
^^^^^^^^^^^^
Here...
> System.out.println(n);
> }
>
> Or
>
> List list = getList();
>
> for (Object element : list) {
^^^^^^^^^^^^^^^^^^^^^
... and here.
> out.println(element);
>
> // Do something else with this element
> }
Markus
Lloyd Bonafide
news:cone.1207306990...@commodore.email-scan.com:
> James Kanze writes:
>> No. You're not comparing things in an absolute. If you call
>> something an "iterator", it is because it fulfills a specific
>> purpose. Implicit in the statement is that "Java iterators are
>> better iterators than C++ iterators". Sort of like "oranges are
>> a better source of vitamin C than apples".
>
> Except that there is no common denominator between Java and C++
> iterators that can be used as a measuring stick. A better analogy
> would be saying that because both apples and oranges are fruits, one
> of them is a better fruit than the other.
>
> Totally meaningless.
Both Java and C++ implement iterators over containters, and I think Java
containers are better implemented because...
The because part is what Erik was asking James about.
Obnoxious User
No, you don't. I even use custom iterators for a lot more than
simple containers.
--
OU
Sam
Before you can make that argument, you need to define what "better" means.
And, what "better" might mean to you, in this context, may not necessarily
mean the same thing to someone else, who uses a different definition of
"better".
For example, I happen to believe that C++'s iterators are "better", and I
happen to believe that they're better for the same reason it's argued that
Java's java.lang.Iterator is "better". The argument -- that you carry around
one object in Java, versus two objects in C++ (the beginning and the ending
iterator) -- and that because of this Java is better, is full of crap.
Only if your pristine fingers are too tired to type a few extra keywords,
and only your brain lacks the capacity to keep track of two things at the
same time, only then I would perhaps concede that Java Iterator
implementation is better. In terms of speed, performance, and efficiency,
C++ spanks the monkey out of Java's iterators for most use cases.
What the Java fan club fails to comprehend is that each iteration, in Java,
involves two virtual function calls: hasNext() and next(), while equivalent
C++ code is likely to involve more than a pair of CPU instructions:
increment and comparison, since the C++ generated code is likely to inline
and keep both iterators in registers (most C++ STL iterators usually get
optimized into nothing more than glorified pointers). In the worst case, a
C++ iterator would be a basic, no-frills object, which would incur only a
slightly bigger overhead than a direct pointer.
Meanwhile, since all Java methods are virtual, unless explicitly specified
otherwise; and I'm rather skeptical that even modern Java VMs will be able
to optimize away the required virtual function calls, one for each method:
hasNext(), and next(), on each iteration.
What you actually have, in terms of Java iterators, is something that in C++
would be equivalent to:
class Iterator {
public:
virtual Iterator *next()=0;
virtual bool hasNext()=0;
};
I'm ignoring an obvious issue here with memory allocation. When you factor
in the fact that, with most Java iterators, their next() method has to
allocate another instance of an Iterator object, and that Java's famous VM
has to keep track of references to each instance of every Iterator object
that gets instantiated, and garbage-collect it, from where I'm standing,
anyone who claims that Java implements iteration better than C++, from a
practical standpoint, are out of their freaking skulls.
So, really, for the same reasons that it's argued that Java's iterator
implementation is "better", I am going to argue that when you actually
examine what has to happen, you have no choice but to reach a completely
opposite conclusion, if you want to be intellectually honest about it. I
just can't accept that modern Java VMs, with all their JIT wizardly, can
optimize all this bloat away; especially since Java iterators are defined
mostly as interface objects, and all containers subclass the iterator
interface, and implement whatever next() and hasNext() means to them. That's
what they must do, there's just no way around it, and I see slim-to-none
chance that at runtime you can avoid two virtual function calls for each
loop iteration, and having to deal with instantiating a brand new iterator
object on each loop iteration, and having to deal with garbage-collecting
the entire mess, when you're done.
Yeah, that's MUCH "better" than just keeping two words in a pair of
registers, then incrementing the first one and comparing it against the
second one, on each loop iteration.
Lloyd Bonafide
news:cone.1207346793...@commodore.email-scan.com:
> Lloyd Bonafide writes:
>
>> Sam <s...@email-scan.com> wrote in
>> news:cone.1207306990...@commodore.email-scan.com:
>>
>>> James Kanze writes:
>>
>>>> No. You're not comparing things in an absolute. If you call
>>>> something an "iterator", it is because it fulfills a specific
>>>> purpose. Implicit in the statement is that "Java iterators are
>>>> better iterators than C++ iterators". Sort of like "oranges are
>>>> a better source of vitamin C than apples".
>>>
>>> Except that there is no common denominator between Java and C++
>>> iterators that can be used as a measuring stick. A better analogy
>>> would be saying that because both apples and oranges are fruits, one
>>> of them is a better fruit than the other.
>>>
>>> Totally meaningless.
>>
>> Both Java and C++ implement iterators over containters, and I think
>> Java containers are better implemented because...
>
> Before you can make that argument, you need to define what "better"
> means. And, what "better" might mean to you, in this context, may not
> necessarily mean the same thing to someone else, who uses a different
> definition of "better".
Maybe it will help you to preface each post, in your mind, with "in my
opinion". James' opinion is that Java's iterator implementation is
superior to C++, and Erik wants to know why he thinks that. No need to
get your shorts in a wad.
<remainder of cowboy programmer bullshit elided>
Mirek Fidler
> involves two virtual function calls: hasNext() and next(), while equivalent
> C++ code is likely to involve more than a pair of CPU instructions:
> increment and comparison, since the C++ generated code is likely to inline
What makes you think that "hasNext" and "next", if implemented in C++,
would not be expressed by "a pair of CPU instructions" - compare and
increment?
> and keep both iterators in registers (most C++ STL iterators usually get
> optimized into nothing more than glorified pointers).
As could be Java style iterators implemented in C++. Just consider
template <class T>
struct Iter {
T::iterator ptr;
T::iterator end;
bool hasNext() const { return ptr != end; }
void next() { ptr++; }
};
Your arguments are completely moot.
> Meanwhile, since all Java methods are virtual, unless explicitly specified
> otherwise; and I'm rather skeptical that even modern Java VMs will be able
> to optimize away the required virtual function calls, one for each method:
> hasNext(), and next(), on each iteration.
What that has to do with iterator concept?
Mirek
Lloyd Bonafide
news:cone.1207350375...@commodore.email-scan.com:
>> Maybe it will help you to preface each post, in your mind, with "in
>> my opinion". James' opinion is that Java's iterator implementation
>> is superior to C++, and Erik wants to know why he thinks that. No
>> need to get your shorts in a wad.
>>
>> <remainder of cowboy programmer bullshit elided>
>
> I note that you falied to elucidate a counterargument to the lengthy,
> and detailed, technical discussion of the relative merits of Java and
> C++ iterators.
Naturally, as I have no particular preference. No horse in the race, so
to speak. You, on the other hand, are talking out of both sides of your
mouth. First you claim that it's stupid to say one is better than the
other, then you give a lengthy dissertation as to why your favorite is
the better one. Seems a little inconsistent, no?
Sam
>> What the Java fan club fails to comprehend is that each iteration, in Java,
>> involves two virtual function calls: hasNext() and next(), while equivalent
>> C++ code is likely to involve more than a pair of CPU instructions:
>> increment and comparison, since the C++ generated code is likely to inline
>
> What makes you think that "hasNext" and "next", if implemented in C++,
> would not be expressed by "a pair of CPU instructions" - compare and
> increment?
>
>> and keep both iterators in registers (most C++ STL iterators usually get
>> optimized into nothing more than glorified pointers).
>
> As could be Java style iterators implemented in C++. Just consider
>
> template <class T>
> struct Iter {
> T::iterator ptr;
> T::iterator end;
>
> bool hasNext() const { return ptr != end; }
> void next() { ptr++; }
> };
>
> Your arguments are completely moot.
For starters, your implementation of next() is wrong. See
http://java.sun.com/javase/6/docs/api/java/util/Iterator.html. The correct,
equivalent, implementation would be:
Iter<T> next() const { Iter<T> n; n.ptr=ptr+1; n.end=end; return n }
That's your "Java style iterator" for you. That's what you have to do, on
each iteration of the loop. Good luck optimizing that. Now, why don't you go
and benchmark this abomination against the STL iterator, see what happens,
then get back to me.
Gosh, what the heck are they teaching in college, these days?
Mirek Fidler
Sorry about that. I do not know Java very well, because 20 years back,
when I was in college, nobody was teaching it anyway (for the very
simple and obvious reason). I have just reflect to other posts.
BTW, even this would be optimized very well on most compliers AFAIK.
Compilers are quite good eliminating dead inlined code.
Mirek
Erik Wikström
Don't know if you posted the correct link or if they just teaches us to
read better in college these days. :-) I think the correct
implementation, given the link you posted, should be
T& next() { ptr++; return *ptr; }
Which also shows the problem that James Kanze pointed out, namely that
you can not dereference the iterator more than once without changing
what it refers to.
Ideally you would have two methods, one to increment and one to
dereference, like so:
typename T::value_type& getValue() const { return *ptr; }
void moveNext{ ptr++; }
Rewriting it all in a bit my C++ stylish way we get:
#include <vector>
#include <iostream>
template <class T>
struct Iter {
typedef typename T::iterator STLIter;
typedef typename T::value_type Val;
STLIter ptr, end;
Iter(STLIter begin, STLIter end) : ptr(begin), end(end) {}
operator bool() const { return ptr != end; }
Val& operator*() const { return *ptr; }
void operator++() { ptr++; }
};
int main()
{
std::vector<int> v;
for (int i = 0; i < 10; ++i)
v.push_back(i);
Iter<std::vector<int> > it(v.begin(), v.end());
while (it)
{
std::cout << *it;
++it;
}
}
Not too sure about the operator bool() thing though...
--
Erik Wikström
Sam
No, that's not correct. In java.util.Iterator, the next() method does not
modify the Iterator, it returns a new Iterator. The existing iterator
remains valid and continues to refer to the same element. Note the
description of the next() method in the API:
Returns the next element in the iteration.
And *not*:
Updates the Iterator to refer to the next element in the iteration,
and returns self.
The language in the API is very precise, and means exactly that, nothing
more, nothing less. Go back to my earlier post, where I indicated that Java
containers subclass Iterator, and implement the next() and hasNext() methods
that are appropriate to the container, that constructor and return a new
Iterator subclass instance. That's how they work.
Erik Wikström
No, it return a reference to an object of type E, in other words it
returns a reference to the next element.
> The existing iterator remains valid and continues to refer to the
> same element.
The link you sent is silent on what happened to the iterator, but if a
new one is created the user will not have a reference to it since the
return-type of next() is E, and not Iterator<E>. Which means that the
user can not make the iterator go forward unless the first iterator is
modified.
> Note the description of the next() method in the API:
>
> Returns the next element in the iteration.
Notice that nowhere does it say that a new Iterator object should be
created or returned, rather it says that the next *element* should be
returned.
> And *not*:
>
> Updates the Iterator to refer to the next element in the iteration,
> and returns self.
Well, my next() does not return the iterator but the next element (just
as the Java Iterator).
--
Erik Wikström
James Kanze
> On 2008-04-05 14:45, Sam wrote:
[...]
> Don't know if you posted the correct link or if they just
> teaches us to read better in college these days. :-) I think
> the correct implementation, given the link you posted, should
> be
> T& next() { ptr++; return *ptr; }
> Which also shows the problem that James Kanze pointed out,
> namely that you can not dereference the iterator more than
> once without changing what it refers to.
T& next() { return *ptr ++ ; }
would be the correct implementation in C++. Except, of course,
that incrementing an iterator generally involves a lot more than
just incrementing a pointer. The whole performance discussion
is just so much hand waving to avoid discussing the real issues;
in practice, the only thing that could possibly cause a
measurable difference is the fact that Java uses virtual
functions, and even that can often be optimized away with a JIT
compiler. More to the point, of course, is that the work
arounds you need to make the STL iterators work (extra
variables, etc.) will often outweigh the cost of the virtual
function calls.
But of course, both patterns will be sufficiently fast for 99.9%
of any use. What really counts is the amount of extra
programmer work you have to do, and the loss of design
cleanliness and understanding that is introduced. And when
performance is an issue, of course, the time you save using a
well designed iterator will give you more time to address the
issue, and solve it correctly. If speed is important, you need
to encapsulate, profile and then attack the critical points.
And you need the time to do it, time which shouldn't be wasted
on premature optimization (which generally has a negative effect
on performance in the long run, because it so often breaks
encapsulation).
> Ideally you would have two methods, one to increment and one to
> dereference, like so:
> typename T::value_type& getValue() const { return *ptr; }
> void moveNext{ ptr++; }
> Rewriting it all in a bit my C++ stylish way we get:
> #include <vector>
> #include <iostream>
> template <class T>
> struct Iter {
> typedef typename T::iterator STLIter;
> typedef typename T::value_type Val;
> STLIter ptr, end;
> Iter(STLIter begin, STLIter end) : ptr(begin), end(end) {}
> operator bool() const { return ptr != end; }
> Val& operator*() const { return *ptr; }
> void operator++() { ptr++; }
> };
Except that I don't really like the abuse of operator
overloading. What's wrong with:
template< typename T >
class Iter
{
public:
Iter( Container& c ) ;
bool isDone() const ;
T& element() const ;
void next() ;
}
> int main()
> {
> std::vector<int> v;
> for (int i = 0; i < 10; ++i)
> v.push_back(i);
> Iter<std::vector<int> > it(v.begin(), v.end());
> while (it)
> {
> std::cout << *it;
> ++it;
> }
> }
> Not too sure about the operator bool() thing though...
I am:-). It's definitly an abuse. (But I've seen worse; I once
saw someone recommend overloading unary plus. So that the loop
would be:
for ( Iter i( container ) ; +i ; ++ i ) {
// ...
}
I far prefer nice clear names that say exactly what the function
is doing. Overloading ++ is arguable both ways, but the others
are blatant abuse.
Owen Jacobson
> > Don't know if you posted the correct link or if they just teaches us to
> > read better in college these days. :-) I think the correct
> > implementation, given the link you posted, should be
>
> > T& next() { ptr++; return *ptr; }
>
> No, that's not correct. In java.util.Iterator, the next() method does not
> modify the Iterator, it returns a new Iterator.
Seeing as I fundamentally agree that C++'s iterators, which are a
generalization of pointers, are a very solid concept and are very easy
to optimize back to being pointers when necessary, it's rather galling
to see you go so wildly wrong.
For your consideration, the following Java source code:
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class FunWithIterators {
public static void main (String[] args) {
List<String> list = Arrays.asList ("One", "Two", "Three");
Iterator<String> i = list.iterator ();
System.out.printf ("i is %s (identity %d)\n", i, System
.identityHashCode (i));
String next = i.next ();
System.out.printf ("i.next() returned %s\n", next);
System.out.printf ("i is %s (identity %d)\n", i, System
.identityHashCode (i));
next = i.next ();
System.out.printf ("i.next() returned %s\n", next);
System.out.printf ("i is %s (identity %d)\n", i, System
.identityHashCode (i));
}
}
I'd like you to explain how the output of this program squares with
the statements you've made. For reference, public static int
System.identityHashCode(Object) is, for programs with fewer than 2**32
live objects, a unique identifier for the object passed in. You can
trust that, if it returns the same number for two references, that
those references point to the same object.
The signature of Iterator.next() in Java is, in full,
public T next ();
where T is the type of the values being iterated over. It is not,
public Iterator<T> next();
and there is no corresponding
public T getValue();
Iterators in Java act as cursors, and are mutated by access.
I'm not convinced either language's primary Iterator implementation --
C++'s pointer generalization, or Java's cursors -- is all that great.
I've a preference for intrinsic iteration, as with Smalltalk, Ruby, or
most functional languages, where a functor to apply to each element is
passed to the collection, which then applies it. That you can't
mutate the collection during iteration (easily) this way is a feature,
not a bug; there are other tools that are better for that.
-o
(And really, can't language trolls find something juicier to argue
about?)
Lasse Reichstein Nielsen
> For starters, your implementation of next() is wrong. See
> http://java.sun.com/javase/6/docs/api/java/util/Iterator.html. The
> correct, equivalent, implementation would be:
>
> Iter<T> next() const { Iter<T> n; n.ptr=ptr+1; n.end=end; return n }
Actually not. A Java iterator's next() method returns an element,
not an iterator. A closer match would be:
template <class T>
struct Iterator {
T::iterator ptr;
T::iterator end;
bool hasNext() const { return ptr != end; }
T next() { return *(ptr++); }
};
so that you can do:
for(Iterator<Something> iter = myCollection.iterator(); iter.hasNext();) {
Something element = iter.next();
// ...
}
> Gosh, what the heck are they teaching in college, these days?
Java :)
/L
--
Lasse Reichstein Nielsen - l...@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Martin York
> Sam <s...@email-scan.com> writes:
> > For starters, your implementation of next() is wrong. See
> >http://java.sun.com/javase/6/docs/api/java/util/Iterator.html. The
> > correct, equivalent, implementation would be:
>
> > Iter<T> next() const { Iter<T> n; n.ptr=ptr+1; n.end=end; return n }
>
> Actually not. A Java iterator's next() method returns an element,
> not an iterator. A closer match would be:
Just to be nit-picky :)
It should probably return a reference.
T& next() { return *(ptr++); }
> > Gosh, what the heck are they teaching in college, these days?
Gosh the old bizzers :-)
chsa...@gmail.com
subjective, aesthetic reasons. However, there are times when I
question the sanity of having two iterator objects instead of one.
Sam pointed out that Java iterators are much less efficient
constructs, (using virtual functions and frequent reallocation), but
the issue here I think is not so much the actual implementation, but
the interface. In other words, would it be better to implement Java-
style iterator constructs in C++?
Especially, in a case where you have a rather complex iterator object
that has a lot of member variables, and so takes up a lot more stack
space than a simple pointer. Usually, the "end" iterator object is
only there so you can compare a single member variable. The rest of
the member variables in the "end" iterator object are usually unused.
While there's probably not any measurable performance loss, the Java-
style interface would me more efficient in theory, because you
wouldn't have the extra "end" iterator with all the useless member
variables it stores.
James Kanze
> Overall, I usually prefer C++ iterators to Java style
> iterators for subjective, aesthetic reasons. However, there
> are times when I question the sanity of having two iterator
> objects instead of one.
That is, of course, the crux of the problem. Requiring two
objects to implement a single instance of a specific concept,
with each object only containing part of the information.
> Sam pointed out that Java iterators are much less efficient
> constructs, (using virtual functions and frequent reallocation),
Sam's just our local troll. I wouldn't pay too much attention
to what he says. In practice, I've not found Java's iterators
to be excessively slow. In the end, however, it will depend a
lot on the VM or the compiler optimizer.
> but the issue here I think is not so much the actual
> implementation, but the interface. In other words, would it
> be better to implement Java- style iterator constructs in C++?
Why not implement something better than either, like the GoF
iterators?
There are actually two issues involved, the iterator interface,
and whether it uses copy or reference semantics. With regards
to the first, it seems fairly clear from a design point of view
that requiring two iterators isn't really very clean, and cause
problems. The choice between copy and reference semantics,
however, is much less clear. There are significant use cases
for both (and the input iterator concept in the STL makes
allowances for this---an input iterator basically has, or is
allowed to have, reference semantics). My own current policy is
to implement copy semantics, using the GoF pattern, and adding
an isEquals() function if possible, then derive from a template
using the Barton & Nackman trick to provide the STL
interface---at best, however, a forward iterator. This seems to
work well in practice, most of the time; in cases where I need
reference semantics, I can always pass a reference.
(Note that reference semantics more or less impose an in order
traversal; copy semantics give the implementation much more
freedom. This probably isn't a critical point at present, but
once we start getting compilers capable of automatically
parallelizing loops, it could start making a significant
difference in performance.)
> Especially, in a case where you have a rather complex iterator
> object that has a lot of member variables, and so takes up a
> lot more stack space than a simple pointer. Usually, the
> "end" iterator object is only there so you can compare a
> single member variable. The rest of the member variables in
> the "end" iterator object are usually unused. While there's
> probably not any measurable performance loss, the Java- style
> interface would me more efficient in theory, because you
> wouldn't have the extra "end" iterator with all the useless
> member variables it stores.
This is really part of the copy vs reference semantic issue,
more than the interface issue. The STL supposes that copy is
cheap, and copies a lot. From a performance point of view, this
isn't always the right solution, but performance is rarely the
issue. Copy and reference have different semantics. Sometimes
one is more appropriate, and sometimes another. There is no
"right" answer.
Jerry Coffin
@q10g2000prf.googlegroups.com>, chsa...@gmail.com says...
> Overall, I usually prefer C++ iterators to Java style iterators for
> subjective, aesthetic reasons. However, there are times when I
> question the sanity of having two iterator objects instead of one.
C++ 0x should be somewhat more to your liking then -- it introduces
Ranges. A range is essentially equivalent to a pair of iterators; it
represents a range of objects (typically, but not necessarily, in a
container).
[ ... ]
> Especially, in a case where you have a rather complex iterator object
> that has a lot of member variables, and so takes up a lot more stack
> space than a simple pointer. Usually, the "end" iterator object is
> only there so you can compare a single member variable. The rest of
> the member variables in the "end" iterator object are usually unused.
> While there's probably not any measurable performance loss, the Java-
> style interface would me more efficient in theory, because you
> wouldn't have the extra "end" iterator with all the useless member
> variables it stores.
True. I think an iterator containing a lot of data is fairly unusual,
but if/when you need to create an iterator that contains a lot of data
that's never used, that's obviously not particularly efficient.
--
Later,
Jerry.
The universe is a figment of its own imagination.