Em que cenário eu uso um contêiner STL específico?

Estive lendo sobre contêineres STL em meu livro sobre C ++, especificamente a seção sobre o STL e seus contêineres. Agora eu entendo que cada um deles tem suas próprias propriedades específicas e estou quase memorizando todas elas ... Mas o que ainda não entendo é em que cenário cada uma delas é usada.

Qual a explicação? Código de exemplo é muito preferido.

Esta folha de dicas fornece um resumo muito bom dos diferentes contêineres.

Veja o fluxograma na parte inferior como um guia sobre o qual usar em diferentes cenários de uso:

_{Criado por David Moore e licenciado CC BY-SA 3.0}

Aqui está um fluxograma inspirado na versão de David Moore (veja acima) que eu criei, que está atualizada (principalmente) com o novo padrão (C ++ 11). Esta é apenas minha opinião pessoal, não é indiscutível, mas achei que poderia ser valioso para esta discussão:

Resposta simples: use std::vectorpara tudo, a menos que você tenha um motivo real para fazer o contrário.

Quando você encontrar um caso em que está pensando "Nossa, std::vectornão funciona bem aqui por causa do X", vá com base no X.

Veja o STL eficaz de Scott Meyers. É bom em explicar como usar o STL.

Se você deseja armazenar um número determinado / indeterminado de objetos e nunca excluir nenhum, então um vetor é o que você deseja. É a substituição padrão para uma matriz C e funciona como uma, mas não transborda. Você pode definir seu tamanho antecipadamente e também com reserve ().

Se você deseja armazenar um número indeterminado de objetos, mas irá adicioná-los e excluí-los, provavelmente deseja uma lista ... porque é possível excluir um elemento sem mover nenhum dos seguintes elementos - diferente do vetor. Porém, é preciso mais memória que um vetor e você não pode acessar sequencialmente um elemento.

Se você quiser pegar vários elementos e encontrar apenas os valores exclusivos desses elementos, a leitura de todos eles em um conjunto fará isso e os classificará para você também.

Se você possui muitos pares de valores-chave e deseja classificá-los por chave, um mapa é útil ... mas ele contém apenas um valor por chave. Se você precisar de mais de um valor por chave, poderá ter um vetor / lista como seu valor no mapa ou usar um multimap.

Não está no STL, mas está na atualização TR1 para o STL: se você tiver muitos pares de valores-chave, procurará por chave e não se importará com a ordem deles. deseja usar um hash - que é tr1 :: unordered_map. Eu usei com o Visual C ++ 7.1, onde foi chamado stdext :: hash_map. Ele tem uma pesquisa de O (1) em vez de uma pesquisa de O (log n) para o mapa.

Redesenhei o fluxograma para ter 3 propriedades:

1. Acho que os contêineres da STL são divididos em duas classes principais. Os contêineres básicos e esses aproveitam os contêineres básicos para implementar uma política.
2. No início, o fluxograma deve dividir o processo de decisão para as principais situações em que devemos decidir e, em seguida, elaborar cada caso.
3. Alguns contêineres estendidos têm a possibilidade de escolher diferentes contêineres básicos como contêineres internos. O fluxograma deve considerar as situações em que cada um dos contêineres básicos pode ser usado.

O fluxograma:

Mais informações fornecidas neste link .

Um ponto importante apenas brevemente mencionado até agora, é que se você precisar de memória contígua (como uma matriz C dá), então você só pode usar vector, arrayou string.

Use arrayse o tamanho for conhecido no momento da compilação.

Use stringse você precisar trabalhar apenas com tipos de caracteres e precisar de uma sequência, não apenas de um contêiner de uso geral.

Use vectorem todos os outros casos (vector na maioria dos casos, deve ser a escolha padrão do contêiner).

Com os três itens, você pode usar a data()função de membro para obter um ponteiro para o primeiro elemento do contêiner.

Tudo depende do que você deseja armazenar e do que deseja fazer com o contêiner. Aqui estão alguns exemplos (não exaustivos) para as classes de contêiner que eu mais uso:

vector: Layout compacto com pouca ou nenhuma sobrecarga de memória por objeto contido. Eficiente para iterar. Anexar, inserir e apagar pode ser caro, principalmente para objetos complexos. Barato para encontrar um objeto contido por índice, por exemplo, myVector [10]. Use onde você teria usado uma matriz em C. Bom, onde você tem muitos objetos simples (por exemplo, int). Não se esqueça de usar reserve()antes de adicionar muitos objetos ao contêiner.

list: Sobrecarga de memória pequena por objeto contido. Eficiente para iterar. Anexar, inserir e apagar são baratos. Use onde você teria usado uma lista vinculada em C.

set(e multiset): sobrecarga significativa de memória por objeto contido. Use onde for necessário descobrir rapidamente se esse contêiner contém um determinado objeto ou mesclar contêineres com eficiência.

map (e multimap ): sobrecarga significativa de memória por objeto contido. Use onde deseja armazenar pares de valores-chave e procure valores por chave rapidamente.

O fluxograma na folha de dicas sugerido por zdan fornece um guia mais completo.

Uma lição que aprendi é: tente envolvê-lo em uma classe, pois alterar o tipo de contêiner em um belo dia pode render grandes surpresas.

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

Não custa muito adiantado e economiza tempo na depuração quando você deseja interromper sempre que alguém faz a operação x nessa estrutura.

Chegando à seleção da estrutura de dados perfeita para um trabalho:

Cada estrutura de dados fornece algumas operações, que podem variar a complexidade do tempo:

O (1), O (lg N), O (N), etc.

Você precisa essencialmente adivinhar quais são as operações mais executadas e usar uma estrutura de dados que possua essa operação como O (1).

Simples, não é (-:

I expandiu de Mikael Persson fluxograma fantástico. Adicionei algumas categorias de contêineres, o contêiner de matriz e algumas notas. Se você quiser uma cópia sua, aqui está o desenho do Google. Obrigado, Mikael, por fazer as bases! Selecionador de Contêiner C ++

Eu respondi isso em outra pergunta que está marcada como dup desta. Mas acho bom consultar alguns bons artigos sobre a decisão de escolher um contêiner padrão.

Como @David Thornley respondeu, std :: vector é o caminho a percorrer se não houver outras necessidades especiais. Este é o conselho dado pelo criador do C ++, Bjarne Stroustrup em um blog de 2014.

Aqui está o link para o artigo https://isocpp.org/blog/2014/06/stroustrup-lists

e citar esse,

E, sim, minha recomendação é usar std :: vector por padrão.

Nos comentários, o usuário @NathanOliver também fornece outro bom blog, que possui medidas mais concretas. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html .