Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Hash table in C++? STL?

Reply
Thread Tools

Hash table in C++? STL?

 
 
pembed2003
Guest
Posts: n/a
 
      04-14-2004
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!
 
Reply With Quote
 
 
 
 
John Harrison
Guest
Posts: n/a
 
      04-14-2004

"pembed2003" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m...
> 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


 
Reply With Quote
 
 
 
 
Kevin Goodsell
Guest
Posts: n/a
 
      04-14-2004
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.
 
Reply With Quote
 
Andre Kostur
Guest
Posts: n/a
 
      04-14-2004
Kevin Goodsell <(E-Mail Removed)> wrote in
news:Nxhfc.9574$(E-Mail Removed) ink.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).
 
Reply With Quote
 
Claudio Puviani
Guest
Posts: n/a
 
      04-14-2004
"Kevin Goodsell" <(E-Mail Removed)> 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


 
Reply With Quote
 
David Harmon
Guest
Posts: n/a
 
      04-14-2004
On Wed, 14 Apr 2004 20:54:05 GMT in comp.lang.c++, Kevin Goodsell
<(E-Mail Removed)> 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

 
Reply With Quote
 
Kevin Goodsell
Guest
Posts: n/a
 
      04-14-2004
David Harmon wrote:

> On Wed, 14 Apr 2004 20:54:05 GMT in comp.lang.c++, Kevin Goodsell
> <(E-Mail Removed)> 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<<(ostream &, 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.
 
Reply With Quote
 
pembed2003
Guest
Posts: n/a
 
      04-15-2004
"John Harrison" <(E-Mail Removed)> wrote in message news:<c5k82i$2nhvo$(E-Mail Removed)-berlin.de>...
> "pembed2003" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) m...
> > 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!
 
Reply With Quote
 
Siemel Naran
Guest
Posts: n/a
 
      04-15-2004
"pembed2003" <(E-Mail Removed)> 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\CBuilder6\Include\Stlport and look for
a file like hash_map. Or try your compiler documentation or
http://www.sgi.com/tech/stl/HashedAs...Container.html.


 
Reply With Quote
 
John Harrison
Guest
Posts: n/a
 
      04-15-2004
>
> 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
Hash#select returns an array but Hash#reject returns a hash... Srijayanth Sridhar Ruby 19 07-02-2008 12:49 PM
Table/table rows/table data tag question? Rio HTML 4 11-05-2004 08:11 AM
standard library for hash table storage and hash algorithm Pieter Claassen C Programming 1 08-04-2004 03:11 AM
Could not load type VTFixup Table from assembly Invalid token in v-table fix-up table. David Williams ASP .Net 2 08-12-2003 07:55 AM



Advertisments