So verwendest Du den std::vector - Modernes C++

Table of Contents

Motivation

Auf meiner Lernreise in die Welt der Robotik ist eines meiner Ziele, mein angestaubtes C++-Wissen aufzubessern.
Heute schauen wir uns den std::vector an. Der std::vector ist ein praktisches Hilfsmittel, um in C++ Daten zu verwalten.
Man kann ihn mit der Liste in Python vergleichen. Im Gegensatz zum std::array ist der std::vector eine dynamische Datenstruktur, die wächst, wenn neue Werte hinzugefügt werden und die bisherige Kapazität nicht mehr ausreicht.

Historie

Den std::vector gibt es bereits ab C++98, er wurde von Alexander Stepanov entwickelt. Seit C++11 sind einige interessante Neuerungen hinzugekommen.

Include

Um einen Vector zu benutzen, wird der Header vector eingebunden:

#include <vector>

Deklaration

Der std::vector ist eine Template-Datenstruktur, d.h. wir müssen ihn mit dem Datentyp parametrieren, der eingefügt werden soll:

TEST(VectorTest, VectorInitialSize) {
    const std::vector int_vector;
    EXPECT_EQ(int_vector.capacity(), 0);
    EXPECT_EQ(int_vector.size(), 0);
    EXPECT_EQ(int_vector.empty(), true);
}

Die Kapazität und die Größe sind am Anfang 0; empty() gibt true zurück

Daten einfügen

Die einfachste Art, Daten in den Vector zu packen, ist die push_back()-Methode. Sie hängt ein neues Element an das Ende des vectors

TEST(VectorTest, VectorPushBack) {
    std::vector int_vector;
    int_vector.push_back(1);
    int_vector.push_back(2);
    int_vector.push_back(3);
    EXPECT_EQ(int_vector.size(), 3);
}

Mit der Insert-Methode kann an einer beliebigen Stelle im Vector ein Element eingefügt werden:

TEST(VectorTest, VectorElementInsert) {
    std::vector int_vector = {1,2,3};
    int_vector.insert(int_vector.begin(), 0);
    EXPECT_EQ(int_vector.at(0), 0);
}

Allerdings werden dann Elemente um jeweils eine Stelle verschoben (kopiert) was zur Laufzeit in O(n) führt, also O(n²).
Bei vielen Elementen kann es sich lohnen push_back + std::sort zu verwenden, das ist dann in O(n log n)
Zu beachten ist hier zudem, dass die Stelle an der eingefügt werden soll, nicht durch einen Index, sondern durch einen Iterator angegeben wird.

Daten auslesen

Grundsätzlich unterstützt vector sowohl den Index-Operator als auch die at()-Methode:

TEST(VectorTest, VectorGetElement) {
    const std::vector int_vector = {1,2,3,4,5};
    EXPECT_EQ(int_vector[2], 3);
    EXPECT_EQ(int_vector.at(2), 3);
}

Die at()-Methode ist zu bevorzugen, weil sie eine Exception wirft, wenn der Index nicht verfügbar ist.


TEST(VectorTest, VectorGetElementException) {
    const std::vector int_vector = {1,2,3,4,5};
    EXPECT_THROW((void)int_vector.at(10), std::out_of_range);
}

Wenn man am ersten Element im Vektor interessiert ist, kann die front()-Methode benutzt werden. Das letzte Element kann mit back() abgefragt werden.
Aber Vorsicht: auch hier solltest du prüfen, ob der vector nicht leer ist.

TEST(VectorTest, VectorElementBackFront) {
    const std::vector int_vector = {1,2,3};
    if (!int_vector.empty())
    {
        EXPECT_EQ(int_vector.front(), 1);
        EXPECT_EQ(int_vector.back(), 3);
    }
}

Daten löschen

Mit der Methode pop_back() löschst du das letzte Element aus einem Vektor.


TEST(VectorTest, VectorElementPopBack) {
    std::vector int_vector = {1,2,3};
    int_vector.pop_back();
    EXPECT_EQ(int_vector.size(), 2);
}

Mit der Methode clear() kann der komplette Vektor geleert werden. Die Size ist danach auch wieder = bzw. empty wieder true

TEST(VectorTest, VectorClear) {
    std::vector int_vector = {1,2,3};
    int_vector.clear();
    EXPECT_EQ(int_vector.size(), 0);
}

Kapazität vs Größe

Die Kapazität ist die maximal mögliche Anzahl von Elementen, die Größe die wirkliche Anzahl.
Je nach Compiler wird der Vector unterschiedlich vergrößert:
Clang und der GCC verdoppeln die Größe eines Vectors, sobald die Kapazität nicht mehr ausreicht, um ein weiteres Element einzufügen.

MSVC erhöht die Kapazität um lediglich 50 %.

Das Verhalten kann mit folgendem Code überprüft werden:

TEST(VectorTest, VectorPushBack) {
    std::vector int_vector;
    int_vector.push_back(1);
    int_vector.push_back(2);
    int_vector.push_back(3);
    EXPECT_EQ(int_vector.size(), 3);

#if defined(_MSC_VER)
    EXPECT_EQ(int_vector.capacity(), 3);
#elif defined(__clang__) || defined(__GNUC__)
    EXPECT_EQ(int_vector.capacity(), 4);
#endif

    int_vector.push_back(4);
    EXPECT_EQ(int_vector.size(), 4);
    EXPECT_EQ(int_vector.capacity(), 4);

    int_vector.push_back(5);
    EXPECT_EQ(int_vector.size(), 5);

#if defined(_MSC_VER)
    EXPECT_EQ(int_vector.capacity(), 6);
#elif defined(__clang__) || defined(__GNUC__)
    EXPECT_EQ(int_vector.capacity(), 8);
#endif

}

Beide Strategien haben Vor- und Nachteile

Wenn du lieber von vornherein eine explizite Größe vorgeben möchtest, kannst du die reserve()-Funktion benutzen. Dann wird im Vector für die konkrete Kapazität Speicher allokiert.

TEST(VectorTest, VectorReserve) {
    std::vector int_vector;
    int_vector.reserve(100);
    EXPECT_EQ(int_vector.capacity(), 100);
}

emplace_back

Jetzt wird es spannend. Wir haben bisher das push_back auf einfache Datentypen angewendet.
Was passiert aber, wenn wir Objekte in den Vector pushen?

std::vector str_vector;
str_vector.push_back("Hello world");

Hier wird der string erst erzeugt und dann nochmal kopiert. Das ist natürlich ineffizient, weil das initiale Objekt außerhalb des Funktions-Aufrufes nicht verwendet wird. Deshalb sparen wir uns seit C++11 die Kopie, indem wir emplace_back() verwenden.

TEST(VectorTest, VectorEmplaceBackString) {
    std::vector my_vector;
    my_vector.emplace_back("Hello");
    my_vector.emplace_back("World");
    EXPECT_EQ(my_vector.at(0), "Hello");
}