Re: Using java.util.map
- From: The Ghost In The Machine <ewill@xxxxxxxxxxxxxxxxxxxxxxx>
- Date: Wed, 16 Aug 2006 16:00:03 GMT
In comp.lang.java.advocacy, Christopher Benson-Manica
<ataru@xxxxxxxxxxxxxxxxxxx>
wrote
on Wed, 16 Aug 2006 13:54:28 +0000 (UTC)
<ebv82k$ocp$2@xxxxxxxxxxxxxxxx>:
Thomas Weidenfeller <nobody@xxxxxxxxxxxxxxxx> wrote:
(Continuing a thread from comp.lang.java.programmer...)
F'up set.
(I still have no idea why, but since I'd rather continue the
conversation than debate whether or not my comments constitute
"advocacy", I've superseded the previous post and directed the
conversation to your group of choice.)
a) You don't traverse the map twice (traversing means systematically
visiting every entry). You perform a lookup and an insertion. Only if
these operations degenerate each element in the map would have been visited.
You're right, "traverse" was not the right word.
b) You assume that the C++ way is clean (with the need to explicitly
create an extra pair<K,T> object for each entry), and the Java way is dirty.
I'm not saying Java is dirty, I'm just saying it seems to require two
lookups unless the programmer takes countermeasures.
The terms "clean" and "dirty" are less than clear to me,
since I've not seen this subthread in awhile (if at all).
It's not necessary for the C++ caller to create the pair:
std::map<std::string, SomeClass> mapSto;
mapSto[std::string("mykey")] = SomeClass(...);
will suffice. Of course if you're referring to
std::map<>'s internals, I'd have to dig into the details.
I can tell you that there's a red-black tree involved
and that this call ultimately gets pushed down into an
insert_unique() method. Farther than that the code gets
a little tortured, though that's probably because I don't
have an equivalent to Eclipse for C++, or the appropriate
C++ plugin. :-)
(Spoiled rotten? Naaaaaah.)
I do see the routine
pair<iterator, bool> insert(pair<const _Key, _Tp> const &),
so presumably that's what all this is about. I've never had to use
that routine in maps although now that I know about it I'll add it
to my arsenal. :-) Not that I expect to use it except in
implied loops such as
pair<const std::string, SomeClass> arraySto[] = {
...
};
mapSto = std::map<std::string, SomeClass>(arraySto, arraySto +
sizeof(arraySto)/sizeof(arraySto[0]));
which isn't exactly the most comprehensible of C++
constructs, without a nearby comment, or a macro definition
such as
#define ARRAYLENGTH(a) (sizeof(a)/sizeof(a[0])) [*]
It looks convenient for creating C++ maps, though,
especially for command lookup/keyword lookup tables,
which don't change too often.
In Java I'd have to use an explicit for loop. Hard for me
to say whether this is good or bad; most people don't have
problems understanding simple for loops of the sort
for(int i = 0; i < keys.length; i++)
map.put(keys[i], values[i]);
although one has to be careful in this particular loop lest
keys[] and values[] get out of synch. (One could of course
define a Map.Entry implementation or a class that has two
fields and an appropriate constructor, but see below.)
I claim the C++ way is dirty, because it exposes implementation interna.
It's certainly an arguable point.
c) You claim there is an equivalent of the get() method in C++ for maps,
which return a pair<K,T>. To the best of my knowledge, there isn't.
find( const key_type& x ) returns an iterator to the pair with key x,
if it exists.
entrySet() returns an iterator to all key-value pairs
in a Java map (java.util.Map.Entry). There's no lookup,
however, for individual elements, although one could in a
pinch use tailMap() in a SortedMap. I strongly suspect a
proxy implementation with bounding, which means a lookup
would not be performed during tailMap() construction, but
one gets an extra comparison on occasion.
Nor can one explicitly construct java.util.Map.Entry
elements; Map.Entry is an interface. Implementing the
interface is possible but the map won't do much with the
resulting Object; it will copy the key and value into its
own datastructures. In that way, Map protects itself.
For its part the C++ implementation does the same; the
array in the above C++ mapSto example is discardable
(though the actual strings thereof may not be!) once
the map is constructed, although for a static example
such as the one above discarding would be difficult in a
contemporary operating system unless one throws away an
entire loadable library; that's possible but cumbersome
using dlopen()/dlclose() in Linux. (Windows might have
a slightly easier time of it but I'm not as familiar
with it. Caveat programmer. :-) )
Clearly it doesn't mean that.
But the lookup is performed twice, yes?
More than once, yes...and that's not counting the redblack
edge traversal.
That kludge is in fact a re-creation of the C++ kludge. You are adding
another level of indirection. Which is what the C++ pair<K,T> provides
in the first place in C++.
Yes, it's exactly a recreation of the C++ kludge, and I'm just
astonished that apparently the desire for it is small enough that
isn't built into the java.util.map...
I for one might want a NotFoundException or some such,
probably as an option. (There is a NoSuchElementException,
but get() doesn't throw it; firstKey() and lastKey() will
throw NoSuchElementException on an empty map, which makes some
sense but one might prefer EmptyMapException instead -- but
Java is a collection of compromises, same as C++. This
area could be cleaned up a bit, though.)
I'll admit Java is a little brainscattered when it comes
to nulls; get() can return null either because the key is
not in the map, or the key is associated with a null value
in the map. (containsKey() can be used to distinguish the
two cases but there's that double lookup again.) However,
beware a null key with natural ordering or a Comparator
that doesn't know how to handle them. :-)
For its part C++ operator[](const _Key &) simply creates
the entry if it doesn't exist. There is no
operator[](const _Key &) const, presumably because many
C++ programmers don't like to deal with exceptions. stl::map
doesn't have issues with null pointers in maps, unless the
programmer dereferences a pointer during operator<() or one
runs off the end of an iterator, leading to undefined behavior.
[*] there is a XtNumber(arr) macro in Intrinsic.h, but most
people don't use X's Intrinsics, and C++ does not require X.
--
#191, ewill3@xxxxxxxxxxxxx
Windows Vista. Because it's time to refresh your hardware. Trust us.
.
- Follow-Ups:
- Re: Using java.util.map
- From: Christopher Benson-Manica
- Re: Using java.util.map
- Prev by Date: Re: Boycott Intel
- Next by Date: Re: Using java.util.map
- Previous by thread: Is it possible to make a program to generate a sudoku
- Next by thread: Re: Using java.util.map
- Index(es):
Relevant Pages
|
