Why STL does not have hash_table?
Minkoo Seo
I'm writing a program where hash table is required in C++. Hence, I
searched for hash table/map implementation in STL, but I found
that there's no such one. Though there is map which relies on
red-black tree, but no hash table in the standard, which is quite
surprising to me.
Of course, SGI STL contains hash_table, and g++ have one, but
both of them are *non-standard*.
Anybody knows the reason?
What did happen at the time STL specification was being written?
Sincerely,
Minkoo Seo
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Thomas Tutone
> I'm writing a program where hash table is required in C++. Hence, I
> searched for hash table/map implementation in STL, but I found
> that there's no such one. Though there is map which relies on
> red-black tree, but no hash table in the standard, which is quite
> surprising to me.
They are now part of the tr1 extensions. Google for
std::tr1::unordered_map.
> Of course, SGI STL contains hash_table, and g++ have one, but
> both of them are *non-standard*.
And they will now be replaced by std::tr1::unordered_map and its
siblings. See
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf
> Anybody knows the reason?
> What did happen at the time STL specification was being written?
Take a look at Matt Austern's proposal to add hash table support:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
Here's a relevant quote:
"There is extensive experience with hash tables implemented in C++ in
the style of standard containers. Hash tables were proposed for the C++
standard in 1995; the proposal was rejected for reasons of timing."
Scott Meyers' Effective STL also discusses this issue.
Best regards,
Tom
Thomas Maeder
> I'm writing a program where hash table is required in C++. Hence, I
> searched for hash table/map implementation in STL, but I found
> that there's no such one. Though there is map which relies on
> red-black tree, but no hash table in the standard, which is quite
> surprising to me.
I have far more often be surprised at how much there is than at what
there isn't.
> Of course, SGI STL contains hash_table, and g++ have one, but
> both of them are *non-standard*.
But the Technical Report 1 (TR1) has unordered_set etc.
> Anybody knows the reason?
You didn't propose a hash table in time. Nor did I. Nor anybody else.
> What did happen at the time STL specification was being written?
The Standardization committees decided to restrict themselves to a set
they felt they were able to deal with within a reasonable time frame.
kanze
> "Minkoo Seo" <minko...@gmail.com> writes:
[...]
> > What did happen at the time STL specification was being
> > written?
> The Standardization committees decided to restrict themselves
> to a set they felt they were able to deal with within a
> reasonable time frame.
It's a little more complicated than that. One might reasonably
ask why Stepanov didn't include a hash table in the original
STL, for example. To get a definitive answer to that, of
course, you'd have to ask Stepanov, but I can think of some
possible reasons -- how do you define the complexity of a hash
table, for example? Stepanov was very concerned with
performance, or so I'be been told. It's pretty straight forward
to say that a balanced tree uses at most lg(n) comparisons, but
what can you say about a hash table, given that you don't know
what the user's hash function will look like. And what about
usability: it's pretty easy to define an ordering function
(although people still get it wrong), but writing a good hash
function -- or even recognizing one when you see it -- is not
obvious. (Note that the default hash function for std::string
provided with g++ is far from optimal for certain data sets.)
There was a proposal for hash tables presented to the committee,
toward the end of the standardization process. From what I've
heard, it was about the same length as the rest of the STL in
its entirity. Not surprising, given the choice of delaying the
standard, in order to analyse it, or standardizing without it,
the committee chose the latter.
--
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
Thomas Maeder
> It's pretty straight forward to say that a balanced tree uses at
> most lg(n) comparisons, but what can you say about a hash table,
> given that you don't know what the user's hash function will look
> like.
Well, quick sort takes O(n*lg(n)) on the average and O(n*n) in the
worst case. Why can't we say that a hash table lookup takes O(1) if
the table is well distributed and O(n) in the worst case?
> There was a proposal for hash tables presented to the committee,
> toward the end of the standardization process.
I see.
James Kanze
> "kanze" <ka...@gabi-soft.fr> writes:
>>It's pretty straight forward to say that a balanced tree uses
>>at most lg(n) comparisons, but what can you say about a hash
>>table, given that you don't know what the user's hash function
>>will look like.
> Well, quick sort takes O(n*lg(n)) on the average and O(n*n) in
> the worst case. Why can't we say that a hash table lookup
> takes O(1) if the table is well distributed and O(n) in the
> worst case?
Oh, I'm not saying that it cannot be done. I was just
speculating on the possible reasons why Stepanov didn't do it to
begin with.
Note too that in template code, the function must have a
predefined name. There is a fairly obvious spelling for the
comparison function he uses in map and set, "<". There is no
equivalently obvious spelling for the hashing function. Again,
not a killer as reasons go, but something that could have
influenced the choice.
--
James Kanze mailto: james...@free.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
John Nagle
> Hello all.
>
> I'm writing a program where hash table is required in C++. Hence, I
> searched for hash table/map implementation in STL, but I found
> that there's no such one.
>
> What did happen at the time STL specification was being written?
The actual reason is that the person who was writing the
hash table part of the spec didn't finish it in time.
That's all.
It's going into the next revision of C++, a decade late.
John Nagle
Animats