"Multiset" e "MultiMap" - qual é o ponto?

Question

Como afirma a pergunta ... eu não entendo multisets / multimaps.

Então, qual é o propósito?

Answer 1

Alguns casos de uso:

MultiMap

• Com o código postal como uma chave, todas as pessoas que têm esse código postal
• Com o ID da conta como chave, todas as ordens abertas dessa pessoa/conta
• Um dicionário, com palavra -chave várias explicações

Multiset

é em essência um mapa com uma chave e uma contagem inteira.

• O inventário de uma loja, todos os produtos têm sua chave e a quantidade ainda disponível é o valor
• Dados de vendas acumulados de uma loja, toda vez que um produto é vendido, a identificação do produto é adicionada ao multiset, aumentando assim a quantidade vendida

Answer 2

Um exemplo em que um multimap seria útil se você tivesse uma situação em que na maioria das vezes as chaves são únicas, mas às vezes não são.

Por exemplo, se você estivesse criando uma classe de cache que usava um hash como chave. Na maioria das vezes, dois objetos diferentes não terão o mesmo hash, então as chaves serão únicas. Mas é possível que você obtenha colisões de hash para diferentes objetos, então desejará que um multimap cubra essa situação.

Outro exemplo seria qualquer tipo de índice não único (como em um banco de dados).

Quanto a um multiset - acho que isso seria menos útil. A única coisa que posso pensar seria usá -lo como uma espécie de lista automaticamente classificada.

Answer 3

Um multiset ou multimap é simplesmente para situações em que pode haver mais de um de um item específico. Por exemplo, digamos que você queria criar um índice para um livro. Você examinaria o texto, jogava fora todas as palavras sem sentido realmente comuns ("a", "an", "the" etc.) e depois fazia uma lista de todo o resto e o lugar do livro onde cada um ocorreu.

Algumas das palavras aparecerão em mais de uma página; nesse caso, você terá várias entradas mapeando de uma palavra para páginas diferentes. Uma maneira de lidar com isso seria um multimap de palavras para números de página.

Answer 4

http://www.cplusplus.com/reference/stl/multimap/

Os mapas são um tipo de contêineres associativos que armazena elementos formados pela combinação de um valor de chave e um valor mapeado, assim como os contêineres de mapa, mas permitindo que elementos diferentes tenham o mesmo valor de chave.

É uma espécie de registro em que os elementos podem compartilhar uma chave. Você pode pensar em empresas e funcionários. O endereço da rua é uma chave e os funcionários são valores.

Answer 5

Aqui está o quê Wikipedia diz sobre usos:

• Em um sistema de matrícula de estudantes, onde os alunos podem ser matriculados em várias aulas simultaneamente, pode haver uma associação para cada matrícula de um aluno em um curso, onde a chave é a identificação do aluno e o valor é o ID do curso. Se um aluno estiver matriculado em três cursos, haverá três associações contendo a mesma chave.
• O índice de um livro pode relatar qualquer número de referências para um determinado termo de índice e, portanto, pode ser codificado como um multimap de termos de índice para qualquer número de locais de referência

Answer 6

Use MultiMap, onde quer que você queira usar uma estrutura de árvore.

Answer 7

O benefício mais importante do uso de um multiset em um vetor/lista (ou qualquer outro contêiner) é a complexidade do tempo da operação de localização. A complexidade média do tempo do caso para multiset é O (logn) e não -ordered_multiset é O (1). O mesmo vale para MultiMap e Ordered_multImap.