Die Unterschiede zwischen STL-Vektor und STL-Liste in C++

Dieser Artikel erklärt und demonstriert die Hauptunterschiede zwischen STL-vector- und list-Containern in C++.

Bestimmen, wann man std::vector im Gegensatz zu std::list-Container in C++ verwendet

C++-STL-Container verwenden häufig ähnliche Schnittstellen zum Bearbeiten von Elementen. Dennoch sollte man die internen Unterschiede dieser Datenstrukturen untersuchen, um den optimalen Container für das gegebene Problem auszuwählen. Die Funktion std::vector wird allgemein als dynamisches Array bezeichnet. Es verwaltet automatisch den dynamischen Speicher intern und hält die Elemente, die zusammenhängend gespeichert sind, ähnlich einem Array im C-Stil. Letzteres ermöglicht den Zugriff auf Elemente in konstanter Zeit.

Andererseits implementiert der Befehl std::list eine Datenstruktur, in der Elemente als doppelt verkettete Liste verwaltet werden. Wir formulieren den vorherigen Satz so, wie er ist, da der C++-Standard die genaue Implementierung normalerweise nicht als doppelt verknüpfte Liste erzwingt. Dennoch spezifiziert es bestimmte Eigenschaften, die von den Standardbibliothek-Implementierern erfüllt werden müssen.

Als Template-Klasse steht der Befehl std::list zur Verfügung, der beliebige Objekttypen ähnlich dem std::vector speichert. Wir können neue Elemente im std::list-Objekt speichern, indem wir die Member-Funktionen push_back oder push_front verwenden, die alle eine konstante Zeitkomplexität haben. Was den std::vector angeht, haben wir nur push_back, was die durchschnittliche konstante Komplexität hat. Beachten Sie, dass diese Funktionen verwendet werden, um Elemente am Anfang/Ende der angegebenen Objekte hinzuzufügen.

Der folgende Beispielcode zeigt die grundlegende Verwendung der obigen Funktionen für jeden Containertyp.

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

Im Gegensatz dazu müssen wir die Member-Funktion insert verwenden, wenn wir ein neues Element an der angegebenen Position einfügen möchten. Diese Operation ist nun einer der Hauptunterschiede zwischen std::list und std::vector. Im Allgemeinen ist die Operation Einfügen bei Vektor-Objekten teurer als bei list-Objekten.

Da die Vektorinhalte zusammenhängend gespeichert werden, erzwingt jedes neu eingefügte Element, dass die folgenden Elemente nach rechts verschoben werden, was von der Größe des Vektors selbst abhängt. Daher sollten wir den Vektor-Container vermeiden, wenn wir viele Einfügungen mitten am Anfang des Objekts durchführen müssen. Wenn letzteres der Fall ist, verwenden wir lieber den Container list, da es ständig dauert, ein neues Element an einer beliebigen Stelle in der Liste einzufügen, sobald die Position bekannt ist.

Wir demonstrieren den Einfügezeitunterschied im nächsten Codebeispiel, in dem beide Container mit beliebigen 100000 ganzen Zahlen initialisiert werden und dann eine einzelne Einfügeoperation in jedes Objekt zeitlich festgelegt wird. Beachten Sie, dass wir für beide Container eine relativ mittlere Position (39999) gewählt haben, die mit der Funktion std::search abgerufen wird. Daher braucht es mehrere hundert Faktoren, um ein neues Element in den Vektor der Liste einzufügen.

Da der Vorgang zum Entfernen von Elementen dem Einfügen ähnlich ist, ist er beim Objekt Liste effizienter als beim Objekt Vektor. Auf der anderen Seite haben list-Elemente keine konstante Zeitzugriffsoperation, mit Ausnahme des ersten und des letzten Elements.

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

Ausgabe:

insert vector: 0.00053000 sec
insert list  : 0.00000100 sec