[C Elementary] Vorläufiges Verständnis der Liste class

[C Elementary] Vorläufiges Verständnis der Listenklasse

2024-07-12

1. StandardbibliothekListeArt

Die unterste Ebene der Liste ist eine bidirektionale, zirkulär verknüpfte Listenstruktur mit Sentinel-Bits.
Im Vergleich zur einfach verknüpften Listenstruktur von forward_list ist der Iterator von list ein bidirektionaler Iterator
Im Vergleich zu sequentiell strukturierten Containern wie Vektoren ist die Liste beim Einfügen und Löschen an jeder Position effizienter, unterstützt jedoch keinen wahlfreien Zugriff an jeder Position.
List ist eine Vorlagenklasse. Bei der Verwendung müssen wir den Typ des Elements angeben.

Wenn Sie die Listenklasse verwenden, müssen Sie die Header-Datei einbinden<list>

2. Gemeinsame Schnittstellen der Listenklasse

1. Häufig verwendete Konstruktoren

1. Standardkonstruktor, erstellt eine leere verknüpfte Liste

list();

Zum Beispiel:


void test()
{
	list<int> lt;
}

2. Erstellen Sie ein Listenobjekt und initialisieren Sie es mit n Werten

list(size_type n, const value_type& val =  value_type());

Zum Beispiel:


void test()
{
	list<int> lt(3, 1);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

3.Kopieren Sie den Konstruktor der Listenklasse

list(const list& x);

Zum Beispiel:


void test()
{
	list<int> lt(3, 1);
	list<int> lt1(lt);
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

4. Verwenden Sie den Initialisierungskonstruktor des Iterators


Template<class InputIterator>
 
list(InputIterator first, InputIterator last);

Zum Beispiel:


void test()
{
	list<int> lt(3, 1);
	list<int> lt1(lt.begin(), lt.end());
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

2. Häufig verwendete Kapazitätsschnittstellen

Es ist immer noch dasselbe, lasst mich hier gemeinsam darüber reden.

1.Größe,leer,max_size,Größe ändern

Größe:zurückkehrenverlinkte ListeDie Anzahl der Elemente im Container.
size_type size() const;
leer:zurückkehrenListeOb der Behälter leer ist (d. h. seineGrößeist 0).
(Hinweis: Diese Funktion verändert den Container in keiner Weise. Zum Löschenverlinkte ListeDen Inhalt des Behälters finden Sie unterListe::löschen。）
bool empty() const;
maximale Größe(nicht häufig verwendet): Rückkehrverlinkte ListeDie maximale Anzahl von Elementen, die der Container enthalten kann.
(Aufgrund bekannter Einschränkungen bei der System- oder Bibliotheksimplementierung ist dies das maximale Potenzial, das ein Container erreichen kannGröße , es gibt jedoch keine Garantie dafür, dass der Container diese Größe erreicht: Möglicherweise ist er dennoch nicht in der Lage, zu irgendeinem Zeitpunkt vor Erreichen dieser Größe Speicher zuzuweisen. )
size_type max_size() const;
Größe ändern:Ändern Sie die Größe des Containers, den er enthalten sollNElemente.
WennNkleiner als der aktuelle ContainerGröße, wird der Inhalt auf den vorherigen Wert reduziertNElemente entfernen, diejenigen entfernen, die darüber hinausgehen (und sie zerstören).
WennNGrößer als der aktuelle ContainerGrößeAnschließend wird der Inhalt erweitert, indem am Ende die erforderliche Anzahl von Elementen eingefügt wird, um dies zu erreichenN die Größe von.Falls angegebenWert, dann wird das neue Element initialisiertWertKopien, andernfalls werden sie wertinitialisiert.
(Beachten Sie, dass diese Funktion den tatsächlichen Inhalt des Containers ändert, indem sie Elemente in den Container einfügt oder löscht.)
void resize (size_type n, value_type val = value_type());

Zum Beispiel:


void test()
{
	list<int> lt(3, 1);
	/*list<int> lt1(lt);*/
	list<int> lt1(lt.begin(), lt.end());
	list<int> lt2;
	cout << lt1.size() <<endl;
	cout << lt1.empty() <<endl;
	cout << lt2.empty() <<endl;
	lt1.resize(10);
	cout << lt1.size() << endl;
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

3. Gemeinsamer Zugriff und Durchquerung

1.Iterator


iterator begin();
 
const_iterator begin() const;
 
iterator end();
 
const_iterator end() const;

Iterator: Wird verwendet, um die Position des ersten Knotens und des letzten Knotens in der verknüpften Liste zu ermittelnNächste Position (d. h. Sentinel-Position)

Zum Beispiel:


void test()
{
	list<int> lt(5, 2);
	list<int> ::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
}

Operationsergebnis:

2. Umgekehrter Iterator

umgekehrter Iterator rbegin();

rbegin() const;

reverse_iterator rend();

: const_reverse_iterator rend() const;

Umgekehrter Iterator, rbegin ruft die Position des letzten Knotens im Container ab, rend ruft die Position des Sentinel-Bits im Container ab


void test()
{
	list<int> lt = { 1,23,4,4,5,2 };
	list<int> ::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
}

Operationsergebnis:

Hinweis: Das Reverse-Iterator-Rit sollte auch ++ anstelle von -- verwenden.

3.Vorne und Hinten

Vorderseite:

Referenzfront();

const_reference vorne() const;

Gibt einen Verweis auf die Daten zurück, die im ersten Knoten der verknüpften Liste gespeichert sind

zurück:

Referenz zurück();

const_reference zurück() const;

Gibt einen Verweis auf die Daten zurück, die im letzten Knoten der verknüpften Liste gespeichert sind

Zum Beispiel:


void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.front() << endl;
	cout << lt.back() << endl;
 
}

Operationsergebnis:

4. Liste hinzufügen, löschen, prüfen und ändern

1) push_front und pop_front

push_front wird als Kopfeinfügung bezeichnet und fügt ein Element aus dem Kopf der verknüpften Liste ein

void push_front(const wert_typ& val);

pop_front wird als Kopflöschung bezeichnet und löscht ein Element aus dem Kopf der verknüpften Liste.

ungültige Popup-Front();

void pop_front();

Zum Beispiel:


void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.front() << endl;
	lt.push_front(21345);
	cout << lt.front() << endl;
	lt.pop_front();
	cout << lt.front() << endl;
}

Operationsergebnis:

2) push_back und pop_back

push_back heißt Tail Insertion und fügt ein Element vom Ende der verknüpften Liste ein

void push_back(const wert_typ& val);

pop_back heißt tail deletion und löscht ein Element vom Ende der verknüpften Liste.

ungültiger Popup-Zurück();

Zum Beispiel:


void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.back() << endl;
	lt.push_back(21345);
	cout << lt.back() << endl;
	lt.pop_back();
	cout << lt.back() << endl;
}

Operationsergebnis:

3) finden


template <class InputIterator, class T>
 
InputIterator find(InputIterator first, InputIterator last, const T& val);

Finden Sie val im Bereich von zwei Iteratoren und geben Sie den Iterator dort zurück, wo er sich befindet

Zum Beispiel:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	*pos = 114514;
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

Hinweis: Diese Funktion ist keine Mitgliedsfunktion der Liste, sondern eine Funktion in der Standardbibliothek. Mehrere Container teilen sich die Suchfunktion.

Wie Sie sehen, können wir den Iterator der Liste direkt dereferenzieren und seinen Inhalt ändern, aber sollte der Iterator nicht auf den Knoten verweisen? Warum kann die Dereferenzierung die Daten verändern?

Tatsächlich wird der Iterator der Liste nicht mithilfe des ursprünglichen ökologischen Zeigers simuliert und implementiert, sondern muss unten gekapselt werden, was sich im Quellcode der simulierten Implementierung der Liste widerspiegelt.

4) einfügen

Iterator einfügen (Iteratorposition, const value_type & val);

void insert(Iteratorposition, Größentyp n, const Werttyp& Wert);

————————————————————————————————————————

Vorlage<class InputIterator>

void insert(Iteratorposition, InputIterator zuerst, InputIterator zuletzt);

Fügen Sie ein oder mehrere Elemente vor Position ein

Zum Beispiel:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	lt.insert(pos, 8848);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

Aufmerksame Schüler haben vielleicht herausgefunden, dass die Einfügeoperation einer Liste funktioniertFührt nicht dazu, dass der Iterator ungültig wird, da der Knoten, auf den pos zeigt, unverändert bleibt und sich die relative Position nicht ändert.

Der Löschvorgang der Liste führt jedoch definitiv dazu, dass der Iterator ungültig wird und nur der Iterator, der auf den gelöschten Knoten zeigt, ungültig wird und andere Iteratoren nicht betroffen sind.

5) löschen


iterator erase(iterator position);
 
iterator erase(iterator first, iterator last);

Löschen Sie das Element an der Position oder alle Elemente im Bereich [erstes, letztes]

Zum Beispiel:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	lt.erase(lt.begin());
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

Operationsergebnis:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
	lt.erase(lt.begin(),pos);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

6) tauschen

void swap(Vektor&x);

Tauschen Sie zwei Listenobjekte aus

Zum Beispiel:


void test()
{
	list<int> lt;
	list<int> lt2(6, 12);
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.swap(lt2);
	for (auto i : lt2)
	{
		cout << i << " ";
	}
	cout << endl;
}

Operationsergebnis:

7) zuweisen

Vorlage<class InputIterator>

void zuweisen (InputIterator zuerst, InputIterator zuletzt);

void zuweisen(Größentyp n, const Werttyp& Wert);

Geben Sie neuen Inhalt für die Liste an, ersetzen Sie den aktuellen Inhalt und ändern Sie die Anzahl der Knoten

Zum Beispiel:


void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.assign(4, 0);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

Operationsergebnis:

8) löschen

ungültig löschen();

Löschen Sie alle Knoten in der verknüpften Liste

Zum Beispiel:


void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.clear();
	cout << lt.size() << endl;
}

Operationsergebnis:

5. Schnittstelle zur Änderung der Listenbestellung

(1）Sortieren

ungültige Sortierung();

Vorlage<class Compare>

void sort(Vergleiche Komp);

Aufgrund der Besonderheit der Listenstruktur kann die Sortierfunktion in der Standardbibliothek nicht verwendet werden, da der Iterator keine Subtraktionsoperationen durchführen kann.

Und in der C++-Dokumentation können wir sehen, dass die Sortierung in der Standardbibliothek auch den Typ des Iterators auf Direktzugriff (RandomAccess) beschränkt.


default (1)	
template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)	
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Iteratoren haben mehrere Funktionskategorien:

Einweg-Iterator, kann nur ++ ausführen
Bidirektionaler Iterator, kann ++ und - sein
Zufälliger Iterator, kann ++, --, + und - sein

Die Sortierfunktion der Liste ist jedoch nicht erforderlich, da die Effizienz des direkten Sortierens der verknüpften Liste viel langsamer ist als das Kopieren in den Vektor, das Sortieren und das anschließende Zurückkopieren in die verknüpfte Liste.

(2）umkehren

template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

Kehren Sie die verknüpfte Liste um

Zum Beispiel:


void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	for (auto i : lt)
	{
		cout << i << " ";
	}
	cout << endl;
	lt.reverse();
	for (auto i : lt)
	{
		cout << i << " ";
	}
	cout << endl;
 
}

Operationsergebnis:

Wenn es Fehler gibt, korrigieren Sie mich bitte.

Technologieaustausch

[C Elementary] Vorläufiges Verständnis der Listenklasse

1. StandardbibliothekListeArt

2. Gemeinsame Schnittstellen der Listenklasse

1. Häufig verwendete Konstruktoren

1. Standardkonstruktor, erstellt eine leere verknüpfte Liste

2. Erstellen Sie ein Listenobjekt und initialisieren Sie es mit n Werten

3.Kopieren Sie den Konstruktor der Listenklasse

4. Verwenden Sie den Initialisierungskonstruktor des Iterators

2. Häufig verwendete Kapazitätsschnittstellen

1.Größe,leer,max_size,Größe ändern

3. Gemeinsamer Zugriff und Durchquerung

1.Iterator

2. Umgekehrter Iterator

3.Vorne und Hinten

4. Liste hinzufügen, löschen, prüfen und ändern

1) push_front und pop_front

2) push_back und pop_back

3) finden

4) einfügen

5) löschen

6) tauschen

7) zuweisen

8) löschen

5. Schnittstelle zur Änderung der Listenbestellung

(1）Sortieren

(2）umkehren

Persönliches Profil

meine Kontaktdaten