25 元组

本章实现了Tuple<>,类似于std::tuple

25.1 基本设计

25.1.1 存储

最简单的方式还是将元组拆分为头和尾的形式进行存储:

// tuples/tuple0.hpp
template<typename... Types>
class Tuple;

// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
{
    private:
        Head head;
        Tuple<Tail...> tail;
    public:
        // constructors:
        Tuple() {
        }
        Tuple(Head const& head, Tuple<Tail...> const& tail)
            : head(head), tail(tail) {
        }
        // ...

        Head& getHead() { return head; }
        Head const& getHead() const { return head; }
        Tuple<Tail...>& getTail() { return tail; }
        Tuple<Tail...> const& getTail() const { return tail; }
};

// basis case:
template<>
class Tuple<> {
// no storage required
};

元组中的元素通过TupleGet<>提取:

// tuples/tupleget.hpp
// recursive case:
template<unsigned N>
struct TupleGet {
    template<typename Head, typename... Tail>
    static auto apply(Tuple<Head, Tail...> const& t) {
        return TupleGet<N-1>::apply(t.getTail());
    }
};

// basis case:
template<>
struct TupleGet<0> {
    template<typename Head, typename... Tail>
    static Head const& apply(Tuple<Head, Tail...> const& t) {
        return t.getHead();
    }
};

template<unsigned N, typename... Types>
auto get(Tuple<Types...> const& t) {
    return TupleGet<N>::apply(t);
}

25.1.2 构造函数

书中提到了其它几个构造函数,但是配套代码中没有,下面的是我自己写的:

#include <functional>

template<typename... Types>
class Tuple;

// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
{
    private:
        Head head;
        Tuple<Tail...> tail;
    public:
        // #1
        Tuple() {
        }
        // #2
        Tuple(Head const& head, Tuple<Tail...> const& tail)
            : head(head), tail(tail) {
        }
        // #3
        Tuple(Head const& head, Tail const&... tail)
            : head(head), tail(tail...) {
        }
        // #4
        template<typename VHead, typename... VTail>
        Tuple(VHead&& vhead, VTail&&... vtail)
            : head(std::forward<VHead>(vhead)), tail(std::forward<VTail>(vtail)...) {
        }
        // #5
        template<typename VHead, typename... VTail>
        Tuple(Tuple<VHead, VTail...> const& other)
            : head(other.getHead()), tail(other.getTail()) {
        }

        Head& getHead() { return head; }
        Head const& getHead() const { return head; }
        Tuple<Tail...>& getTail() { return tail; }
        Tuple<Tail...> const& getTail() const { return tail; }
};

// basis case:
template<>
class Tuple<> {
// no storage required
};

int main()
{
    Tuple<int, double, std::string> t(17, 3.14, "Hello, World!");
    Tuple<long int, long double, std::string> t2(t);
}

t2的初始化会报错,显示无法将Tuple<int, double, std::string>转换为long类型。

下面分析下构造函数的重载解析过程。1和2参数数量不匹配,3中Headlong,不能匹配Tuple<int, double, std::string>。4实例化后的构造函数为Tuple<Tuple<int, double, std::string>&>(Tuple<int, double, std::string>&),5实例化后的构造函数为Tuple<int, double, std::string>(Tuple<int, double, std::string> const&),用t初始化t2时4比5的匹配度更高,编译器将匹配构造函数4,这就导致了在构造head的过程中出现类型转换的错误。

4的本意是通过一系列的值初始化元组,5的本意是从其它的元组初始化,所以应该在两个模板构造函数中添加std::enable_if来保证参数包的大小是相同的:

template<typename VHead, typename... VTail,
            typename = std::enable_if_t<sizeof...(VTail)==sizeof...(Tail)>>
Tuple(VHead&& vhead, VTail&&... vtail)
    : head(std::forward<VHead>(vhead)), tail(std::forward<VTail>(vtail)...) { }

template<typename VHead, typename... VTail,
            typename = std::enable_if_t<sizeof...(VTail)==sizeof...(Tail)>>
Tuple(Tuple<VHead, VTail...> const& other)
    : head(other.getHead()), tail(other.getTail()) { }

类似std::make_tuple,还可以通过makeTuple()构造元组:

// tuples/maketuple.hpp
template<typename... Types>
auto makeTuple(Types&&... elems)
{
    return Tuple<std::decay_t<Types>...>(std::forward<Types>(elems)...);
}

25.2 基本操作

25.2.1 比较

比较操作判断两个元组类型是否相同:

// tuples/tupleeq.hpp
// basis case:
bool operator==(Tuple<> const&, Tuple<> const&)
{
    // empty tuples are always equivalent
    return true;
}

// recursive case:
template<typename Head1, typename... Tail1,
            typename Head2, typename... Tail2,
            typename = std::enable_if_t<sizeof...(Tail1)==sizeof...(Tail2)>>
bool operator==(Tuple<Head1, Tail1...> const& lhs, Tuple<Head2, Tail2...> const& rhs)
{
    return lhs.getHead() == rhs.getHead() && lhs.getTail() == rhs.getTail();
}

25.2.5 输出

// tuples/tupleio.hpp
#include <iostream>
void printTuple(std::ostream& strm, Tuple<> const&, bool isFirst = true)
{
    strm << ( isFirst ? '(' : ')' );
}

template<typename Head, typename... Tail>
void printTuple(std::ostream& strm, Tuple<Head, Tail...> const& t,
bool isFirst = true)
{
    strm << ( isFirst ? "(" : ", " );
    strm << t.getHead();
    printTuple(strm, t.getTail(), false);
}

template<typename... Types>
std::ostream& operator<<(std::ostream& strm, Tuple<Types...> const& t)
{
    printTuple(strm, t);
    return strm;
}

25.3 算法

元组和上一章实现的类型列表TypeList<>类似,都存储了一系列的类型,但不同的是元组中还包括类型所对应的值,因此元组所支持的算法既要在编译时确定类型,又需要在运行时对值进行计算。

25.3.1 类型操作算法

下面是元组的编译时算法,主要用来确定类型:

// tuples/tupletypelist.hpp
// determine whether the tuple is empty:
template<>
struct IsEmpty<Tuple<>> {
    static constexpr bool value = true;
};

// extract front element:
template<typename Head, typename... Tail>
class FrontT<Tuple<Head, Tail...>> {
    public:
        using Type = Head;
};

// remove front element:
template<typename Head, typename... Tail>
class PopFrontT<Tuple<Head, Tail...>> {
    public:
        using Type = Tuple<Tail...>;
};

// add element to the front:
template<typename... Types, typename Element>
class PushFrontT<Tuple<Types...>, Element> {
    public:
        using Type = Tuple<Element, Types...>;
};

// add element to the back:
template<typename... Types, typename Element>
class PushBackT<Tuple<Types...>, Element> {
    public:
        using Type = Tuple<Types..., Element>;
};

这里只有原始的类模板,没有给出别名模板。

25.3.2 值操作算法

和前一节类型操作算法对应的值算法如下:

// tuples/popfront.hpp
template<typename... Types>
PopFront<Tuple<Types...>> popFront(Tuple<Types...> const& tuple)
{
    return tuple.getTail();
}
// tuples/pushfront.hpp
template<typename... Types, typename V>
PushFront<Tuple<Types...>, V> pushFront(Tuple<Types...> const& tuple, V const& value)
{
    return PushFront<Tuple<Types...>, V>(value, tuple);
}
// tuples/pushback.hpp
// basis case
template<typename V>
Tuple<V> pushBack(Tuple<> const&, V const& value)
{
    return Tuple<V>(value);
}

// recursive case
template<typename Head, typename... Tail, typename V>
Tuple<Head, Tail..., V> pushBack(Tuple<Head, Tail...> const& tuple, V const& value)
{
    return Tuple<Head, Tail..., V>(tuple.getHead(), pushBack(tuple.getTail(), value));
}

25.3.3 反转算法

反转算法通过递归的方式实现:

// tuples/reverse.hpp
// basis case
Tuple<> reverse(Tuple<> const& t)
{
    return t;
}

// recursive case
template<typename Head, typename... Tail>
Reverse<Tuple<Head, Tail...>> reverse(Tuple<Head, Tail...> const& t)
{
    return pushBack(reverse(t.getTail()), t.getHead());
}

有了反转算法后,就可以实现弹出最后一个元素的算法了:

// tuples/popback.hpp
template<typename... Types>
PopBack<Tuple<Types...>> popBack(Tuple<Types...> const& tuple)
{
    return reverse(popFront(reverse(tuple)));
}

25.3.4 索引列表

上一节中的反转算法效率可以通过统计拷贝的次数来测量:

// tuples/copycounter.hpp
template<int N>
struct CopyCounter
{
    inline static unsigned numCopies = 0;
    CopyCounter() {
    }
    CopyCounter(CopyCounter const&) {
        ++numCopies;
    }
};
// tuples/copycountertest.hpp
void copycountertest()
{
    Tuple<CopyCounter<0>, CopyCounter<1>, CopyCounter<2>,
            CopyCounter<3>, CopyCounter<4>> copies;
    auto reversed = reverse(copies);
    std::cout << "0: " << CopyCounter<0>::numCopies << " copies\n";     // 5
    std::cout << "1: " << CopyCounter<1>::numCopies << " copies\n";     // 8
    std::cout << "2: " << CopyCounter<2>::numCopies << " copies\n";     // 9
    std::cout << "3: " << CopyCounter<3>::numCopies << " copies\n";     // 8
    std::cout << "4: " << CopyCounter<4>::numCopies << " copies\n";     // 5
}

拷贝次数过多主要是由于pushBack()的递归,每次在构造Tuple::tail时都会发生拷贝。更有效率的方式是使用makeTuple()进行构造,类似下面的代码:

auto reversed = makeTuple(get<4>(copies), get<3>(copies),
                            get<2>(copies), get<1>(copies),
                            get<0>(copies));

这样拷贝次数就都降低为1次了,但是上面的写法很麻烦,所以应该将索引序列变成非类型的模板参数包,也就是索引列表。

25.3.5 通过索引列表实现反转

索引列表借助上一章的ValueList<>实现:

// tuples/indexlistreverse.hpp
template<typename... Elements, unsigned... Indices>
auto reverseImpl(Tuple<Elements...> const& t, Valuelist<unsigned, Indices...>)
    -> decltype(makeTuple(get<Indices>(t)...))
{
    return makeTuple(get<Indices>(t)...);
}

template<typename... Elements>
auto reverse(Tuple<Elements...> const& t)
    -> decltype(reverseImpl(t, Reverse<MakeIndexList<sizeof...(Elements)>>()))
{
    return reverseImpl(t, Reverse<MakeIndexList<sizeof...(Elements)>>());
}

reverseImpl()中第二个参数没有名字,因为在函数体中并不需要使用该参数,主要作用是通过该参数推导Indices。如果没有该参数,则必须要通过显示实例化模板的方式显式指定。

构造ValueList<>MakeIndexList()代码如下:

// tuples/makeindexlist.hpp
// recursive case
template<unsigned N, typename Result = Valuelist<unsigned>>
struct MakeIndexListT : MakeIndexListT<N-1, PushFront<Result, CTValue<unsigned, N-1>>>
{
};

// basis case
template<typename Result>
struct MakeIndexListT<0, Result>
{
    using Type = Result;
};

template<unsigned N>
using MakeIndexList = typename MakeIndexListT<N>::Type;

25.3.6 重排和选择

reverseImpl()只是通过一个递减的值列表选择出元组中的元素,其核心是提取算法:

// tuples/select.hpp
template<typename... Elements, unsigned... Indices>
auto select(Tuple<Elements...> const& t, Valuelist<unsigned, Indices...>)
{
    return makeTuple(get<Indices>(t)...);
}

下面是一个将I重复N次的索引序列,可以用来生成由元组中第I个元素重复N次的新元组:

// tuples/splat.hpp
template<unsigned I, unsigned N, typename IndexList = Valuelist<unsigned>>
class ReplicatedIndexListT;

template<unsigned I, unsigned N, unsigned... Indices>
class ReplicatedIndexListT<I, N, Valuelist<unsigned, Indices...>>
    : public ReplicatedIndexListT<I, N-1, Valuelist<unsigned, Indices..., I>> {
};

template<unsigned I, unsigned... Indices>
class ReplicatedIndexListT<I, 0, Valuelist<unsigned, Indices...>> {
    public:
        using Type = Valuelist<unsigned, Indices...>;
};

template<unsigned I, unsigned N>
using ReplicatedIndexList = typename ReplicatedIndexListT<I, N>::Type;

template<unsigned I, unsigned N, typename... Elements>
auto splat(Tuple<Elements...> const& t)
{
    return select(t, ReplicatedIndexList<I, N>());
}

注意ReplicatedIndexListT<>的主模板和特化模板之间的模板形参有区别。

如果要对元组中的元素按照大小进行排序进行排序,可以先对下标进行排序,然后再应用select()

// tuples/tuplesorttest.hpp
#include <complex>
template<typename T, typename U>
class SmallerThanT
{
    public:
        static constexpr bool value = sizeof(T) < sizeof(U);
};

void testTupleSort()
{
    auto t1 = makeTuple(17LL, std::complex<double>(42,77), 'c', 42, 7.7);
    std::cout << t1 << '\n';
    auto t2 = sort<SmallerThanT>(t1); // t2 is Tuple<int, long, std::string>
    std::cout << "sorted by size: " << t2 << '\n';
}
// tuples/tuplesort.hpp
// metafunction wrapper that compares the elements in a tuple:
template<typename List, template<typename T, typename U> class F>
class MetafunOfNthElementT {
    public:
        template<typename T, typename U> class Apply;
        template<unsigned N, unsigned M>
        class Apply<CTValue<unsigned, M>, CTValue<unsigned, N>>
            : public F<NthElement<List, M>, NthElement<List, N>> { };
};

// sort a tuple based on comparing the element types:
template<template<typename T, typename U> class Compare, typename... Elements>
auto sort(Tuple<Elements...> const& t)
{
    return select(t,
            InsertionSort<MakeIndexList<sizeof...(Elements)>, 
                            MetafunOfNthElementT<Tuple<Elements...>, Compare>::template Apply>
                            ());
}

InsertionSort<>中第一个参数是需要排序的值列表,第二个参数是比较值列表的元函数。因为不是简单的比较值列表中索引的大小,而是比较元组中具有该索引的类型的大小,因此需要将额外的参数Tuple<Elements...>和比较函数SmallerThanT<>进行组合。此外由于InsertionSort<>中第二个参数依然是模板(模板的模板参数),而MetafunOfNthElementT<Tuple<Elements...>, Compare>并不是模板,所以需要再次引用嵌入的类模板Apply<>,同时提示编译器Apply<>是模板。

25.4 将元组像参数包一样展开

为了将元组传递给接收可变参数的函数,可以利用和select()中同样的方式将参数包展开:

// tuples/apply.hpp
template<typename F, typename... Elements, unsigned... Indices>
auto applyImpl(F f, Tuple<Elements...> const& t, Valuelist<unsigned, Indices...>)
    ->decltype(f(get<Indices>(t)...))
{
    return f(get<Indices>(t)...);
}

template<typename F, typename... Elements, unsigned N = sizeof...(Elements)>
auto apply(F f, Tuple<Elements...> const& t)
    ->decltype(applyImpl(f, t, MakeIndexList<N>()))
{
    return applyImpl(f, t, MakeIndexList<N>());
}

25.5 优化

25.5.1 元组和空基类优化

为了利用空基类优化,就不能将Tuple::tail作为成员,而应该作为基类:

// tuples/tuplestorage1.hpp
// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...> : private Tuple<Tail...>
{
    private:
        Head head;
    public:
        Head& getHead() { return head; }
        Head const& getHead() const { return head; }
        Tuple<Tail...>& getTail() { return *this; }
        Tuple<Tail...> const& getTail() const { return *this; }
};

问题在于采用继承的方式会先初始化基类,虽然没什么问题,但是看起来有些别扭,解决办法是通过多重继承:

// tuples/tuplestorage2.hpp
template<typename... Types>
class Tuple;

template<typename T>
class TupleElt
{
        T value;
    public:
        TupleElt() = default;

        template<typename U>
        TupleElt(U&& other) : value(std::forward<U>(other) { }

        T& get() { return value; }
        T const& get() const { return value; }
};

// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...> : private TupleElt<Head>, private Tuple<Tail...>
{
    public:
        Head& getHead() {
            // potentially ambiguous
            return static_cast<TupleElt<Head> *>(this)->get();
        }
        Head const& getHead() const {
            // potentially ambiguous
            return static_cast<TupleElt<Head> const*>(this)->get();
        }
        Tuple<Tail...>& getTail() { return *this; }
        Tuple<Tail...> const& getTail() const { return *this; }
};

// basis case:
template<>
class Tuple<> {
// no storage required
};

这虽然解决了初始化顺序的问题,但是当多重继承的基类相同时就会出现歧义,为了解决这个问题,可以在TupleElt<>中加入一个高度信息:

// tuples/tupleelt1.hpp
template<unsigned Height, typename T>
class TupleElt {
        T value;
    public:
        TupleElt() = default;
        template<typename U>
        TupleElt(U&& other) : value(std::forward<U>(other)) { }
        T& get() { return value; }
        T const& get() const { return value; }
};
// tuples/tuplestorage3.hpp
template<typename... Types>
class Tuple;

// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
    : private TupleElt<sizeof...(Tail), Head>, private Tuple<Tail...>
{
        using HeadElt = TupleElt<sizeof...(Tail), Head>;
    public:
        Head& getHead() {
        return static_cast<HeadElt *>(this)->get();
        }
        Head const& getHead() const {
        return static_cast<HeadElt const*>(this)->get();
        }
        Tuple<Tail...>& getTail() { return *this; }
        Tuple<Tail...> const& getTail() const { return *this; }
};

// basis case:
template<>
class Tuple<> {
// no storage required
};

下面的程序可以用来测试优化后的存储空间:

// tuples/compressedtuple1.cpp
#include <algorithm>
#include "tupleelt1.hpp"
#include "tuplestorage3.hpp"
#include <iostream>

struct A {
    A() {
        std::cout << "A()" << '\n';
    }
};

struct B {
    B() {
        std::cout << "B()" << '\n';
    }
};

int main()
{
    Tuple<A, char, A, char, B> t1;
    std::cout << sizeof(t1) << " bytes" << '\n';}

t1的大小是5字节,说明继承链中的空元组的存储空间被优化了。由于上例中的AB也是空类型,所以可以改进TupleElt<>来将AB所占用的存储空间也优化掉:

// tuples/tupleelt2.hpp
#include <type_traits>
template<unsigned Height, typename T,
            bool = std::is_class<T>::value && !std::is_final<T>::value>
class TupleElt;

template<unsigned Height, typename T>
class TupleElt<Height, T, false>
{
        T value;
    public:
        TupleElt() = default;
        template<typename U>
        TupleElt(U&& other) : value(std::forward<U>(other)) { }

        T& get() { return value; }
        T const& get() const { return value; }
};

template<unsigned Height, typename T>
class TupleElt<Height, T, true> : private T
{
    public:
        TupleElt() = default;
        template<typename U>
        TupleElt(U&& other) : T(std::forward<U>(other)) { }

        T& get() { return *this; }
        T const& get() const { return *this; }
};

25.5.2 常量时间的get()

由于TupleElt<>的实现方法是通过继承,因此可以利用派生类到基类的转换实现常量时间的get()

// tuples/constantget.hpp
template<unsigned H, typename T>
T& getHeight(TupleElt<H,T>& te)
{
    return te.get();
}

template<typename... Types>
class Tuple;

template<unsigned I, typename... Elements>
auto get(Tuple<Elements...>& t)
    -> decltype(getHeight<sizeof...(Elements)-I-1>(t))
{
    return getHeight<sizeof...(Elements)-I-1>(t);
}

因为优化后的元组是私有继承的方式,所以需要将get()声明为友元。

25.6 下标运算

元组也可以定义下标运算符,内部借助get()实现:

template<typename T, T Index>
auto& operator[](CTValue<T, Index>) {
    return get<Index>(*this);
}

auto t = makeTuple(0, '1', 2.2f, std::string{"hello"});
auto a = t[CTValue<unsigned, 2>{}];
auto b = t[CTValue<unsigned, 3>{}];

由于get<Index>(*this)是编译期间确定的值,所以参数也必须是一个编译期间的值。可以发现CTValue<>的写法有些复杂,所以可以借助字面值运算符模板:

// tuples/literals.hpp
#include "ctvalue.hpp"
#include <cassert>
#include <cstddef>

// convert single char to corresponding int value at compile time:
constexpr int toInt(char c) {
    // hexadecimal letters:
    if (c >= 'A' && c <= 'F') {
        return static_cast<int>(c) - static_cast<int>('A') + 10;
    }
    if (c >= 'a' && c <= 'f') {
        return static_cast<int>(c) - static_cast<int>('a') + 10;
    }
    // other (disable '.' for floating-point literals):
    assert(c >= '0' && c <= '9');
    return static_cast<int>(c) - static_cast<int>('0');
}

// parse array of chars to corresponding int value at compile time:
template<std::size_t N>
constexpr int parseInt(char const (&arr)[N]) {
    int base = 10;                  // to handle base (default: decimal)
    int offset = 0;                 // to skip prefixes like 0x
    if (N > 2 && arr[0] == '0') {
        switch (arr[1]) {
            case 'x':               // prefix 0x or 0X, so hexadecimal
            case 'X':
                base = 16;
                offset = 2;
                break;
            case 'b':               // prefix 0b or 0B (since C++14), so binary
            case 'B':
                base = 2;
                offset = 2;
                break;
            default:                // prefix 0, so octal
                base = 8;
                offset = 1;
                break;
        }
    }
    // iterate over all digits and compute resulting value:
    int value = 0;
    int multiplier = 1;
    for (std::size_t i = 0; i < N - offset; ++i) {
        if (arr[N-1-i] != '\'') {   // ignore separating single quotes (e.g. in 1'000)
            value += toInt(arr[N-1-i]) * multiplier;
            multiplier *= base;
        }
    }
    return value;
}

// literal operator: parse integral literals with suffix _c as sequence of chars:
template<char... cs>
constexpr auto operator"" _c() {
    return CTValue<int, parseInt<sizeof...(cs)>({cs...})>{};
}
auto t = makeTuple(0, '1', 2.2f, std::string{"hello"});
auto c = t[2_c];
auto d = t[3_c];

25.7 后记

25.3.125.3.225.3.3中没有给出别名模板,配套代码中也缺少省略的内容,完整的反转算法如下:

#include <functional>
#include <type_traits>

template<typename... Types>
class Tuple;

// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
{
    private:
        Head head;
        Tuple<Tail...> tail;
    public:
        Tuple() {
        }
        Tuple(Head const& head, Tuple<Tail...> const& tail)
            : head(head), tail(tail) {
        }
        Tuple(Head const& head, Tail const&... tail)
            : head(head), tail(tail...) {
        }
        template<typename VHead, typename... VTail,
                    typename = std::enable_if_t<sizeof...(VTail) == sizeof...(Tail)>>
        Tuple(VHead&& vhead, VTail&&... vtail)
            : head(std::forward<VHead>(vhead)), tail(std::forward<VTail>(vtail)...) {
        }
        template<typename VHead, typename... VTail,
                    typename = std::enable_if_t<sizeof...(VTail) == sizeof...(Tail)>>
        Tuple(Tuple<VHead, VTail...> const& other)
            : head(other.getHead()), tail(other.getTail()) {
        }

        Head& getHead() { return head; }
        Head const& getHead() const { return head; }
        Tuple<Tail...>& getTail() { return tail; }
        Tuple<Tail...> const& getTail() const { return tail; }
};

// basis case:
template<>
class Tuple<> {
// no storage required
};

template<typename Tuple>
struct IsEmpty {
    static constexpr bool value = false;
};

template<>
struct IsEmpty<Tuple<>> {
    static constexpr bool value = true;
};

template<typename Tuple>
class FrontT;

template<typename Head, typename... Tail>
class FrontT<Tuple<Head, Tail...>> {
    public:
        using Type = Head;
};

template<typename Tuple>
using Front = typename FrontT<Tuple>::Type;

template<typename Tuple>
class PopFrontT;

template<typename Head, typename... Tail>
class PopFrontT<Tuple<Head, Tail...>> {
    public:
        using Type = Tuple<Tail...>;
};

template<typename Tuple>
using PopFront = typename PopFrontT<Tuple>::Type;

template<typename Tuple, typename Element>
class PushFrontT;

template<typename... Types, typename Element>
class PushFrontT<Tuple<Types...>, Element> {
    public:
        using Type = Tuple<Element, Types...>;
};

template<typename Tuple, typename Element>
using PushFront = typename PushFrontT<Tuple, Element>::Type;

template<typename Tuple, typename Element>
class PushBackT;

template<typename... Types, typename Element>
class PushBackT<Tuple<Types...>, Element> {
    public:
        using Type = Tuple<Types..., Element>;
};

template<typename Tuple, typename Element>
using PushBack = typename PushBackT<Tuple, Element>::Type;

template<typename Tuple, bool Empty = IsEmpty<Tuple>::value>
class ReverseT;

template<typename Tuple>
using Reverse = typename ReverseT<Tuple>::Type;

template<typename Tuple>
class ReverseT<Tuple, false>
{
    public:
        using Type = PushBack<Reverse<PopFront<Tuple>>, Front<Tuple>>;
};

template<typename Tuple>
class ReverseT<Tuple, true>
{
    public:
        using Type = Tuple;
};

template<typename Tuple>
class PopBackT {
    public:
        using Type = Reverse<PopFront<Reverse<Tuple>>>;
};

template<typename Tuple>
using PopBack = typename PopBackT<Tuple>::Type;

template<typename V>
Tuple<V> pushBack(Tuple<> const&, V const& value)
{
    return Tuple<V>(value);
}

// recursive case
template<typename Head, typename... Tail, typename V>
Tuple<Head, Tail..., V> pushBack(Tuple<Head, Tail...> const& tuple, V const& value)
{
    return Tuple<Head, Tail..., V>(tuple.getHead(), pushBack(tuple.getTail(), value));
}

Tuple<> reverse(Tuple<> const& t)
{
    return t;
}

// recursive case
template<typename Head, typename... Tail>
Reverse<Tuple<Head, Tail...>> reverse(Tuple<Head, Tail...> const& t)
{
    return pushBack(reverse(t.getTail()), t.getHead());
}

int main()
{
    Tuple<int, double, std::string> t(1, 2.5, std::string("hello"));
    reverse(t);
}

results matching ""

    No results matching ""