Hashtable em C ++?
https://stackoverflow.com/questions/133569
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
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.
