Re: Good ole gnu::hash_map, I'm impressed
On Jul 17, 11:45 am, Lionel B <m...@privacy.net> wrote:
On Thu, 17 Jul 2008 01:21:34 -0700, James Kanze wrote:
On Jul 16, 10:53 pm, Mirco Wahab <wa...@chemie.uni-halle.de> wrote:
[...]
Q2: Which "future" can be expected regarding "hashing"?
There will be an std::unordered_set and std::unordered_map
in the next version of the standard, implemented using hash
tables, and there will be standard hash functions for most
of the common types.
GNU g++ has supported those for quite a while in tr1, it seems.
(I wonder, however. Is the quality of the hashing function
going to be guaranteed?)
By whom/what?
By the standard.
I don't think the standard makes any guarantees. I've only got
a draft here, which says just:
6.3.3 Class template hash [tr.unord.hash]
1 The unordered associative containers defined in this clause use
specializations of hash as the default hash function. This class template
is only required to be instantiable for integer types
([basic.fundamental]), floating point types ([basic.fundamental]),
pointer types ([dcl.ptr]), and std::string and std::wstring.
template <class T>
struct hash : public std::unary_function<T, std::size_t>
{
std::size_t operator()(T val) const;
};
2 The return value of operator() is unspecified, except that equal
arguments yield the same result. operator() shall not throw exceptions.
That's about what I expected, and more or less what I said.
(But I do hope they add a few more types. There's no way you
can write a hash function on std::type_info, for example, yet it
seems quite reasonable to me to want to use it as an index in an
unordered_map.)
Still, you can always roll your own [possibly inappropriate
metaphor alert]
Which, for most people, is likely to be worse than whatever is
in the library; while there are no guarantees, I'm willing to
bet that most implementations will do something which is fairly
good most of the time. (But if you're willing to consider
special data sets, it's relatively trivial to get tons of
collisions with the string hashing functions in g++'s
implementation.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34