vetor vs. lista no STL

238

Notei no Effective STL que

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

O que isso significa? Parece que ignorar a eficiência vectorpode fazer qualquer coisa.

Alguém poderia me oferecer um cenário em que vectornão é uma opção viável, mas listdeve ser usada?

skydoor
fonte
6
Embora não seja o que você pediu, vale ressaltar que o padrão de vetor também significa que você pode interagir facilmente com códigos mais antigos, bibliotecas C ou bibliotecas que não são de modelos, pois o vetor é um invólucro fino em torno da matriz dinâmica "tradicional" de um ponteiro e tamanho.
18
Na verdade, Bjarne Strostrup fez um teste no qual gerou números aleatórios e os adicionou a uma lista e um vetor, respectivamente. As inserções foram feitas para que a lista / vetor fosse sempre solicitada. Mesmo que esse seja tipicamente "domínio de lista", o vetor superou a lista por uma margem GRANDE. O motivo é que o acesso à memória é lento e o armazenamento em cache funciona melhor para dados seqüenciais. É tudo disponível em seu discurso de "GoingNative 2012"
fugindo
1
Se você quiser ver o keynote por Bjarne Stroustrup que @evading mencionado, eu achei aqui: youtu.be/OB-bdWKwXsU?t=2672
brain56

Respostas:

98

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?

Martin York
fonte
2
A inserção de elementos no final também conta, pois pode levar à alocação de memória e aos custos de cópia de elementos. E também, inserir elenets no começo de um vetor é quase impossível, listtempush_front
Notinlist
9
Não, a inserção de elementos no final de um vetor é amortizada em tempo constante. As alocações de memória ocorrem apenas ocasionalmente, e você pode pré-alocar o vetor para evitá-lo. Obviamente, se você DEVE ter garantido inserções constantes de tempo constante, acho que isso ainda é um problema.
Brian
16
@ Notinlist - É o seguinte "quase impossível" para você? v.insert (v.begin (), i)
Manuel
5
@ Notinlist - eu concordo com você, é só que eu não queria que o OP pensasse que a interface não existe, caso alguém queira se dar um tiro no pé (de desempenho).
Manuel
16
Na verdade, Bjarne Strostrup fez um teste no qual gerou números aleatórios e os adicionou a uma lista e um vetor, respectivamente. As inserções foram feitas para que a lista / vetor fosse sempre solicitada. Mesmo que esse seja tipicamente "domínio de lista", o vetor superou a lista por uma margem GRANDE. O motivo é que o acesso à memória é lento e o armazenamento em cache funciona melhor para dados seqüenciais. É tudo disponível em seu discurso de "GoingNative 2012"
fugindo
409

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 próprio tipo de elemento (sem ponteiros extras).
  • Pode realocar a memória para o vetor inteiro a qualquer momento que você adicionar um elemento.
  • As inserções no final são constantes, tempo amortizado, mas as inserções em outros lugares são um O (n) caro.
  • As apagões no final do vetor são tempo constante, mas, no restante, é O (n).
  • Você pode acessar aleatoriamente seus elementos.
  • Os iteradores são invalidados se você adicionar ou remover elementos de ou para o vetor.
  • Você pode acessar facilmente a matriz subjacente se precisar de uma matriz dos elementos.

Lista:

  • Memória não contígua.
  • Não há memória pré-alocada. A sobrecarga de memória para a própria lista é constante.
  • Cada elemento requer espaço extra para o nó que contém o elemento, incluindo ponteiros para os elementos seguintes e anteriores da lista.
  • Nunca é necessário realocar memória para a lista inteira apenas porque você adiciona um elemento.
  • Inserções e rasuras são baratas, não importa onde estejam na lista.
  • É barato combinar listas com emendas.
  • Você não pode acessar elementos aleatoriamente, portanto, chegar a um elemento específico da lista pode ser caro.
  • Os iteradores permanecem válidos mesmo quando você adiciona ou remove elementos da lista.
  • Se você precisar de uma matriz dos elementos, precisará criar uma nova e adicioná-la a todos, pois não há matriz subjacente.

Em geral, use vetor quando você não se importa com o tipo de contêiner seqüencial que está usando, mas se estiver fazendo muitas inserções ou apagamentos para e de qualquer lugar do contêiner que não seja o final, você desejará para usar a lista. Ou, se você precisar de acesso aleatório, desejará vetor, não lista. Fora isso, existem casos em que naturalmente você precisará de um ou outro com base em seu aplicativo, mas, em geral, essas são boas diretrizes.

Jonathan M Davis
fonte
2
Além disso, a alocação a partir da loja gratuita não é gratuita. :) A adição de novos itens a um vetor executa alocações de armazenamento livre de O (log n), mas você pode ligar reserve()para reduzi-lo a O (1). Adicionar novos itens a uma lista (ou seja, sem emendá-los) executa O (n) alocações de armazenamento gratuito.
bk1e
7
Outra consideração é que listlibera memória quando você apaga elementos, mas vectornão o faz. A vectornão reduz sua capacidade quando você reduz seu tamanho, a menos que você use o swap()truque.
bk1e
@ bk1e: Eu realmente quero saber seu truque na reserva () e swap () :)
Dzung Nguyen
2
@nXqd: se você precisar adicionar N elementos a um vetor, chame v.reserve (v.size () + N) para que ele execute apenas uma alocação de loja gratuita. O truque swap () está aqui: stackoverflow.com/questions/253157/how-to-downsize-stdvector
bk1e
1
@simplename Não. O que diz está correto. o vetor aloca espaço extra além do espaço para os elementos atualmente no vetor; essa capacidade extra é então usada para aumentar o vetor, para que o crescimento seja amortizado O (1).
Jonathan M Davis
35

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

Hans Passant
fonte
32

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

O que você deseja manter no contêiner?

Se for uma coleção de ints, std::listperderá em todos os cenários, independentemente se você pode realocar, você remove apenas da frente etc. As listas são mais lentas para percorrer, cada inserção custa uma interação com o alocador. Seria extremamente difícil preparar um exemplo, onde list<int>bate vector<int>. E mesmo assim, deque<int>pode ser melhor ou mais próximo, sem prejudicar o uso de listas, que terão maior sobrecarga de memória.

No entanto, se você estiver lidando com grandes e feios blobs de dados - e poucos deles -, não deseja atribuir uma classificação geral ao inserir, e copiar devido à realocação seria um desastre - então talvez você esteja melhor com um list<UglyBlob>que vector<UglyBlob>.

Ainda assim, se você alternar para vector<UglyBlob*>ou mesmo vector<shared_ptr<UglyBlob> >novamente - a lista ficará para trás.

Portanto, o padrão de acesso, a contagem de elementos de destino etc. ainda afeta a comparação, mas, na minha opinião - o tamanho dos elementos - o custo da cópia etc.

Tomasz Gandor
fonte
1
Mais uma reflexão que tive ao ler "Effective STL" de Meyers: uma propriedade peculiar de list<T>é a possibilidade de spliceem O (1) . Se você precisar de splicing de tempo constante, lista também pode ser a estrutura de escolha;)
Tomasz Gandor
+1 - Ele nem sequer tem que ser um UglyBlob- até mesmo um objetos com apenas alguns membros da corda pode facilmente ser proibitivamente caro para copiar, por isso as realocações vai custar. Além disso: não negligencie a sobrecarga de espaço que o crescimento exponencial de vectorobjetos retidos com algumas dúzias de bytes de tamanho pode causar (se você não puder reserveantecipadamente).
Martin Ba
Quanto a vector<smart_ptr<Large>>vs. list<Large>- eu diria que, se você precisar de acesso aleatório aos elementos, vectorfaz sentido. Se você não precisar de acesso aleatório, o listprocedimento parecerá mais simples e deverá ter o mesmo desempenho.
Martin Ba
19

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

Ou talvez se seu conteúdo for 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 objetos simples.

Eu não acho que existem regras muito difíceis. Depende do que você mais deseja fazer com o contêiner, bem como do tamanho que você espera que o contêiner seja e do 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 circunstâncias, uma matriz é a maneira mais eficiente de armazenar várias coisas).

UncleBens
fonte
1
+1. A emenda é negligenciada, mas infelizmente não é constante, conforme desejado. : (((Pode não ser se a lista :: tamanho é constante de tempo).
Tenho certeza de que list :: size é (permitida) linear por esse motivo.
UncleBens
1
@ Roger: list::sizenão é necessariamente tempo constante. Veja stackoverflow.com/questions/228908/is-listsize-really-on e gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html
Potatoswatter
@ Potatoswatter: O fato de o padrão ser vago e, consequentemente, você não poder confiar em implementações "compatíveis" torna ainda mais um problema. Você literalmente precisa evitar o stdlib para obter uma garantia portátil e confiável.
@ Roger: sim, infelizmente. Meu projeto atual depende fortemente de operações de emenda e essa estrutura é quase reta C. Ainda mais infelizmente, na sequência do N3000 spliceentre listas diferentes é especificada como complexidade linear e sizeé especificamente constante. Portanto, para acomodar iniciantes que iteram sizeou qualquer outra coisa, toda uma classe de algoritmos está fora do alcance do STL ou de qualquer período de contêineres "compatíveis".
Potatoswatter
13

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

É assim que eu 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 não sejam classificados, a ordem não será alterada: será eficiente se a memória estiver fragmentada. Mas também tem uma outra grande vantagem: você pode inserir / remover itens facilmente, porque a única coisa que você precisa fazer é alterar alguns indicadores. Desvantagem: para ler um item único aleatório, você deve pular de um item para outro até encontrar o endereço correto.

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

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

Não sei como as listas são otimizadas, mas você deve saber que, se quiser acesso rápido à leitura, use vetores, porque o quão bom o STL prende as listas não será tão rápido no acesso de leitura quanto o vetor.

jokoon
fonte
"modificar a matriz do vetor ou alterar um valor é muito mais lento" - como lido, isso parece contradizer o que você disse antes sobre o predisposição do vetor para um bom desempenho devido à sua natureza contígua e de baixo nível. você quis dizer que a realocação do vectorcausado pela mudança de tamanho pode ser lenta? então concordou, mas nos casos em que reserve()pode ser usado, evita esses problemas.
Underscore_d
10

Basicamente, um vetor é uma matriz com gerenciamento automático de memória. Os dados são contíguos na memória. Tentar inserir dados no meio é uma operação cara.

Em uma lista, os dados são armazenados em locais de memória não relacionados. Inserir no meio não envolve copiar alguns dados para abrir espaço para o novo.

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

os vetores geralmente são os mais eficientes no tempo para acessar elementos e adicionar ou remover elementos do final da sequência. Para operações que envolvem a inserção ou remoção de elementos em posições diferentes do final, elas apresentam desempenho pior que deques e listas e têm iteradores e referências menos consistentes que as listas.

f4
fonte
9

A qualquer momento, você não pode ter os iteradores invalidados.

dirkgently
fonte
2
Mas nunca chegue a essa conclusão sobre os iteradores sem perguntar se as referências persistentes em um dequeseriam suficientes.
Potatoswatter
8

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

AraK
fonte
então a diferença entre eles é apenas eficiência, não questão funcional.
skydoor
Ambos modelam uma sequência de elementos, é claro. Há uma pequena diferença no uso, como mencionado por @dirkgently, mas você precisa analisar a complexidade de suas operações "frequentemente concluídas" para decidir qual sequência escolher (resposta @Martin).
AraK
@skydoor - Existem algumas diferenças funcionais. Por exemplo, apenas o vetor suporta acesso aleatório (ou seja, pode ser indexado).
Manuel
2
@skydoor: eficiência se traduz em desempenho. Um desempenho ruim pode arruinar a funcionalidade. Afinal, o desempenho é a vantagem do C ++.
Potatoswatter
4

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

John Dibling
fonte
4

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

Por exemplo, um algoritmo de particionamento de gráfico pode ter um número constante de objetos divididos recursivamente entre um número crescente de contêineres. Os objetos devem ser inicializados uma vez e sempre permanecem nos mesmos locais na memória. É muito mais rápido reorganizá-los religando do que realocando.

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

Potatoswatter
fonte
2

A única regra rígida onde listdeve ser usada é onde você precisa distribuir ponteiros para os elementos do contêiner.

Ao contrário de vector, você sabe que a memória dos elementos não será realocada. Se possível, você pode ter ponteiros para a memória não utilizada, o que é, na melhor das hipóteses, um grande não-não e, na pior das hipóteses, a SEGFAULT.

(Tecnicamente, um vectorde *_ptrtambém funcionaria, mas nesse caso você está emulando, listentão isso é 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, pelo listque seria preferível.

iPherian
fonte
2

Simplifique -
No final do dia, quando você estiver confuso escolhendo os contêineres em C ++, use esta imagem do fluxograma (diga obrigado): - insira a descrição da imagem aqui

Vetor -
1. o vetor é baseado na memória contagiosa
2. o vetor é o caminho a seguir para um pequeno conjunto de dados
3. o desempenho do vetor é mais rápido enquanto percorre o conjunto de dados
4. a exclusão da inserção do vetor é lenta em um conjunto de dados enorme, mas rápida em muito pequeno

List-
1. lista é baseada em memória heap
2. lista é caminho a percorrer para muito grande de dados em conjunto
3. lista é relativamente lento em atravessar pequena de dados em conjunto, mas rápido com enormes Conjunto de dados
4. lista de exclusão de inserção é rápido em conjunto de dados enorme, mas lento nos menores

xyz xyz
fonte
1

As listas são apenas um invólucro para um duplamente LinkedList no stl, oferecendo assim o recurso que você pode esperar do d-linklist, a saber, inserção e exclusão de O (1). Enquanto vetores são uma sequência de dados contagiosa que funciona como um array dinâmico.PS - mais fácil de percorrer.

Ritankar Paul
fonte
0

No caso de um vetor e lista , as principais diferenças que se destacam para mim são as seguintes:

vetor

  • Um vetor armazena seus elementos na memória contígua. Portanto, o acesso aleatório é possível dentro de um vetor, o que significa que acessar um elemento de um vetor é muito rápido, porque podemos simplesmente multiplicar o endereço base com o índice do item para acessar esse elemento. De fato, leva apenas O (1) ou tempo constante para esse fim.

  • Como um vetor basicamente envolve uma matriz, toda vez que você insere um elemento no vetor (matriz dinâmica), ele deve se redimensionar, encontrando um novo bloco contíguo de memória para acomodar os novos elementos, que são dispendiosos em termos de tempo.

  • Não consome memória extra para armazenar ponteiros para outros elementos dentro dele.

Lista

  • Uma lista armazena seus elementos na memória não contígua. Portanto, o acesso aleatório não é possível dentro de uma lista, o que significa que, para acessar seus elementos, precisamos usar os ponteiros e percorrer a lista que é mais lenta em relação ao vetor. Isso leva O (n) ou tempo linear mais lento que O (1).

  • Como uma lista usa memória não contígua, o tempo necessário para inserir um elemento dentro de uma lista é muito mais eficiente do que no caso de sua contraparte vetorial, pois a realocação da memória é evitada.

  • Consome memória extra para armazenar ponteiros para o elemento antes e depois de um elemento específico.

Portanto, mantendo essas diferenças em mente, geralmente consideramos memória , acesso aleatório frequente e inserção para decidir o vencedor da lista de vetores versus vetor em um determinado cenário.

Ardent Coder
fonte
0

A lista é uma lista duplamente vinculada, portanto é fácil inserir e excluir um elemento. Temos apenas que alterar os poucos ponteiros, enquanto que no vetor, se queremos inserir um elemento no meio, cada elemento depois que ele precisa mudar um índice. Além disso, se o tamanho do vetor estiver cheio, é necessário primeiro aumentá-lo. Portanto, é uma operação cara. Portanto, sempre que for necessário executar operações de inserção e exclusão com mais frequência, uma lista de casos deve ser usada.

Siddesh Pawar
fonte