Какова временная сложность доступа к элементу для boost :: hana :: tuple?

Question

Насколько я могу судить, для чисто функциональных типов последовательностей наивная реализация последовательности приведет к сложности времени O (n) для доступа к элементу, а лучшая реализация (как описано в Chris Okasaki) обладает сложностью O (log n) для последовательности длины n.

Какова временная сложность доступа к произвольному элементу в boost::hana::tuple с помощью operator[]? Если это не так, как это реализовано?

Answer 1

Сложность выполнения - O (1). В принципе, это так же быстро, как доступ к члену структуры (потому что это по существу то, что есть). Реализация аналогична реализации std::tuple.

Что касается сложности времени компиляции, это также O (1), но вы платите сложность времени выполнения O (n) для создания кортежа в начале. Кроме того, здесь я измеряю сложность времени компиляции с точки зрения количества экземпляров шаблонов, но это очень наивный способ измерения конечного времени компиляции.

Edit: Вот суть того, как работает доступа кортежей:

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