|
|
Re: Collection overused as an argument in Java Libraries?
|
Posted: Jul 15, 2005 1:19 AM
|
|
> The main reason in STL for using iterators is not good
> design, it is to support arrays.
Huh? Where have you got that from? I haven't heard that anywhere else.
STL was designed by Alexander Stepanov. At the time, as I understand, he was looking for a language to implement his idea, and found that C++ fit the bill. Iterator is a general abstraction (in fact a pattern) that allows you to treat any sequence the same way, like I said in my posting, it also works for streams, etc. Also, with things like iterator adaptors, you may for example perform jumps, say accessing every tenth element, traversing it backwards, and so on.
Thus, I haven't seen any evidence that iterators where used in STL to support arrays. Yes, it supports arrays, too, but that's just one of the many things that the iterator abstraction supports.
But don't take my word for it, have a look at what its creator have to say about the subject: http://www.stlport.org/resources/StepanovUSA.html. For example:
"I believe that iterator theories are as central to Computer Science as theories of rings or Banach spaces are central to Mathematics."
No mentioning of C++ arrays, here. :)
> Since Java collections
> don't do any primitive types this isn't a consideration in
> Java and they went for a cleaner and simpler design of the
> 'Iterable' interface instead of an 'Iterator' that was
> cloneable etc.
What is cleaner and simpler is apparently in the eye of the beholder. I find a design, where you're not forced to inherit from an interface, for it to be used in algorithms, to be a cleaner design. You remove a dependency, so it may work with types that were designed separately.
Not to mention operator overloading in C++, something I find particularly elegant, since you can then make user-defined types which behave the same way as built-in types (and you avoid the clumsy wrapping of built-in types in an object, like in Java, just to be able to use it in a container, and you also typically get a performance hit that way, from the memory management).
The Java generics (although I understand the design rationale - in particular to be backwards compatible) also ensures that this continues - a List<int> is still just a List (of Object) to the bytecode...
> (see below for all the Iterator needs to
> do). One of the best example of when the Java design
> shines is with sort, in STL you have:
>
> sort( RandomAccessIterator begin, RandomAccessIterator end
> )
>
> with Java you have the simpler
>
> sort( List unsorted )
*shrugs*
// Sort for random access container (like vector)
template<class RandomAccessContainer>
void sort(const RandomAccessContainer &c)
{
sort(c.begin(), c.end());
}
// Sort for list
template<class T>
void sort(const list<T> &c)
{
c.sort();
}
These functions might just as well have been in the standard library, so you could use sort(), regardless of container type.
Note that in the above, it chooses the most efficient sort function (random access container) possible, depending on the container type.
> For the STL version to work you need a
> 'RandomAccessIterator' which has the following methods:
>
> Copy constructor
> Default constructor
> =
> swap
> ==
> !=
> * (dereference for both sides of =)
> -> (member access)
> ++ (both post and pree)
> *++ (post ++ combined with *)
> -- (both post and pre)
> +=
> + (two versions with arguments reversed)
> -=
> - (two versions with different argument types)
> [] (array access for both sides of =)
>
That also makes the STL iterator more powerful than the Java one (allowing you to traverse forward and backward or in jumps, and accessing any element, so it may be used as arguments to a generic sort function, unlike the Java version).
In other words, there's a reason for the complexity. Remember that when you compare designs, complexity by itself is not a good measurement. Compexity compared to versatility, however, is a good measurement. And that's where _C++ and STL_ shines.
Before the STL, there were several collection libraries in C++ (similar to the Java design). However, when STL came, it blew all these away. That was simply because many people feel it's a better design (not just so that you can also use it for arrays).
> As you can see this is considerably more complex than the
> Java 'Iterator' class. Not only is the
> 'RandomAccessIterator' necessarily much more complex; but
> it is typically used inefficiently, in particular a
> typical call would be:
>
> sort( vector.begin(), vector.end() )
>
> Then the first thing that 'sort' does is to make copies
> (clones) of its input arguments because it needs to
> guarantee that they aren't modified externally.
Actually, no, that's not the reason: C++ has no notion of concurrency in the current standard (something that will likely change in the next version of it). Moreover, there's no requirement for it to copy the iterators internally. It may do it, depending on the implementation, so iterators are assumed to be "lightweight" objects (unlike containers).
> Thus four
> 'RandomAccessIterator's are created before you even
> begin.
Wrong conclusion. Besides, these are typically pointers, and therefore this operation is neglible compared to the actual sort. Besides, who's to say that Java doesn't perform its own copying? Perhaps do a benchmark between C++ and Java?
> The STL sort can sort sub-ranges, but this typically isn't
> that useful and in anycase is easy in Java:
>
> sort( list.subList( 1, 2 ) )
>
> and STL still needs a subrange constructor in its 'vector'
> class.
Really? It doesn't need that, to use a subrange of it. The point is to modify the iterators, not the container. With lists, you may get away with a few pointer operations, to get a sublist, but how will you be able to sort a subrange of a vector, if you need to pass the whole vector to sort? Then you need something like a "view", that provides such a subrange. So in exchange for iterator and iterator adapters, you may need a similar collection of views, which could be considered at least as complicated, and potentially less general.
> Having said all this, the STL design is correct for STL
> because it gives support for arrays and the Java design is
> correct for Java because it is much simpler.
You may say that the Java collections framework is simpler than STL, but that's because it doesn't try to cover all that STL covers (support for arrays is only a small part of it - the iterator abstraction is a general concept that extends far beyond this, as mentioned).
Thus, comparing the two is a bit like comparing apples to oranges.
However, as mentioned above (and as you also mention here), the complexity is there for a reason, and having a more complex language and library can actually make your own code simpler. The essential complexity has to go somewhere, and if it's not in the language or library, it will be in the programs. I have experience with both programming C++ and Java, and Java code (in particular because it treats built-in and user-defined types fundamentally different, and doesn't support operator overloading, unlike C++) tends to become more verbose.
Take the C++ code:
++my_map[key];
This increments the element in the map referenced to by the key. With Java code, the above typically requires 4-5 lines of code (although some of the casting and manual "boxing" disappears with generics and auto-boxing, so it's better than it used to be, in Java 5).
Regards,
Terje
|
|
Previous Topic
