C++ vector-Container

In C++,vectorEs ist einer der am häufigsten verwendeten STL-Container.

vectorIm Wesentlichen ist es einEin dynamisches Array, das sich automatisch erweitern kann.Im Vergleich zu traditionellen Arrays erfordert vector keine manuelle Speicherverwaltung und kann sich automatisch entsprechend der Anzahl der Elemente erweitern.

Denn vector hat:

  • Zusammenhängende Speicherung
  • Schneller wahlfreier Zugriff
  • Vollständiges STL-Ökosystem
  • Cache-freundlich

Daher ist vector in der modernen C++-Entwicklung die bevorzugte Wahl für die meisten Szenarien der sequenziellen Datenspeicherung.

Kernmerkmale von vector

  • Dynamische Größe:vector kann sich automatisch erweitern und verkleinern.
  • Zusammenhängender Speicher:Elemente werden zusammenhängend im Speicher abgelegt, daher ist die Zugriffseffizienz sehr hoch.
  • Wahlfreier Zugriff:Es unterstützt schnellen Zugriff auf Elemente über den Index, mit einer Zeitkomplexität von O(1).
  • Automatische Speicherverwaltung:Kein manuelles malloc/free erforderlich.
  • Unterstützt Iteratoren:Er kann leicht zusammen mit STL-Algorithmen verwendet werden.

Warum ist vector schnell?

Die Elemente in einem vector sind zusammenhängend im Speicher angeordnet:

[1][2][3][4][5]

Dieses Layout ist sehr CPU-Cache-freundlich.

Wenn die CPU das erste Element liest, lädt sie normalerweise die folgenden Daten im Voraus in den Cache, daher ist die Iteration über einen vector normalerweise sehr schnell.

Das ist auch der Grund, warum in vielen Fällen:

vector 比 list 更快

Obwohl list eine geringere theoretische Löschkomplexität hat.

vector verwenden

Bevor Sie vector verwenden, müssen Sie die Header-Datei einbinden:

#include <vector>

vector erstellen

Einen leeren vector erstellen:

std::vector<int>vec;

Anfangsgröße angeben:

std::vector<int>vec(5);

Der obige Code erstellt 5 Elemente mit dem Standardwert 0.

Initialwert angeben:

std::vector<int>vec(5, 10);

Erstellungsergebnis:

[10, 10, 10, 10, 10]

Initialisierungsliste verwenden:

std::vector<int>vec = {1, 2, 3, 4};

Elemente hinzufügen

Nutzungpush_back()Elemente am Ende hinzufügen:

vec.push_back(100);

Die durchschnittliche Zeitkomplexität beim Anhängen eines Elements an das Ende eines Vektors ist:

O(1)

Zugriff auf Elemente

Zugriff über Indizes:

int x = vec[0];

Nutzungat()： 

int y = vec.at(1);

Unterschied:

  • []Keine Bereichsprüfung, schneller.
  • at()Bereichsprüfung wird durchgeführt, sicherer.

Größe ermitteln

vec.size();

Gibt die aktuelle Anzahl der Elemente zurück.

Der Unterschied zwischen Größe und Kapazität

Dies ist eines der wichtigsten Konzepte des Vektors.

std::vector<int>vec;

vec.push_back(1);
vec.push_back(2);

std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl;

Die Ausgabe kann wie folgt aussehen:

2
4
  • Größe：Aktuelle Anzahl der Elemente.
  • Kapazität：Die aktuell zugewiesene Speicherkapazität.

Die Kapazität ist normalerweise größer als oder gleich der Größe.

Der Grund dafür ist, dass der Vektor im Voraus mehr Speicher anfordert, um häufige Neuzuweisungen zu reduzieren.

Vektor-Erweiterungsmechanismus

Wenn die Kapazität eines Vektors nicht ausreicht, erfolgt eine Neuzuweisung:

  1. Größeren Speicher zuweisen
  2. Alte Elemente kopieren
  3. Alten Speicher freigeben

Dieser Vorgang ist relativ kostspielig.

Zum Beispiel:

std::vector<int>vec;

for (int i = 0; i < 1000000; i++) {
    vec.push_back(i);
}

Es kann zu mehrfachen Speicher-Neuallokationen kommen.

reserve() reserviert Speicher im Voraus.

Um häufige Neuallokationen zu vermeiden, kann Speicher im Voraus zugewiesen werden:

std::vector<int>vec;

vec.reserve(1000000);

Dies kann reduzieren:

  • Speicher-Neuallokation
  • Kopieren von Elementen
  • Performance-Overhead

Dies ist eine sehr wichtige Optimierungstechnik in der Ingenieurentwicklung.

Durchlaufen eines Vektors

Verwendung des Indexoperators

for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

Verwendung von Iteratoren

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

Bereichsbasierte for-Schleife

for (int element : vec) {
    std::cout << element << " ";
}

Element löschen

Das dritte Element löschen:

vec.erase(vec.begin() + 2);

Hinweis:

Wenn ein vector ein Element in der Mitte löscht, werden die nachfolgenden Elemente als Ganzes nach vorne verschoben.

Zum Beispiel:

1 2 3 4 5

删除 2 后：

1 3 4 5

Wobei:

3 4 5

Alle müssen verschoben werden.

Daher:

erase() 的时间复杂度为 O(n)

Szenarien, in denen vector nicht geeignet ist

  • Häufiges Einfügen am Anfang
  • Häufiges Löschen in der Mitte
  • Häufige Erweiterung mit übergroßen Objekten

Zum Beispiel:

vec.insert(vec.begin(), 100);

Dies ist eine relativ langsame Operation.

Iterator-Invalidierung

Nach der Neuallokation von vector können die ursprünglichen Speicheradressen ungültig werden.

Zum Beispiel:

std::vector<int>vec = {1, 2, 3};

auto it = vec.begin();

vec.push_back(4);

std::cout << *it;

hieritMöglicherweise ungültig geworden.

Weil push_back() eine Speicherneuallokation verursachen kann.

Dies ist einer der häufigsten Fallstricke von vector.

Hinweise zu clear()

vec.clear();

clear() löscht nur die Elemente:

  • size wird 0
  • Die Kapazität kann weiterhin beibehalten werden.

Das heißt:

clear() 不一定释放内存

Wenn Sie Speicher freigeben möchten:

std::vector<int>().swap(vec);

Oder:

vec.shrink_to_fit();

push_back und emplace_back

Modernes C++ empfiehlt die Verwendung von:

emplace_back()

Zum Beispiel:

vec.push_back(Person("Tom", 20));

Es können temporäre Objekte erzeugt werden.

Und:

vec.emplace_back("Tom", 20);

Es konstruiert das Objekt direkt an Ort und Stelle im vector.

Normalerweise effizienter.

Unterschiede zwischen vector und array

Funktionen array vector
Feste Größe Ja nein
Automatische Größenänderung nein Ja
Zusammenhängender Speicher Ja Ja
Wahlfreier Zugriff Schnell Schnell
STL-Unterstützung Weniger Vollständig
Sicherer Zugriff Keine at()

Komplexität gängiger vector-Operationen

Aktion Zeitkomplexität
Wahlfreier Zugriff O(1)
push_back Durchschnittlich O(1)
Löschen am Ende O(1)
Einfügen am Anfang O(n)
Löschen in der Mitte O(n)
clear O(n)

Beispiel: Notenverwaltung für Studierende

Beispiel


#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int>scores = {85, 90, 78, 92};
    scores.push_back(88);
    std::cout << Alle Punktzahlen:;
    for (int score : scores) {
        std::cout << score << " ";
    }

    std::cout << std::endl;
    int total = std::accumulate(scores.begin(), scores.end(), 0);
    double average = total * 1.0 / scores.size();
    std::cout << Durchschnittliche Punktzahl: << average << std::endl;
    scores.erase(scores.begin() + 2);
    std::cout << Punkte nach dem Löschen:;
    for (int score : scores) {
        std::cout << score << " ";
    }

    std::cout << std::endl;

    return 0;
}

Das Ausgabeergebnis ist wie folgt:

所有成绩: 85 90 78 92 88 
平均成绩: 86.6
删除后成绩: 85 90 92 88

Zusammenfassung

vector ist eine der wichtigsten und am häufigsten verwendeten Datenstrukturen im modernen C++.

Seine Kernvorteile:

  • Dynamische Größenanpassung
  • Zusammenhängender Speicher
  • Schneller wahlfreier Zugriff
  • Cache-freundlich
  • Vollständiges STL-Ökosystem

Beachten Sie jedoch gleichzeitig:

  • Leistungskosten der Erweiterung
  • Geringe Effizienz beim Löschen in der Mitte
  • Problem der Iterator-Invalidierung

Für die überwiegende Mehrheit der sequenziellen Speicherszenarien:

vector 通常都是默认首选容器
Weitere Erweiterungen