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 "BISEH"
"Live"-Implementierung aus den Lehrveranstaltungen vom 04.05. und 11.05.2021
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 BISEH siehe Unterlagen, Vorlesung Kapitel 3 Vektoren (ab Seite 38).
Abschlussklausur Termin 1A
Im folgenden eine von vielen Lösungsmöglichkeiten am Beispiel BISEH. 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" werden zwei Instanzvariablen für den größten und zweitgrößten Wert angelegt, sowie zugehörige Schalter die anzeigen, ob die Variablen bereits einen definierten Wert haben (C++17 bietet für solche Problemstellungen übrigens std::optional). Wir verwenden zwei Felder der Länge 2, einzelne Variablen tun es auch.
key_type max_key[2];
bool max_key_exists[2] {};
Die private Methode set_max setzt die Historie neu, sofern aufgrund des neuen Wertes k erforderlich.
void set_max(const key_type &k) {
if (!max_key_exists[0] || std::less<key_type>{}(max_key[0], k)) {
max_key[1] = max_key[0];
max_key_exists[1] = max_key_exists[0];
max_key[0] = k;
max_key_exists[0] = true;
} else if (std::less<key_type>{}(k,max_key[0]) && (!max_key_exists[1] || std::less<key_type>{}(max_key[1], k))) {
max_key[1] = k;
max_key_exists[1] = true;
}
}
set_max ist immer dann aufzurufen, wenn ein neuer Wert eingefügt wird, in unserem Fall ist das in template<typename InputIt> void insert(InputIt first, InputIt last) und std::pair<iterator,bool> insert(const key_type &k), jeweils unmittelbar nach dem ++curr_size.
Die Methode z() ist dann recht simpel:
key_type z() const {
if (!max_key_exists[1]) throw std::runtime_error{"order 66"};
return max_key[1];
}
Da die Historie in swap zu tauschen ist, muss diese Methode ebenfalls am Ende erweitert werden:
swap(max_key, other.max_key);
swap(max_key_exists, other.max_key_exists);
Abhängig von der gewählten Implementierung sind unter Umständen weitere Methoden anzupassen. Bei uns sind das
- Der Kopierkonstruktor ADS_set(const ADS_set &other), da hier die Historie aus other zu übernehmen ist
max_key[0] = other.max_key[0];
max_key_exists[0] = other.max_key_exists[0];
max_key[1] = other.max_key[1];
max_key_exists[1] = other.max_key_exists[1];
- clear, da hier die Historie erhalten bleiben muss. Da wir swap verwenden (dieses tauscht die Historie) tauschen wir die Historie dann am Ende wieder zurück.
using std::swap;
swap(max_key, tmp.max_key);
swap(max_key_exists, tmp.max_key_exists);
Abschlussklausur Termin 1B
Im folgenden eine von vielen Lösungsmöglichkeiten am Beispiel BISEH. 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" werden zwei Instanzvariablen für den größten und zweitgrößten Wert angelegt, sowie zugehörige Schalter die anzeigen, ob die Variablen bereits einen definierten Wert haben (C++17 bietet für solche Problemstellungen übrigens std::optional). Wir verwenden zwei Felder der Länge 2, einzelne Variablen tun es auch.
key_type max_key[2];
bool max_key_exists[2] {};
Die private Methode set_max setzt die Historie neu, sofern aufgrund des neuen Wertes k erforderlich.
void set_max(const key_type &k) {
if (!max_key_exists[0] || std::less<key_type>{}(max_key[0], k)) {
max_key[1] = max_key[0];
max_key_exists[1] = max_key_exists[0];
max_key[0] = k;
max_key_exists[0] = true;
} else if (std::less<key_type>{}(k,max_key[0]) && (!max_key_exists[1] || std::less<key_type>{}(max_key[1], k))) {
max_key[1] = k;
max_key_exists[1] = true;
}
}
set_max ist immer dann aufzurufen, wenn ein neuer Wert eingefügt wird, in unserem Fall ist das in template<typename InputIt> void insert(InputIt first, InputIt last) und std::pair<iterator,bool> insert(const key_type &k), jeweils unmittelbar nach dem ++curr_size.
Die Methode y() ist dann recht simpel:
key_type y() const {
if (!max_key_exists[1]) throw std::runtime_error{"order 66"};
return max_key[1];
}
Abhängig von der gewählten Implementierung sind unter Umständen weitere Methoden anzupassen. Bei uns sind das
- Der Kopierzuweisungsoperator ADS_set &operator=(const ADS_set &other). Da die Historie erhalten und gegebenfalls angepasst werden muss, ist die bisherige Implementierung mittels swap ungünstig. Daher wird diese komplett ersetzt durch
clear();
insert(other.begin(), other.end());
- Der Initializer-List-Zuweisungsoperator ADS_set &operator=(std::initializer_list<key_type> ilist) aus demselben Grund. Auch hier wird die gesamte Implementierung ersetzt durch
clear();
insert(ilist);
Siehe auch der Hinweis in der Aufgabenstellung: "sind wie Einfügeoperationen zu betrachten, bei denen die Werte aus other bzw. ilist eingefügt werden".
Abschlussklausur Termin 2
Im folgenden eine von vielen Lösungsmöglichkeiten am Beispiel BISEH. 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" werden zwei Instanzvariablen für den kleinsten und größten Wert angelegt, sowie ein Schalter der anzeigt, ob die Variablen bereits einen definierten Wert haben.
key_type min_key, max_key;
bool min_max_keys_exist {false};
Die private Methode set_min_max setzt die Historie neu, sofern aufgrund des neuen Wertes k erforderlich.
void set_min_max(const key_type &k) {
if (!min_max_keys_exist) {
min_key = max_key = k;
min_max_keys_exist = true;
} else if (std::less<key_type>{}(k,min_key)) {
min_key = k;
} else if (std::less<key_type>{}(max_key,k)) {
max_key = k;
}
}
set_min_max ist immer dann aufzurufen, wenn ein neuer Wert mit insert erfolgreich eingefügt wird, in unserem Fall ist das in template<typename InputIt> void insert(InputIt first, InputIt last) und std::pair<iterator,bool> insert(const key_type &k), jeweils unmittelbar nach dem ++curr_size.
Die Methode x() liefert die Werte, sofern vorhanden, als std::pair:
std::pair<key_type,key_type> x() const {
if (!min_max_keys_exist) throw std::runtime_error{"order 66"};
return {min_key,max_key};
}
Da die Historie in swap zu tauschen ist, muss diese Methode ebenfalls am Ende erweitert werden:
swap(max_key, other.max_key);
swap(min_key, other.min_key);
swap(min_max_keys_exist, other.min_max_keys_exist);
Abhängig von der gewählten Implementierung sind unter Umständen weitere Methoden anzupassen. Bei uns sind das
- Der Kopierkonstruktor ADS_set(const ADS_set &other), da hier die Historie aus other zu übernehmen ist
min_key = other.min_key;
max_key = other.max_key;
min_max_keys_exist = other.min_max_keys_exist;
- clear, da hier die Historie erhalten bleiben muss. Da wir swap verwenden (dieses tauscht die Historie) tauschen wir die Historie dann am Ende wieder zurück.
using std::swap;
swap(max_key, tmp.max_key);
swap(min_key, tmp.min_key);
swap(min_max_keys_exist, tmp.min_max_keys_exist);
Zusätzlich ist darauf zu achten, dass nur "direkte" Aufrufe von insert berücksichtigt werden. Es gibt mehrere Möglichkeiten, dies umzusetzen. Eine Möglichkeit besteht darin, die insert-Methoden um einen optionalen bool-Parameter zu erweitern, der bei indirekten (also internen) Aufrufen entsprechend gesetzt und in der insert-Methode abgefragt wird. Bei uns gibt es allerdings nur einen internen insert-Aufruf, der abzusichern ist, und zwar im Range-Konstruktor template<typename InputIt> ADS_set(InputIt first, InputIt last). Wir entscheiden uns daher für eine simplere Variante und "löschen" die Historie nach dem insert-Aufruf mittels
min_max_keys_exist = false;
Auch diese Variante sollte in allen Implementierungen umsetzbar sein. Weitere Kandidaten sind, je nach Implementierung, der Initializer-List-Zuweisungsoperator und der Initializer-List-Konstruktor. Alle drei werden in der Aufgabenstellung explizit angeführt ("wird die Historie in den Anfangszustand gesetzt").
Abschlussklausur Termin 3
Im folgenden eine von vielen Lösungsmöglichkeiten am Beispiel BISEH. 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 des historischen Maximums wird eine Instanzvariable definiert, sowie ein Schalter der anzeigt, ob die Variable bereits einen definierten Wert hat.
key_type hist_max_key;
bool hist_max_exists{false};
Die private Methode set_max setzt das historische Maximum neu, sofern aufgrund des neuen Wertes k erforderlich.
void set_max(const key_type &k) {
if (!hist_max_exists || std::less<key_type>{}(hist_max_key, k)) {
hist_max_exists = true;
hist_max_key = k;
}
}
set_max ist immer dann aufzurufen, wenn ein neuer Wert erfolgreich eingefügt wird, in unserem Fall ist das in template<typename InputIt> void insert(InputIt first, InputIt last) und std::pair<iterator,bool> insert(const key_type &k), jeweils unmittelbar nach dem ++curr_size.
Die Methode w() liefert den gesuchten Wert, sofern vorhanden. Dazu wird der aktuell größte vorhandene Wert gesucht, wobei allerdings das historische Maximum ignoriert wird.
key_type w() const {
key_type rc;
bool rc_exists {false};
for (const auto &k: *this) {
if (std::less<key_type>{}(k,hist_max_key) && (!rc_exists || std::less<key_type>{}(rc,k))) {
rc = k;
rc_exists = true;
}
}
if (!rc_exists) throw std::runtime_error{"order 66"};
return rc;
}
Da die Historie in swap zu tauschen ist, muss diese Methode ebenfalls am Ende erweitert werden:
swap(hist_max_key, other.hist_max_key);
swap(hist_max_exists, other.hist_max_exists);
Abhängig von der gewählten Implementierung sind unter Umständen weitere Methoden anzupassen. Bei uns sind das
- Der Kopierkonstruktor ADS_set(const ADS_set &other), da hier die Historie aus other zu übernehmen ist
hist_max_key = other.hist_max_key;
hist_max_exists = other.hist_max_exists;
- clear, da hier die Historie erhalten bleiben muss. Da wir swap verwenden (dieses tauscht die Historie) setzen wir die Historie dann am Ende wieder zurück in den vorherigen Zustand.
hist_max_key = tmp.hist_max_key;
hist_max_exists = tmp.hist_max_exists;
- Der Kopierzuweisungsoperator ADS_set &operator=(const ADS_set &other). Da die Historie erhalten und gegebenfalls angepasst werden muss, ist die bisherige Implementierung mittels swap ungünstig. Daher wird diese komplett ersetzt durch
clear();
insert(other.begin(), other.end());
- Der Initializer-List-Zuweisungsoperator ADS_set &operator=(std::initializer_list<key_type> ilist) aus demselben Grund. Auch hier wird die gesamte Implementierung ersetzt durch
clear();
insert(ilist);
Wie man auch an den hier verwendeten Textbausteinen erkennen kann, ist diese Aufgabe eine vereinfachte Kombination aus den vorherigen Aufgaben dieses Semesters, erweitert um die Maximumsuche in w().
Letzte Änderung: 23.06.2022, 08:50 | 1521 Worte