C++: Reduce und Collect

von Hubert Schmid vom 2014-06-01

Was in Java Stream::reduce und Stream::collect ist, ist std::accumulate in C++. Ein genauerer Blick auf dieses Funktionstemplate deckt jedoch Schwächen beim Umgang mit R‑Value-Referenzen auf. Anscheinend wurde die Spezifikation mit C++11 nicht angepasst. Dieser Artikel zeigt Alternativen.

reduce

Die Summenbildung ist ein typisches Beispiel für die Verwendung von std::accumulate. Elemente des Typs int lassen sich mit std::accumulate(v.begin(), v.end(), 0) summieren. Die Berechnung mit int ist effizient. Verwendet man dagegen einen Typ mit dynamischer Speicherverwaltung – wie beispielsweise einen Integer-Typ unbeschränkter Größe – so leidet die Laufzeit unter zahlreichen Kopierkonstruktionen.

Das Problem lässt durch geeigneten Einsatz der Move-Semantik vermeiden. Das folgende Listing zeigt eine effizientere Alternative zu std::accumulate, die Move-Semantik berücksichtigt.

template <typename Iterator, typename Ac, typename Op>
auto reduce(Iterator first, Iterator last, Ac ac, Op&& op) -> Ac
{
    for (; first != last; ++first) {
        ac = op(std::forward<Ac>(ac), *first); // line A
    }
    return std::forward<Ac>(ac); // line B
}

Bei dieser Implementierung sind Move-Operationen potentiell an drei Stellen relevant:

In der Zeile A wird der Akkumulator ac der Operation op explizit mittels std::forward übergeben, da der Akkumulator anschließend sowieso überschrieben wird.
Ebenfalls in der Zeile A kann für den Ausdruck *first die Move-Semantik genutzt werden, wenn ein passender Iterator-Typ verwendet wird (beispielsweise std::move_iterator).
Und schließlich wird in der Zeile B explizit std::forward verwendet, um Move-Konstruktion für den Rückgabewert verwenden zu können. Denn an dieser Stelle greift die sogenannte Return-Value-Optimization nicht.

Besonderes Augenmerk liegt auf dem Template-Parameter A. Entweder wird er explizit angegeben, oder er wird automatisch beim Aufruf aus den Argumenten abgeleitet. Nur im ersten Fall kann es sich um einen Referenztyp handeln. Wichtig dabei ist, dass std::forward im Gegensatz zu std::move dafür sorgt, dass für L‑Value-Referenzen keine Move-Semantik genutzt wird.

Ein Beispiel: Im folgenden Listing wird reduce verwendet, um einen std::vector<int> mittels Iterator-Paar zu befüllen. Auch wenn es einfachere Methoden gibt, um das Gleiche zu erreichen, ist diese Verwendung dennoch effizient. Denn der Kopierkonstruktor von std::vector<int> wird kein einziges Mal aufgerufen.

using ints = std::vector<int>;
ints result = reduce(input.begin(), input.end(), ints{},
    [](ints lhs, int rhs) {
        lhs.push_back(rhs);
        return lhs;
    });

collect

In Java gibt es mit Stream::collect eine Variante zu Stream::reduce, die sich besser für Operationen eignet, die den Akkumulator in-place verändern. Eine entsprechende Variante wäre auch in C++ wünschenswert. Das folgende Listing zeigt, wie eine Implementierung dazu aussehen könnte.

template <typename Iterator, typename Ac, typename Op>
auto collect(Iterator first, Iterator last, Ac ac, Op&& op) -> Ac
{
    for (; first != last; ++first) {
        op(ac, *first);
    }
    return std::forward<Ac>(ac);
}

Analog zu reduce unterstützt diese Implementierung die Move-Semantik für *first – falls ein geeigneter Iterator verwendet wird – und für den Rückgabewert. Beim Aufruf der Operation op wird der Akkumulator ac dagegen stets als L‑Value-Referenz übergeben.

Obiges Beispiel lässt sich damit wie folgt vereinfachen. Wiederum wird der Kopierkonstruktor von std::vector<int> nicht aufgerufen, und im Gegensatz zu reduce ist nicht nur die Lambda-Funktion kompakter sondern es werden auch zahlreiche Move-Konstruktionen gespart.

ints result = collect(values.begin(), values.end(), ints{},
    [](ints& lhs, int rhs) { lhs.push_back(rhs); });

Schade, dass bei C++11 versäumt worden ist, das Funktionstemplate std::accumulate zu überarbeiten. Leider ignoriert es die Move-Semantik, was die sinnvollen Verwendungsmöglichkeiten einschränkt. Doch man kann es auch positiv sehen: Die Funktionalität ist so einfach, dass man sie selbst implementieren kann, und sie bietet die Gelegenheit, sich intensiver mit dem Thema zu beschäftigen, als man es vermutlich sonst getan hätte.