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

Question

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

boost::hana::tuple访问with中的任意元素的时间复杂度是operator[]多少？如果以上都不是，那它是如何实现的呢？

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