vetor vs. lista no STL

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?

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 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.

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.

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.

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).

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.

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.

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

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

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.

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.

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.

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

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.

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.

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.