Using Gcc C++ Hash Classes With Strings

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

MLRUS

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();
}
};
David

Hi! I’ve been looking for a long time how to add hash support to my old gcc version! Now I am facing a new problem : how can I add hash support ? Thanks in advance!
David

mmm… something strange happend when I wrote my comment… My question is about hash functions for unsigned long long int type!

Using Gcc C++ Hash Classes With Strings

Tags

Meta