Hash table in C++? STL?

[pembed2003]

Hi All,
Does C++/STL have hashtable where I can do stuff like:

Hashtable h<int>;

h.store("one",1 );
h.store("two",2 );

and then later retrieve them like:

cout<<h.fetch(" one")<<endl;

prints 1

any idea?

Thanks!

[John Harrison]

"pembed2003 " <pe********@yah oo.com> wrote in message
news:db******** *************** **@posting.goog le.com...

Hi All,
Does C++/STL have hashtable where I can do stuff like:

Hashtable h<int>;

h.store("one",1 );
h.store("two",2 );

and then later retrieve them like:

cout<<h.fetch(" one")<<endl;

prints 1

any idea?

Thanks!

It has a map which has the same functionality as above (but store is called
insert and fetch is called find). Map is usually based on a red-black tree
algorithm. Several library implementers also offer a genuine hash table
(called hash_map) and apparently some version of this will make it into a
future version of the standard.

john

[Kevin Goodsell]

John Harrison wrote:

It has a map which has the same functionality as above (but store is called
insert and fetch is called find). Map is usually based on a red-black tree
algorithm. Several library implementers also offer a genuine hash table
(called hash_map) and apparently some version of this will make it into a
future version of the standard.

Does anyone know what will need to be provided in order to hash on a
particular type? std::map requires a less-than comparison operation --
what operations would a hash-based map need?

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Claudio Puviani]

"Kevin Goodsell" <us************ *********@never box.com> wrote

Does anyone know what will need to be provided in
order to hash on a particular type? std::map requires
a less-than comparison operation -- what operations
would a hash-based map need?

A hashing function and an equality operation are the minimum requirements, but
requiring a relational comparison (such as less_than) instead of equality would
allow for certain optimizations on the part of the implementers (such as using
a tree-like structure instead of lists for the buckets). I don't know whether
the standard will require equality or a relational comparator.

Sadly, the hashing function is where all the complexity lies and I'd be
pleasantly surprised if more than 1% of programmers knew what constitutes a
good hashing function. With a bad hashing function (and a naive bucket
strategy), performance can quickly degenerate to much worse than a balanced
tree on large data sets.

Claudio Puviani

[Andre Kostur]

Kevin Goodsell <us************ *********@never box.com> wrote in
news:Nx******** *********@newsr ead2.news.pas.e arthlink.net:

John Harrison wrote:

It has a map which has the same functionality as above (but store is
called insert and fetch is called find). Map is usually based on a
red-black tree algorithm. Several library implementers also offer a
genuine hash table (called hash_map) and apparently some version of
this will make it into a future version of the standard.

Does anyone know what will need to be provided in order to hash on a
particular type? std::map requires a less-than comparison operation --
what operations would a hash-based map need?

That would depend on your implementation of hash_map. I would suspect
some mechanism for generating a hash value from your key type, and I
suppose some sort of comparison on the hash value as well (and probably
you'd still need some sort of comparison function for your keys since they
may need to be compared in the event of hash collisions).

[David Harmon]

On Wed, 14 Apr 2004 20:54:05 GMT in comp.lang.c++, Kevin Goodsell
<us************ *********@never box.com> wrote,

Does anyone know what will need to be provided in order to hash on a
particular type? std::map requires a less-than comparison operation --
what operations would a hash-based map need?

Mainly, a hashing function that takes a argument of type Key
and returns an int.

http://std.dkuug.dk/jtc1/sc22/wg21/d...003/n1443.html

[Kevin Goodsell]

David Harmon wrote:

On Wed, 14 Apr 2004 20:54:05 GMT in comp.lang.c++, Kevin Goodsell
<us************ *********@never box.com> wrote,

Does anyone know what will need to be provided in order to hash on a
particular type? std::map requires a less-than comparison operation --
what operations would a hash-based map need?

Mainly, a hashing function that takes a argument of type Key
and returns an int.

http://std.dkuug.dk/jtc1/sc22/wg21/d...003/n1443.html

(Having only glanced over the link so far...)

I thought maybe they'd supply a hashing function that you can use, for
example if there's an operator<<(ostr eam &, const Key&). The string
representation could be generated with that and hashed. Since the
proposal includes a hash function for std::string, I suppose it would be
fairly easy to create this yourself.

I don't know how well this would work in practice, though. Obviously the
printed form of the Key would need to be unique.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[pembed2003]

"John Harrison" <jo************ *@hotmail.com> wrote in message news:<c5******* *****@ID-196037.news.uni-berlin.de>...

"pembed2003 " <pe********@yah oo.com> wrote in message
news:db******** *************** **@posting.goog le.com...

Hi All,
Does C++/STL have hashtable where I can do stuff like:

Hashtable h<int>;

h.store("one",1 );
h.store("two",2 );

and then later retrieve them like:

cout<<h.fetch(" one")<<endl;

prints 1

any idea?

Thanks!

It has a map which has the same functionality as above (but store is called
insert and fetch is called find). Map is usually based on a red-black tree
algorithm. Several library implementers also offer a genuine hash table
(called hash_map) and apparently some version of this will make it into a
future version of the standard.

john

Hi John,
Can you point me to the documentation where I can find the map and
hash_map data structure? Thanks for the help!

[Siemel Naran]

"pembed2003 " <pe********@yah oo.com> wrote in message

Can you point me to the documentation where I can find the map and
hash_map data structure? Thanks for the help!

It's not in the standard, but lots of compilers have it. Go to the include
folder like C:\Program Files\Borland\C Builder6\Includ e\Stlport and look for
a file like hash_map. Or try your compiler documentation or
http://www.sgi.com/tech/stl/HashedAs...Container.html.

[John Harrison]

>

Hi John,
Can you point me to the documentation where I can find the map and
hash_map data structure? Thanks for the help!

http://www.dinkumware.com/refxcpp.html

but remember because hasp_map is non standard the description here might
differ from the implementation you have (if you have one at all).

john