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 1A
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 dieser beim Erreichen des letzten Elements auf das erste Element gesetzt wird, und beim nächsten Weiterschalten auf end().
Der Iterator wird um zwei Instanzvariablen erweitert. n enthält die Anzahl der Elemente im ADS_set (und wird in weiterer Folge auch als Zähler verwendet), save_e speichert die Position des ersten Elements, und später die Position des letzten Elements. Wenn in einer Datenstruktur mehrere Instanzvariablen im Iterator für die Positionierung erfoderlich sind, so sind in der Regel alle diese Instanzvariablen zu sichern.
size_type n {0};
Element *save_e {nullptr};
Wenn n nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem ADS_set mit weniger als zwei Elementen 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 n = 0): e{e}, n{n} {
if (this->e) skip();
if (this->n) this->save_e = this->e;
}
Im Konstruktor wird save_e gesetzt. Jeder funktionierende Iterator zeigt (sofern das ADS_set nicht leer ist) am Ende des Konstruktors definitionsgemäß auf das erste Element. Das ist daher die ideale Stelle für diese Aktion.
Der neue Konstruktor wird in z() verwendet.
const_iterator z() const {
if (size() < 2) return begin();
return const_iterator{table,size()};
}
Zu guter Letzt wird der operator++() um zwei Zeilen erweitert. Wenn der Iterator im Modus speziell beim letzten Element angekommen ist (n && –n == 1), dann wird der Iterator auf das erste Element gesetzt. Zugleich wird die aktuelle (=letzte) Position in save_e gesichert. Beim nächsten Weiterschalten (n == 1) wird zurück auf die letzte Position gesetzt, und danach normal zu end() weitergeschaltet.
Iterator &operator++() {
if (n == 1) std::swap(e, save_e);
++e;
skip();
if (n && --n == 1) std::swap(e, save_e);
return *this;
}
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
Abschlussklausur Termin 1B
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 dieser zu Beginn auf das letzte Element, beim ersten Weiterschalten auf das erste Element, und beim Erreichen des letzten Elements auf end() gesetzt wird.
Der Iterator wird um zwei Instanzvariablen erweitert. reset gibt an, ob der Iterator auf das erste Element zu setzen ist, save_e speichert die Position des ersten Elements, und später die Position des letzten Elements. Wenn in einer Datenstruktur mehrere Instanzvariablen im Iterator für die Positionierung erfoderlich sind, so sind in der Regel alle diese Instanzvariablen zu sichern.
bool reset {false};
Element *save_e {nullptr};
Wir erweitern den Konstruktor entsprechend:
explicit Iterator(Element *e = nullptr, size_type n = 0): e{e} {
if (this->e) skip();
if (n) {
this->save_e = this->e;
while (n-- > 1) ++*this;
this->reset = true;
}
}
Wenn n nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem ADS_set mit weniger als zwei Elementen ist der Modus speziell ident mit dem Modus normal). Man kann natürlich auch eine gesonderte bool-Variable für den Modus spendieren.
Im Konstruktor wird save_e gesetzt. Jeder funktionierende Iterator zeigt (sofern das ADS_set nicht leer ist) am Ende des Konstruktors definitionsgemäß auf das erste Element. Das ist daher die ideale Stelle für diese Aktion. Danach wird der Iterator (normal) bis zum letzten Element weitergeschaltet. reset wird auf true gesetzt, damit beim ersten Inkrementieren auf das erste Element zurückgesetzt wird.
Der neue Konstruktor wird in y() verwendet.
const_iterator y() const {
if (size() < 2) return begin();
return const_iterator{table,size()};
}
Zu guter Letzt wird der operator++() erweitert. Beim ersten Inkrementieren (reset == true) wird der Iterator auf das erste Element gesetzt. Zugleich wird die aktuelle (=letzte) Position in save_e gesichert. Erreicht der Iterator in weiterer Folge das letzte Element (e == save_e), dann wird sofort zu end() weitergeschaltet.
Iterator &operator++() {
if (reset) {
std::swap(e, save_e);
reset = false;
return *this;
}
++e;
skip();
if (e == save_e) ++*this;
return *this;
}
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
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 dieser zu Beginn auf das zweite Element (sofern vorhanden), nach dem ursprünglich letzten Element auf das erste und beim nächsten weiterschalten auf end() gesetzt wird.
Der Iterator wird um zwei Instanzvariablen erweitert. n enthält die Anzahl der Elemente im ADS_set (und wird in weiterer Folge auch als Zähler verwendet), save_e speichert die Position des ersten Elements, und später die Position von end(). Wenn in einer Datenstruktur mehrere Instanzvariablen im Iterator für die Positionierung erfoderlich sind, so sind in der Regel alle diese Instanzvariablen zu sichern.
size_type n {0};
Element *save_e {nullptr};
Wenn n nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem ADS_set mit weniger als zwei Elementen 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 n = 0): e{e} {
if (this->e) skip();
if (n) {
this->save_e = this->e; // Position des ersten Elements in save_e sichern
++*this; // im Modus normal inkrementieren
this->n = n; // erst ab jetzt operiert der operator++ im Modus speziell
}
}
Wenn n nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem ADS_set mit weniger als zwei Elementen ist der Modus speziell ident mit dem Modus normal). Man kann natürlich auch eine gesonderte bool-Variable für den Modus spendieren.
Im Konstruktor wird save_e gesetzt. Jeder funktionierende Iterator zeigt (sofern das ADS_set nicht leer ist) am Ende des Konstruktors definitionsgemäß auf das erste Element. Das ist daher die ideale Stelle für diese Aktion. Danach wird der Iterator (normal) bis zum zweiten Element weitergeschaltet und n erhält den Startwert.
Der neue Konstruktor wird in x() verwendet.
const_iterator x() const {
if (size() < 2) return begin();
return const_iterator{table,size()};
}
Zu guter Letzt wird der operator++() erweitert. Es gibt zwei spezielle Positionen, nämlich n == 2 (bzw. –n == 1) und n == 1. Bei n == 2 steht der Iterator nach dem weiterschalten auf end(), daher wird der Iterator auf die Position des ersten Elements gesetzt (aus save_e) und zugleich die Position von end() gesichert. Das nächste weiterschalten findet bei n == 1 statt, hier wird der Iterator auf end() gesetzt (aus save_e).
Iterator &operator++() {
++e;
skip();
if (n && (n == 1 || --n == 1)) std::swap(e, save_e);
return *this;
}
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.
Im wesentlichen ist der Iterator für den Modus speziell so umzubauen, dass dieser das zweite Element (sofern vorhanden) überspringt, nach dem ursprünglich letzten Element auf das zweite und beim nächsten weiterschalten auf end() gesetzt wird.
Der Iterator wird um zwei Instanzvariablen erweitert. n enthält die Anzahl der Elemente im ADS_set (und wird in weiterer Folge auch als Zähler verwendet), save_e speichert die Position des zweiten Elements, und später die Position von end(). Wenn in einer Datenstruktur mehrere Instanzvariablen im Iterator für die Positionierung erfoderlich sind, so sind in der Regel alle diese Instanzvariablen zu sichern.
size_type n {0};
Element *save_e {nullptr};
Wenn n nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem ADS_set mit weniger als drei Elementen 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 (abgesehen von der Initialisierung von n passiert hier nichts neues):
explicit Iterator(Element *e = nullptr, size_type n = 0): e{e}, n{n} {
if (this->e) skip();
}
Wenn n nicht 0 ist bedeutet das, dass der Iterator im Modus speziell ist (bei einem ADS_set mit weniger als drei Elementen ist der Modus speziell ident mit dem Modus normal). Man kann natürlich auch eine gesonderte bool-Variable für den Modus spendieren.
Der neue Konstruktor wird in w() verwendet.
const_iterator w() const {
if (size() < 3) return begin();
return const_iterator{table,size()};
}
Zu guter Letzt wird der operator++() erweitert. Im Modus speziell (also wenn n ungleich 0 ist) wird beim ersten Aufruf des operator++() nach dem Weiterschalten save_e gesetzt, um die Position des zweiten Elements zu speichern. Den ersten Aufruf erkennen wir daran, dass save_e noch den nullptr enthält. Danach wird der Iterator (hier rekursiv) zum dritten Element weitergeschaltet. Im weiteren Verlauf gibt es noch zwei spezielle Positionen, nämlich n == 2 (bzw. –n == 1) und n == 1. Bei n == 2 steht der Iterator nach dem weiterschalten auf end(), daher wird der Iterator auf die Position des zweiten Elements gesetzt (aus save_e) und zugleich die Position von end() gesichert. Das nächste weiterschalten findet bei n == 1 statt, hier wird der Iterator auf end() gesetzt (aus save_e).
Iterator &operator++() {
++e;
skip();
if (n) {
if (!save_e) {
save_e = e;
++*this;
} else if (n == 1 || --n == 1) std::swap(e, save_e);
}
return *this;
}
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
Letzte Änderung: 13.12.2024, 10:49 | 1547 Worte