【C++ Templates（23）】Tuple

2018-07-02 本文已影响26人 downdemo

整本书中常使用同类容器来阐述模板的强大威力，这些同类构造扩展了数组概念，在许多程序中被广泛使用。C++也有包含异类对象的能力，即tuple
tuple还可以在可执行程序中表示typelist，如Typelist<int, double, std::string>描述了能在编译期操控的一个包含int、double和std::string的序列，而Tuple<int, double, std::string>描述了对应的运行期的序列，比如下面的程序就会创建这样一个tuple的实例

template<typename... Types>
class Tuple {
    ... // implementation discussed below
};
Tuple<int, double, std::string> t(17, 3.14, "Hello, World!");

使用typelist的模板元编程来生成用于存储数据的tuple是很常见的

基本Tuple设计

存储

tuple包含模板实参列表中的每个类型的存储，存储可以通过函数模板get访问，对tuple t使用get<Index>(t)即可
递归构造tuple存储的思路是，一个包含N>0个元素的tuple可以存储为一个单元素（首元素）和一个包含N-1个元素的tuple（尾），对于零元素tuple分离一个特殊情况。因此Tuple<int, double, std::string>可以存储为int和Tuple<double, std::string>，Tuple<double, std::string>又可以存储为double和Tuple<std::string>，Tuple<std::string>又可以存储为std::string和一个Tuple<>

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
};

get函数模板遍历递归结构来提取需求的元素

// 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);
}

注意函数模板get只是一个调用静态成员函数TupleGet的简单封装，这个技术对于缺少局部特化的函数模板十分有用，这里用来基于值N特化。在递归情况中（N>0），静态成员函数apply()提取当前tuple的尾部并递减N来保持寻找需求的元素，基本情况（N=0）返回当前tuple的头部，完成这个实现

构造

除了已定义的构造函数

Tuple() {
} Tuple(Head const& head, Tuple<Tail...> const& tail)
: head(head), tail(tail) {
}

还需要能从一系列独立的值和另一个tuple构造。从一系列独立的值拷贝构造传递首个值来初始化head元素（通过基类），然后传递剩余值给表示尾部的基类

Tuple(Head const& head, Tail const&... tail)
: head(head), tail(tail...) {
}

然而这不是最通用的接口，用户可能希望移动构造来初始化一些元素或有一个来自不同类型值构造的元素，因此应该使用完美转发来初始化tuple

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

接着实现用另一个tuple构造tuple

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

然而，这个构造的引入不能满足tuple的转换：给出上述的tuple t，尝试创建另一个类型兼容的tuple将失败

// ERROR: no conversion from Tuple<int, double, string> to long
Tuple<long int, long double, std::string> t2(t);

这里的问题在于，从一系列值初始化的构造模板比接受一个tuple的构造模板更优，为了解决这个问题，必须使用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()) { }

makeTuple()函数模板使用推断来决定返回的Tuple元素类型，使得从一系列给定值创建一个tuple更简单

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

再次使用完美转发结合std::decay<>来转换字符串字面值和其他原始数组为指针并移除const和引用，比如

makeTuple(17, 3.14, "Hello, World!")

初始化一个

Tuple<int, double, char const*>

基本Tuple操作

比较

tuple是包含其他值的结构化类型，为了比较两个tuple，必须比较他们的元素

// 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();
}

其他的比较运算符实现同理

输出

下面的operator<<打印元素类型能被打印的tuple

// 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;
}

现在创建和显示tuple很简单

std::cout << makeTuple(1, 2.5, std::string("hello")) << '\n';
// prints
(1, 2.5, hello)

Tuple算法

tuple算法有趣的一点是，同时要求编译期和运行期计算

Tuple作为Typelist

如果忽略Tuple模板的运行期组件，可以发现它有和Typelist模板完全相同的结构：接受任意数量的模板类型参数。事实上，通过一些局部特化，可以把Tuple转换成一个功能完整的typelist

// 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>;
};

现在所有的typelist的算法都能用于Tuple和Typelist了

Tuple<int, double, std::string> t1(17, 3.14, "Hello, World!");
using T2 = PopFront<PushBack<decltype(t1), bool>>;
T2 t2(get<1>(t1), get<2>(t1), true);
std::cout << t2; // 打印(3.14, Hello, World!, 1)

从Tuple添加和移除

添加一个元素到tuple的开头或结尾十分重要，对于typelist，在一个tuple的开头插入比在尾部插入更容易，所以先从pushFront开始

// 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);
}

这里编译期PushFront计算需要构造的类型来生成对应的运行期值
添加一个新元素到现有tuple的尾部复杂得多，因为它要求递归遍历tuple，建立改进的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));
}

popFront()很容易实现

// tuples/popfront.hpp

template<typename... Types>
PopFront<Tuple<Types...>>
popFront(Tuple<Types...> const& tuple)
{
    return tuple.getTail();
}

使用这些算法

Tuple<int, double, std::string> t1(17, 3.14, "Hello, World!");
auto t2 = popFront(pushBack(t1, true));
std::cout << std::boolalpha << t2 << '\n'; // 打印(3.14, Hello, World!, true)

翻转Tuple

一个tuple的元素可以用另一个结构遵循typelist翻转的递归tuple算法翻转

// 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());
}

和typelist一样，现在可以简单地通过对临时的翻转列表调用popFront()提供popBack()

// tuples/popback.hpp

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

索引表

tuple翻转的递归构建是正确的，但在运行期是低效的，为了明白这个问题，引入一个简单的类来计算拷贝次数

// tuples/copycounter.hpp
template<int N>
struct CopyCounter
{
    inline static unsigned numCopies = 0;
    CopyCounter() {
    }
    CopyCounter(CopyCounter const&) {
        ++numCopies;
    }
};

然后创建并翻转一个CopyCounter的tuple实例

// 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";
    std::cout << "1: " << CopyCounter<1>::numCopies << " copies\n";
    std::cout << "2: " << CopyCounter<2>::numCopies << " copies\n";
    std::cout << "3: " << CopyCounter<3>::numCopies << " copies\n";
    std::cout << "4: " << CopyCounter<4>::numCopies << " copies\n";
}

这个程序将输出

0: 5 copies
1: 8 copies
2: 9 copies
3: 8 copies
4: 5 copies

理想的翻转tuple的实现是，每个元素只拷贝一次，直接从原有的tuple拷贝到结果tuple的正确位置，通过引用可以实现这点，但这样做使得实现十分复杂
为了消除无关的拷贝，考虑对已知长度的tuple一次性操作，可以简单使用makeTuple()和get()

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

这个程序将生成期望的输出，每个tuple元素只拷贝一次

0: 1 copies
1: 1 copies
2: 1 copies
3: 1 copies
4: 1 copies

索引表通过捕获tuple索引到一个参数包（即这里的43210）推广这个概念，这允许索引计算的分离，它可以是一个任意复杂的模板元程序。标准类型std::integer_sequence（C++14）常用于表示索引表

使用索引表翻转

为了使用索引表执行tuple反转，首先需要一个索引表的表示。一个索引表是一个包含用作一个typelist或一个混杂数据结构的索引值的typelist，这里将使用以前提到过的Valuelist，对应翻转tuple的索引表为

Valuelist<unsigned, 4, 3, 2, 1, 0>

生成这个索引表的一个方法就是使用一个简单的模板元程序MakeIndexList，归纳一个从0到N-1计数的索引表，N是tuple的长度

// 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;

然后可以使用typelist Reverse组成生成索引表的操作

using MyIndexList = Reverse<MakeIndexList<5>>;
// equivalent to Valuelist<unsigned, 4, 3, 2, 1, 0>

为了执行这个翻转，索引表中的索引需要被捕获到一个非类型参数包中，这是通过将索引集tuple的reverse()算法的实现分成两部分来处理的

// tuples/indexlistreverse.hpp

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

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

C++11中，返回类型必须声明为

-> decltype(makeTuple(get<Indices>(t)...))
// 和
-> decltype(reverseImpl(t, Reverse<MakeIndexList<sizeof...(Elements)>>()))

reverseImpl()函数模板从Valuelist参数捕获索引到参数包Indices中，然后返回调用由get()构建实参的makeTuple()的结果
reverse()算法本身仅构建索引集，并提供给reverseImpl算法，索引作为一个模板元程序被操作，因此生成无运行期的代码。这里唯一的运行期代码是在reverseImpl中，它使用makeTuple()一步到位构造结果tuple，因此tuple元素的拷贝仅有一次

洗牌算法和选择算法（Shuffle and Select）

reverseImpl()函数模板实际上没有针对reverse()操作的代码，它只是简单地从已有tuple选择索引构建一个新的tuple，reverse()提供了一个翻转的索引集合，不过许多算法能构建在核心的tuple select()算法上

// tuples/select.hpp

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

一个基于select()构建的简单算法是一个tuple splat操作，它使用tuple中的一个元素，并重复拷贝一定次数以创建另一个tuple

Tuple<int, double, std::string> t1(42, 7.7, "hello"};
auto a = splat<1, 4>(t);
std::cout << a << '\n'; // (7.7, 7.7, 7.7, 7.7)

给出一个元程序，生成由值I拷贝N次组成的重复索引集，splate()是select()的一个直接应用

// 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>());
}

复杂的tuple算法也能根据一个基于遵循select()应用的索引表的模板元程序实现，比如可以使用插入排序基于元素类型的大小排序一个tuple，给出这样一个sort()函数，它接受一个比较tuple元素类型的模板元函数

// 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';
}

输出可能为

(17, (42,77), c, 42, 7.7)
sorted by size: (c, 42, 7.7, 17, (42,77))

实际的sort()实现涉及带有一个tuple select()的InsertionSort的使用

// 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的使用：实际要排序的typelist是一个用MakeIndexList<>构造的typelist的索引表，因此插入排序的结果是一系列随后将提供给select()的tuple的索引。然而因为InsertionSort操作在索引上，它希望比较操作来比较两个索引，考虑std::vector的索引排序更容易理解这个原则

// tuples/indexsort.cpp

#include <vector>
#include <algorithm>
#include <string>
int main()
{
    std::vector<std::string> strings = {"banana", "apple", "cherry"};
    std::vector<unsigned> indices = { 0, 1, 2 };
    std::sort(indices.begin(), indices.end(),
        [&strings](unsigned i, unsigned j) {
            return strings[i] < strings[j];
        });
}

扩展Tuple

在某些时候，可能需要拆开tuple，比如将其元素作为分离的实参传递给函数。作为一个简单的例子，可能想将一个tuple的元素传递给可变参数的print()

Tuple<std::string, char const*, int, char> t("Pi", "is roughly", 3, '\n');
print(t...); //ERROR: cannot expand a tuple; it isn't a parameter pack

这里拆开tuple将失败，因为它不是一个参数包。使用一个索引表可以实现相同目的，下面的函数模板apply()接受一个函数和一个tuple，然后使用拆包的tuple元素调用函数

// 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>());
}

applyImpl()函数模板使用一个给出的索引表扩展tuple元素为实参列表，提供给函数对象实参f，面向用户的apply()只负责构造初始索引表，他们一起以允许扩展一个tuple到print()的实参

Tuple<std::string, char const*, int, char> t("Pi", "is roughly", 3, '\n');
apply(print, t); // OK: prints Pi is roughly 3

C++17提供了一个相似的函数，可用于任何tuple-like类型

优化Tuple

Tuple与EBCO

Tuple存储的构建使用了比严格需要的更多的存储，一个问题是tail成员最终将是一个空的tuple。为了改进Tuple的存储效率，可以使用EBCO，派生自tail tuple而不是让它作为一个成员

// 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; }
};

不幸的是，它在翻转构造函数中初始化的tuple元素顺序时有副作用，之前head成员先于tail成员初始化，而在这里tail在一个基类中，所以会先于head成员初始化
这个问题的解决方法是，把head成员沉入它自己的基类，将起置于基类列表的tail之前，一个直接的实现是引入一个TupleElt模板，用来包裹每个元素类型以使Tuple能继承自它

// 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
};

但这个方法引入了一个新问题：不再能从一个有两个相同类型元素的tuple提取元素，比如Tuple<int, int>，因为从一个tuple到那个类型的TupleElt（比如TupleElt<int>）的派生类到基类的转换将会是二义性的
为了打破二义性，需要确保每个TupleElt基类在给出的Tuple中是独一无二的，一个方法是给值的高度（即tail tuple的长度）编码，tuple中最后的元素被存储为高度0，倒数第二个则为高度1，以此类推

// 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; }
};

使用这个解决方案，当保持初始化顺序时，可以生成一个应用EBCO的Tuple，并支持多个同类型元素

// 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';
}

打印结果为

A()
A()
B()
5 bytes

EBCO消除了一个字节（对于空的Tuple<>），然而注意A和B都是空类，这提示再多一次在Tuple中应用EBCO的机会。TupleElt可以稍微扩展以继承元素类型，而不需要改变Tuple

// 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; }
};

当TupleElt用一个non-final类提供时，私有继承来允许应用EBCO存储值，通过这个变化，之前的程序现在将打印

A()
A()
B()
2 bytes

常数时间的get()

get()操作在使用tuple时十分常用，但它是需要线性数量模板实例化的递归实现，这会影响编译时间。幸运的是，EBCO优化允许一个更高效的get实现
关键在于，当匹配一个基类类型参数给一个派生类类型实参时，模板实参推断为基类推断模板实参。因此，如果能计算希望提取的元素高度H，可以依赖于从Tuple特化到TupleElt<H, T>（T是被推断的）的转换来提取元素，而不需要手动遍历所有索引

// 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<I>(t)接受想要的元素的索引I，tuple的实际存储依据高度H（从tuple尾计数），可以从I计算H。调用getHeight()的模板实参推断执行实际查找：高度H在调用中显式提供，是固定的，所以只有一个TupleElt基类将匹配，类型T将被推断。注意getHeight()必须声明为Tuple的友元以允许私有基类的转换，比如

// inside the recursive case for class template Tuple:
template<unsigned I, typename... Elements>
friend auto get(Tuple<Elements...>& t)
    -> decltype(getHeight<sizeof...(Elements)-I-1>(t));

注意这个实现只需要常数数量的模板实例化，因为匹配索引到编译器的模板实参推断引擎的负担已经被卸掉了

Tuple下标（Subscript）

原则上可以定义一个operator[]访问元素，然而tuple的元素可以有不同类型，所以operator[]必须是模板，这就要求每个索引有一个不同类型，因此索引类型能用于确定元素类型
之前引入的类模板CTValue允许编码一个类型中的数值索引，可以使用这点定义一个下标操作作为Tuple的成员

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>{}];

为了更方便地使用常数索引，可以使用constexpr直接从后缀_c的原始字面值计算数值编译期字面值，以实现字面值操作符

// 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...})>{};
}

对于数值字面值，可以使用字面值操作符推断每个字符作为模板参数。传递字符给constexpr辅助函数parseInt()，在编译期计算字符序列值，并作为CTValue生成，比如
- 42_c生成CTValue<int,42>
- 0x815_c生成CTValue<int,2069>
- 0b1111'1111_c生成CTValue<int,255>
注意解析不处理浮点字面值，对于他们，断言会引发一个编译期错误，因为它是一个运行期特性，不能用于编译期上下文
可以使用tuple如下

auto t = makeTuple(0, '1', 2.2f, std::string{"hello"});
auto c = t[2_c];
auto d = t[3_c];

【C++ Templates（23）】Tuple

基本Tuple设计

存储

构造

基本Tuple操作

比较

输出

Tuple算法

Tuple作为Typelist

从Tuple添加和移除

翻转Tuple

索引表

使用索引表翻转

洗牌算法和选择算法（Shuffle and Select）

扩展Tuple

优化Tuple

Tuple与EBCO

常数时间的get()

Tuple下标（Subscript）

猜你喜欢

热点阅读