std::map: emplace und die kontrollierte Objekterzeugung

Seit C++11 besitzen viele Container der Standardbibliothek eine oder mehrere emplace-Funktionen, mit denen sich Objekte an Ort und Stelle erzeugen lassen. Auch std::map bietet mit emplace und emplace_hint zwei solcher Funktionen. In diesem Artikel betrachte ich, wie sich unnötige Objekterzeugungen beim Einfügen von Elementen in eine std::map vermeiden lassen, und welche Rolle emplace dabei spielt.

Zunächst einmal ist ein wichtiger Use-Case zu nennen: Möchte man Objekte direkt in eine std::map einfügen, die weder kopierbar noch verschiebbar sind, dann funktioniert das nur über eine der beiden emplace-Funktionen. Das folgende Listing zeigt ein Beispiel mit std::atomic. Für die erste Anweisung mit insert liefert der Compiler einen Fehler, da std::atomic<int> nicht kopierbar ist. Die Anweisung mit emplace funktioniert dagegen.

Der emplace-Aufruf sieht ein wenig umständlich aus. Leider ist in diesem Fall die einfache Form emplace("foo", 0) aufgrund einer übermäßig restriktiven Spezifikation nicht möglich. Dafür kann diese Form auch verwendet werden, wenn die Objekte mit mehr als einem Argument konstruiert werden sollen.

Der Aufruf von emplace sollte allerdings nicht darüber hinwegtäuschen, dass das Objekt selbst dann erzeugt wird, wenn bereits ein Eintrag mit gleichem Key existiert. Die Formulierung im Sprachstandard ist diesbezüglich etwas schwammig. Doch bei genauerer Betrachtung wird offensichtlich, dass die Konstruktion notwendig ist, um feststellen zu können, ob dies der Fall ist.

Im Fall von std::atomic spielt die unnötige Konstruktion keine Rolle. In anderen Fällen kann es jedoch sehr wohl ein Problem sein – entweder weil die Konstruktion aufwendig ist, oder weil sie hinderlich ist. Möchte man diesen Fall vermeiden, so bleibt einem nichts anderes übrig, als vorab zu testen, ob ein entsprechender Key bereits existiert. Dafür bietet sich die Member-Funktion lower_bound an, deren Rückgabewert mit emplace_hint verwendet werden kann, um eine zweite Suche zu vermeiden.

In diesem Fall wird zwar aus "bar" nur dann ein std::string erzeugt, wenn tatsächlich ein Eintrag eingefügt wird. Doch der Code hat das Problem unnötiger Konstruktionen nicht gelöst sondern nur an eine andere Stelle verschoben: Beim Aufruf von lower_bound wird aus "foo" ein std::string für die Suche erzeugt.

Mit C++14 gibt es dafür allerdings eine Lösung: Ab dieser Version können die Member-Funktionen find, lower_bound und upper_bound mit beliebigen Typen verwendet werden – vorausgesetzt sie werden von der Vergleichsfunktion unterstützt, die der Datenstruktur zu Grund liegt. Das folgende Listing enthält dazu ein Beispiel. Die Klasse transparent_less unterstützt neben dem Vergleich zweier std::string-Objekte auch alle anderen Typen, die von operator< unterstützt werden. Signalisiert wird diese Unterstützung durch den Member is_transparent.

Der Typ transparent_less dient nur zur Veranschaulichung, denn mit der Spezialisierung std::less<> gibt es in der Standardbibliothek bereits einen Typ, der sich genau so verhält. Dieser kommt im folgenden Listing zum Einsatz. Der restliche Code ist identisch zum obigen Listing. Doch dieses Mal werden die std::string-Objekte nur noch erzeugt, wenn tatsächlich ein Element in die std::map eingefügt wird.

Zu dem Beispiel sollte man anmerken, dass die Implementierung dadurch nicht zwangsweise effizienter wird. Es wird zwar kein unnötiges std::string-Objekt mehr erzeugt. Dafür ist der Vergleich zweier Zeichenketten jedoch potentiell teurer, da die Länge a priori nicht bekannt ist. Unabhängig davon kann man festhalten, dass C++14 alle Voraussetzungen enthält, um unnötige Objekt-Erzeugungen zu unterbinden, dass die Member-Funktion emplace dabei allerdings nur eine kleine Rolle spielt.