C++11: Zähl mich! Aber richtig!

von Hubert Schmid vom 2013-05-12

Die Berichterstattung zu C++ hat in den letzten zwei Jahren gefühlt stark zugenommen. In Fachzeitschriften finden sich vermehrt Artikel, die gegen alte Vorurteile antreten und ein modernes C++ präsentieren. Diese Entwicklung finde ich sehr erfreulich. Allerdings sind mir die Beispiele in manchen Fällen nicht modern genug.

Anhand des Artikels Zähl mich! aus dem Linux-Magazin 06/2013 gehe ich auf zehn Punkte ein. Dazu verwende ich Fragmente aus dem zugehörigen Beispiel. Um die Darstellung kurz und übersichtlich zu halten, gebe ich den Programmtext nicht originalgetreu wieder, sondern passe ihn ein wenig an meine Darstellung an. Dabei versuche ich jedoch, die Absicht des ursprünglichen Autors nicht zu verfälschen.

occurrences

Im Beispiel wird zunächst eine in der Variablen text vorliegende Zeichenkette in Worte zerteilt und die Häufigkeit dieser Worte gezählt. Der angepasste Code ist im folgenden Listing zu sehen, wobei ich im Anschluss auf die mit 1, 2 und 3 markierten Punkte eingehen werde.

using std::string; // -- 1 --
// same with std::unordered_map, std::regex, std::sregex_iterator, ...
using str2Int = unordered_map<string, size_t>; // -- 2 --
using int2Words = map<size_t, vector<string>>;
using intAndWords = pair<size_t,vector<string>>;

regex pattern(R"(\w+)");
str2Int occurrences;
sregex_iterator tokens_begin(text.begin(), text.end(), pattern); // -- 3 --
const sregex_iterator tokens_end;
for (; tokens_begin != tokens_end; ++tokens_begin) {
    ++occurrences[tokens_begin->str()];
}

Explizite Nutzung von Namespaces: Im ursprünglichen Beispiel werden alle verwendeten Klassen, Funktionen und Objekte aus dem Namensraum std in den globalen Namensraum importiert. Dadurch wird dieses Feature weitgehend ausgehebelt – anstatt es zu nutzen.

Aus meiner Sicht unterstützt C++ die Verwendung von Namensräumen vergleichsweise gut durch kurze Namen, Aliase, Inline-Namespaces und Argument-Dependent-Name-Lookup (ADL). Daher bin ich der Meinung, man sollte Namespaces nutzen und nur in Einzelfällen die Namen in andere Namensräume importieren.
Sinnvoller Einsatz von Typ-Aliasen: Im ursprünglichen Beispiel werden mit str2Int, int2Words und intAndWords drei Aliase für parametrisierte Klassen-Templates eingeführt. Dadurch wird der Schreibaufwand im weiteren Code reduziert. Die entscheidende Frage ist hingegen: Erhöht sich dadurch auch die Lesbarkeit?

Die Antwort hängt in der Regel davon ab, wie aussagekräftig die gewählten Namen sind. Zumindest für dieses Beispiel fallen mir spontan keine guten Namen ein. Dass die drei gezeigten Namen nicht optimal sind, zeigt sich bereits daran, dass sie in sich nicht konsistent sind. Daher würde ich in diesem Fall eher auf die Aliase verzichten, denn wie sich zeigen wird, werden sie eh nur an wenigen Stellen benötigt.
Spezifische Datenstrukturen: Die Standardbibliothek unterstützt zwei Varianten, um über alle Suchergebnisse regulärer Ausdrücke zu iterieren. std::sregex_iterator liefert die Details zu jedem Ergebnis wohingegen std::sregex_token_iterator auf das Gesamtergebnis optimiert ist. Da in diesem Fall nur Letzteres benötigt wird, würde ich auch diese Datenstruktur verwenden.

Insgesamt würde ich die gleiche Funktionalität wie folgt realisieren – auch wenn ich über die komplexe for-Schleife nicht glücklich bin. An dieser Stelle fehlt aus meiner Sicht die seit langem diskutierte Unterstütztung für Ranges.

auto pattern = std::regex{R"(\w+)"};
auto occurrences = std::unordered_map<std::string, std::size_t>{};
using iterator = std::sregex_token_iterator;
for (iterator p{text.begin(), text.end(), pattern}, q; p != q; ++p) {
    ++occurrences[*p];
}

distribution

Im zweiten Teil wird umgekehrt bestimmt, welche Wörter pro Häufigkeit auftreten. Die aus meiner Sicht relevanten Punkte sind in dem leicht veränderten Code wiederum entsprechend markiert, wobei es dieses Mal ein wenig interessanter wird.

int2Words distribution;
for (auto item : occurrences) { // -- 4 --
    auto count = item.second;
    if (distribution.find(count) != distribution.end()) {
        distribution[count].push_back(item.first); // -- 5 --
    } else {
        distribution.insert(intAndWords(count, {item.first})); // -- 6 --
    }
}

Typinferenz mit Referenz: Für die Iteration über die Elemente wird im ursprünglichen Code die neue Form der for-Schleife mit Typinferenz kombiniert. Das ist grundsätzlich sinnvoll – verursacht jedoch zusätzliche Laufzeitkosten, wenn es auf diese Weise eingesetzt wird. Der Typ der Variable item ist nämlich std::pair<std::string, std::size_t>. Das bedeutet, dass bei der Iteration jedes Element einmal kopiert wird, obwohl es dafür keinen Grund gibt.

Die Lösung ist einfach: Statt auto verwendet man einfach auto& oder auto&&, wodurch die Variable zu einer Referenz wird, und die Kopie entfällt. Bei for-Schleifen ist dieses Vorgehen fast immer richtig. Dabei sind beide Varianten möglich, wobei ich persönlich Letztere bevorzuge.
Vermeidung doppelter Teilberechnungen: Der Ausdruck distribution[count] sieht harmlos aus. Tatsächlich erfolgt dabei jedoch eine Suche im Binärbaum mit logarithmischem Aufwand. Allerdings vollkommen unnötig: Denn die gleiche Suche erfolgt bereits eine Zeile zuvor. Man müsste lediglich das Ergebnis der find-Funktion speichern und darauf die push_back-Funktion aufrufen. Es geht aber noch einfacher, wie sich gleich zeigen wird.
Verwendung von Hints: Die Suche nach der Einfügeposition hat ebenfalls logarithmischen Aufwand, der sich ebenfalls optimieren lässt. Dafür müsste man statt find die Funktion lower_bound aufrufen, und das Ergebnis als zusätzlichen Parameter der insert-Funktion übergeben.

Bei genauerer Betrachtung zeigt sich, dass die gleiche Funktionalität tatsächlich viel einfacher realisiert werden kann. Im folgenden Listing ist meine präferierte Version zu sehen, die lediglich den operator[] verwendet. Das funktioniert, weil der operator[] automatisch einen Eintrag mit leerem std::vector anlegt, wenn noch kein entsprechendes Element existiert.

auto distribution = std::map<std::size_t, std::vector<std::string>>{};
for (auto&& item : occurrences) {
    distribution[item.second].push_back(item.first);
}

Anmerkung: Bei dieser Implementierung wird jedes eindeutige Wort einmal kopiert. Abhängig von der Implementierung von std::string und der durchschnittlichen Wortlänge können diese Kopien vergleichsweise teuer sein. Um den Overhead zu reduzieren könnte man statt std::string auch decltype(occurrences)::iterator verwenden. Diese Änderung wirkt sich allerdings negativ auf die Lesbarkeit aus, so dass ich sie nur vornehmen würde, wenn die Performance an dieser Stelle tatsächlich wichtig ist.

top

Im letzten Teil werden alle Wörter ausgegeben, die mindestens 1000 Mal auftreten. Zunächst zeige ich wieder den Code aus dem eigentlichen Beispiel (in leicht geänderter Form). Die Implementierung nutzt dabei die automatisch vorhandene Sortierung der Datenstruktur std::map.

auto iter = std::find_if(distribution.begin(), distribution.end(),
    [](intAndWords item) { return item.first >= 1000; }); // -- 7 & 8 --
for (; iter != distribution.end(); ++iter) {
    std::cout << iter->first << ':';
    for (auto token : iter->second) { // -- 9 --
        std::cout << ' ' << token;
    }
    std::cout << std::endl; // -- 10 --
}

Pass by Reference: Im Beispiel wird eine anonyme Funktion (Lambda-Ausdruck) verwendet, die als Parametertyp intAndWords verwendet. Da es sich um keine Referenz handelt, werden die Argumente beim Aufruf kopiert. Und das ist richtig teuer: Denn schließlich ist in dem Typ auch ein std::vector<std::string> enthalten.

Die allgemeine Regel ist: Wenn ein nicht-trivialer Parameter innerhalb einer Funktion nur gelesen und weder kopiert noch als Referenz gespeichert wird, dann sollte man ihn als Const-Referenz übergeben. Das ist sicher und effizient, und gilt auch noch für C++11.
Passende Algorithmen: Die Funktion std::find_if durchläuft die Datenstruktur beginnend beim ersten Element bis zu dem Element, für das die übergebene Funktion true liefert. Dieser Aufwand ist theoretisch linear wenn auch in dem konkreten Beispiel auf 1000 Schritte beschränkt.

Offensichtlich ist dieser Aufwand für eine sortierte Datenstruktur viel zu hoch. So sollte es kaum überraschen, dass std::map für diesen Fall die Member-Funktion lower_bound bietet, die das gleiche Element in logarithmischer Zeit findet. Unten ist zu sehen wie das aussieht.
Typinferenz mit Referenz: An dieser Stelle tritt nochmals das gleiche Problem auf, das ich bereits weiter oben beschrieben habe. Die Variable token ist vom Typ std::string und wird für jedes Element durch Kopierkonstruktion initialisiert. Das ist unnötig und lässt sich mit einer Referenz leicht vermeiden.
'\n' statt std::endl: Die Ausgabe von std::endl ist gleichbedeutend mit der Ausgabe des Zeichens '\n' und dem Aufruf der Funktion std::flush. In diesem Beispiel ist jedoch nicht ersichtlich, warum man nach jeder einzelnen Zeile Letzteres tun sollte. Es ist wesentlich effizienter und genügt, den Puffer ganz am Ende zu leeren.

Setzt man all diese Änderungen ums, so könnte der Code beispielsweise wie folgt aussehen. Er wird dadurch zwar nicht kürzer – jedoch wesentlich effizienter.

for (auto p = distribution.lower_bound(1000), q = distribution.end(); p != q; ++p) {
    std::cout << p->first << ':';
    for (auto&& token : p->second) {
        std::cout << ' ' << token;
    }
    std::cout << '\n';
}
std::cout << std::flush;

Bei all den Anmerkungen habe ich nicht vergessen, dass der ursprüngliche Autor in erster Linie die Möglichkeiten von C++11 darstellen wollte – ohne durch zu viele Details abzulenken. Trotzdem wünsche ich mir, dass man zumindest an der ein oder anderen Stelle näher an dem idiomatischem C++ dran ist, das sich für den produktiven Einsatz eignet.