>>>> Thus spake 'Fergus Henderson (fjh@mundook.cs.mu.OZ.AU)':
[snip]
 >>> I looked at the STL for the first time. Is there an implementation of
 >>> hash tables that "fits" wit the rest of STL?

 FH> Yes, somewhere there is such a thing. (I don't know the URL off hand,
 FH> though.)

Check out <ftp://butler.hpl.hp.com/stl>. Found this reference in the book
"C++ Programmer's Guide to the Standard Template Library" by Mark Nelson (pg.
286):

  If you're interested in the future of hash-based containers, you might want
  to check HP's distribution site for the STL (butler.hpl.hp.com, in directory
  /stl). Some sample code and a document have been posted. Together, they
  should provide you with enough information to begin experimenting with this
  new type of container.

HTH.
--
Brad Howes                          Motorola E-Mail ID: XBH001
EMT Development                     SMTP E-Mail: bhowes@cssun3.corp.mot.com
Motorola Corporate - MD H1780       Voice: 602 441 1522  Fax: 602 441 5455

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

Enno Rehling wrote:
>
> I'm looking for something, though. Hash tables. It seems they aren't
> implemented anywhere, and I need them.

The SGI site has the STL with has an implementation of hashtables.  Besides the
standard 4 assocative containers, they define 4 additional *hashed* assocative
containers: hash_set, hash_multiset, hash_map, and hash_multimap, which are all
implemented using a hashtable class (hashtable.h).

The site itself has *loads* of information and, IMHO, is very nicely origanized
and
presented.

Go to http://www.sgi.com/Technology/STL/.

Jay Ernst

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

Enno Rehling wrote:

> Is there an implementation of hash tables that "fits"
> wit the rest of STL? (I want to use for_each(),
> find(), etc. on it)

You can try

  ftp://ftp.cs.rpi.edu/pub/stl/hashimp2.tar.gz


Kresimir Fresl


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

> "Enno Rehling" <enno@uni-paderborn.de> wrote:
> >I'm looking for something, though. Hash tables. It seems they aren't
> >implemented anywhere, and I need them.

Rogue Wave's STL implementation includes rw_hashset, rw_hashmap,
rw_hashmultiset, rw_hashmultimap;  Rogue Wave is available on many
platforms and tailors the template code for each compiler's (lack of)
features.

I've written my own doubly-linked list as a replacement for my vendor's
list implementation (Rogue Wave), because the stock implementation
allocates a minimum of 1k for each list (to be used as a freelist), so
keeping many small lists was wastful.  It is not hard to write an STL
container, really!  Just study the examples of the HP reference
implementation.  But, it *is* hard to accomodate all varying levels of
compiler implementation (e.g. no member templates, weird allocators).

Harlan Messinger wrote:

> The basic data structure that STL provides for the purpose of matching
> key values with the items they represent is the "map" (or the
> multimap, which allows duplicate keys). A hash table is  just one way
> of implementing a map.

Could be, but generally hash tables do not preserve order, which is
something guaranteeed by map.  But if you have a map implementation that
preserves  order *and* provides constant-time operations, let me know!
I want one!  Rogue Wave's rw_hashset/map implementation does not
preserve order of the keys, but rw_hashmultiset/map does support
upper_bound/lower_bound for finding all entries for a single key.

john lilley


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

"Enno Rehling" <enno@uni-paderborn.de> writes:

> Hello,
>
> I have recently been introduced to the STL. In my eyes, the most wonderful
> peice of software ever written. Congratulations to the designers.
>
> I'm looking for something, though. Hash tables. It seems they aren't
> implemented anywhere, and I need them.
>
> I'm thinking about implementing my own now, something I wanted to avoid
> when I looked at the STL for the first time. Is there an implementation of
> hash tables that "fits" wit the rest of STL? (I want to use for_each(),
> find(), etc. on it)

Yes.  Hash tables are part of SGI's implementation of the STL.  SGI's
implementation, which is freely available to the public, is located
at http://www.sgi.com/Technology/STL/.

SGI will continue to enhance the STL with additional data structures
and algorithms, and this WWW site will be updated frequently.


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

gusty@mail.clark.net (Harlan Messinger) writes:

>"Enno Rehling" <enno@uni-paderborn.de> wrote:
>
>>I looked at the STL for the first time. Is there an implementation of
>>hash tables that "fits" wit the rest of STL? (I want to use for_each(),
>>find(), etc. on it)

Yes, somewhere there is such a thing.
(I don't know the URL off hand, though.)

>Unless there is a particular reason why you need to use a hash table
>to implement a key value lookup, use map or multimap.

Red-black trees are often a lot less efficient than hash tables.
In the normal case, lookup in a tree has O(log N) complexity, whereas
lookup in a hash table is O(1) (constant time).

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

Hello,

I have recently been introduced to the STL. In my eyes, the most wonderful
peice of software ever written. Congratulations to the designers.

I'm looking for something, though. Hash tables. It seems they aren't
implemented anywhere, and I need them.

I'm thinking about implementing my own now, something I wanted to avoid
when I looked at the STL for the first time. Is there an implementation of
hash tables that "fits" wit the rest of STL? (I want to use for_each(),
find(), etc. on it)

Thanks for your input.

Enno Rehling
---
rehling@usa.net  Int+ 49 (0) 5251-760796  Paderborn, Germany


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]