Quando o vetor / lista deve ser usado?

Consigo entender quando usar listas, mas não entendo quando é melhor usar vetores do que usar listas em videogames: quando é melhor ter acesso aleatório rápido?

(E eu entendo por que é mais rápido inserir / excluir em listas porque apenas remove / adiciona ponteiros, mas ainda precisa encontrar o item correspondente ...)

Minha regra de ouro, e tenho certeza de que haverá debate sobre isso, é nunca usar listas (a menos que você precise remover com muita, muita frequência coisas do meio de grandes listas).

A velocidade que você ganhará ao ter todos os seus elementos em seu contêiner na memória contígua (e, portanto, mais amigável ao cache) vale a compensação dos custos adicionais de adicionar / remover / redimensionar o vetor.

Edit: Apenas para esclarecer um pouco mais, é claro que não é preciso dizer que qualquer tipo de pergunta "que é mais rápida" deve ser testada em qualquer plataforma com quaisquer conjuntos de dados pertinentes às suas necessidades particulares. Se eu apenas precisar de uma coleção de elementos, apenas uso vetor (ou deque, que é quase a mesma coisa), a menos que haja um bom motivo para não fazê -lo.

Use uma lista quando a invalidação do iterador causada pela modificação do meio da estrutura de dados causar um problema ou você precisar manter seus elementos classificados para que o truque de troca e pop para exclusões rápidas da coleção do meio não funcione e você tenha uma grande número de exclusões de coleção intermediária.

Você também pode considerar usar um Deque. Possui características de desempenho semelhantes às de um vetor, mas não possui necessidade de memória contígua e é um pouco mais flexível.

Sua escolha deve refletir suas necessidades. Todos os elementos dos vetores são contínuos na memória e as listas têm ponteiros para os elementos seguintes / anteriores, para que cada um tenha suas vantagens / desvantagens:

Listas:

• Cada elemento leva 2 números inteiros para apontar os elementos anteriores e seguintes, portanto, mais comumente, são 8 bytes a mais para cada elemento da sua lista
• O inserto é linear no tempo: O (n)
• Remover é uma operação constante: O (1)
• Acesse o elemento x é linear no tempo: O (n)

Vetores:

• Precisa de menos memória (sem ponteiros para outros elementos, é um algoritmo matemático simples)
• Remover é linear no tempo: O (n)
• O acesso ao elemento x é constante: O (1) (Isso ocorre porque os elementos são contínuos na memória, por isso é uma operação matemática simples vectorPtr + (x * bytesOfTheType))
• A inserção pode ocorrer em tempo linear, mas, mais comumente, é uma operação constante: O (1) (isso ocorre porque o vetor em uma matriz sempre reserva 2 vezes sua capacidade quando a matriz está cheia, para que a cópia da matriz não seja frequente)

Portanto, a lista é melhor quando o programa precisa adicionar e remover elementos com frequência, mas nunca acesse (ou raramente acesse) um elemento específico sem a necessidade dos outros antes. O vetor deve ser usado para melhorar o tempo de acesso, mas falta eficiência quando você precisa remover ou adicionar elementos.

Verifique esta postagem no stackoverflow, ela apresenta um gráfico muito bom, com perguntas básicas sobre suas necessidades, que o levam a um contêiner específico, dependendo de suas respostas:

/programming/366432/extending-stdlist

Geralmente, as listas são usadas para estruturas como filas, nas quais existem muitas operações de acréscimo e remoção. Exemplo: uma lista em constante mudança de entidades que devem ser atualizadas. A lista em si contém apenas entidades na tela e, portanto, muda frequentemente.

Os vetores (ou matrizes) são mais adequados para uma coleção que não muda muito e onde você precisa de acesso rápido a itens individuais da coleção. Exemplo: um mapa de blocos em que você precisa procurar blocos em um determinado índice.

A opinião do Tetrads pode ser verdadeira, mas depende da linguagem de programação usada. Vejo que você marcou sua pergunta c++, mas tentei dar uma resposta que não é específica ao idioma.

Nos jogos de console, nunca usamos std :: list porque:

1. ele faz alocações de memória sempre que você adiciona um novo item. as alocações de memória são lentas.
2. está cheio de ponteiros. ponteiros são ruins. um ponteiro é um erro de cache. uma falta de cache é ruim.

Até o std :: vector está perdendo o interesse nos consoles porque:

1. você geralmente se preocupa apenas com, por exemplo, as posições de todos os objetos. por exemplo, você deseja colidir os objetos entre si, caso em que não se importa com a cor deles. para que todas as posições sejam contíguas na memória e as cores estejam em outro lugar distante, para evitar poluir o cache. mas std :: vector exige que você armazene tudo para cada objeto em um pedaço contíguo de memória (por exemplo, posição e cor). Portanto, se você trabalha lendo apenas as posições, também precisa ler todas as cores no cache, até se você não os usar. isso é um desperdício.