用于boost::hana::tuple的元素访问的时间复杂性是多少？

Question

据我所知，对于纯函数序列类型，序列的朴素实现将导致元素访问的O( n )时间复杂度，更好的实现(如克里斯·冈崎所描述)具有O(log )复杂度，对于长度为n的序列。

使用boost::hana::tuple访问operator[]中的任意元素的时间复杂度是多少？如果两者都没有，它是如何实现的？

Answer 1

运行时复杂度为O(1)。基本上，它就像访问一个struct成员一样快(因为它本质上就是这样的)。实现类似于std::tuple。

至于编译时的复杂性，也是O(1)，但是在开始创建元组时需要支付O(n)编译时复杂度。此外，在这里，我用模板实例化的数量来度量编译时的复杂性，但这是测量最终编译时间的一种非常幼稚的方法。

编辑：，这是元组访问的基本原理：

// Holds an element of the tuple
template <std::size_t n, typename Xn>
struct elt { Xn data_; };

// Inherits multiply from the holder structs
template <typename Indices, typename ...Xn>
struct tuple_impl;

template <std::size_t ...n, typename ...Xn>
struct tuple_impl<std::index_sequence<n...>, Xn...>
    : elt<n, Xn>...
{ /* ... */ };

template <typename ...Xn>
struct basic_tuple
    : tuple_impl<std::make_index_sequence<sizeof...(Xn)>, Xn...>
{ /* ... */ };

// When you call get<n>(tuple), your tuple is basically casted to a reference
// to one of its bases that holds a single element at the right index, and then
// that element is accessed.
template <std::size_t n, typename Xn>
Xn const& get(elt<n, Xn> const& xn)
{ return xn.data_; }