C++11 am Beispiel: Zeilenweise Umkehrung der Eingabe

von Hubert Schmid vom 2011-12-04

Ich mache mich zur Zeit mit den Neuerungen von C++11 vertraut. Und besonders interessant finde ich, wie sich die Möglichkeiten der neuen Sprachversion auf ganz normalen Code auswirken. Um ein Gefühl dafür zu entwickelzan, habe ich mir einen einfachen Anwendungsfall ausgesucht. Die Eingabe soll zeilenweise eingelesen und die Zeilen in umgekehrter Reihenfolge wieder ausgegeben werden – also ungefähr die Kernfunktionalität des Kommandozeilenprogramms tac.

Das Beispiel

Beginnen werde ich mit einer Version für C++03. Die vollständige Fehlerbehandlung verbleibt in der Verantwortung des Funktionsaufrufers, und die Verwendung des typedef für std::string wird später klar werden. Außerdem habe ich mich dafür entschieden, für die Ausgabe in umgekehrter Reihenfolge über die Elemente zu iterieren. Alternativ hätte man die Elemente auch umgekehrt einfügen können (mit std::deque::push_front) oder die Reihenfolge zwischen der Eingabe und der Ausgabe umkehren können (mit std::reverse). Aus meiner Sicht wägt diese erste Version relativ gut zwischen Lesbarkeit und Effizienz ab und stellt eine gute Ausgangsbasis für die folgenden Betrachtungen dar.

#include <iostream>
#include <string>
#include <vector>

void tac(std::istream& is, std::ostream& os)
{
    typedef std::string line;
    std::vector<line> items;

    // read lines
    line item;
    while (getline(is, item)) {
        items.push_back(item);
    }

    // dump lines in reverse order
    for (std::vector<line>::const_reverse_iterator i = items.rbegin(),
             j = items.rend(); i != j; ++i) {
        os << *i << '\n';
    }
}

Die Ausgabe

Zunächst wende ich mich dem Ausgabeteil der Funktion zu, da in diesem Teil gleich mehrere neue Sprachkonstrukte zum Einsatz kommen können. Meine erste Variante setzt die Typinferenz mit auto ein, um den langen und unbedeutenden Typ des Iterators zu entfernen. Und damit der Code weiterhin mit Const-Iteratoren arbeitet, verwende ich die beiden neuen Member-Funktionen crbegin und crend, während im ursprünglichen Code die Iteratoren implizit bei der Initialisierung konvertiert werden.

    // dump lines in reverse order
    for (auto i = items.crbegin(), j = items.crend(); i != j; ++i) {
        os << *i << '\n';
    }

Für die zweite Variante verwende ich die neu eingeführten Lambda-Ausdrücke. Damit werden einige Algorithmen der Standardbibliothek für mich viel interessanter. Beispielsweise kann ich mich nicht daran erinnern, die Template-Funktion std::for_each vor C++11 jemals eingesetzt zu haben. Aber das folgende Beispiel zeigt, dass es nun durchaus sinnvoll sein kann.

    // dump lines in reverse order
    std::for_each(lines.crbegin(), lines.crend(),
        [&os](const line& item) { os << item << '\n'; });

In der dritten Variante möchte ich die neue range-based for-Schleife einsetzen. Das wäre sehr einfach, wenn wir vorwärts über den Container iterieren würden. Für die Iteration über den Bereich, der durch zwei Iteratoren definiert ist, brauchen wir allerdings noch einen kleinen Zwischenschritt, um die beiden Iteratoren in einen Range zu adaptieren. Dafür eignet sich beispielsweise die Funktion boost::make_iterator_range aus der Boost-Bibliothek.

Eine entsprechende Funktion vermisse ich noch in der Standard-Bibliothek. Da ich mich in diesem Beispiel nicht auf die Boost stützen möchte, zeige ich im folgenden eine einfache Implementierung, die für die for-Schleife ausreichend ist.

template <typename Iterator>
struct range
{
    Iterator _begin;
    Iterator _end;
    auto begin() const -> Iterator
    {
        return _begin;
    }
    auto end() const -> Iterator
    {
        return _end;
    }
};

// convenience function to create instance supporting type inference
template <typename Iterator>
auto make_range(Iterator begin, Iterator end) -> range<Iterator>
{
    return range<Iterator>{begin, end};
}

Damit lässt sich der Ausgabeteil nun einfach entsprechend schreiben. Wichtig finde ich noch, dass die Schleifenvariable als Referenz deklariert wird, um unnötige Kopieroperationen zu vermeiden. Auch wenn es an dieser Stelle unnötig ist, so verwende ich persönlich lieber &&. Wie beim Perfect-Forwarding kann die Variable dann sowohl L‑Value- als auch R‑Value-Referenz sein.

    // dump lines in reverse order
    for (auto&& item : make_range(items.crbegin(), items.crend())) {
        os << item << '\n';
    }

Bemerkenswert finde ich, dass alle drei Varianten ungefähr die gleiche Laufzeiteffizienz haben. Sowohl die beiden Template-Funktionen std::for_each und make_range als auch die Lambda-Funktion wird der Übersetzer vermutlich vollständig entfernen. Und der verbleibende Teil ist auf der Maschinenebene weitgehend identisch.

Der Vollständigkeit wegen zeige ich noch eine weitere Variante des Ausgabeteils. Ich weiß, dass einige Leute diese Variante bevorzugen. Und von den gezeigten Varianten ist es nicht nur die Kürzeste sondern kommt dabei auch mit C++03 aus (abgesehen von crbegin und crend). Mir persönlich gefällt sie allerdings am wenigsten, weil ich std::copy nicht auf natürliche Weise mit der Ausgabe verbinde, und der Code daher für mich weniger intuitiv als die vorherigen Beispiele ist.

    // dump lines in reverse order
    std::copy(items.crbegin(), items.crend(),
        std::ostream_iterator<line>(os, "\n"));

Die Eingabe

Die Anpassung des Eingabeteils fällt mir ein wenig schwerer. Ein erster Schritt ist aber sicherlich die Verwendung von std::move, die sich in diesem Beispiel geradezu anbietet. Damit entfällt für jede Zeile eine Kopieroperation, was in diesem Beispiel einen signifikanten Unterschied beim Laufzeitverhalten machen kann.

    // read lines
    line item;
    while (getline(is, item)) {
        items.push_back(std::move(item));
    }

Das wäre natürlich auch mit C++03 möglich gewesen – allerdings nicht so einfach. Beispielsweise hätte man immer zuerst eine leere Zeile in den Container einfügen können um mit einem anschließenden items.back().swap(item) sie mit dem eigentlichen Inhalt zu ersetzen.

Die weiteren Schritte sind ein wenig komplizierter. Das Ziel sollte eigentlich sein, den Vector direkt mit zwei Iteratoren zu initialisieren. Dafür bietet die Standard-Bibliothek den std::istream_iterator an, und damit sähe der Eingabeteil so aus:

    // read lines
    typedef std::string line;
    typedef std::istream_iterator<line> line_iterator;
    // NOTE: std::move_iterator conflicts with std::istream_iterator
    std::vector<line> items{line_iterator{is}, line_iterator{}};

Allerdings funktioniert das so nicht, weil die Eingabe damit wortweise statt zeilenweise gelesen wird. Eine mögliche Lösung wäre, einen eigenen Iterator zu implementieren. Das ist aber nicht trivial – auch nicht für Input-Iteratoren. Einfacher ist es den obigen Code zusammen mit einem benutzerdefinierten Typ zu verwenden, der den Eingabe-Operator passend überlädt.

class line
{
    std::string _value;
    friend auto operator>>(std::istream& is, line& item)
        -> std::istream&
    {
        return getline(is, item._value);
    }
    friend auto operator<<(std::ostream& os, const line& item)
        -> std::ostream&
    {
        return os << item._value << '\n';
    }
};

Einen korrespondierenden Ausgabe-Operator habe ich dabei auch gleich definiert, denn damit bleibt der restliche Code weitgehend unberührt – außer dass der Zeilenumbruch nicht mehr explizit ausgegeben werden muss.

Der Code ist durch diese Maßnahmen allerdings nicht einfacher geworden. Die Verwendung lohnt sich nur, wenn man die zusätzliche Klasse auch aus anderen Gründen braucht. Und auch die Kopieroperation für jede Zeile, die ich weiter oben mit Hilfe von std::move beseitigt habe, hat sich nun wieder eingeschlichen.

Das Ende

Insgesamt ging es mir bei diesem Beispiel weder darum, den kürzesten noch den effizientesten Code zu erstellen. Vielmehr war das Ziel, ein wenig mit den neuen Möglichkeiten aus C++11 zu experimentieren und ein Gefühl dafür zu entwickeln. Und auch wenn mir das beim Eingabeteil nicht gelungen ist, so finde ich doch die Ergebnisse insgesamt sehr interessant und machen Lust auf mehr C++11.