Hashtable em C ++?
-
02-07-2019 - |
Pergunta
I geralmente usar C ++ stdlib mapa sempre que preciso armazenar alguns dados associados com um tipo específico de valor (um valor de chave - e.g. uma corda ou outro objecto). A implementação mapa stdlib baseia-se em árvores que proporciona melhor desempenho (O (N log N)) do que a matriz ou stdlib vector padrão.
As minhas perguntas é, você sabe de qualquer C ++ implementação hashtable "padrão" que proporciona um desempenho ainda melhor (O (1))? Algo semelhante ao que está disponível na classe Hashtable da API Java.
Solução
Se você estiver usando C ++ 11, você tem acesso aos cabeçalhos <unordered_map>
e <unordered_set>
. Estes fornecem aulas std::unordered_map
e std::unordered_set
.
Se você estiver usando C ++ 03 com TR1, você tem acesso às classes std::tr1::unordered_map
e std::tr1::unordered_set
, usando os mesmos cabeçalhos (a menos que você está usando o GCC, caso em que os cabeçalhos são <tr1/unordered_map>
e <tr1/unordered_set>
vez).
Em todos os casos, não são correspondentes tipos unordered_multimap
e unordered_multiset
também.
Outras dicas
Se você já não tem unordered_map ou unordered_set, eles fazem parte da impulso .
Aqui está a documentação para tanto .
Há um hash_map objeto como muitos aqui têm mencionado, mas não faz parte do STL. É uma extensão SGI, por isso, se você estava procurando algo no STL, eu acho que você está fora de sorte.
std :: tr1 :: unordered_map, em <unordered_map>
Se você não tem tr1, obter impulso, eo uso
boost :: unordered_map em <boost/unordered_map.hpp>
Visual Studio tem a stdext::hash_map
classe no <hash_map>
cabeçalho e gcc tem a __gnu_cxx::hash_map
classe no mesmo cabeçalho.
std :: hash_map da SGI.
Este está incluído no href="http://www.stlport.com/doc/index.html" rel="nofollow noreferrer"> STLport distribuição também.
hash_map também é suportado no GNU é libstdc ++ .
Dinkumware também suportes isso, o que significa que muitas implementações terá um hash_map (acho que até Visual C ++ oferece com Dinkumware).
Se você tem as extensões TR1 disponíveis para yor compilador, usá-los. Se não, boost.org tem uma versão que é bastante semelhante, exceto para o std :: namespace. Nesse caso, coloque em um usando-declaração para que você possa mudar para std :: mais tarde.