Why STL does not have hash_table?

December 9, 2005

Tags:

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! ]

2. Thomas Tutone
Dec 9, 7:00 am show options
Newsgroups: comp.lang.c++.moderated
From: “Thomas Tutone” – Find messages by this author
Date: 8 Dec 2005 17:00:46 -0500
Local: Fri, Dec 9 2005 7:00 am
Subject: Re: Why STL does not have hash_table?
Reply | Reply to Author | Forward | Print | Individual Message | Show original | Report Abuse

Minkoo Seo wrote:
> 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

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

3. Thomas Maeder
Dec 9, 8:53 am show options
Newsgroups: comp.lang.c++.moderated
From: Thomas Maeder – Find messages by this author
Date: 8 Dec 2005 18:53:59 -0500
Local: Fri, Dec 9 2005 8:53 am
Subject: Re: Why STL does not have hash_table?
Reply | Reply to Author | Forward | Print | Individual Message | Show original | Report Abuse

“Minkoo Seo” writes:
> 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.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Why STL does not have hash_table?

Comments

Leave a Reply