Variationen variadischer Templates in C++

von Hubert Schmid vom 2013-06-23

In Python gibt es die Funktion zip, die eine beliebige Anzahl iterierbarer Objekte nimmt und einen Iterator liefert, der die Elemente aller Argumente jeweils zu einem Tupel zusammenfasst. In C++ ist das ein typischer Anwendungsfall für variadische Templates und gleichzeitig ein gutes Beispiel, verschiedene Implementierungsalternativen aufzuzeigen. Genau das werde ich in diesem Artikel machen.

Einfaches Beispiel

Ich beginne mit einem einfachen Beispiel. Im folgenden Listing werden zwei std::vector verwendet, die mit zip zusammengefasst werden, um anschließend über die Tupel (1, 'A'), (2, 'B') und (3, 'C') zu iterieren.

using ints = std::vector<int>;
using chars = std::vector<char>;
for (auto&& item : zip(ints{1, 2, 3}, chars{'A', 'B', 'C'})) {
    print(item);
}

Bevor ich auf die eigentliche Implementierung eingehe, betrachte ich zunächst den Randfall ohne Argumente. Wie in Python wird in diesem Fall ein leerer Container zurückgegeben. Alle drei Varianten decken ihn über die folgende, überladene Funktion ab. Sie ist sehr einfach – verwendet allerdings bereits die Return-Type-Decuction aus C++14, die vor allem die folgenden Listings vereinfachen wird.

auto zip() { return std::vector<std::tuple<>>{}; }

1. Variante

C++11 und C++14 beschränken die Unterstützung variadischer Templates auf das Notwendigste. In vielen Fällen kommt man damit dennoch überraschend weit. Das folgende Funktionstemplate ist vergleichsweise einfach und funktioniert für obiges Beispiel ausgezeichnet. Die wesentliche Einschränkung ist, dass es nur mit Argumenten vom Typ std::vector verwendet werden kann.

template <typename ...Types>
auto zip(const std::vector<Types>&... vectors)
{
    static_assert(sizeof...(Types) >= 1, "requires at least one argument");
    auto size = std::min({ vectors.size()... });
    std::vector<std::tuple<Types...>> result;
    result.reserve(size);
    for (decltype(size) i = 0; i != size; ++i) {
        result.emplace_back(vectors[i]...);
    }
    return result;
}

In dieser Implementierung gibt es zwei beachtenswerte Stellen: Erstens wird mit std::min bestimmt, wie viele Elemente das Ergebnis enthalten wird. Dazu werden die Längen der einzelnen Argumente in eine std::initializer_list expandiert. Zweitens werden die Elemente aller Argumente auf die gleiche Weise über einen Index adressiert, so das eine Laufvariable ausreichend ist.

Komplexes Beispiel

Die zip-Funktion sollte grundsätzlich auch mit anderen Datenstrukturen funktionieren, die sich wie Container verhalten. Daher werden im folgenden Beispiel ein natives Array, eine std::initializer_list und eine std::list verwendet.

auto&& foo = { 'A', 'B', 'C' };
double bar[] = { 0.1, 0.2, 0.3, };
for (auto&& item : zip(std::list<int>{1, 2, 3}, foo, bar)) {
    print(item);
}

Die erste Variante scheitert an diesem Aufruf, da erstens die Template-Typen nicht automatisch bestimmt werden können, und da sich zweitens die Parameter vom Typ std::vector nicht direkt aus den Argumenten initialisieren lassen. Die folgenden beiden Varianten schließen diese Lücke.

2. Variante

Eine allgemeine Implementierung für Ranges muss intern Iteratoren verwenden. Dabei wird für jedes Argument ein eigenes Iterator-Paar benötigt. Eine Möglichkeit mit der variablen Anzahl Iterator-Paare umzugehen, ist diese selbst in Tupel zu verpacken. Genau das wird in der folgenden Implementierung gemacht. Um die Iteratoren im Tupel jedoch wieder adressieren zu können, werden zusätzliche Template-Parameter für die Indizes benötigt.

template <std::size_t ...Indexes, typename ...Ranges>
auto zip_aux(indexes<Indexes...>, Ranges&&... ranges)
{
    static_assert(sizeof...(Ranges) >= 1, "requires at least one argument");
    using std::begin;
    using std::end;
    std::vector<std::tuple<std::decay_t<decltype(*begin(ranges))>...>> result;
    auto p = std::make_tuple(begin(ranges)...);
    auto q = std::make_tuple(end(ranges)...);
    while (all(std::get<Indexes>(p) != std::get<Indexes>(q)...)) {
        result.emplace_back(*std::get<Indexes>(p)...);
        pass{++std::get<Indexes>(p)...};
    }
    return result;
}

Die Funktion all liefert die Und-Verknüpfung der Argumente und ist selbst über ein einfaches, variadisches Funktionstemplate realisiert. Bei pass handelt es sich um ein weiteres und gebräuchliches Hilfskonstrukt, um mehrere Ausdrücke ohne weiteren Effekt auswerten zu können. Schließlich ist noch der erste Parameter der Funktion speziell: Er wird lediglich für die Inferenz der Indizes benötigt, und die einzige Aufgabe der folgenden Funktion besteht darin, für diese Inferenz zu sorgen.

template <typename ...Ranges>
auto zip(Ranges&&... ranges)
{
    return zip_aux(build_indexes<sizeof...(Ranges)>{}, std::forward<Ranges>(ranges)...);
}

Die Klassentemplates indexes und build_indexes sind Hilfskonstrukte, die bei der Programmierung mit variadischen Templates vergleichsweise häufig eingesetzt werden. Leider sind sie nicht Bestandteil der offiziellen Standardbibliothek, und müssen daher immer wieder neu erfunden werden. Um die Beispiele kurz zu halten habe ich in diesem Fall aber einfach auf die Klassentemplates der GCC-Bibliothek wie folgt zurückgegriffen.

template <std::size_t ...Indexes>
using indexes = std::_Index_tuple<Indexes...>;
template <std::size_t Size>
using build_indexes = typename std::_Build_index_tuple<Size>::__type;

3. Variante

Die vorherige Implementierung ist bereits relativ gut. Es geht allerdings noch besser und einfacher, wenn man die Iteratoren umgekehrt verwendet: Anstatt für begin- und end-Iteratoren ein Tupel zu konstruieren, konstruiert man für jedes Argument ein Paar aus begin- und end-Iterator.

template <typename ...Iterator>
auto zip_aux(std::pair<Iterator, Iterator>... ranges)
{
    static_assert(sizeof...(Iterator) >= 1, "requires at least one argument");
    std::vector<std::tuple<typename std::iterator_traits<Iterator>::value_type...>> result;
    while (all(ranges.first != ranges.second...)) {
        result.emplace_back(*ranges.first...);
        pass{++ranges.first...};
    }
    return result;
}

Wie man sieht vereinfacht sich die Implementierung, da nun keine Indizes mehr benötigt werden. Die Trennung in zwei Funktionstemplate bleibt dagegen erhalten, da nun die Iterator-Paare erzeugt werden müssen.

template <typename ...Ranges>
auto zip(Ranges&&... ranges)
{
    using std::begin;
    using std::end;
    return zip_aux(std::make_pair(begin(ranges), end(ranges))...);
}

Fazit

Man kann das gleiche Ziel mit variadischen Templates ganz unterschiedlich erreichen. Auffallend ist, dass einige Hilfskonstrukte immer wieder benötigt werden, jedoch leider nicht Bestandteil der Standardbibliothek sind. Und auch die Kernsprache beschränkt die Unterstützung auf das Minimale. Doch trotz allem sind die Implementierungen erstaunlich einfach und verständlich – insbesondere wenn man sie mit den Alternativen vergleichen würde, die ohne variadische Templates auskommen. Allein der Gedanke daran ...