Eigener STL-Container mit Iteratoren: Einführung in `simple_linked_list` für CSCI 340

Warum einen eigenen Container schreiben? Von STL lernen und über den Tellerrand blicken

Die Standard Template Library (STL) ist das Rückgrat moderner C++-Programmierung. Container wie std::vector, std::list und std::map sind extrem nützlich, aber sie bleiben oft eine Blackbox. Die Aufgabe „CSCI 340 Assignment 2b – Writing a Container with Support for Iterators“ fordert dich heraus, diese Blackbox zu öffnen. Du implementierst eine simple_linked_list – eine einfach verkettete Liste – und ihre Iteratoren. Das Ziel: STL-Algorithmen wie std::sort oder std::find sollen mit deinem Container nahtlos funktionieren. Klingt nach trockener Theorie? Nicht, wenn du es mit aktuellen Trends verbindest.

Stell dir vor, du entwickelst eine Leaderboard-App für ein E-Sports-Turnier wie die League of Legends Worlds 2025. Jeder Spieler ist ein Knoten in einer Liste. Um schnell den besten Spieler zu finden oder die Rangliste zu sortieren, brauchst du Iteratoren. Genau diese Fähigkeiten trainierst du hier. Oder denk an eine KI-gestützte Playlist, die Songs in Echtzeit neu ordnet – auch das basiert auf verketteten Listen und Iteratoren.

Die Bausteine: linked_node, simple_linked_list und simple_linked_iterator

Deine Implementierung besteht aus drei Klassen, die in der Datei simple_linked_list.decl.h deklariert sind. Du schreibst den Code in simple_linked_list.h. Die Klasse linked_node ist bereits fertig – sie speichert data und einen Zeiger next. Deine Aufgabe beginnt bei der Liste und den Iteratoren.

Die simple_linked_list: Kernfunktionen

Die Liste verwaltet zwei Zeiger: head und tail. Diese zeigen auf den ersten bzw. letzten Knoten. Der Standardkonstruktor setzt beide auf nullptr. Implementieren musst du unter anderem:

• Range-Konstruktor: template<typename ITERATOR> simple_linked_list(ITERATOR first, ITERATOR last) – kopiert Elemente aus einem beliebigen Iteratorbereich. Das ist typisch für STL-Container.
• empty(): Gibt true zurück, wenn head == nullptr.
• begin() und end(): Liefern einen Iterator auf den ersten Knoten bzw. einen End-Iterator (üblicherweise nullptr).
• front() und back(): Referenzen auf die Daten des ersten bzw. letzten Knotens.
• push_back(const T& value): Hängt einen neuen Knoten an. Achte darauf, dass tail aktualisiert wird.
• pop_back(): Entfernt den letzten Knoten – hier musst du den Vorgänger finden, da es keine Rückwärtsverkettung gibt.
• size(): Zählt die Knoten durch (oder du verwaltest einen Zähler).
• clear(): Löscht alle Knoten und setzt head und tail auf nullptr.
• Destruktor: Ruft clear() auf, um Speicher freizugeben.

Die simple_linked_iterator: Der Schlüssel zu STL-Algorithmen

Ein Iterator kapselt einen Zeiger auf einen Knoten (pos). Du musst folgende Operatoren implementieren:

• Preincrement (++i): Setzt pos = pos->next und gibt *this zurück.
• Postincrement (i++): Speichert den alten Zustand, erhöht dann und gibt die alte Kopie zurück.
• Dereferenz (*i): Gibt pos->data als Referenz zurück.
• Gleichheit (i == j): Vergleicht die pos-Zeiger.

Damit ist dein Iterator ein Forward Iterator – ausreichend für viele STL-Algorithmen. Du kannst z. B. std::for_each oder std::find verwenden.

Praktische Tipps: So vermeidest du typische Fehler

Bei der Implementierung lauern einige Fallstricke:

• Speicherverwaltung: Jeder new-Aufruf braucht ein delete. Vergiss nicht, im Destruktor und in clear() alle Knoten zu löschen.
• Korrektheit von pop_back(): Bei einer einfach verketteten Liste musst du den vorletzten Knoten finden. Das geht nur durch lineare Suche – also Laufzeit O(n). Das ist okay für diese Übung.
• Iterator-Invalidierung: Wenn du die Liste modifizierst, werden bestehende Iteratoren ungültig. Das ist normal – dokumentiere es im Code.
• Testen: Schreibe kleine Unit-Tests, z. B. mit assert. Teste Randfälle: leere Liste, ein Element, viele Elemente.

Trend-Beispiel: Eine KI-Playlist mit deiner Liste

Stell dir vor, du baust eine einfache KI, die Songs basierend auf Benutzerfeedback sortiert. Die Songs sind in deiner simple_linked_list gespeichert. Mit einem Iterator kannst du std::sort (aus deiner assign2-algos.h) verwenden, um die Liste nach Bewertung zu ordnen. Oder du suchst mit std::find nach einem bestimmten Titel. Deine Container-Implementierung macht all das möglich – ohne dass du die Algorithmen anpassen musst.

Aktuell (Mai 2026) ist KI ein Riesenthema. Viele Studierende interessieren sich für Machine Learning und Datenverarbeitung. Deine simple_linked_list könnte als Grundlage für eine einfache Datenstruktur dienen, die in einem KI-Projekt verwendet wird – etwa um Trainingsdaten zu verwalten. Das macht die Aufgabe nicht nur lehrreich, sondern auch zukunftsträchtig.

Wichtige Hinweise zur Abgabe

Arbeite auf einem development-Branch und lasse main unberührt. Am Ende erstellst du einen Pull-Request. Denke daran, deine assign2-algos.h aus dem vorherigen Assignment zu kopieren – die Algorithmen werden für Tests benötigt. Füge keine ausführbaren Dateien hinzu (sie sind groß und werden beim Compilieren neu erzeugt). Du kannst beliebig viele eigene Testdateien schreiben, aber committe sie nicht.

Fazit: Iteratoren verstehen – ein Schlüssel zur C++-Meisterschaft

Indem du einen eigenen STL-Container mit Iteratoren schreibst, gewinnst du tiefe Einblicke in die Funktionsweise der STL. Du lernst Speicherverwaltung, Operatorüberladung und die Konzepte hinter generischer Programmierung. Diese Fähigkeiten sind nicht nur für die Klausur relevant, sondern auch für reale Projekte – ob in der Spieleentwicklung, bei Finanzanwendungen oder in der Robotik. Also: Leg los, implementiere deine simple_linked_list und erlebe, wie STL-Algorithmen auf deinem eigenen Container „einfach funktionieren“.