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
Im folgenden eine von vielen Lösungsmöglichkeiten am Beispiel Double Hashing. Die Lösung ist datenstrukturunabhängig und im Kern auch implementierungsunabhängig. Der Code kann daher in jeder Implementierung verwendet werden, allfällige Anpassungen siehe unten.
Zum Verwalten der Historie definieren wir diesmal ein struct und eine entsprechende zusätzliche private Instanzvariable. Mit einzelnen Variablen kann man natürlich auch arbeiten.
struct History {
bool has_max1 {false}, has_max2 {false};
key_type max1, max2;
};
History hist;
Da das Aktualisieren der Historie an mehr als einer Stelle passieren wird, definieren wir eine entsprechende Funktion, und zwar als Methode von History (auch das muss man nicht so machen).
void set(const key_type &k) {
if (!has_max1 || std::less<key_type>{}(max1,k)) {
max2 = max1;
has_max2 = has_max1;
max1 = k;
has_max1 = true;
} else if (std::less<key_type>{}(k,max1) && (!has_max2 || std::less<key_type>{}(max2,k))) {
max2 = k;
has_max2 = true;
}
}
In erase() wird die Historie im Erfolgsfall (unmittelbar vor return 1;) aktualisiert.
hist.set(key);
Ebenso in clear(). In dieser Methode werden ja alle aktuell vorhandenen Werte gelöscht. Es sind daher alle aktuell vorhandenen Werte zu berücksichtigen. Da unser clear() ohne Schleife implementiert ist, sondern mit swap, bauen wir am Beginn von clear() eine solche Schleife über alle Werte ein. Um Schreibarbeit zu sparen, nehmen wir eine range based for loop. Jede andere Schleife über alle Werte tut es auch.
for (const auto &k: *this) hist.set(k);
Da die Historie in swap() getauscht wird (siehe unten), muss diese nach dem swap(tmp) in clear() gerettet werden:
hist = tmp.hist;
Zum Tauschen der Historie wird swap erweitert:
swap(hist, other.hist);
Die Methode z() retourniert den relevanten Teil der Historie. Falls hist.has_max2 gleich false ist, ist hist.max2 noch aus dem Defaultkonstruktor defaultkonstruiert (es wurde noch nie ein Wert zugewiesen). Das ist ok, da der Wert in diesem Fall laut Angabe nicht definiert ist und daher jeder beliebige Wert zulässig ist.
std::pair<bool,key_type> z() const { return {hist.has_max2,hist.max2}; }
Je nach Implementierung sind dann noch weitere Methoden anzupassen. Bei uns ist das nur der Kopierkonstruktor (die Historie ist zu übernehmen)
hist = other.hist;
Wenn erase() oder clear() auch intern verwendet werden (bei uns ist das nicht der Fall), so sind wie üblich spezielle Varianten dieser Methoden für die interne Verwendung vorzusehen, die die Historie nicht verändern (und bei Hashverfahren auch das ansonsten verbotene std::less nicht benutzen). Das kann zB über eigene private Varianten dieser Methoden für die interne Verwendung realisiert werden.
Abschlussklausur Termin 2
Im folgenden eine von vielen Lösungsmöglichkeiten am Beispiel Double Hashing. Die Lösung ist datenstrukturunabhängig und im Kern auch implementierungsunabhängig. Der Code kann daher in jeder Implementierung verwendet werden, allfällige Anpassungen siehe unten.
Zum Verwalten der Historie definieren wir der Einfachheit halber eine Instanzvariable vom Typ std::pair<size_type,key_type>. Mit einzelnen Variablen kann man natürlich auch arbeiten.
std::pair<size_type, key_type> hist;
In insert(const key_type &) wird die Historie im Erfolgsfall (unmittelbar vor return {iterator{add(key)},true};) aktualisiert.
if (!hist.first || std::less<key_type>{}(hist.second,key)) hist = {hist.first+1,key};
Ebenso im insert(InputIt, InputIt). In dieser Methode ist zudem darauf zu achten, dass der Aufruf nur einmal gezählt wird, auch wenn mehrere Werte eingefügt werden, die größer als das aktuelle historische Maximum sind. Dazu definieren wir einen Schalter
bool first_max {true};
und aktualisieren ggf die Historie im if (!count(*it)) {…}
if (!hist.first || std::less<key_type>{}(hist.second,*it)) {
if (first_max) {
first_max = false;
++hist.first;
}
hist.second = *it;
}
Da die Historie in swap() getauscht wird (siehe unten), muss diese nach dem swap(tmp) in clear() gerettet werden:
hist = tmp.hist;
Zum Tauschen der Historie wird swap erweitert:
swap(hist, other.hist);
Die Methode y() retourniert die Historie. Falls hist.first gleich 0 ist, ist hist.second noch aus dem Defaultkonstruktor defaultkonstruiert (es wurde noch nie ein Wert zugewiesen). Das ist ok, da der Wert in diesem Fall laut Angabe undefiniert ist und daher jeder beliebige Wert zulässig ist.
std::pair<size_type,key_type> y() const { return hist; }
Je nach Implementierung sind dann noch weitere Methoden anzupassen. Bei uns ist das nur der Kopierkonstruktor (die Historie ist zu übernehmen)
hist = other.hist;
Wenn veränderte Methoden auch intern verwendet werden, so ist darauf zu achten, dass die Historie nicht falsch verändert wird (bei uns wird die Historie bei den internen Verwendungen immer korrekt verändert, daher ist nichts zu tun). Sollte das der Fall sein, so sind wie üblich spezielle Varianten dieser Methoden für die interne Verwendung vorzusehen, die die Historie nicht falsch verändern. Das kann zB über eigene private Varianten dieser Methoden für die interne Verwendung realisiert werden.
Abschlussklausur Termin 3
Im folgenden eine von vielen Lösungsmöglichkeiten am Beispiel Double Hashing. Die Lösung ist datenstrukturunabhängig und im Kern auch implementierungsunabhängig. Der Code kann daher in jeder Implementierung verwendet werden, allfällige Anpassungen siehe unten.
struct History {
key_type mi, ma;
bool is_set {false};
void set(const key_type &key) {
if (!is_set) {
mi = ma = key;
is_set = true;
} else if (std::less<key_type>{}(key,mi)) {
mi = key;
} else if (std::less<key_type>{}(ma,key)) {
ma = key;
}
}
void reset() { is_set = false; }
};
History hist;
In insert(const key_type &) wird die Historie im Erfolgsfall (unmittelbar vor dem return) aktualisiert.
hist.set(key);
Ebenso in insert(InputIt,InputIt), unmittelbar vor add(*it).
hist.set(*it);
Da die Historie in swap() getauscht wird (siehe unten), muss diese nach dem swap(tmp) in clear() gerettet werden:
hist = tmp.hist;
Zum Tauschen der Historie wird swap erweitert:
swap(hist, other.hist);
In der Methode x() wird, falls die Historie noch nicht gesetzt wurde, eine Exception ausgelöst. Andernfalls retourniert die Methode x() den relevanten Teil der Historie.
std::pair<key_type,key_type> x() const {
if (!hist.is_set) throw std::runtime_error{"order 66"};
return {hist.mi,hist.ma};
}
Je nach Implementierung sind dann noch weitere Methoden anzupassen. Bei uns ist das zum einen der Kopierkonstruktor (die Historie ist zu übernehmen)
hist = other.hist;
Zum anderen verwenden Initializer-List-Konstruktor und Range-Konstruktor die insert-Methoden. Da dies "interne" Aufrufe sind, die nicht berücksichtigt werden, wird die Historie danach wieder in den Ausgangszustand versetzt.
hist.reset();
Letzte Änderung: 23.09.2022, 20:38 | 1061 Worte