c++ - 在 O(1) 中访问模板参数包的背面

Question

在a recent mail在 boost 开发人员邮件列表上，Eric Niebler 提到可以在 O(1) 实例化中获取模板参数包的最后一个元素。

如何做到这一点？

Answer 1

可以查看https://github.com/ericniebler/proto-0x/blob/master/boost/proto/utility.hpp ，正如帖子中提到的，关于如何 get_nth元函数被实现。经过大量简化后的本质:

#include <type_traits>
#include <cstdlib>

// A template to store a variadic list.
template <typename...>
struct List;

// Concatenate two variadic lists together. Should be O(1).
template <typename Left, typename Right>
struct Concat;

template <typename... Lefts, typename... Rights>
struct Concat<List<Lefts...>, List<Rights...>> {
    typedef List<Lefts..., Rights...> Type;
};

// Construct List<void, void, void, ...> with 'n' elements.
// Uses "bisection" method, which should instantiate O(log n) templates
template <size_t n>
struct RepeatVoid : Concat<typename RepeatVoid<n/2>::Type,
                           typename RepeatVoid<n - n/2>::Type> {};

template <>
struct RepeatVoid<0> {
    typedef List<> Type;
};

template <>
struct RepeatVoid<1> {
    typedef List<void> Type;
};

template <typename>
struct GetNthAux;

// This would create a function of the form:
//
//   T eval(cv void*, cv void*, cv void*, ..., cv void*, T*, ...)
//
// where there are 'n' const volatile void*. These will be used to absorb
// the first 'n' template arguments. The actual one can be extracted from
// the return type.
//
template <typename... Ts>
struct GetNthAux<List<Ts...>> {
    template<typename T>
    static constexpr T eval(const volatile Ts*..., T*, ...);
};

// Run the whole thing.
template<size_t n, typename... Ts>
using GetNth = decltype(
    GetNthAux<typename RepeatVoid<n>::Type>::eval((Ts*)nullptr...)
);

// Example:
int main() {
    static_assert(std::is_same<GetNth<0, int, float, char>, int>::value, "");
    static_assert(std::is_same<GetNth<1, int, float, char>, float>::value, "");
    static_assert(std::is_same<GetNth<2, int, float, char>, char>::value, "");
}

实际上它是 O(log N)，而不是 O(1)，因为在 RepeatVoid 中花费的时间.

但是这种方法确实比线性方法表现得更好，比如 tuple_element<> 的典型实现.我尝试比较 GetNth 的性能与 tuple_element<>在获取列表的第 899 项时，后者快了一个数量级:

                         tuple_element<>   GetNth<>
g++ 4.7 with libstdc++   0.7s              0.1s
clang++ 3.1 with libc++  0.9s              0.1s