C++: hash_set, hash_map

Apesar dos templates para hash_set e hash_map não serem padronizados, ambos são relativamente comuns, estando disponíveis tanto na implementação GNU (ie, no GCC) quanto no Visual C++ no Windows. Existem algumas diferenças, como o namespace um pouco mais escondido no GNUC (__gnu_cxx vs stdext) e alguns métodos que existem em um mas não em outro (p.ex.: reverse_iterator que não existe no GCC); mas a maioria das vezes servem para o serviço.

Um problema comum com essas classes no GCC é um erro meio criptico quando tentamos usar __gnu_cxx::hash_set<std::string> ou __gnu_cxx::hash_map<std::string>:

/usr/include/c++/4.2/ext/hashtable.h:595: error: no match for call to '(const __gnu_cxx::hash<std::basic_string<char, std::char_traits, std::allocator > >) (const std::basic_string<char, std::char_traits, std::allocator >&)'


Este erro ocorre porque a libstdc++ não define uma função de hash para std::string. A solução é definir uma (O RLY?). Felizmente a biblioteca padrão define uma função de hash para strings do tipo char*, então podemos aproveitá-la:

struct string_hash : public std::unary_function<std::string,size_t>
{
  size_t operator() (const std::string &v) const
  {
    return __gnu_cxx::hash()(v.c_str());
  }
};
typedef __gnu_cxx::hash_set<std::string,string_hash> string_hash_set;