Please disable Adblockers and enable JavaScript for domain CEWebS.cs.univie.ac.at! We have NO ADS, but they may interfere with some of our course material.
Beispiel "Double Hashing"
"Live"-Implementierung aus den Lehrveranstaltungen vom 29.04. und 13.05.2022
Der Code ist so wie in der Lehrveranstaltung erstellt, daher nicht optimiert und stellenweise auch nicht "schön", eventuell auch fehlerhaft (Fehler bitte im Forum melden).
Download:
ADS_set.h (Funktionsumfang für die erste Projektphase)
Der Film zum Code:
«Aufzeichnung Teil 1 (29.04.2022)» (Handlung beginnt bei Minute 8:00)
Unterlagen zu Double Hashing siehe Unterlagen, Vorlesung Kapitel 3 Vektoren (ab Seite 14).
Abschlussklausur Termin 1 (A)
Es gibt viele zum Teil sehr unterschiedliche Herangehensweisen, die zum Teil datenstruktur- und/oder implementationsabhängig sind, zum Teil auch nicht. Im folgenden ist eine der Lösungsmöglichkeiten am Beispiel Double Hashing beschrieben.
Im wesentlichen ist der Iterator für den Modus speziell so umzubauen, dass beim "Weiterschalten" mittels operator++ jedes dritte Element (mit Ausnahme des letzten Elements) übersprungen wird.
Der Iterator wird um zwei Instanzvariablen erweitert, die angeben, wie viele Elemente im ADS_set enthalten sind (current_size) und beim wievielten Element der Iterator gerade positioniert ist (n).
size_type current_size, n;
Wenn current_size nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem leeren ADS_set ist der Modus speziell ident mit dem Modus normal). Man kann natürlich auch eine gesonderte bool-Variable für den Modus spendieren.
Wir erweitern den Konstruktor entsprechend:
explicit Iterator(Element *e = nullptr, size_type current_size = 0): e{e}, current_size{current_size}, n{1} { if (e) skip(); }
Der neue Konstruktor wird in z() verwendet.
const_iterator z() const { return const_iterator{table, current_size}; }
Zu guter Letzt wird der operator++() erweitert.
Iterator &operator++() {
do { // NEU
++e;
skip();
} while (current_size && ++n % 3 == 0 && n < current_size); //NEU
return *this;
}
Im wesentlichen wird der originale Iterator-Code in eine Schleife eingebettet, die im richtigen Augenblick ein Element überspringt (also den Iteratorcode noch einmal ausführt).
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
Abschlussklausur Termin 1 (B)
Die Aufgabe kann genau wie die Aufgabe A (oben) gelöst werden, wenn im operator++ der Vergleich "++n % 3 == 0" durch "++n % 3 != 1" ersetzt wird.
Zur Abwechslung implementieren wir eine Variante mit zusätzlichem Konstruktor und rekursivem Überspringen.
Die Instanzvariablen werden in-class-initialisiert, damit sie auch in den bestehenden Konstruktoren korrekt initialisiert werden, ohne diese Konstruktoren zu ändern.
size_type current_size{0}, n{0};
Der zusätzliche Konstruktor hat keine Defaultwerte für die Parameter, da sonst ein weiterer Defaultkonstruktor definiert werden würde (das ist verboten).
explicit Iterator(Element *e, size_type current_size): e{e}, current_size{current_size}, n{1} { if (e) skip(); }
Fehlen noch y und der operator++:
const_iterator y() const { return const_iterator{table, current_size}; }
Iterator &operator++() {
++e;
skip();
return current_size && ++n % 3 != 1 && n < current_size ? ++*this : *this;
}
Wenn man dem ternären ?-operator eher skeptisch gegenübersteht, kann man das natürlich auch mit einer if-Anweisung realisieren.
Abschlussklausur Termin 2
Es gibt viele zum Teil sehr unterschiedliche Herangehensweisen, die zum Teil datenstruktur- und/oder implementationsabhängig sind, zum Teil auch nicht. Im folgenden ist eine der Lösungsmöglichkeiten am Beispiel Double Hashing beschrieben.
Im wesentlichen ist der Iterator für den Modus speziell so umzubauen, dass beim "Weiterschalten" mittels operator++ gegebenenfalls solange Werte übersprungen werden, bis das Element an der neuen Iteratorposition größer ist als das Element an der vorhergehenden Iteratorposition.
Der Iterator wird um eine Instanzvariable erweitert, die angibt, ob der Iterator im Modus speziell ist (special).
bool special;
Wir erweitern den Konstruktor entsprechend:
explicit Iterator(Element *e = nullptr, bool special = false): e{e}, special{special} { if (e) skip(); }
Der neue Konstruktor wird in x() verwendet.
const_iterator x() const { return const_iterator{table, true}; }
Zu guter Letzt wird der operator++() erweitert.
Iterator &operator++() {
auto e_pred {e}; // NEU
do { // NEU
++e;
skip();
} while (special && e->mode != Mode::end && std::less<value_type>{}(e->key,e_pred->key)); // NEU
return *this;
}
Im wesentlichen wird der originale Iterator-Code in eine Schleife eingebettet, die im richtigen Augenblick ein Element überspringt (also den Iteratorcode noch einmal ausführt). Vor dem Weiterschalten wird ein Zeiger auf die aktuelle Position gesetzt, um beim Weiterschalten die Werte an der aktuellen und an der neuen Position vergleichen zu können. Beim Weiterschalten ist darauf zu achten, dass der Iterator nicht über das Ende hinausläuft. Auch da gibt es wie immer mehrere Möglichkeiten, wir fragen diesmal die Endmarkierung ab.
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
Abschlussklausur Termin 3
Es gibt viele zum Teil sehr unterschiedliche Herangehensweisen, die zum Teil datenstruktur- und/oder implementationsabhängig sind, zum Teil auch nicht. Im folgenden ist eine der Lösungsmöglichkeiten am Beispiel Double Hashing beschrieben.
Der Iterator wird um zwei Instanzvariablen erweitert, die angeben, wie viele Elemente im ADS_set enthalten sind (current_size) und beim wievielten Element der Iterator gerade positioniert ist (n).
size_type current_size, n;
Wenn current_size nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem leeren ADS_set ist der Modus speziell ident mit dem Modus normal). Man kann natürlich auch eine gesonderte bool-Variable für den Modus spendieren.
Wir erweitern den Konstruktor entsprechend. Der Konstruktor muss nach dem Initialisieren der Instanzvariablen und der Positionierung auf das erste Element im ADS_set (mittels skip() wie bisher) nun im Modus speziell auch die ersten beiden Elemente überspringen (sofern vorhanden). Das erledigt der operator++.
explicit Iterator(Element *e = nullptr, size_type current_size = 0): e{e}, current_size{current_size}, n{1} {
if (e) skip();
if (current_size) ++*this;
}
Der neue Konstruktor wird in w() verwendet.
const_iterator z() const { return const_iterator{table, current_size}; }
Zu guter Letzt wird der operator++() erweitert.
Iterator &operator++() {
do { // NEU
++e;
skip();
} while (current_size && ++n % 3 && n <= current_size); //NEU
return *this;
}
Im wesentlichen wird der originale Iterator-Code in eine Schleife eingebettet, die im richtigen Augenblick ein Element überspringt (also den Iteratorcode noch einmal ausführt).
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
Letzte Änderung: 18.09.2023, 18:25 | 898 Worte