As diferenças entre STL Vector e STL List em C++

Este artigo explica e demonstra as principais diferenças entre os contêineres STL vetor e lista em C++.

Determinar quando utilizar std::vector em oposição a std::list contentor em C++

Os contêineres C++ STL geralmente compartilham interfaces semelhantes para manipular elementos. Ainda assim, deve-se explorar as diferenças internas dessas estruturas de dados para escolher o contêiner ideal para o problema em questão. A função std::vector é geralmente conhecida como array dinâmico. Ele gerencia automaticamente a memória dinâmica internamente e mantém os elementos armazenados de forma contígua, semelhante a um array de estilo C. Este último recurso permite acessar os elementos em tempo constante.

Por outro lado, o comando std::list implementa uma estrutura de dados onde os elementos são gerenciados como uma lista duplamente vinculada. Formulamos a frase anterior como ela é, porque o padrão C++ geralmente não impõe que a implementação exata seja uma lista duplamente vinculada. Ainda assim, ele especifica certas características que precisam ser satisfeitas pelos implementadores de biblioteca padrão.

O comando std::list é fornecido como a classe de modelo, armazenando qualquer tipo de objeto semelhante ao std::vector. Podemos armazenar novos elementos no objeto std::list usando as funções de membro push_back ou push_front, que têm complexidade de tempo constante. Quanto ao std::vector, temos apenas push_back, que tem a complexidade média constante. Observe que essas funções são usadas para adicionar elementos no início/fim dos objetos fornecidos.

O código de exemplo abaixo demonstra o uso básico das funções acima em cada tipo de contêiner.

#include <algorithm>
#include <iostream>
#include <list>

using std::cout;
using std::endl;
using std::list;
using std::vector;

int main() {
  vector<int> v = {1, 2, 13, 84};
  list<int> l = {1, 2, 13, 84};

  v.push_back(25);
  v.push_back(13);

  l.push_back(25);
  l.push_front(13);

  return EXIT_SUCCESS;
}

Em contraste, precisamos utilizar a função de membro insert se quisermos inserir um novo elemento na posição dada. Agora, esta operação é uma das principais diferenças entre std::list e std::vector. Geralmente, a operação insert é mais cara em objetos vector do que nos objetos lista.

Como o conteúdo do vetor é armazenado de forma contígua, cada elemento recém-inserido força os seguintes elementos a serem movidos para a direita, o que depende do tamanho do próprio vetor. Assim, devemos evitar o uso do recipiente vector se precisarmos realizar muitas inserções no meio do início do objeto. Se for o último caso, preferimos usar o contêiner list porque leva um tempo constante para inserir um novo elemento em qualquer lugar da lista, uma vez que a posição é conhecida.

Demonstramos a diferença de tempo de inserção no próximo exemplo de código, onde ambos os contêineres são inicializados com inteiros 100000 arbitrários e, em seguida, cronometramos uma única operação de inserção em cada objeto. Observe que escolhemos uma posição relativamente intermediária (39999) para ambos os contêineres, recuperada com a função std::search. Como resultado, são necessárias várias centenas de fatores para inserir um novo elemento no vector da list.

Uma vez que a operação de remoção do elemento é semelhante à inserção, é mais eficiente no objeto list em comparação com o vector. No lado negativo, os elementos list não têm operação de acesso em tempo constante, exceto para o primeiro e o último elemento.

#include <sys/time.h>

#include <algorithm>
#include <iostream>
#include <list>
#include <random>

using std::cout;
using std::endl;
using std::list;
using std::vector;

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

const int MIN = 1;
const int MAX = 100;
const int CAPASITY = 100000;

int main() {
  struct timeval start {};
  struct timeval end {};

  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  vector<int> vec1;
  list<int> list1;

  vec1.reserve(CAPASITY);
  for (int i = 0; i < CAPASITY; ++i) {
    if (i % 39999 == 0) {
      vec1.push_back(111);
      continue;
    }
    vec1.push_back(distr(eng));
  }

  for (int i = 0; i < CAPASITY; ++i) {
    if (i % 39999 == 0) {
      list1.push_back(111);
      continue;
    }
    list1.push_back(distr(eng));
  }

  auto iter = std::find(vec1.begin(), vec1.end(), 111);
  gettimeofday(&start, nullptr);
  vec1.insert(iter, 1111);
  gettimeofday(&end, nullptr);
  printf("insert vector: %0.8f sec\n", time_diff(&start, &end));

  auto iter2 = std::find(list1.begin(), list1.end(), 111);
  gettimeofday(&start, nullptr);
  list1.insert(iter2, 1111);
  gettimeofday(&end, nullptr);
  printf("insert list  : %0.8f sec\n", time_diff(&start, &end));

  return EXIT_SUCCESS;
}

Resultado:

insert vector : 0.00053000 sec insert list : 0.00000100 sec