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.3. und 5.4.2019 (SS 2019)
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).
Der Film zum Code:
Download:
ADS_set.h (Funktionsumfang für die erste Projektphase)
Unterlagen zu Double Hashing siehe Unterlagen, Vorlesung Kapitel 3 Vektoren (ab Seite 14).
Abschlussklausur Termin 1
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. Die Lösung ist etwas umfangreicher als notwendig, um die erforderlichen Änderungen besser zu verdeutlichen.
Im wesentlichen ist der Iterator für den Modus speziell so umzubauen, dass beim "Weiterschalten" mittels operator++ nach m Elementen abgebrochen, also zu end() weitergeschaltet wird. Wenn die Datenstruktur weniger als m Elemente enthält, wird nach dem letzten Element wieder mit dem ersten begonnen, also der Iterator in den Startzustand versetzt.
Der Iterator wird um zwei Instanzvariablen erweitert, die angeben, ob der Iterator im Modus speziell ist und nach wie vielen Elementen abzubrechen ist.
bool special {false};
size_t m {0};
Zusätzlich benötigen wir Instanzvariablen, um den Anfangszustand zu speichern. Bei unserer Datenstruktur reicht es, den Anfangswert von pos zu speichern.
element *save_pos {nullptr};
Wir definieren einen zusätzlichen Konstruktor. Der ursprüngliche Konstruktor kann unverändert bleiben, da die zusätzlichen Instanzvariablen in-class initialisiert werden (siehe oben).
explicit Iterator(element *pos, size_t m): pos{pos}, special{true}, m{m}, save_pos{pos} {
if (this->pos) skip();
}
Der neue Konstruktor wird in z() verwendet. Hier wird auch überprüft, ob das ADS_set leer ist oder m == 0. In diesen Fällen ist laut Aufgabenstellung end() zu retournieren.
const_iterator z(size_t m) const { return curr_size && m ? const_iterator{table, m} : end(); }
Zu guter Letzt wird der operator++() erweitert. Bei dieser Variante sind die beiden Modi normal (wie bisher) und speziell (neu) ganz plakativ per if getrennt.
Iterator &operator++() {
if (special) {
if (--m) { // Zähler dekrementieren. Falls Zähler != 0 (also > 0, da size_t) weitermachen
++pos; // normal ...
skip(); // ... weiterschalten
if (pos->mode == Mode::end) reset(); // wenn das Ende erreicht wird -> auf Anfang setzen
} else { // Zähler == 0, daher Abbruch
while (pos->mode != Mode::end) ++pos; // bis Ende weiterschalten
}
} else {
++pos;
skip();
}
return *this;
}
Das Zurücksetzen auf die Anfangsposition wird zur besseren Veranschaulichung in einer eigenen privaten Methode erledigt.
void reset() { pos = save_pos; skip(); }
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. Die Lösung ist etwas umfangreicher als notwendig, um die erforderlichen Änderungen besser zu verdeutlichen. Da die Aufgabenstellung teilweise starke Ähnlichkeiten zur Aufgabenstellung beim Termin 1 hat, werden wir zur Abwechslung keine eigene Methode reset() und keinen zusätzlichen Konstruktor definieren.
Im wesentlichen ist der Iterator für den Modus speziell so umzubauen, dass beim "Weiterschalten" mittels operator++ nach einer gewissen Anzahl von Elementen wieder mit dem ersten begonnen wird, also der Iterator in den Startzustand versetzt wird. Beim ersten "Durchgang" erfolgt dies nach dem ersten Element, beim zweiten Durchgang nach dem zweiten Element usw. bis wir im letzten (n-ten) Durchgang nach dem letzten Element bei end() landen.
Der Iterator wird um drei Instanzvariablen erweitert, die angeben, ob der Iterator im Modus speziell ist, in welchem Durchgang wir uns befinden (m) und wie viele Elemente in diesem Durchgang bereits geliefert worden sind (c).
bool special;
size_t m, c;
Zusätzlich benötigen wir Instanzvariablen, um den Anfangszustand zu speichern. Bei unserer Datenstruktur reicht es, den Anfangswert von pos zu speichern.
element *save_pos;
Wir erweitern den ursprünglichen Konstruktor, um die zusätzlichen Instanzvariablen zu initialisieren.
explicit Iterator(element *pos = nullptr, bool special = false): pos{pos}, special{special}, m{1}, c{0}, save_pos{pos} {
if (this->pos) skip();
}
Der Konstruktor wird in y() entsprechend verwendet.
const_iterator y() const { return const_iterator{table, true}; }
Zu guter Letzt wird der operator++() erweitert. Im wesentlichen wird nach dem Code für den Modus normal überprüft, ob der Iterator im Modus speziell ist. In diesem Fall wird, sofern wir noch nicht end() erreicht haben, der Iterator auf die Anfangsposition gesetzt, wenn wir das Ende des aktuellen Duchgangs erreicht haben.
Iterator &operator++() {
++pos;
skip();
if (special && pos->mode != Mode::end && ++c == m) {
pos = save_pos; // Zurücksetzen auf Anfang Schritt 1
skip(); // Zurücksetzen auf Anfang Schritt 2
++m; // nächster Durchgang
c = 0; // Zähler zurücksetzen
}
return *this;
}
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
Abschlussklausur Termin 3 - Variante 1
Da der Iterator nur drei Positionen liefert (letztes Element, erstes Element und end()), können diese Positionen bereits bei der Erzeugung des Iterators ermittelt und dann in entsprechenden Instanzvariablen gespeichert werden, um sie beim Inkrementieren ohne zusätzlichen Suchaufwand verwenden zu können. Da der Iterator bei der Erzeugung auf das letzte Element zu setzen ist, ist die Datenstruktur jedenfalls bis zum Ende zu durchlaufen, die Ermittlung der anderen beiden Positionen ist daher ohne Zusatzaufwand möglich. Bei manchen Strukturen (zB bei dieser) ist es möglich, das letzte Element schneller zu finden, wenn mit der Suche "hinten" begonnen wird. Im Sinne der allgemeinen Anwendbarkeit der Strategie wird darauf aber hier verzichtet.
In dieser Variante erfolgt die Ermittlung der Positionen im Konstruktor des Iterators.
const_iterator x() const { return const_iterator{table, true}; }
Zusätzliche Instanzvariablen im Iterator
bool special, done;
element *first_pos, *end_pos;
Bestehenden Konstruktor erweitern
explicit Iterator(element *pos = nullptr, bool special = false): pos{pos}, special{special}, done{false}, first_pos{nullptr}, end_pos{nullptr} {
if (this->pos) skip();
if (this->special) {
auto last_pos = this->first_pos = this->pos;
while (this->pos->mode != Mode::end) {
last_pos = this->pos;
++this->pos;
skip();
}
this->end_pos = this->pos;
this->pos = last_pos;
}
}
Präfix-Inkrementoperator erweitern (der Postfix-Inkrementoperator verwendet den Präfix-Inkrementoperator und braucht daher nicht geändert zu werden)
Iterator &operator++() {
if (special) {
pos = done ? end_pos : first_pos;
done = true;
} else {
++pos;
skip();
}
return *this;
}
Abschlussklausur Termin 3 - Variante 2
Im Unterschied zur Variante 1 erfolgt bei dieser Variante die Ermittlung der drei benötigten Iteratorpositionen bereits in x(), es kann daher auf die normale Iteratorfunktionalität zurückgegriffen werden.
const_iterator x() const {
auto last {begin()};
for (auto it {begin()}; it != end(); ++it) last = it;
return const_iterator{begin(), last, end()};
}
Zusätzliche Instanzvariablen im Iterator - wie Variante 1, allerdings in-class initialisiert
bool special {false}, done {false};
element *first_pos {nullptr}, *end_pos {nullptr};
Zusätzlicher Konstruktor
explicit Iterator(const Iterator &first_it, const Iterator &last_it, const Iterator &end_it): pos{last_it.pos}, special{true}, first_pos{first_it.pos}, end_pos{end_it.pos} { }
Präfix-Inkrementoperator erweitern (der Postfix-Inkrementoperator verwendet den Präfix-Inkrementoperator und braucht daher nicht geändert zu werden) - wie Variante 1
Iterator &operator++() {
if (special) {
pos = done ? end_pos : first_pos;
done = true;
} else {
++pos;
skip();
}
return *this;
}
Letzte Änderung: 11.02.2021, 14:20 | 1086 Worte