Tuesday, October 28, 2008

C/C++ __gnu_cxx hash_map

I had some trouble getting this to work, so I decided to post a quick tutorial...

We start with a simple hash_map with int keys and string values:

#include <iostream>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

int main(int argc, char *argv[])
{
//declaration
hash_map<int, string> hmap;

//insertion
int ints[] = {213, 432, 45, 10};
string strings[] = {"s1", "s2", "s3", "s4"};

for(int i = 0; i < 4; i ++)
hmap[ints[i]] = strings[i];

//iteration
for(hash_map<int, string>::iterator it = hmap.begin(); it != hmap.end(); it ++)
cout << (*it).first << " => " << (*it).second << endl;

//deletion
hmap.erase(ints[0]);
cout << "Removed: " << ints[0] << endl;

//search
if(hmap.find(ints[0]) == hmap.end())
cout << "Couldn't find: " << ints[0] << endl;

if(hmap.find(ints[1]) != hmap.end())
cout << "Found: " << ints[1] << ": " << hmap[ints[1]] << endl;

return EXIT_SUCCESS;
}
It gets a little bit messy when using string keys. Since hash_map is not part of the standard STL, there're some issues you need to worry about. In our case, there's no implementation provided for hash, or in other words, the hash_map can't hash strings by default. Strangely though, hash is defined for char*, and we'll make use of that fact.

You can either specialize the hash template for std::string inside the __gnu_cxx namespace or define your own hash functor and use it in your hash_map declaration. Remember that hash_map is declared as hash_map<Key, Type, HashFcn, EqualKey, Alloc>. I prefer the second solution, you can check it out here. For now, we'll go on with the first one.
#include <iostream>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

namespace __gnu_cxx {
template<>
struct hash<std::string>
{
hash<char*> h;
size_t operator()(const std::string &s) const
{
return h(s.c_str());
};
};
}

typedef struct {
int x;
int y;
} point;

int main(int argc, char *argv[])
{
//declaration
hash_map<string, point> hmap;

//insertion
string strings[] = {"p1", "p2", "p3", "p4"};

point a, b, c, d;
a.x = a.y = 0;
b.x = b.y = 1;
c.x = c.y = 2;
d.x = d.y = 3;

hmap[strings[0]] = a;
hmap[strings[1]] = b;
hmap[strings[2]] = c;
hmap[strings[3]] = d;

//iteration
for(hash_map<string, point>::iterator it = hmap.begin(); it != hmap.end(); it ++)
cout << (*it).first << " => (" << (*it).second.x << ", " << (*it).second.y << ")" << endl;

//deletion
hmap.erase(strings[1]);
cout << "Removed: " << strings[1] << endl;

//search
if(hmap.find(strings[1]) == hmap.end())
cout << "Couldn't find: " << strings[1] << endl;

if(hmap.find(strings[0]) != hmap.end())
cout << "Found: " << strings[0] << ": (" << hmap[strings[0]].x << ", " << hmap[strings[0]].y << ")" << endl;

return EXIT_SUCCESS;
}

8 comments:

Jin Chen said...

very helpful! thank you!

John said...

Thanks very much.. I couldn't figure out why hash_map wasn't working on my ubuntu installation!

Anonymous said...

I can't see the link to the first solution -define and use a hash function for the hash map-, could you please post the link? -thanks

Ahmed Abdelkader said...

Done. You're welcome!

Daniel Kats said...

Are there any portability issues?

Ahmed Abdelkader said...

Check this: http://codepad.org/2H3ajE06 (g++ 4.1.2). You should also find this useful: http://gcc.gnu.org/gcc-4.3/changes.html.

Anonymous said...

Thanks! This was a great help!

Anonymous said...

Thanks for sharing. Good work.