Re: hash_map
Earl Purple wrote:
Jiang wrote:
Actually it is well-formed code, but "const char *" is
not a good choice for keys, it is pointer. And your string
literals can have different addresses.
That does not matter if they have different addresses for
hash_map as he has to provide a hashing algorithm, and it will
presumably be based on the contents of the strings, not the
addresses.
A hash map needs two functions, one to calculate the hash code,
and another to compare for equality.
If I understand his use of g++'s map, he specified the hash
function, but not the comparison function. It's been a while
since I last played with g++'s map, but I rather doubt that it
has a specialization which uses something other that the
standard = operator for char const* (although I wouldn't be
surprised if the hash function had such a specialization).
It is very important when using a hash map that the equality
comparison and the hash function work together. Logically, you
shouldn't be able to specify one without specifying the other;
my own hash map uses a traits class for this. I find it rather
surprising the g++ (and the TR1) would allow you to specify one
without specifying the other. I presume that this is because
the built-in types automatically have equality comparaison, but
not a hash function, but it still smells very much like a hack
to me; a hasher traits class with the necessary explicit
specializations would seem a more appropriate choice.
Please do not use it as map's key, use std::string
instead.
I do possibly agree with you but for a different reason - so
that you don't have to handle maintenance of the pointers. How
are you planning to handle the cleanup of the pointers?
It's not rare, at least in my code, to have maps whose indexes
are all string literals. I still use std::string with std::map,
because I'm too lazy to provide the comparison functions; my own
hash map, on the other hand, uses a single traits class to
specify both equality and the hash function---and I do have a
specialization on it for char const*.
But I see you considered that possibility later.
[...]
BTW, you need specialized hask<std::string> to work with
g++, IIRC.
Hopefully, they've fixed this since then.
More generally, as unordered_set moves toward standardization, I
would expect that 1) all of the standard classes which can be
put into a standard container (e.g. all which support copy and
assignment) should get a hashcode() function, which the
non-specialized version of hash<> uses, and 2) the standard
specifies specializations for all built-in types, as well as for
pointers, with special handling of char const*.
Finally, if it isn't absolutely too late, I would like to plee
for a change in the interface, so that it uses a single traits
class for both values, rather than two separate, independant
hash and equal parameters. From my own experience: once I got
my basic hash traits right, with the necessary specializations,
I don't think I've ever had to explicitly provide a hasher since
then, so the added overhead of providing a class, rather than a
single function, doesn't seem relevant. And if not, you will
constantly end up with cases where the string is hashed, but the
pointers compared, or similar things.
From a QoI point of view, of course, I would generally expect
Fowler/Noll/Vo. But I don't think that the standard should
impose such; I imagine that there are special cases where it
isn't appropriate. (On machines without hardware
multiplication, or a very slow multiplier, for example,
calculating FNV could be significantly slower than using the
Mersenne prime generator that I invented. Could be, not is: the
Sparc I work on most of the time doesn't have hardware
multiplication, and yet I can't find a measurable difference.)
In his case a specialised hash<const char *> if that's what
he's using as the key.
G++ already provides that. Even if the hash function it uses
has some weaknesses. (If you have a hash table with two
character keys, you'll get a very definite clustering in roughly
the first 1500 entries. Of course, most of the time, if you
only have two character keys, you won't have more than a couple
of hundred entries, and it won't be a problem. But never the
less; better solutions are known.)
--
James Kanze GABI Software
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
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]