Was ist der Unterschied zwischen den Containern vector und list in C++?

std::vector stellt ein dynamisches Array dar. Die Daten werden in einem zusammenhängenden Speicherblock gespeichert.

Vorteile von vector:

• Schneller Zugriff per Index (O(1)).
• Gute Datenlokalität, nützlich für den CPU-Cache.
• Schnelles Hinzufügen/Entfernen am Ende (durchschnittlich O(1)).

Nachteile von vector:

• Komplexität bei Einfügen/Entfernen an beliebigen Stellen (O(n)).
• Speicherneuzuweisung beim Wachsen, erfordert Kopieren der Elemente.

std::list ist eine doppelt verkettete Liste. Jedes Element speichert Zeiger auf das vorherige und das nächste Element.

Vorteile von list:

• Komplexität bei Einfügen/Entfernen an beliebigen Stellen (O(1)), nachdem die Position gefunden wurde (kann O(n) sein).
• Erfordert keinen zusammenhängenden Speicherblock.

Nachteile von list:

• Langsamer Zugriff per Index (O(n)).
• Verbraucht mehr Speicher pro Element (aufgrund der Zeiger).
• Schlechte Datenlokalität.

Hauptunterschied:

Eigenschaft	std::vector	std::list
Datenstruktur	Dynamisches Array	Doppelt verkettete Liste
Datenspeicherung	Kontinuierlicher Speicher	Knoten mit Zeigern
Zugriff per Index	O(1)	O(n)
Einfügen/Entfernen	O(n) (außer am Ende)	O(1) (nach Iterator)
Lokalität	Gut	Schlecht
Speicherverbrauch	Elemente	Elemente + Zeiger

Die Wahl zwischen vector und list hängt von den typischen Operationen mit dem Container ab. Wenn häufig zufälliger Zugriff und Hinzufügen/Entfernen am Ende erforderlich sind, ist vector vorzuziehen. Wenn häufige Einfügungen/Entfernungen in der Mitte der Liste wichtig sind, ist list vorzuziehen.