Modernere Arrays

Klassische Arrays sind immer etwas umständlich und fehleranfällig: feste Größe, kein automatisches Speichermanagement, um alles muss man sich selbst kümmern. Das ist meist eher unpraktisch und unnötig viel Aufwand. Viel einfacher dagegen std::vector.

Video

Quellcode

#include <iostream>
#include <vector>

void oldInterface(int *numbers)
{
  std::cout << "Wert via Pointer: " << *(numbers+1000) << std::endl;
  std::cout << "Wert aus Array: " << numbers[1234] << std::endl;
}

int main()
{
  std::vector<int> v;
  v.reserve(10000);
  
  std::cout << "Kapazität: " << v.capacity() << std::endl;
 
  size_t cap = v.capacity();
  for (int i = 0; i < 1000000; ++i) {
    v.push_back(i);
    if (v.capacity() != cap) {
      cap = v.capacity();
      std::cout << "Neue Kapazität: " << cap << std::endl;
    }
  }
  std::cout << "Vektor-Index: " << v[1000] << std::endl;
  oldInterface(v.data());
}

Erklärung

Auf den ersten Blick sieht std::vector aus, wie ein klassisches Array: Index-Zugriff in O(1), Einfügen am Anfang oder in der Mitte in O(n). Er bietet allerdings ein paar Nettigkeiten. So kann zum Beispiel ein Einfügen am Ende in amortisiert O(1) erreicht werden. Das funktioniert ganz einfach: std::vector trennt zwischen seiner Größe (die Anzahl an Elementen, die im Vektor vorhanden ist) und seiner Kapazität (die Anzahl an Elementen, die der Vektor aufnehmen kann, bevor eine teure Neuallokierung notwendig wird). Die Kapazität (im Quelltext oben mit std::vector::capacity() ermittelt) wächst exponentiell. Mit jedem Mal, wo der Vektor intern vergrößert werden muss, wird seine Kapazität verdoppelt. Dadurch sind diese Neuallokierungen selten notwendig und "verteilen" ihren Aufwand auf viele Einfügeschritte, die dann eben amortisiert O(1) sind. Hier muss man allerdings etwas aufpassen: in Wirklichkeit sind die meisten Schritte tatsächlich O(1), aber immer mal zwischendrin einer O(n) über die Länge des Vektors, da in diesem einen Schritt die Neuallokierung und damit Kopie stattfinden muss. Normalerweise kein Problem, außer wenn man bspw. Echtzeitsysteme entwickelt und sich auf die Dauer eines Einfügeschrittes einigermaßen verlassen will.

Warum nun eigentlich der Aufwand mit Neuallokierung und Kopie beim Vergrößern? Könnte der Vektor nicht einfach blockweise allokieren und immer einen neuen Block hinzufügen, wenn nötig? Kann er nicht, denn wir bekommen noch eine zweite interessante Garantie vom Standard: die Elemente eines Vektors liegen im Speicher am Block hintereinander. Intern verhält sich diese Klasse also wirklich wie ein Array. Das ist dann sehr praktisch, wenn wir den Container mit älteren Schnittstellen oder C-Bibliotheken benutzen wollen (oben im Quelltext durch die Funktion oldInterface() repräsentiert). Diese nehmen für Arrays üblicherweise nur einen Pointer auf das erste Element (und meist noch eine Länge, weil man die ja anders nicht ermitteln kann aus einem Pointer). Dadurch, dass std::vector uns garantiert, dass die Elemente intern am Stück als Array vorliegen und uns auch noch eine Schnittstelle bereitstellt, um einen Pointer auf dieses interne Array zu erhalten (die Methode data()), können wir ihn sehr einfach mit solchen Legacy-Schnittstellen verwenden.

Wenn wir vorher schon wissen, wieviele Elemente wir in den Vektor einfügen wollen, dann können wir das Kopieren des internen Arrays sogar ganz vermeiden: mit std::vector::reserve() setzen wir die interne Kapazität auf den gewünschten Wert und gehen so dem Platzmangel aus dem Weg.