This is not really a question, but a tip for others who may possibly search the forum for this particular issue:
The problem:
This code works:
Code:
#include <iostream>
#include <hash_map>
using namespace std;
hash_map <const char *, int> months;
int main(void) {
months["january"] = 31;
months["february"] = 28;
return 0;
}
However, this code doesn't compile:
Code:
#include <iostream>
#include <string>
#include <hash_map>
using namespace std;
hash_map <string, int> months;
int main(void) {
months["january"] = 31;
months["february"] = 28;
return 0;
}
Note that the only difference between the two codes is that one uses const char * and the other uses string for the hash key type. So why does the second instance not compile?
Background: What is a hash_map?
The STL library provides a template type called
map which allows a C++ programmer to create an associative array (i.e). array[key] = value;
However, a map template automatically orders its elements as they're inserted, therefore lookups are a little slower. A
hash_map is a template type that allows a programmer to quickly look up a value. The hash_map template uses a hashing algorithm to store values that are inserted into it, hence the elements are NOT sorted. This is OK, if you just want to do quick in-memory lookups, but don't care about the data being sorted. The map type is part of the STL, but hash_map was introduced by SGI and is present in
only some implementations of the STL (M$ VC++ 6.0 and .NET do not have it in their default installation). However, two of the well known implementations from SGI (
http://www.sgi.com/tech/stl/index.html) and stlport (
http://www.stlport.org/) do and can be used as drop in replacements, if your compiler does not support hash maps. See
http://www.sgi.com/tech/stl/table_of_contents.html for documentation and sample code using hash_map
.
The reason it doesn't compile:
Since hash_map is not part of the standard STL, there are certain other parts of the STL that it doesn't work with (notably the string template, which is pretty much standard across all STL implementations). You need to supply some extra code yourself, for the hash function to work correctly with other parts of the STL, which are standard across all implementations.
The solution:
Add the following chunk of code between the BEGIN FIX and END FIX comments:
Code:
#include <iostream>
#include <string>
#include <hash_map>
using namespace std;
/** BEGIN FIX **/
namespace std
{
template<> struct hash< std::string >
{
size_t operator()( const std::string& x ) const
{
return hash< const char* >()( x.c_str() );
}
};
}
/** END FIX **/
hash_map <string, int> months;
int main(void) {
months["january"] = 31;
months["february"] = 28;
return 0;
}
I tested this code on the following OS/compiler environments:
Red Hat Linux 7.1: gcc version 2.96 20000731 (Red Hat Linux 7.1 2.96-81)
FreeBSD 4.7-RELEASE-p7:gcc version 2.95.4 20020320 [FreeBSD]
OpenBSD 3.3-CURRENT:gcc version 2.95.3 20010125 (prerelease, propolice)
[edit] Note that I was using the STL implementations that came by default with the distros and they all supported hash_map
[/edit]
Hope this helps!
Dev Shed Forums Sponsor:
March 12th, 2003, 02:14 PM
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
