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 1
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 Statistikdaten definieren wir zwecks Einfachheit eine zusätzliche private Instanzvariable vom Typ statistics_t. Mit einzelnen size_t-Variablen kann man natürlich auch arbeiten. Ebenfalls zur Vereinfachung bzw. besseren Lesbarkeit definieren wir einen enum für die verschiedenen Aufrufvarianten von insert. Die korrespondierenden Zahlenwerte der einzelnen Ausprägungen entsprechen den zugehörigen Indexpositionen in den Zählfeldern ok und fail (ausgenommen INTERN, diese Aufrufe sind ja nicht zu berücksichtigen). Die Verwendung eines enum ist natürlich nicht erforderlich.
statistics_t statistics;
enum Imode {ILIST, SINGLE, RANGE, INTERN};
Range-insert wird bei uns auch intern verwendet, daher muss diese Methode entsprechend erweitert werden, damit nur externe Aufrufe gezählt werden:
template<typename InputIt> void insert(InputIt first, InputIt last, Imode imode = Imode::RANGE) { // NEU
for (auto it{first}; it != last; ++it) {
if (Address a{*it, this}) {
if (imode != Imode::INTERN) ++statistics.fail[imode]; // NEU
}
else {
if (imode != Imode::INTERN) ++statistics.ok[imode]; // NEU
++curr_size;
entries[a.h.x][a.h.y].append(*it,a.h.r);
}
}
}
Der Aufruf im Initializer-List-Konstruktor wird dann entsprechend angepasst
insert(first, last, Imode::INTERN)
und ebenso jener im Initializer-List-insert. Dieser Aufruf ist zwar intern, aber die dabei (nicht) eingefügten Werte sind für das Initializer-List-insert zu zählen.
insert(std::begin(ilist),std::end(ilist),Imode::ILIST);
Das insert für Einzelwerte wird ebenfalls aufgerüstet
std::pair<iterator,bool> insert(const key_type &k) {
if (Address a{k,this}) {
++statistics.fail[Imode::SINGLE]; // NEU
return {{entries, a}, false};
} else {
++statistics.ok[Imode::SINGLE]; // NEU
++curr_size;
return {{entries, {a.h, entries[a.h.x][a.h.y].append(k,a.h.r)}}, true};
}
}
Da die Statistikdaten in swap zu tauschen sind, muss diese Methode ebenfalls am Ende erweitert werden:
swap(statistics, other.statistics);
Die Methode z() selbst ist wie so oft von überschaubarer Komplexität:
statistics_t z() const { return statistics; }
Je nach Implementierung sind dann noch weitere Methoden anzupassen. Bei uns sind das der Kopierkonstruktor (die Statistikdaten sind zu übernehmen)
statistics = other.statistics;
sowie clear(), das ja swap verwendet, aber die Statistikdaten unverändert lassen soll. Wir ergänzen daher am Ende zur Rettung der in swap weggetauschten Statistikdaten
statistics = tmp.statistics;
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 Statistikdaten definieren wir eine zusätzliche private Instanzvariable stats, ein Feld der Länge 3, der Einfachheit halber mit Elementtyp std::pair<size_t,size_t>. Mit einzelnen size_t-Variablen kann man natürlich auch arbeiten, oder mit size_t-Feldern. Auf einen enum verzichten wir diesmal, um auch mal eine andere Variante auszuprobieren. Der Index im Feld entspricht dem beim Aufruf von y() angegebenen idx:
std::pair<size_t,size_t> stats[3];
Die Methode swap wird bei uns auch intern verwendet. Anstelle der Lösungsvariante mit einem zusätzlichem Parameter (siehe Termin 1) erstellen wir diesmal zur Abwechslung eine private Variante von swap(), die von den beiden öffentlichen swap()s aufgerufen wird (hinsichtlich Datenkapsel ist das sauberer). swap_() ist eine Kopie von swap(), am Ende findet außerdem der geforderte Tausch der Statistikdaten statt.
void swap_(ADS_set &other) { // CHANGED
using std::swap;
swap(entries, other.entries);
swap(curr_size, other.curr_size);
swap(stats,other.stats); // NEW
}
Das neue swap() aktualisiert die Statistikdaten und ruft das private swap_() auf:
void swap(ADS_set &other) {
++stats[0].first;
stats[0].second += size();
++other.stats[0].first;
other.stats[0].second += other.size();
swap_(other);
}
Dasselbe passiert in der globalen Funktion swap(). Um den Aufruf des privaten swap_() zu ermöglichen, wird die globale Funktion swap() als friend deklariert und der Einfachheit halber gleich innerhalb der Klasse definiert. Das Aktualisieren der Statistik könnte man auch im privaten swap_() zentralisieren und über einen Parameter steuern.
friend void swap(ADS_set &lhs, ADS_set &rhs) {
++lhs.stats[1].first;
lhs.stats[1].second += lhs.size();
++rhs.stats[1].first;
rhs.stats[1].second += rhs.size();
lhs.swap_(rhs);
}
Die Aufrufe von swap() in den beiden Zuweisungsoperatormethoden werden dann entsprechend geändert:
swap_(tmp);
Auch der swap()-Aufruf in clear() wird geändert. clear() wird außerdem für das Aktualisieren der Statistikdaten aufgerüstet und es wird am Ende sichergestellt, dass diese durch das swap_() nicht verloren gehen. Zwecks Übersichtlichkeit das gesamte geänderte clear():
void clear() {
++stats[2].first; // NEW
stats[2].second += size(); // NEW
ADS_set tmp;
swap_(tmp); // CHANGED
using std::swap; // NEW
swap(stats,tmp.stats); // NEW
}
Die Methode y() liefert das gefordert Element aus dem Feld (eine Absicherung des Indexbereichs war der Einfachheit halber nicht gefordert):
std::pair<size_t,size_t> y(size_t idx) const { return stats[idx]; }
Je nach Implementierung sind dann noch weitere Methoden anzupassen. Bei uns ist das der Kopierkonstruktor (die Statistikdaten sind zu übernehmen)
stats[0] = other.stats[0];
stats[1] = other.stats[1];
stats[2] = other.stats[2];
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 der Historie definieren wir zwecks Einfachheit eine zusätzliche private Instanzvariable vom Typ std::pair<size_type,key_type>. Mit zwei einzelnen Variablen kann man natürlich auch arbeiten.
std::pair<size_type,key_type> rc_x;
In erase() wird die Historie im Erfolgsfall (rc==1) aktualisiert.
if (rc && (!rc_x.first++ || std::less<key_type>{}(rc_x.second,k))) rc_x.second = k;
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) if (!rc_x.first++ || std::less<key_type>{}(rc_x.second,k)) rc_x.second = k;
Da die Historie in swap() getauscht wird (siehe unten), muss diese nach dem swap(tmp) in clear() gerettet werden:
rc_x = tmp.rc_x;
Zum Tauschen der Historie wird swap erweitert:
swap(rc_x, other.rc_x);
Die Methode x() retourniert die Historie. Falls rc_x.first == 0 ist, ist rc_x.second noch aus dem Konstruktor 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<size_type,key_type> x() const { return rc_x; }
Je nach Implementierung sind dann noch weitere Methoden anzupassen. Bei uns ist das nur der Kopierkonstruktor (die Historie ist zu übernehmen)
rc_x = other.rc_x;
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 einen zusätzlichen Parameter gesteuert werden, oder über eigene private Methoden für die interne Verwendung.
Letzte Änderung: 19.04.2022, 13:21 | 1182 Worte