hash_map is not part of the current C++ STL, but is universally adopted as an extension. Using hash_map is simple when using built-in primitives like int or char*. Attempting to use user-defined classes as a key is somewhat more difficult, as the following example demonstrates:
class example1 {
public:
example1() {};
~example1() {};
uint8_t name_[8];
};
typedef __gnu_cxx::hash_map<example1,int> Example1HashType;
Example1HashType hash_map1;
int main(int argc, char **argv) {
example1 e1;
hash_map1.insert(std::make_pair(e1, 1));
}
When compiled with gcc 4.2 this results in:
/usr/include/c++/4.2/bits/stl_function.h:200: error: no match for ‘operator==’ in ‘__x == __y’
/usr/include/c++/4.2/ext/hashtable.h:595: error: no match for call to ‘(const __gnu_cxx::hash<example1>) (const example1&)’
hash_map requires two things: a hash function, and an ability to compare equality. To use a class as a key you need to provide a hash<> template specialized for the class in question. You also need to implement an equality operator.
class example1 {
public:
example1() {};
~example1() {};
bool operator==(const example1 &other) const {
return (memcmp(name_, other.name_, sizeof(name_)) == 0);
};
uint8_t name_[8];
};
namespace __gnu_cxx {
template<> struct hash<example1> {
size_t operator()(const example1& k) const {
size_t hashval = 0;
for (int i = 0; i < sizeof(k.name_); ++i) {
hashval = 5 * hashval + k.name_[i];
}
return hashval;
}
};
} // namespace __gnu_cxx
typedef __gnu_cxx::hash_map<example1,int> Example1HashType;
int main(int argc, char **argv) {
example1 e1;
Example1HashType hash_map1;
hash_map1.insert(std::make_pair(e1, 1));
}
This works, but what if we cannot add an operator method? For example, perhaps the class is in a library which we cannot modify, or is created by a code generator. Consider this case where key is a simple struct with no member functions. This code fails to compile, due to lack of "__x == __y"
struct example2 {
uint8_t name_[8];
};
namespace __gnu_cxx {
template<> struct hash<example2> {
size_t operator()(const example2& k) const {
size_t hashval = 0;
for (int i = 0; i < sizeof(k.name_); ++i) {
hashval = 5 * hashval + k.name_[i];
}
return hashval;
}
};
} // namespace __gnu_cxx
typedef __gnu_cxx::hash_map<example2,int> Example2HashType;
Example2HashType hash_map2;
int main(int argc, char **argv) {
example2 e2;
hash_map2.insert(std::make_pair(e2, 1));
}
As this is C++, the solution will of course involve more templates. hash_map does not directly invoke "x == y," it uses an equal_to<> template. The "__x == __y" compiler error is from the template. We can provide an equal_to<> specialization instead.
struct example2 {
uint8_t name_[8];
};
namespace std {
template<> struct equal_to<example2> {
bool operator()(const example2& x, const example2& y) const {
return (memcmp(x.name_, y.name_, sizeof(x.name_)) == 0);
}
};
} // namespace std
namespace __gnu_cxx {
template<> struct hash<example2> {
size_t operator()(const example2& k) const {
size_t hashval = 0;
for (int i = 0; i < sizeof(k.name_); ++i) {
hashval = 5 * hashval + k.name_[i];
}
return hashval;
}
};
} // namespace __gnu_cxx
typedef __gnu_cxx::hash_map<example2,int> Example2HashType;
Example2HashType hash_map2;
int main(int argc, char **argv) {
example2 e2;
hash_map2.insert(std::make_pair(e2, 1));
}
Extending hash_map to custom key types makes it useful in far more situations.
Electronics distribution giant 