Não entendo std::tr1::unordered_map

Question

Preciso de um container associativo que me faça indexar um determinado objeto através de uma string, mas que também mantenha a ordem de inserção, para que eu possa procurar um objeto específico pelo seu nome ou apenas iterar sobre ele e recuperar os objetos na mesma ordem que inseri eles.

eu acho isto híbrido de lista vinculada e mapa hash deveria fazer o trabalho, mas antes de tentar usar std::tr1::unordered_map pensando que estava funcionando da maneira que descrevi, mas não estava.Alguém poderia me explicar o significado e o comportamento de unordered_map?

---

@wesc:Tenho certeza de que std::map é implementado por STL, enquanto tenho certeza de que std::hash_map NÃO está no STL (acho que a versão mais antiga do Visual Studio o colocou em um namespace chamado stdext).

@cristal:então, se entendi direito, a diferença está na implementação (e, portanto, no desempenho), não na maneira como ela se comporta externamente.

Answer 1

Aumente a documentação de contêineres não solicitados

A diferença está no método como você gera a pesquisa.

Nos contêineres de mapa/conjunto, o operator< é usado para gerar uma árvore ordenada.

Nos contêineres não ordenados, um operator( key ) => index é usado.

Veja hashing para uma descrição de como isso funciona.

Answer 2

Você perguntou a razão canônica pela qual Boost::MultiIndex foi criado:ordem de inserção de lista com pesquisa rápida por chave. Tutorial Boost MultiIndex:lista de pesquisa rápida

Answer 3

Você precisa indexar um contêiner associativo de duas maneiras:

• Pedido de inserção
• Comparação de strings

Tentar Boost.MultiIndex ou Boost.Intrusivo.Não usei dessa forma, mas acho que é possível.

Answer 4

Desculpe, li seu último comentário errado.Sim, hash_map não está em STL, map está.Mas unordered_map e hash_map são iguais pelo que tenho lido.

mapa -> log (n) inserção, recuperação, iteração é eficiente (e ordenada por comparação de chave)

hash_map/unordered_map -> inserção e recuperação em tempo constante, o tempo de iteração não é garantido para ser eficiente

Nenhum deles funcionará sozinho, pois o mapa ordena as coisas com base no conteúdo da chave, e não na sequência de inserção (a menos que sua chave contenha informações sobre a sequência de inserção).

Você terá que fazer o que descreveu (lista + hash_map) ou criar um tipo de chave que tenha o número de sequência de inserção mais uma função de comparação apropriada.

Answer 5

EU pensar que unordered_map e hash_map são mais ou menos a mesma coisa.A diferença é que o STL não possui oficialmente um hash_map (o que você está usando provavelmente é algo específico do compilador), então unordered_map é a correção para essa omissão.

unordered_map é apenas isso ...não ordenado.Você não pode depender disso preservando qualquer ordem na iteração.

Answer 6

Você tem certeza de que std::hash_map existe em todos Implementações STL?SGI STL o implementa, porém o GNU g++ não o possui (está localizado no namespace __gnu_cxx) a partir de 4.3.1 de qualquer maneira.Pelo que eu sei, hash_map sempre foi fora do padrão e agora tr1 está corrigindo isso.

Answer 7

@wesc:STL tem std::map...então qual é a diferença com unordered_map?Não acho que o STL implementaria duas vezes a mesma coisa e a chamaria de forma diferente.