Le differenze tra vettore STL e lista STL in C++

Questo articolo spiega e dimostra le principali differenze tra i contenitori STL vector e list in C++.

Determina quando utilizzare std::vector in contrapposizione a std::list contenitore in C++

I contenitori C++ STL spesso condividono interfacce simili per manipolare gli elementi. Tuttavia, si dovrebbero esplorare le differenze interne di queste strutture di dati per scegliere il contenitore più ottimale per il dato problema. La funzione std::vector è generalmente nota come array dinamico. Gestisce automaticamente la memoria dinamica internamente e mantiene gli elementi archiviati in modo contiguo simile a un array in stile C. Quest’ultima caratteristica consente di accedere agli elementi in tempo costante.

D’altra parte, il comando std::list implementa una struttura dati in cui gli elementi sono gestiti come una lista doppiamente collegata. Formuliamo la frase precedente così com’è perché lo standard C++ di solito non impone che l’implementazione esatta sia una lista con collegamenti doppi. Tuttavia, specifica alcune caratteristiche che devono essere soddisfatte dagli implementatori della libreria standard.

Il comando std::list è fornito come classe template, memorizzando qualsiasi tipo di oggetto simile a std::vector. Possiamo memorizzare nuovi elementi nell’oggetto std::list utilizzando le funzioni membro push_back o push_front, che hanno tutte una complessità temporale costante. Per quanto riguarda std::vector, abbiamo solo push_back, che ha la complessità media costante. Nota che queste funzioni sono usate per aggiungere elementi all’inizio/alla fine degli oggetti dati.

Il codice di esempio seguente mostra l’utilizzo di base delle funzioni precedenti su ciascun tipo di contenitore.

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

Al contrario, dobbiamo utilizzare la funzione membro insert se vogliamo inserire un nuovo elemento nella posizione data. Ora, questa operazione è una delle principali differenze tra std::list e std::vector. In genere, l’operazione insert è più costosa sugli oggetti vector rispetto agli oggetti list.

Poiché i contenuti del vettore sono memorizzati in modo contiguo, ogni elemento appena inserito forza lo spostamento a destra dei seguenti elementi, che dipende dalla dimensione del vettore stesso. Pertanto, dovremmo evitare di utilizzare il contenitore vector se dobbiamo eseguire molti inserimenti nel mezzo dell’inizio dell’oggetto. In quest’ultimo caso, preferiamo utilizzare il contenitore list perché ci vuole tempo costante per inserire un nuovo elemento in qualsiasi punto della lista una volta nota la posizione.

Dimostriamo la differenza di tempo di inserimento nel prossimo esempio di codice, in cui entrambi i contenitori sono inizializzati con interi 100000 arbitrari, e quindi cronometriamo una singola operazione di inserimento in ciascun oggetto. Nota che abbiamo scelto una posizione relativamente centrale (39999) per entrambi i contenitori, recuperata con la funzione std::search. Di conseguenza, occorrono più centinaia di fattori per inserire un nuovo elemento nel vector quello della lista.

Poiché l’operazione di rimozione dell’elemento è simile all’inserimento, è più efficiente sull’oggetto list rispetto al vector. Al rovescio della medaglia, gli elementi list non hanno un’operazione di accesso a tempo costante ad eccezione del primo e dell’ultimo 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;
}

Produzione:

insert vector : 0.00053000 sec insert list : 0.00000100 sec