Für ein kleines Experiment habe ich vor Kurzem versucht, mit einer Ordered Map in C++ effizient einen bestimmten Key-Bereich zu bearbeiten. Danach habe ich das gleiche in Rust versucht und eine API entdeckt, die ich noch nicht kannte und die das Problem auf sehr elegante Art löst.
Die Aufgabe
Die Details sind hier irrelevant. Ich habe generell versucht, einen bestimmten Key-Bereich der Map effizient zu bearbeiten und dabei einzelne Einträge einzufügen, zu verschieben und zu entfernen. Dabei sollte die bestmögliche Performance erreicht werden. Konkret sollte
die Map nur einmal durchsucht werden (was
O(log(n))Operationen über die Anzahl der Einträge in der Map benötigt)so wenig Keys und Values wie möglich kopiert werden.
Mit std::map
In C++ ist die Standardimplementation einer Ordered Map std::map. Der Weg, die gewünschten Operationen in C++ durchzuführen ist, einen Iterator auf den Anfang oder das Ende des gesuchten Bereichs zu setzen mit
std::map::lower_bound(key) // größter Eintrag, der nicht größer ist als key
std::map::upper_bound(key) // kleinster Eintrag, der größer ist als keyund dann die auf dem Iterator basierenden Overloads der Mutations-Methoden von std::map zu verwenden. Weiterhin kann std::map::extract genutzt werden, um effizient Einträge zu verschieben, ohne sie zu kopieren.
Das Problem mit diesem Ansatz ist, dass std::map zwar dafür sorgt, dass bestehende Iteratoren soweit möglich valide bleiben, während Mutationen, insbesondere extract, den Iterator invalidieren, den man hineingibt (was sich auch logisch nicht vermeiden lässt). Man muss also überprüfen, ob nicht aus Versehen an irgend einer Stelle ein invalider Iterator dereferenziert wird.
Außerdem fand ich es kompliziert (ich bin aber auch alles andere als ein C++-Experte), den Überblick über die verschiedenen (historisch gewachsenen) Overloads von Methoden, wie insert, zu behalten. Zudem diese sich teilweise wesentlich unterschiedlich verhalten und teilweise unterschiedliche Typen von Werten zurückgeben.
Mit BTreeMap
Rusts Standardimplementation einer Ordered Map ist std::collections::BTreeMap. Dass C++' std::map einen Rot-Schwarz-Tree verwendet, während Rust (wie der Name impliziert) einen B-Tree einsetzt, ist in diesem Zusammenhang ein Implementationsdetail. Beide eignen sich für die gleichen Zwecke und bieten ähnliche Performance-Garantien.
Zuerst war ich überrascht zu sehen, dass fast alle Methoden von BTreeMap als Input einen Key akzeptieren (keinen Iterator) und einen Lookup (O(log(n))) durchführen, bevor sie die entsprechenden Einträge zurückgeben oder modifizieren. Dann habe ich entdeckt, dass es zwei neue APIs in (zumindest momentan noch) nightly Rust gibt, offensichtlich angeregt von std::map:
BTreeMap::lower_bound
BTreeMap::upper_bound
// und die mutierenden äquivalente
BTreeMap::lower_bound_mut
BTreeMap::upper_bound_mutDiese geben Objekte vom typ Cursor (bzw. CursorMut, das mutierende Äquivalent) zurück, die exakt das tun was ich brauche.
Cursor sind wie Iteratoren, aber sie zeigen nicht auf ein Element sondern zwischen zwei Elemente, so dass ich sie nutzen kann, um einen mutierenden Cursor zu erhalten, der vor das erste Element in meinem Wertebereich zeigt.
Mit diesem Cursor kann ich:
Effizient Elemente in die Lücke einfügen, in die mein Cursor gerade zeigt. Danach zeigt der Cursor, je nachdem wo ich weiterarbeiten möchte, vor oder hinter das eingefügte Element.
Elemente vor oder hinter dem Cursor entfernen, wonach der Cursor in die durch das Entfernen entstandene Lücke zeigt.
Die entfernten Elemente effizient an anderer Stelle wieder einfügen, weil Rust per default move-semantics verwendet und Werte sowieso nur kopiert werden, wenn es explizit per
cloneangefragt wird.Referenzen zu den Elementen vor und hinter dem Cursor erhalten mit den peek-methoden des Cursor.
Den Cursor frei Element-weise nach links und rechts zu bewegen mit
nextundprev.
Diese API fühlt sich extrem natürlich an für die gesuchte Funktionalität und führt alle Operationen auf eine effiziente und standardmäßig sichere Art aus.