vetor vs. lista em STL

Notei no Efetivo STL que

vector é o tipo de sequência que deve ser usado por padrão.

O que isso significa? Parece que ignorar o vector eficiência pode fazer qualquer coisa.

Alguém poderia me oferecer um cenário em que o vector não é uma opção viável, mas a list deve ser usada?

Situações em que você deseja inserir muitos itens em qualquer lugar, exceto no final de uma sequência repetidamente.

Confira as garantias de complexidade para cada tipo diferente de contêiner:

Quais são as garantias de complexidade dos contêineres padrão?

vetor:

  • Memória contígua.
  • Pré-aloca espaço para elementos futuros, portanto, é necessário espaço extra além do necessário para os próprios elementos.
  • Cada elemento requer apenas o espaço para o tipo de elemento em si (sem pointers extras).
  • Pode realocar memory para todo o vetor sempre que você adicionar um elemento.
  • Inserções no final são constantes, tempo amortizado, mas inserções em outros lugares são onerosas O (n).
  • Erasures no final do vetor são constantes, mas para o resto é O (n).
  • Você pode acessar aleatoriamente seus elementos.
  • Iteradores são invalidados se você adicionar ou remover elementos de ou para o vetor.
  • Você pode obter facilmente o array subjacente se precisar de uma matriz dos elementos.

Lista:

  • Memória não contígua.
  • Nenhuma memory pré-alocada. O overhead de memory para a lista em si é constante.
  • Cada elemento requer espaço extra para o nó que contém o elemento, incluindo pointers para os elementos seguinte e anterior na lista.
  • Nunca tem que realocar a memory para toda a lista só porque você adiciona um elemento.
  • Inserções e rasuras são baratas, não importa em que lugar da lista elas ocorram.
  • É barato combinar listas com splicing.
  • Você não pode acessar aleatoriamente elementos, portanto, obter um elemento específico na lista pode ser caro.
  • Iteradores permanecem válidos mesmo quando você adiciona ou remove elementos da lista.
  • Se você precisar de uma matriz dos elementos, terá que criar um novo e adicioná-los todos a ele, já que não há um array subjacente.

Em geral, use vetor quando você não se importa com o tipo de contêiner sequencial que está usando, mas se estiver fazendo muitas inserções ou rasuras de qualquer lugar no contêiner que não seja o final, você vai querer para usar a lista. Ou se você precisar de access random, então você vai querer vetor, não lista. Fora isso, existem naturalmente casos em que você vai precisar de um ou outro com base em sua aplicação, mas em geral, essas são boas diretrizes.

Se você não precisa inserir elementos com freqüência, um vetor será mais eficiente. Tem localidade de cache da CPU muito melhor que uma lista. Em outras palavras, o access a um elemento torna muito provável que o próximo elemento esteja presente no cache e possa ser recuperado sem precisar ler a RAM lenta.

A maioria das respostas aqui erra um detalhe importante: para quê?

O que você quer manter no contêiner?

Se for uma coleção de int s, então std::list perderá em todos os cenários, independentemente de você poder realocar, remover apenas da frente, etc. As listas são mais lentas, todas as inserções custam uma interação com o alocador … Seria extremamente difícil preparar um exemplo, onde a list bate o vector . E, mesmo assim, o deque pode ser melhor ou mais próximo, não apenas o uso de listas, que terão maior sobrecarga de memory.

No entanto, se você está lidando com grandes e feias gotas de dados – e poucos deles – você não quer sobrecarregar ao inserir, e copiar devido a realocação seria um desastre – então você pode, talvez, estar melhor com uma list que o vector .

Ainda assim, se você mudar para o vector ou mesmo para o vector > , novamente – a lista ficará para trás.

Assim, o padrão de access, a contagem de elementos de destino, etc. ainda afetam a comparação, mas, a meu ver, o tamanho dos elementos – custo de cópia, etc.

Um recurso especial do std :: list é o splicing (vincular ou mover parte de uma lista inteira para outra lista).

Ou talvez se o seu conteúdo é muito caro para copiar. Nesse caso, pode ser mais barato, por exemplo, classificar a coleção com uma lista.

Observe também que, se a coleção for pequena (e o conteúdo não for particularmente caro para copiar), um vetor ainda poderá superar uma lista, mesmo se você inserir e apagar em qualquer lugar. Uma lista aloca cada nó individualmente, e isso pode ser muito mais caro do que mover alguns objects simples ao redor.

Eu não acho que há regras muito difíceis. Depende do que você mais deseja fazer com o contêiner, bem como de quão grande você espera que o contêiner seja e o tipo contido. Um vetor geralmente supera uma lista, porque aloca seu conteúdo como um único bloco contíguo (é basicamente uma matriz alocada dinamicamente e, na maioria das vezes, uma matriz é a maneira mais eficiente de manter um monte de coisas).

Bem, os alunos da minha turma parecem incapazes de me explicar quando é mais eficaz usar vetores, mas parecem muito felizes quando me aconselham a usar listas.

É assim que entendo

Listas : Cada item contém um endereço para o elemento seguinte ou anterior, portanto, com esse recurso, você pode randomizar os itens, mesmo que eles não estejam classificados, a ordem não será alterada: é eficiente se a memory estiver fragmentada. Mas também tem outra vantagem muito grande: você pode facilmente inserir / remover itens, porque a única coisa que você precisa fazer é mudar alguns pointers. Desvantagem: Para ler um item único random, você tem que pular de um item para outro até encontrar o endereço correto.

Vetores : Ao usar vetores, a memory é muito mais organizada como matrizes regulares: cada n-ésimo item é armazenado logo após (n-1) item e antes (n + 1) item. Por que é melhor que a lista? Porque permite access random rápido. Aqui está como: se você conhece o tamanho de um item em um vetor, e se eles são contíguos na memory, você pode prever facilmente onde está o n-ésimo item; você não precisa procurar todos os itens de uma lista para ler o que você quer, com vetor, você lê diretamente, com uma lista que você não pode. Por outro lado, modifique o vetor array ou altere um valor muito mais lento.

As listas são mais apropriadas para rastrear objects que podem ser adicionados / removidos na memory. Os vetores são mais apropriados quando você deseja acessar um elemento de uma grande quantidade de itens únicos.

Eu não sei como as listas são otimizadas, mas você tem que saber que se você quiser access rápido de leitura, você deve usar vetores, porque o quão bom o STL aperta listas, ele não será tão rápido no access de leitura quanto no vetor.

Toda vez que você não pode ter iteradores invalidados.

Basicamente, um vetor é um array com gerenciamento automático de memory. Os dados são contíguos na memory. Tentar inserir dados no meio é uma operação dispendiosa.

Em uma lista, os dados são armazenados em locais de memory não relacionados. Inserindo no meio não envolve copiar alguns dos dados para abrir espaço para o novo.

Para responder mais especificamente à sua pergunta, vou citar esta página

vetores são geralmente os mais eficientes na hora de acessar elementos e adicionar ou remover elementos do final da seqüência. Para operações que envolvem inserir ou remover elementos em posições diferentes do final, elas têm um desempenho pior que os deques e listas e têm iteradores e referências menos consistentes do que as listas.

Quando você tem muita inserção ou exclusão no meio da sequência. por exemplo, um gerenciador de memory.

Preservar a validade dos iteradores é um dos motivos para usar uma lista. Outra é quando você não quer que um vetor seja realocado ao enviar itens. Isso pode ser gerenciado por um uso inteligente de reserve (), mas, em alguns casos, pode ser mais fácil ou mais viável usar apenas uma lista.

Quando você deseja mover objects entre contêineres, você pode usar list::splice .

Por exemplo, um algoritmo de particionamento de charts pode ter um número constante de objects recursivamente divididos entre um número crescente de contêineres. Os objects devem ser inicializados uma vez e sempre permanecer nos mesmos locais na memory. É muito mais rápido reorganizá-los ao realocar do que realocar.

Editar: como as bibliotecas se preparam para implementar o C ++ 0x, o caso geral de unir uma subsequência em uma lista está se tornando uma complexidade linear com o comprimento da sequência. Isso ocorre porque a splice (agora) precisa iterar na sequência para contar o número de elementos nela. (Porque a lista precisa registrar seu tamanho.) Simplesmente contando e re-ligando a lista ainda é mais rápido do que qualquer alternativa, e splicing uma lista inteira ou um único elemento são casos especiais com complexidade constante. Mas, se você tiver sequências longas para unir, talvez seja necessário procurar um contêiner melhor, antiquado e não compatível.

A única regra difícil em que a list deve ser usada é quando você precisa distribuir pointers para os elementos do contêiner.

Ao contrário do vector , você sabe que a memory dos elementos não será realocada. Se poderia ser então você pode ter pointers para a memory não utilizada, que é na melhor das hipóteses um grande não-não e, na pior, um SEGFAULT .

(Tecnicamente, um vector de *_ptr também funcionaria, mas nesse caso você está emulando uma list modo que é apenas semântica.)

Outras regras flexíveis têm a ver com os possíveis problemas de desempenho da inserção de elementos no meio de um contêiner, sendo a list preferível.