C++11: split, sort und join

von Hubert Schmid vom 2011-12-18

In Vorträgen zu alternativen Programmiersprachen auf der JavaVM (wie beispielsweise JRuby und Scala) kommt am Anfang häufig ein Beispiel, das motivieren soll, wie viel einfacher diese Sprachen doch sind. Beispielsweise wird ein Einzeiler gezeigt, der eine Zeichenkette aufteilt, die einzelnen Worte nach Länge sortiert und zusammengehängt wieder ausgibt. In Python sieht das so aus:

print(' '.join(sorted('python is cool'.split(), key=len)))

Aus meiner Sicht zeigen solche Beispiele aber hauptsächlich Eigenschaften der zugehörigen Bibliotheken statt der Sprachen selbst. Denn solche Einzeiler wären in C++ und Java ebenfalls möglich, wenn deren Standard-Bibliotheken die entsprechenden Funktionen enthielten.

Ich nehme das als Motivation, solche Funktionen beispielhaft für C++ aufzuzeigen, und mich dabei gleichzeitig mit den neuen Features von C++11 auseinanderzusetzen. Alternativ hätte ich das Gleiche natürlich auch mit Java machen können.

split

Ich starte mit einem ersten Entwurf für die split-Funktion. Auffallend daran sind die emplace-Methoden, durch die jeweils eine Kopieroperation beim Einfügen in den Container eingespart wird. Außerdem ist die Rückgabe per Value in C++11 harmlos. Denn entweder greift beim Aufrufer die Return-Value-Optimization (RVO, NRVO) oder die neue Move-Semantik.

auto split(const std::string& value, char separator)
    -> std::vector<std::string>
{
    std::vector<std::string> result;
    std::string::size_type p = 0;
    std::string::size_type q;
    while ((q = value.find(separator, p)) != std::string::npos) {
        result.emplace_back(value, p, q - p);
        p = q + 1;
    }
    result.emplace_back(value, p);
    return result;
}

Diese Funktion akzeptiert bisher lediglich ein einzelnes Zeichen als Trenner. Ich möchte aber auch eine Liste von Zeichen übergeben können, die als Trennzeichen verwendet werden. Damit ich den Algorithmus nicht kopieren muss, refaktorisiere ich die oben stehende Funktion in ein Funktionstemplate, das für beliebige Trenner verwendet werden kann.

// NOTE: put this into the detail namespace
template <typename Separator>
auto split_aux(const std::string& value, Separator&& separator)
    -> std::vector<std::string>
{
    std::vector<std::string> result;
    std::string::size_type p = 0;
    std::string::size_type q;
    while ((q = separator(value, p)) != std::string::npos) {
        result.emplace_back(value, p, q - p);
        p = q + 1;
    }
    result.emplace_back(value, p);
    return result;
}

Statt einem Trennzeichen erwartet die Funktion nun ein Funktionsobjekt, das die Position des nächsten Trennzeichens zurückgibt. Positiv auffallend daran ist, dass die Implementierung weitgehend gleich geblieben ist. Das ist in der Regel ein gutes Zeichen für eine Generalisierung.

Das Funktionsobjekt wird übrigens mit && qualifiziert, weil dadurch das Template noch ein wenig allgemeiner ist. Vereinfacht gesagt bedeutet das, dass sowohl L- als auch R‑Values an diesen Parameter gebunden werden können – also insbesondere auch temporäre Zwischenobjekte. Im Rumpf der Methode wird die Referenz hingegen stets als L‑Value-Referenz verwendet.

Mit Hilfe dieses Templates kann ich nun einfach die beiden überladenen split-Funktionen definieren. Auch weitere Funktionen, die beispielsweise viele Trennzeichen effizienter behandeln, sind einfach möglich. Noch besser würde mir der Code allerdings gefallen, wenn die Syntax für Lambda-Funktionen nicht so ausführlich wäre. Aber dafür muss ich wohl auf die nächste C++‑Version warten.

auto split(const std::string& value, char separator)
    -> std::vector<std::string>
{
    return split_aux(value,
        [=](const std::string& v, std::string::size_type p) {
            return v.find(separator, p);
        });
}

auto split(const std::string& value, const std::string& separators)
    -> std::vector<std::string>
{
    return split_aux(value,
        [&](const std::string& v, std::string::size_type p) {
            return v.find_first_of(separators, p);
        });
}

sort

Eine sort-Funktion existiert in C++ bereits. Diese entspricht aber von der Verwendung nicht dem, was ich oben im Python-Beispiel gezeigt habe. Ich möchte daher eine Sortierfunktion haben, die erstens eine Range statt einem Iterator-Paar und zweitens eine Key-Funktion statt einer Vergleichsfunktion erwartet.

Vermeiden möchte ich hingegen eine Funktion, die eine Referenz als Rückgabetyp besitzt. Denn solche Funktionen können zu merkwürdigen Problemen führen, wenn sie zusammen mit der Lebenszeitverlängerung temporärer Objekte durch Referenzen verwendet werden. Das ist in diesem Fall tatsächlich relevant, weil die Funktion im Kopf einer Range-Based-For-Schleife verwendet werden könnte, womit im Rumpf der Schleife unter bestimmten Umständen mit Dangling-References gearbeitet wird – was ziemlich sicher früher oder später zu sehr kuriosen Fehlern führt.

// NOTE: put this into the detail namespace
template <typename KeyFn>
struct key_fn_adaptor
{
    KeyFn&& _key_fn;
    template <typename Lhs, typename Rhs>
    auto operator()(Lhs&& lhs, Rhs&& rhs) const -> bool
    {
        return _key_fn(lhs) < _key_fn(rhs);
    }
};

template <typename Range, typename KeyFn>
void sort_range_with_key_fn(Range&& range, KeyFn&& key_fn)
{
    // enable ADL with fallback on default implementations
    using std::begin;
    using std::end;
    std::sort(begin(range), end(range),
        key_fn_adaptor<KeyFn>{std::forward<KeyFn>(key_fn)});
}

join

Auch die join-Funktion ist sehr einfach umzusetzen. Die folgenden Punkte sind mir dabei allerdings wichtig: Erstens möchte ich sowohl Ranges als auch Iterator-Paare verwenden können. Zweitens sollen beliebige Trenner verwendet werden können. Und drittens soll auch der Spezialfall eines leeren Trenners effizient sein.

// NOTE: put this into the detail namespace
class noop
{
    friend auto operator<<(std::ostream& os, const noop&)
        -> std::ostream&
    {
        return os;
    }
} noop;

template <typename Iterator, typename Separator>
auto join(Iterator first, Iterator last, Separator&& separator = noop)
    -> std::string
{
    if (first == last) {
        return std::string{};
    } else {
        std::ostringstream os;
        os << *first;
        for (++first; first != last; ++first) {
            os << separator << *first;
        }
        return os.str(); // NOTE: move is currently not supported
    }
}

template <typename Range, typename Separator>
auto join_range(Range&& range, Separator&& separator = noop)
    -> std::string
{
    // enable ADL with fallback on default implementations
    using std::begin;
    using std::end;
    return join(begin(range), end(range), std::forward<Separator>(separator));
}

Auch diese Funktionstemplates sollten eigentlich nicht überraschen. Anstatt die Funktionen zu überladen habe ich unterschiedliche Namen gewählt. Andernfalls könnte der Compiler nicht in jedem Falle die richtige Funktion bestimmen, da beide Templates mit zwei Parametern instanziiert werden können.

Bemerkenswert und bedauerlich finde ich lediglich, dass es anscheinend keine Möglichkeit gibt, den std::string aus dem std::ostringstream ohne Kopie herauszubekommen. Aber ich gehe davon aus, dass auch solche Dinge noch kommen werden, sobald sich die Move-Semantik ein wenig verbreitet hat.

all

Mit diesen Hilfsfunktionen und -templates setze ich nun das obige Python-Beispiel in C++ um. Und trotz der ganzen Vorarbeit ist es immer noch deutlich länger und gesprächiger. Doch zumindest kann man sehen, dass mit einer entsprechenden Bibliothek die einfache Textverarbeitung auch in C++ recht einfach ist.

auto&& tokens = split("c++11 is awesome", ' ');
sort_range_with_key_fn(tokens, std::mem_fn(&std::string::size));
std::cout << join_range(tokens, ' ') << '\n';