std::vector in C++ verwenden

std::vector ist der am häufigsten verwendete sequenzielle Container in C++. Er stellt ein dynamisches Array in zusammenhängendem Speicher bereit: O(1) zufälliger Zugriff, amortisiert O(1) push_back und meist O(n) für Einfügen/Entfernen in der Mitte (wegen Elementverschiebungen). Dieser Artikel behandelt Kapazitätsverwaltung (size/capacity), Wachstumsverhalten, reserve/resize, push_back vs emplace_back, Iteratorungültigkeit, Speicherlayout (data()), shrink_to_fit sowie Performance-Hinweise.

1) Grundlegende Verwendung

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;                // leer
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    cout << "size=" << v.size()
         << " capacity=" << v.capacity() << "\n";

    cout << v[1] << " " << v.at(2) << "\n"; // [] keine Prüfung, at() mit Prüfung

    for (int x : v) cout << x << " ";
}

size ist die Anzahl der Elemente, während capacity die Anzahl der Elemente angibt, die ohne erneute Speicherallokation gespeichert werden können.

2) Zusammenhängender Speicher & data()

Ein Vector speichert seine Elemente in zusammenhängenden Speicherblöcken, sodass er sicher an C-APIs übergeben werden kann.

#include <cstring>  // memcpy
#include <vector>

int main() {
    vector<char> buf(8, 0);
    const char* msg = "C++";
    memcpy(buf.data(), msg, 3);   // zusammenhängender Speicher
}

Dies ist vorteilhaft für I/O, SIMD, Grafik, Netzwerkpuffer und Interoperabilität mit C-Bibliotheken.

3) Wachstumsstrategie, reserve und resize

• reserve(n): Erhöht die Kapazität auf mindestens n, ohne die Größe zu ändern.
• resize(n): Setzt die Größe auf n (erhöht ggf. die Kapazität).

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;

    v.reserve(1000);          // weniger Reallokationen
    for (int i=0; i<1000; i++)
        v.push_back(i);

    v.resize(1200, -1);       // 200 neue Elemente, Wert -1

    cout << v.size() << " " << v.capacity() << "\n";
}

Der Wachstumsfaktor hängt von der Implementierung ab (typisch ~1,5–2×). Vorauszuweisen (reserve) verbessert die Leistung erheblich.

4) Einfügen & Löschen: push_back vs emplace_back, insert/erase

• push_back(x) erstellt eine Kopie/Move eines Objekts.
• emplace_back(args...) konstruiert das Objekt direkt im Speicher (kein temporäres Objekt).
• insert / erase verschieben Elemente → meistens O(n).

#include <string>
#include <vector>
using namespace std;

struct Book {
    string title;
    double price;
    int pages;
    Book(string t, double p, int s)
        : title(t), price(p), pages(s) {}
};

int main() {
    vector<Book> books;
    books.emplace_back("C++ Primer", 180.0, 950);        // in-place
    books.push_back(Book{"Effective C++", 150.0, 320});  // temporär + move
    books.insert(books.begin(), {"Clean Code", 175.0, 464});
    books.erase(books.begin() + 1);
}

emplace_back ist besonders vorteilhaft bei teuer zu kopierenden Objekten. Bei häufigem Einfügen in der Mitte sollten Sie deque oder list in Betracht ziehen.

5) Iterator-Ungültigkeit

Speicherreallokationen und Elementverschiebungen können Iteratoren, Zeiger und Referenzen ungültig machen.

• Reallokation: macht alle Iteratoren, Referenzen und data() ungültig.
• insert/erase: macht Iteratoren ab der Einfüge-/Löschposition ungültig.

#include <vector>
using namespace std;

int main() {
    vector<int> v{1,2,3};
    auto it = v.begin();
    v.push_back(4);   // könnte reallokieren
    // 'it' könnte jetzt ungültig sein → undefiniertes Verhalten
}

Lösung: reserve verwenden, Iteratoren nach kritischen Operationen neu beziehen.

6) Performance-Tipps

• reserve verwenden, wenn die ungefähre Größe bekannt ist.
• emplace_back für direkte Konstruktion nutzen.
• Move-Semantik nutzen, um unnötige Kopien zu vermeiden.
• Einfügen am Ende bevorzugen; Mitte = O(n).
• clear() setzt Größe auf 0, reduziert aber die Kapazität nicht.
• shrink_to_fit() ist unverbindlich – der Compiler darf es ignorieren.

7) assign, swap, shrink_to_fit

#include <vector>
using namespace std;

int main() {
    vector<int> v{1,2,3,4,5};

    v.assign(3, 9);              // {9, 9, 9}

    vector<int>(v).swap(v);      // Shrink-Idiom
    v.shrink_to_fit();           // Anfrage (nicht garantiert)
}

Das „Shrink-Idiom“ (vector<T>(v).swap(v)) ist oft wirkungsvoller als shrink_to_fit().

8) Sortieren, Suchen & Algorithmen

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> a{5,1,4,2,3};

    sort(a.begin(), a.end());                    // 1 2 3 4 5
    bool found4 = binary_search(a.begin(), a.end(), 4);
    auto pos = lower_bound(a.begin(), a.end(), 3);

    cout << found4 << " @" << (pos - a.begin()) << "\n";
}

Mit C++20 ermöglichen std::ranges elegantere und lesbarere Pipelines.

9) Fortgeschrittenes: Allocator, vector<bool>, Small Objects

• Allocator: für eigene Speicherpools, Tracking, Alignment.
• vector<bool>: bitgepackte Spezialisierung; Achtung auf Proxy-Referenzen.
• Small-Object-Optimierung: betrifft std::string, nicht vector.

10) Beispiel: Buchliste

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

struct Book {
    string title;
    double price;
    int pages;
    Book(string t, double p, int s)
        : title(move(t)), price(p), pages(s) {}
};

int main() {
    vector<Book> books;
    books.reserve(4);

    books.emplace_back("C++ Primer", 180.0, 950);
    books.emplace_back("Effective C++", 150.0, 320);
    books.emplace_back("Clean Code", 175.0, 464);

    sort(books.begin(), books.end(),
         [](const Book& a, const Book& b){
             return a.price < b.price;
         });

    auto it = find_if(books.begin(), books.end(),
        [](const Book& b){ return b.price >= 160.0; });

    if (it != books.end())
        cout << it->title << " " << it->price << "\n";
}

11) Häufige Fehler

• Vector für häufiges Einfügen in der Mitte verwenden → besser deque oder list.
• Ungültige Iteratoren nach Reallokation weiterverwenden.
• Unnötige Kopien → Move-/Emplace-Techniken nutzen.
• Fehlende Nutzung von reserve bei bekannter Zielgröße.
• Annahme, dass vector<bool> wie ein normaler Vector funktioniert.

12) TL;DR

Ähnliche Artikel