Las diferencias entre STL Vector y STL List en C++

Este artículo explica y demuestra las principales diferencias entre los contenedores STL vector y list en C++.

Determine cuándo usar std::vector en oposición al contenedor std::list en C++

Los contenedores C++ STL a menudo comparten interfaces similares para manipular elementos. Aún así, se deben explorar las diferencias internas de estas estructuras de datos para elegir el contenedor más óptimo para el problema dado. La función std::vector se conoce generalmente como matriz dinámica. Administra automáticamente la memoria dinámica internamente y mantiene los elementos almacenados de forma contigua de forma similar a un array de estilo C. Esta última característica permite acceder a elementos en tiempo constante.

Por otro lado, el comando std::list implementa una estructura de datos donde los elementos se gestionan como una lista doblemente enlazada. Formulamos la oración anterior tal como está porque el estándar C++ generalmente no exige que la implementación exacta sea una lista doblemente enlazada. Aún así, especifica ciertas características que deben ser satisfechas por los implementadores de bibliotecas estándar.

El comando std::list se proporciona como clase de plantilla, almacenando cualquier tipo de objeto similar al std::vector. Podemos almacenar nuevos elementos en el objeto std::list usando las funciones miembro push_back o push_front, que tienen una complejidad de tiempo constante. En cuanto al std::vector, solo tenemos push_back, que tiene la complejidad constante promedio. Tenga en cuenta que estas funciones se utilizan para agregar elementos al principio/final de los objetos dados.

El código de ejemplo a continuación demuestra el uso básico de las funciones anteriores en cada tipo de contenedor.

#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;
}

Por el contrario, necesitamos utilizar la función miembro insert si queremos insertar un nuevo elemento en la posición dada. Ahora bien, esta operación es una de las principales diferencias entre std::list y std::vector. Generalmente, la operación insert es más costosa en objetos vector que en objetos list.

Dado que el contenido del vector se almacena de forma contigua, cada elemento recién insertado fuerza a los siguientes elementos a moverse hacia la derecha, lo que depende del tamaño del vector en sí. Por lo tanto, debemos evitar el uso del contenedor vector si necesitamos realizar muchas inserciones en el medio del comienzo del objeto. Si el último es el caso, preferimos usar el contenedor list porque lleva un tiempo constante insertar un nuevo elemento en cualquier lugar de la lista una vez que se conoce la posición.

Demostramos la diferencia de tiempo de inserción en el siguiente ejemplo de código, donde ambos contenedores se inicializan con enteros 100000 arbitrarios, y luego cronometramos una sola operación de inserción en cada objeto. Tenga en cuenta que elegimos una posición relativamente intermedia (39999) para ambos contenedores, recuperada con la función std::search. Como resultado, se necesitan varios cientos de factores para insertar un nuevo elemento en el vector de la lista.

Dado que la operación de eliminación de elementos es similar a la inserción, es más eficiente en el objeto list en comparación con el vector. En el lado negativo, los elementos de list no tienen una operación de acceso de tiempo constante, excepto para el primer y ú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;
}

Producción :

insert vector: 0.00053000 sec
insert list  : 0.00000100 sec