C++-Containerklassen<list>
Die C++-Standardbibliothek bietet eine Vielzahl von Funktionen, unter denen<list>eine sehr wichtige Containerklasse zum Speichern von Elementsammlungen ist, die bidirektionale Iteratoren unterstützt.
<list>ist ein Sequenzcontainer in der C++ Standard Template Library (STL), der schnelles Einfügen und Löschen von Elementen an jeder Position im Container ermöglicht. Im Gegensatz zu Arrays oder Vektoren (<vector>) anders,<list>muss bei der Erstellung keine Größe angeben und kann Elemente an jeder Position hinzufügen oder entfernen, ohne Speicher neu zuzuweisen.
Syntax
Die folgenden sind<list>Einige grundlegende Operationen von Containern:
- Header-Datei einbinden:
#include <list> - Eine Liste deklarieren:
std::list<T> mylist;, wobeiTIst der Typ der in der Liste gespeicherten Elemente. - Elemente einfügen:
mylist.push_back(value); - Element löschen:
mylist.pop_back();odermylist.erase(iterator); - Auf Elemente zugreifen:
mylist.front();undmylist.back(); - Durchlaufen der Liste: Verwenden von Iteratoren
for (auto it = mylist.begin(); it != mylist.end(); ++it)
Funktionen
- Bidirektionale Iteration：
<list>bietet bidirektionale Iteratoren, wodurch Elemente vorwärts und rückwärts durchlaufen werden können. - Dynamische Größe: Anders als bei Arrays,
<list>Die Größe kann sich dynamisch ändern, ohne dass eine feste Menge Speicher vorab reserviert werden muss. - Schnelles Einfügen und Löschen: Elemente können an jeder Position in der Liste schnell eingefügt oder entfernt werden, ohne dass eine große Anzahl von Elementen verschoben werden muss, wie es bei Vektoren der Fall wäre.
Deklaration und Initialisierung
<list>Die Deklaration und Initialisierung sind ähnlich wie bei anderen Containern:
#include <iostream>
#include <list>
int main() {
std::list<int> lst1; // 空的list
std::list<int> lst2(5); // 包含5个默认初始化元素的list
std::list<int> lst3(5, 10); // 包含5个元素，每个元素为10
std::list<int> lst4 = {1, 2, 3, 4}; // 使用初始化列表
return 0;
}
Beispiel
Nachfolgend ein Beispiel unter Verwendung von<list>Ein einfaches Beispiel, das das Erstellen einer Liste, das Hinzufügen von Elementen, das Durchlaufen der Liste und die Ausgabe der Ergebnisse umfasst.
Beispiel
#include <iostream>
#include <list>
int main() {
// eine Liste vom Typ Integer erstellen
std::list<int> numbers;
// Elemente zur Liste hinzufügen
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// auf das erste Element der Liste zugreifen und es ausgeben
std::cout << "Erstes Element: " << numbers.front() << std::endl;
// auf das letzte Element der Liste zugreifen und es ausgeben
std::cout << "Last element: " << numbers.back() << std::endl;
// die Liste durchlaufen und alle Elemente ausgeben
std::cout << "Listenelemente: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// das letzte Element in der Liste löschen
numbers.pop_back();
// die Liste erneut durchlaufen und alle Elemente ausgeben
std::cout << "Listenelemente nach dem Entfernen des letzten Elements: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
// eine Liste vom Typ Integer erstellen
std::list<int> numbers;
// Elemente zur Liste hinzufügen
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// auf das erste Element der Liste zugreifen und es ausgeben
std::cout << "Erstes Element: " << numbers.front() << std::endl;
// auf das letzte Element der Liste zugreifen und es ausgeben
std::cout << "Last element: " << numbers.back() << std::endl;
// die Liste durchlaufen und alle Elemente ausgeben
std::cout << "Listenelemente: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// das letzte Element in der Liste löschen
numbers.pop_back();
// die Liste erneut durchlaufen und alle Elemente ausgeben
std::cout << "Listenelemente nach dem Entfernen des letzten Elements: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
Ausgabe:
First element: 10 Last element: 30 List elements: 10 20 30 List elements after removing the last element: 10 20
Übliche Memberfunktionen
Die folgenden sind<list>Einige häufig verwendete Memberfunktionen:
| Funktion | Beschreibung |
|---|---|
push_back(const T& val) |
Ein Element am Ende der verketteten Liste hinzufügen |
push_front(const T& val) |
Ein Element am Kopf der verketteten Liste hinzufügen |
pop_back() |
Das Element am Ende der verketteten Liste entfernen |
pop_front() |
Das Element am Kopf der verketteten Liste entfernen |
insert(iterator pos, val) |
Ein Element an einer angegebenen Position einfügen |
erase(iterator pos) |
Das Element an einer angegebenen Position entfernen |
clear() |
Alle Elemente löschen |
size() |
Die Anzahl der Elemente in der verketteten Liste zurückgeben |
empty() |
Prüfen, ob die verkettete Liste leer ist |
front() |
Das erste Element der verketteten Liste zurückgeben |
back() |
Das letzte Element der verketteten Liste zurückgeben |
remove(const T& val) |
Alle Elemente entfernen, die einem angegebenen Wert entsprechen |
sort() |
Die Elemente in der verketteten Liste sortieren |
merge(list& other) |
Eine weitere sortierte verkettete Liste zusammenführen |
reverse() |
Verkettete Liste umkehren |
begin() / end() |
Die Begin-/End-Iteratoren der verketteten Liste zurückgeben |
Beispiel
1. Grundlegende Operationen
Beispiel
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {10, 20, 30};
// Elemente einfügen und löschen
lst.push_front(5); // 5 am Kopf einfügen
lst.push_back(40); // 40 am Ende einfügen
lst.pop_front(); // Das Kopfelement löschen
lst.pop_back(); // Das Endelement löschen
// Inhalt der verketteten Liste ausgeben
std::cout << "Listenelemente: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {10, 20, 30};
// Elemente einfügen und löschen
lst.push_front(5); // 5 am Kopf einfügen
lst.push_back(40); // 40 am Ende einfügen
lst.pop_front(); // Das Kopfelement löschen
lst.pop_back(); // Das Endelement löschen
// Inhalt der verketteten Liste ausgeben
std::cout << "Listenelemente: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
2. Einfügen und Löschen von Elementen an bestimmten Positionen
Beispiel
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // Den Iterator zum 3. Element verschieben (Wert 3)
lst.insert(it, 10); // 10 vor dem 3. Element einfügen
lst.erase(it); // Das 3. Element löschen
// Inhalt der verketteten Liste ausgeben
std::cout << "Listenelemente: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // Den Iterator zum 3. Element verschieben (Wert 3)
lst.insert(it, 10); // 10 vor dem 3. Element einfügen
lst.erase(it); // Das 3. Element löschen
// Inhalt der verketteten Liste ausgeben
std::cout << "Listenelemente: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
3. Sortieren und Duplikate entfernen
Beispiel
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
lst.sort(); // Sortieren
lst.unique(); // Benachbarte Duplikate entfernen
// Inhalt der verketteten Liste ausgeben
std::cout << "Sortierte und duplikatfreie Liste: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
lst.sort(); // Sortieren
lst.unique(); // Benachbarte Duplikate entfernen
// Inhalt der verketteten Liste ausgeben
std::cout << "Sortierte und duplikatfreie Liste: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
4. Zusammenführen und Umkehren
Beispiel
#include <iostream>
#include <list>
int main() {
std::list<int> lst1 = {1, 3, 5, 7};
std::list<int> lst2 = {2, 4, 6, 8};
lst1.merge(lst2); // Zwei sortierte verkettete Listen zusammenführen
lst1.reverse(); // Verkettete Liste umkehren
// Inhalt der verketteten Liste ausgeben
std::cout << "Zusammengeführte und umgekehrte Liste: ";
for (const auto& elem : lst1) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst1 = {1, 3, 5, 7};
std::list<int> lst2 = {2, 4, 6, 8};
lst1.merge(lst2); // Zwei sortierte verkettete Listen zusammenführen
lst1.reverse(); // Verkettete Liste umkehren
// Inhalt der verketteten Liste ausgeben
std::cout << "Zusammengeführte und umgekehrte Liste: ";
for (const auto& elem : lst1) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
Vergleich mit anderen Containern
| Funktionen | std::list | std::vector | std::deque |
|---|---|---|---|
| Speicherstruktur | Nicht zusammenhängender Speicher, doppelt verkettete Liste | Zusammenhängender Speicher | Segmentierter zusammenhängender Speicher |
| Zugriffsleistung | Sequenzieller Zugriff ist schnell, wahlfreier Zugriff ist langsam | Schneller wahlfreier Zugriff | Zugriff sowohl am Ende als auch am Anfang ist schnell |
| Leistung beim Einfügen/Löschen | Einfügen und Löschen an beliebiger Position sind schnell | Einfügen am Ende ist schnell, in der Mitte jedoch langsam | Einfügen und Löschen am Anfang und am Ende sind schnell |
| Anwendbare Szenarien | Häufiges Einfügen/Löschen in der Mitte | Erfordert effizienten wahlfreien Zugriff | Schnelles Einfügen/Löschen am Anfang und am Ende erforderlich |
| Iteratorstabilität | Stabil; Einfügen oder Löschen von Elementen führt nicht zum Ungültigwerden | Einfügen und Löschen können zur Iterator-Invalidierung führen | Einfügen und Löschen können zur Iterator-Invalidierung führen |
Hinweise
<list>Die Elemente werden in Einfügereihenfolge gespeichert, nicht nach Elementwert sortiert.- Aufgrund von
<list>Die Elemente werden an unterschiedlichen Speicherorten gespeichert, daher ist es nicht für Szenarien geeignet, die wahlfreien Zugriff erfordern. - Im Vergleich zu Vektoren,
<list>Die Effizienz der Speichernutzung ist gering, da jedes Element zusätzlichen Speicherplatz benötigt, um Zeiger auf das vorherige und das nächste Element zu speichern.
Durch diese einfache Einführung und Beispiele sollten Anfänger in der Lage sein, ein grundlegendes Verständnis für C++-<list>Container zu erlangen und damit zu beginnen, ihn zur Lösung realer Probleme einzusetzen.