Oleg Zabluda <zabluda@math.psu.edu> writes:

>Matt Austern <austern@sgi.com> wrote:
>: Oleg Zabluda <zabluda@math.psu.edu> writes:

>: > My guess is that Stroustrup probably removed it from the
>: > original Stepanov and Lee's STL, ...

>: It's true that many things were removed from the STL during
>: standardization, but hash tables weren't in the original Stepanov-Lee
>: STL.  The people who proposed hash tables for the standard C++ library
>: were Bob Fraley, Javier Barreiro, and David Musser.  ("Hash Tables for
>: the Standard Template Library", X3J16/94-0218 and WG21/N0605.)

>Like I've said before, I wasn't around when all this was happening.

But the people who have answered your question WERE around and
have told you (correctly) what happened.

>The only things I know are vague recollections of some stuff I've
>read a year or so ago.

The things I know come from my presence at the meetings and
my access to the C++ Committee papers.

>I went back, and reread original STL
>pepers and a couple of Stepanov's interviews, just to see
>how much of what I remember are hallucinations or false
>memories, or consequence of alien abduction screwing my mind
>or something. I am pretty sure that a lot of what I ``remember''
>probably comes from Stepanov's interviews. For example, from

>http://www.bml.ca/marine/stepanov.htm

>  Remember that it was very hard to push through STL because of its
>  size. I had to throw away dosens of useful components. (Think what
>  happened to hash tables.)

>[ From the ``Byte'' URL (see below) it seems that the Stepanov's   ]
>[ ``component'' means ``class or function'' -- O.Z.                ]

>Like I've said, since I was turning coffee into the theorems at the time,
>and was nowhere near C++, those are only my guesses. Still, it's
>an educated guess. There is a very strong push behind hash containers.
>If an equally strong push was behind, say, a singly linked list,
>or a two-dimentional vector, I think it would be accepted in a jiffy.
>Hash containers were not. Now, why is that? The above is my guess, why.
>I understand that there were issues, like timing of the proposals and
>such. I think (hope) they were secondary.

In fact, the opposite is true.

As has been said already many times, hash tables were not part
of the original STL proposal. A hash table proposal was first
submitted some time after the committee declared that no new
additions would be considered. The committee minutes reflect
that the hash table proposal was rejected SOLELY on the basis
of timing, and NOT for any technical reason. Indeed, no
technical evaluation of the proposal was ever performed. It
was simply too late to consider any proposal of that magnitude.

---
Steve Clamage, stephen.clamage@sun.com

--
Steve Clamage, stephen.clamage@sun.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern <austern@sgi.com> wrote:
: Oleg Zabluda <zabluda@math.psu.edu> writes:

: > My guess is that Stroustrup probably removed it from the
: > original Stepanov and Lee's STL, for the reasons close to
: > the ones mentioned above.
: >
: > About half of the containers and 2/3 of algorithms were removed
: > during this process.

: It's true that many things were removed from the STL during
: standardization, but hash tables weren't in the original Stepanov-Lee
: STL.  The people who proposed hash tables for the standard C++ library
: were Bob Fraley, Javier Barreiro, and David Musser.  ("Hash Tables for
: the Standard Template Library", X3J16/94-0218 and WG21/N0605.)

Like I've said before, I wasn't around when all this was happening.
The only things I know are vague recollections of some stuff I've
read a year or so ago. I went back, and reread original STL
pepers and a couple of Stepanov's interviews, just to see
how much of what I remember are hallucinations or false
memories, or consequence of alien abduction screwing my mind
or something. I am pretty sure that a lot of what I ``remember''
probably comes from Stepanov's interviews. For example, from

http://www.bml.ca/marine/stepanov.htm

  Remember that it was very hard to push through STL because of its
  size. I had to throw away dosens of useful components. (Think what
  happened to hash tables.)

[ From the ``Byte'' URL (see below) it seems that the Stepanov's   ]
[ ``component'' means ``class or function'' -- O.Z.                ]

-=-=-=-=-=-=

Valentin Bonnard <bonnardv@pratique.fr> wrote:
: Oleg Zabluda <zabluda@math.psu.edu> writes:

: > About half of the containers and 2/3 of algorithms were removed
: > during this process.

: Which containners ? Which algorithms ?

: I have compared the HP STL, SGI STL and std STL. The only
: differences I have found with the algorithms are about
: the is_xxx functions (removed) and find_xxx variants (added).

In article <6h1501$emt@marianna.psu.edu>, zabluda@math.psu.edu says...
> Hankel O'Fung <hkfung@ust.hk> wrote:
> : Dear all,
>
> : 1) Please forgive me if this is an old question: what is the reason for
> : not accepting hash table as part of the standard library?
>
> My understanding is that impossibility to guarantee anything
> about performance. Neither average nor worst-case. And it was
> considered unacceptable to burden a user with providing a hash
> table.

I'm a bit confused here: The average case with hash tables is fairly
well known, particularly with ones that do gradual resizing to avoid
pathological cases.

It's also possible to guarantee a worst case of log(n) if you want to.
You simply resolve collisions by placing the colliding elements in a
tree.

However, this does impose somewhat greater responsibility on the user
of the class: the current containers require that the user implement
ordering, where a hash table that used trees for collision handling
would require both ordering and hash generation.

--
    Later,
    Jerry.

The Universe is a figment of its own imagination.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda <zabluda@math.psu.edu> writes:

> About half of the containers and 2/3 of algorithms were removed
> during this process.

Which containners ? Which algorithms ?

I have compared the HP STL, SGI STL and std STL. The only
differences I have found with the algorithms are about
the is_xxx functions (removed) and find_xxx variants (added).

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3533E11D.49D82F4D@ust.hk>, hkfung@ust.hk says...
> Dear all,
>
> 1) Please forgive me if this is an old question: what is the reason for
> not accepting hash table as part of the standard library? Or maybe this
> is a wrong question. I should ask the following first: has any body
> submitted a specification of hash-table to the ANSI/ISO C++ committee?

I don't believe a formal proposal was made before the cutoff for
extensions to be proposed.  If memory serves, David Musser did write
up a proposal, but I'm not sure it was ever formally presented to the
committee.

> 2) Where can I find a portable, reliable, efficient and free-of-charge
> (sorry for being so greedy) implementation of a hash table?

Quite a few implementations of the standard library include an
unordered variant of map and/or multimap, which is typically based on
a hash table.  If memory serves, SGI's freely available version is one
of these.

> 3) Just for curiosity. What is the "std" in "comp.std.c++"? Standard,
> study, or ...?

As you've surmised, "standard" -- meaning it's really for discussion
of the C++ standard itself.  Issues of how to use C++ are relevant
only to the extent that they determine what should be standardized and
what shouldn't.

--
    Later,
    Jerry.

The Universe is a figment of its own imagination.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article 49D82F4D@ust.hk, "Hankel O'Fung" <hkfung@ust.hk> writes:
>
>1) Please forgive me if this is an old question: what is the reason for
>not accepting hash table as part of the standard library? Or maybe this
>is a wrong question. I should ask the following first: has any body
>submitted a specification of hash-table to the ANSI/ISO C++ committee?

The original STL proposal was accepted into the C++ standard in 1994.
Some time later, a proposal for hash table additions was submitted,
but it was past the point where proposals for new features could be
accepted. The proposal was not rejected for any technical reason, but
only because there was not enough time to evaluate it and still have
any hope of getting out the standard in anything approaching the
schedule. The standard took 8 years from inception to approval of a
final draft as it was.

The STL proposal took over 4 years to settle, from original proposal
to when it achieved some stability. (It was still being tweaked up
until the end.) The hash table proposal was nearly as big, and we'd
probably still be working on it had it been accepted.

>3) Just for curiosity. What is the "std" in "comp.std.c++"? Standard,
>study, or ...?

"Standard". See the FAQ for more on that subject.

---
Steve Clamage, stephen.clamage@sun.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hankel O'Fung <hkfung@ust.hk> wrote:
: Dear all,

: 1) Please forgive me if this is an old question: what is the reason for
: not accepting hash table as part of the standard library?

My understanding is that impossibility to guarantee anything
about performance. Neither average nor worst-case. And it was
considered unacceptable to burden a user with providing a hash
table.

: Or maybe this
: is a wrong question. I should ask the following first: has any body
: submitted a specification of hash-table to the ANSI/ISO C++ committee?

My guess is that Stroustrup probably removed it from the
original Stepanov and Lee's STL, for the reasons close to
the ones mentioned above.

About half of the containers and 2/3 of algorithms were removed
during this process.

: 2) Where can I find a portable, reliable, efficient and free-of-charge
: (sorry for being so greedy) implementation of a hash table?

http://www.sgi.com/Technology/STL
http://www.metabyte.com/~fbp/stl/effort.html

: 3) Just for curiosity. What is the "std" in "comp.std.c++"? Standard,
: study, or ...?

Standard.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda <zabluda@math.psu.edu> wrote:
: Hankel O'Fung <hkfung@ust.hk> wrote:
: : Dear all,

: : 1) Please forgive me if this is an old question: what is the reason for
: : not accepting hash table as part of the standard library?

: My understanding is that impossibility to guarantee anything
: about performance. Neither average nor worst-case. And it was
: considered unacceptable to burden a user with providing a hash
: table.
  ^^^^^

Sorry, just in case it was not clear, it's a typo. It was meant to be
hash _function_.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda <zabluda@math.psu.edu> writes:

> My guess is that Stroustrup probably removed it from the
> original Stepanov and Lee's STL, for the reasons close to
> the ones mentioned above.
>
> About half of the containers and 2/3 of algorithms were removed
> during this process.

It's true that many things were removed from the STL during
standardization, but hash tables weren't in the original Stepanov-Lee
STL.  The people who proposed hash tables for the standard C++ library
were Bob Fraley, Javier Barreiro, and David Musser.  ("Hash Tables for
the Standard Template Library", X3J16/94-0218 and WG21/N0605.)
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda <zabluda@math.psu.edu> wrote:
>Hankel O'Fung <hkfung@ust.hk> wrote:
>: Dear all,
>
>: 1) Please forgive me if this is an old question: what is the reason for
>: not accepting hash table as part of the standard library?
>
>My understanding is that impossibility to guarantee anything
>about performance.

I mean no disrespect to Oleg, but this had very little to do with it.

>: Or maybe this
>: is a wrong question. I should ask the following first: has any body
>: submitted a specification of hash-table to the ANSI/ISO C++ committee?
>
>My guess is that Stroustrup probably removed it from the
>original Stepanov and Lee's STL, for the reasons close to
>the ones mentioned above.
>
>About half of the containers and 2/3 of algorithms were removed
>during this process.

No containers were "removed".  The hash tables were coded too late.
All the containers are just examples, anyway, particularly deque and
the priority queue adapter.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Dear all,

1) Please forgive me if this is an old question: what is the reason for
not accepting hash table as part of the standard library? Or maybe this
is a wrong question. I should ask the following first: has any body
submitted a specification of hash-table to the ANSI/ISO C++ committee?

2) Where can I find a portable, reliable, efficient and free-of-charge
(sorry for being so greedy) implementation of a hash table?

3) Just for curiosity. What is the "std" in "comp.std.c++"? Standard,
study, or ...?

Hankel
--
Dept of Ind Engg & Engg Mgt (IEEM)
HKUST, Clear Water Bay, Kowloon
Hong Kong

tel   (852) 2358 7103      fax   (852) 2358 0062
http://home.ust.hk/~hkfung




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hankel O'Fung <hkfung@ust.hk> writes:

> 1) Please forgive me if this is an old question: what is the reason for
> not accepting hash table as part of the standard library?

You know why (see below). Yes you are forgiven. (By me, other
regular posters can still flame you. ;-)

> Or maybe this
> is a wrong question. I should ask the following first: has any body
> submitted a specification of hash-table to the ANSI/ISO C++ committee?

It is. No, I don't think so.

Reason: not enough time to get the details right

> 2) Where can I find a portable, reliable, efficient and free-of-charge
> (sorry for being so greedy) implementation of a hash table?

In the SGI STL, or an adaptation of it (STLport).

> 3) Just for curiosity. What is the "std" in "comp.std.c++"? Standard,
> study, or ...?

Standard, as all comp.std.* groups.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]