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

Question

据我所知，对于纯函数序列类型，序列的简单实现会导致元素访问的时间复杂度为 O(n)，更好的实现（如 Chris Okasaki 所述） O(log n) 复杂度，对于长度为 n 的序列。

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

Answer 1

运行时复杂度为 O(1)。基本上，它与访问结构成员一样快（因为它本质上就是这样）。实现类似于 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_; }