Les différences entre le vecteur STL et la liste STL en C++

Cet article explique et démontre les principales différences entre les conteneurs STL vector et list en C++.

Déterminer quand utiliser std::vector par opposition au conteneur std::list en C++

Les conteneurs STL C++ partagent souvent des interfaces similaires pour manipuler des éléments. Pourtant, il faut explorer les différences internes de ces structures de données pour choisir le conteneur le plus optimal pour le problème donné. La fonction std::vector est généralement connue sous le nom de tableau dynamique. Il gère automatiquement la mémoire dynamique en interne et conserve les éléments stockés de manière contiguë, de la même manière qu’un tableau de style C. Cette dernière caractéristique permet d’accéder à des éléments en temps constant.

D’autre part, la commande std::list implémente une structure de données où les éléments sont gérés comme une liste doublement chaînée. Nous formulons la phrase précédente telle qu’elle est car la norme C++ n’impose généralement pas que l’implémentation exacte soit une liste à double chaînage. Néanmoins, il spécifie certaines caractéristiques qui doivent être satisfaites par les implémenteurs de bibliothèque standard.

La commande std::list est fournie en tant que classe modèle, stockant tout type d’objet similaire au std::vector. Nous pouvons stocker de nouveaux éléments dans l’objet std::list en utilisant les fonctions membres push_back ou push_front, qui ont toutes une complexité temporelle constante. Quant au std::vector, nous n’avons que push_back, qui a la complexité moyenne constante. Notez que ces fonctions sont utilisées pour ajouter des éléments au début/à la fin des objets donnés.

L’exemple de code ci-dessous illustre l’utilisation de base des fonctions ci-dessus sur chaque type de conteneur.

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

En revanche, nous devons utiliser la fonction membre insert si nous voulons insérer un nouvel élément à la position donnée. Or, cette opération est l’une des principales différences entre std::list et std::vector. Généralement, l’opération insert est plus coûteuse sur les objets vector que sur les objets list.

Étant donné que le contenu du vecteur est stocké de manière contiguë, chaque élément nouvellement inséré force les éléments suivants à être déplacés vers la droite, ce qui dépend de la taille du vecteur lui-même. Ainsi, il faut éviter d’utiliser le conteneur vector si l’on a besoin de faire de nombreuses insertions au milieu du début de l’objet. Dans ce dernier cas, nous préférons utiliser le conteneur list car il faut un temps constant pour insérer un nouvel élément n’importe où dans la liste une fois que la position est connue.

Nous démontrons la différence de temps d’insertion dans l’exemple de code suivant, où les deux conteneurs sont initialisés avec des entiers arbitraires 100000, puis nous chronométrons une seule opération d’insertion dans chaque objet. A noter que nous avons choisi une position relativement médiane (39999) pour les deux conteneurs, récupérée avec la fonction std::search. De ce fait, il faut plusieurs centaines de facteurs pour insérer un nouvel élément dans le vector celui de la list.

L’opération de suppression d’élément étant similaire à l’insertion, elle est plus efficace sur l’objet list par rapport au vector. Par contre, les éléments list n’ont pas de fonctionnement d’accès à temps constant, sauf pour le premier et le dernier élément.

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

Production:

insert vector : 0.00053000 sec insert list : 0.00000100 sec