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;
}