Oct
30
2008

<Using Gcc C++ Hash Classes With Strings>

<code>

So even though hash_map and hash_set aren’t a part of the C++ standard, there are still implementations included with the gcc compiler. You have to include or and a little magic to get them to work properly with std::string keys.

// Example code using a hash_set with std::string keys on gcc
// Example based on hash_set code from "6.7 Using Hashed Containers"
// in O'Reilly C++ Cookbook by Stephens, Diggins, Turkanis & Cogswell  (2006)
// and gcc fix from post http://gcc.gnu.org/ml/libstdc++/2002-04/msg00107.html
// Tested with g++ 4.1.2
// Compile with:
// g++ -o hash hash.cpp
// Kristi Tsukida <kristi.tsukida at gmail dot com> 30-10-2008
 
#include <iostream>
#include <string>
#include <ext/hash_set>
 
using namespace std;
// The __gnu_cxx namespace contains the hash_set since it's not standard c++
using namespace __gnu_cxx;
 
// This is the magic that will allow the usage of string keys in the hash
namespace __gnu_cxx
{
        template<> struct hash< std::string >
        {
                size_t operator()( const std::string& x ) const
                {
                        return hash< const char* >()( x.c_str() );
                }
        };
}
 
// must specify the hash<string> hash function
typedef hash_set<string, hash<string> > string_hash_set;
 
int main()
{
	string_hash_set hs;
 
	string s = "bravo";
	hs.insert(s);
	s = "alpha";
	hs.insert(s);
	s = "charlie";
	hs.insert(s);
 
	for(string_hash_set::const_iterator p = hs.begin(); p!= hs.end(); ++p)
	{
		cout << *p << endl;
	}
 
}

This entry was posted on Thursday, October 30th, 2008 at 6:54 pm.
Tags = c++, example, gcc, hash, hash table, hash_map, hash_set, std, string, __gnu_cxx
RSS 2.0 feed  |  Trackback  |  Leave a response

One Response to “Using Gcc C++ Hash Classes With Strings”

1. August 16th, 2009 at 8:04 pm MLRUS Says:
   

   Thank you for this example. I have a more complex template usage, and your example showed me that I simply have to dereference the iterator to get the results back. I suppose I should add a typedef to make things readable, since now I have the following “easy to read” code:

   for( __gnu_cxx::_Hashtable_const_iterator<const char*, const char*, __gnu_cxx::hash,
   std::_Identity, Dictionary::eqstr, std::allocator >
   xit = dictionary.words.begin(); xit != dictionary.words.end(); xit++) {
   cout << *xit << endl;
   }

   class Dictionary: public Storable {
   struct eqstr
   {
   bool operator()(const char* s1, const char* s2) const
   {
   return strcmp(s1, s2) == 0;
   }
   };

   __gnu_cxx::hash_set<const char*,__gnu_cxx:: hash, eqstr> words;

   inline const bool lookup(const __gnu_cxx::hash_set<const char*, __gnu_cxx::hash, eqstr>& words,
   const char* word)
   {
   __gnu_cxx::hash_set<const char*, __gnu_cxx::hash, eqstr>::const_iterator it = words.find(word);
   return it!=words.end();
   }

   inline const bool lookup(const string& word) {
   return lookup(words,word.c_str());
   }

   inline const bool lookup(const char *word) {
   return lookup(words,word);
   }

   public:

   inline const bool contains(const string &entry) {
   return lookup(entry);
   }

   inline const bool contains(const char *entry) {
   return lookup(entry);
   }

   void clear() {
   words.clear();
   }

   inline int wordCount() {
   return words.size();
   }

   void read(const std::string &filename) {
   try {
   ifstream infile(filename.c_str(), std::ios_base::in);
   string line;
   while (getline(infile, line, ‘\n’)) {
   Util::trim(line);
   Util::upperCase(line);
   words.insert(strdup(line.c_str()));
   }
   infile.close();
   } catch (…) {
   cerr << “Error reading ” << filename << endl;
   }
   }

   Dictionary() :
   words() {

   }
   Dictionary(string &filename) :
   words() {
   read(filename);
   }

   virtual ~Dictionary() {
   words.clear();
   }
   };

Leave a Reply