Java und C++: Unterschiedliche Schnittstellen für assoziative Container
Die Unterschiede zwischen Programmiersprachen sind meist auf unterschiedliche Ideologien der prägenden Köpfe zurückzuführen. Diese Zielvorstellungen spiegeln sich nicht nur in der Sprache selbst sondern üblicherweise auch in der zugehörigen Standardbibliothek wider – und interessanterweise auch in der Mentalität der Softwareentwickler. Wobei ich nicht sagen kann, ob die Softwareentwickler ihre Einstellung an die Programmiersprache anpassen, oder ob die Programmiersprache die passenden Entwickler anzieht.
Das Thema ist mir aus vielen Gründen wichtig. An dieser Stelle möchte ich allerdings gar nicht weiter darüber philosophieren, sondern zunächst nur das Bewusstsein dafür schärfen. Dazu werde ich an einem kleinen Beispiel auf unterschiedliche Entwurfsentscheidungen der assoziativen Container aus den Standardbibliotheken von Java und C++ eingehen.
Der folgende Code-Ausschnitt zeigt eine typische Abfolge von Operationen bei der Aktualisierung einer java.util.Map, wobei der Ablauf von der Existenz eines passenden Eintrags abhängt. Zur besseren Veranschaulichung habe ich die Operationen auf mehrere Anweisungen und Zeilen verteilt. Das soll aber nichts an meiner eigentlichen Aussage ändern: Der Code ist gut lesbar, sehr verständlich und nicht weiter ungewöhnlich.
Map<Key, Value> map = ...;
...;
Key key = ...;
Feature feature = ...;
...;
if (map.containsKey(key)) {
Value oldValue = map.get(key);
Value newValue = someExpressionForUpdateWith(oldValue, feature);
map.put(key, newValue);
} else {
Value newValue = someExpressionForInsertWith(feature);
map.put(key, newValue);
}Aus Sicht eines C++‑Entwicklers sieht das anders aus. Ihm wird wahrscheinlich zunächst auffallen, dass die potentiell teuerste Operation im einen Fall zweimal und im anderen Fall sogar dreimal ausgeführt wird. Es geht dabei um die Suche nach der richtigen Stelle für den Schlüssel in der Map, die sowohl bei contains, get als auch put durchgeführt wird, und die von JIT-Compilern praktisch nicht als identisch erkannt und optimiert werden kann.
C++ ist auf Effizienz fokussiert. Die Map-Datenstruktur macht das deutlich, denn ihre Schnittstelle sieht ganz anders als in Java aus. Die drei eben erwähnten Funktionen gibt es in dieser Form überhaupt nicht. Die Verwendung der stattdessen existierenden Funktionen wirken auf Java-Entwickler ein wenig merkwürdig. Daher werde ich eine Umsetzung des obigen Codes im Folgenden genauer betrachten und beginne mit der Kombination aus contains und get:
auto p = map.find(key);
if (p == map.end()) {
// not found
...;
} else {
// found -> access value
auto&& value = p->second;
...;
}Die find-Funktion liefert ein Ergebnis, mit dem festgestellt werden kann, ob ein entsprechender Eintrag existiert, und das im positiven Fall direkt auf das Eintrag verweist. Darüber kann das Ergebnis nicht nur gelesen sondern auch geschrieben werden. Der erste Teil sieht also schon mal ganz gut aus:
Key key = ...;
Feature feature = ...;
...;
auto p = map.find(key);
if (p == map.end()) {
// TODO: insert
} else {
p->second = some_expression_for_update_with(p->second, feature);
}Auch beim Einfügen geht es um die Vermeidung der unnötigen Suche – in diesem Fall nach der Einfügeposition, an der die find-Funktion gerade den Eintrag nicht gefunden hat. Die entsprechende Funktion heißt emplace. Das Ergebnis es Aufrufs zeigt an, ob das Element eingefügt wurde oder ob es bereits existierte – einschließlich dem Ergebnis einer nachgelagerten find-Funktion. Damit lässt sich der Code wie folgt schreiben:
Key key = ...;
Feature feature = ...;
...;
auto r = map.emplace(key, some_expression_for_insert_with(feature));
if (!r.second) {
r.first->second = some_expression_for_update_with(r.first->second, feature);
}In diesem Fall wird allerdings der Ausdruck für das Einfügen immer berechnet. Das gilt es zu vermeiden, falls diese Operation teuer ist. Möglich macht das eine weitere Einfügefunktion, der man die richtige Position übergeben kann. Die richtige Position ist dabei das nachfolgende
Element, für deren Bestimmung sich lower_bound-Funktion eignet, die auch gleich find ersetzt:
Key key = ...;
Feature feature = ...;
...;
auto p = map.lower_bound(key);
if (p == map.end() || key < p->first) {
map.emplace_hint(p, key, some_expression_for_insert_with(feature));
} else {
p->second = some_expression_for_update_with(p->second, feature);
}Dieser Code ist in der Hinsicht optimal, dass die potentiell teure Positionsbestimmung nur ein einziges Mal erfolgt, und dass keine Ausdrücke unnötig berechnet werden. Aber auch in anderer Hinsicht ist er sehr effizient. Ohne auf die Details einzugehen zeige ich zumindest noch eine vollständige Implementierung:
template <typename M, typename K, typename V, typename I, typename U>
void put(M&& map, K&& key, V&& value, I&& insert, U&& update)
{
auto p = map.lower_bound(key);
if (p == map.end() || map.key_comp()(key, p->first)) {
map.emplace_hint(p, std::forward<K>(key), insert(std::forward<V>(value)));
} else {
update(p->second, std::forward<V>(value));
}
}Dieses Template fasst die ganze Funktionalität zusammen und bietet sie in wiederverwendbarer Form an. Das folgende Programm gruppiert die Eingabezeilen nach Länge und zeigt dabei die Verwendung des Funktionstemplates. Ein Blick auf die Details lohnt sich, denn die Abstraktion verursacht praktisch keinen Overhead.
int main()
{
using namespace std;
map<size_t, set<string>> map;
for (string line; getline(cin, line); ) {
auto size = line.size();
put(map, size, move(line),
[](string v) { return set<string>{move(v)}; },
[](set<string>& r, string v) { r.insert(move(v)); });
}
}Nochmals zusammengefasst: Mit dem Beispiel wollte ich bewusster machen, dass die prägenden Zielvorstellungen sich nicht nur auf die Sprache auswirken, sondern auch in den zugehörigen Bibliotheken sichtbar werden. An den Container-Klassen wird das sehr deutlich. Bei Java steht im Fokus einfache Aufgabenstellungen einfach und verständlich zu lösen. C++ ist hingegen sehr um Performance bemüht – auch auf Kosten der Lesbarkeit.