 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Minkoo Seo
Guest
|
 Posted: Thu Dec 08, 2005 8:19 pm Post subject: Why STL does not have hash_table? |
 |
|
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. 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! ]
|
|
| Back to top |
|
 |
Thomas Tutone
Guest
|
| Posted: Thu Dec 08, 2005 10:00 pm Post subject: Re: Why STL does not have hash_table? |
|
|
Minkoo Seo wrote:
| Quote: | 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.
| Quote: | 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
| Quote: | 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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Thomas Maeder
Guest
|
| Posted: Thu Dec 08, 2005 11:53 pm Post subject: Re: Why STL does not have hash_table? |
|
|
"Minkoo Seo" <minkoo.seo (AT) gmail (DOT) com> writes:
| Quote: | 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.
| Quote: | 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.
| Quote: | Anybody knows the reason?
|
You didn't propose a hash table in time. Nor did I. Nor anybody else.
| Quote: | 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.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Fri Dec 09, 2005 3:09 pm Post subject: Re: Why STL does not have hash_table? |
|
|
Thomas Maeder wrote:
| Quote: | "Minkoo Seo" <minkoo.seo (AT) gmail (DOT) com> writes:
|
[...]
| Quote: | 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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Thomas Maeder
Guest
|
| Posted: Fri Dec 09, 2005 9:18 pm Post subject: Re: Why STL does not have hash_table? |
|
|
"kanze" <kanze (AT) gabi-soft (DOT) fr> writes:
| Quote: | 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?
| Quote: | There was a proposal for hash tables presented to the committee,
toward the end of the standardization process.
|
I see.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
James Kanze
Guest
|
| Posted: Sat Dec 10, 2005 9:31 pm Post subject: Re: Why STL does not have hash_table? |
|
|
Thomas Maeder wrote:
| Quote: | "kanze" <kanze (AT) gabi-soft (DOT) 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: [email]james.kanze (AT) free (DOT) fr[/email]
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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
