Boost.Intrusive e unordered_map

Question

Eu estou olhando para usar um unordered_map intrusiva. Por alguma razão há apenas um unordered_set na biblioteca. Há também uma hashtable intruso, mas eu não tenho certeza que ele tem o mesmo functunality, também ele não tem a mesma interface.
Estou errado e eu perdi o link unordered_map
Se eu não estou há um tutorial que vai me ajudar a implementar um?

Answer 1

É uma pergunta interessante. não Boost.Intrusive não parecem fornecer qualquer interface do mapa, ordenada ou desordenada. Tem um monte de tipos de implementação que irá funcionar bem como mapas ambos (árvores rubro-negro, árvores AVL, árvores splay) ordenados e não ordenados (hashtables). Mas há mapas e eu não poderia dizer-lhe porquê.

Você tem duas opções a meu ver:

1. Apenas uso hashtable: os recipientes não ordenadas são implementados como hashtables (ea única razão pela qual eles não são chamado hash_map é evitar colisões de nomes com bibliotecas pré-existentes usando esse nome já). Isso vai funcionar se você quiser fazer o seu trabalho.
2. Se você realmente deseja implementar seu próprio país, você quer tomar uma olhada na descrição da interface para o Boost.Intrusive unordered_set . Eu não olhei para a implementação, mas é quase certamente um invólucro em torno de um ou mais dos tipos de árvores. std::set e std::map ambos são tipicamente implementado como wrappers em torno de uma árvore de vermelho-preto (em todas as implementações de biblioteca padrão eu olhei: GCC de, MSVC de e stdcxx do Apache). Também levar em como libstdc ++ envolve sua implementação árvore em <map> e em <set>. É um monte de clichê, muito do que tedioso, mas ambos os tipos adiar quase todo o trabalho para a árvore. Algo análogo é quase certamente acontecendo com unordered_set de Boost.Intrusive. Você vai precisar de olhar para as diferenças entre o mapa e as interfaces do jogo, e usar isso como base para modificar unordered_set em unordered_map.

Eu fiz o último. É um pouco sobre o lado tedioso, e eu altamente recomendo escrever testes de unidade para ele (ou roubar os que vêm com libstdc ++ ou Boost.Intrusive). Mas é factível. Eu também recomendo a leitura dos documentos de requisitos para conjuntos e mapas, quer no SGI ( set , mapear ) ou para libstdc ++

Update: eu percebi porque eles não estão fazendo mapas: os recipientes intrusivas exigem que você incorporar as informações nó para a estrutura de dados do tipo de valor que você está armazenando nele. Para mapas, você teria que fazer isso para ambos os valores e as teclas . Não é que isso não é possível, mas a implementação padrão para um map usa o mesma tipo interno como os sets fazer. Mas esses tipos internos só têm um variável value_type: para armazenar chaves e valores que copiar a chave e o valor para essa variável e loja que nos gânglios. Para fazer isso com um tipo de intrusiva (ou seja, sem copiar) você teria que modificar esse tipo de implementação para ser incompatível com conjuntos: tem que armazenar referências para as chaves e valores separadamente . Então, para fazer isso você também tem que modificar a implementação você usa (provavelmente hashtable). Novamente não impossível, mas os designers da biblioteca são provavelmente tentando evitar a duplicação de código sério assim, na ausência de maneira simples de implementar isso, eles provavelmente decidiu deixar mapeia.

Isso faz sentido?

Answer 2

Tem sido um longo tempo desde que esta pergunta foi feita, mas eu acho que as pessoas que vêm aqui deve estar interessado em como usar um unordered_set como um mapa. A solução é para usar inserções avançados métodos : uma apenas tem de armazenar uma chave e seu valor no mesmo value_type, e inseri-lo usando insert_check e insert_commit .