Какова временная сложность доступа к элементу для boost :: hana :: tuple?
Насколько я могу сказать, для чисто функциональных типов последовательностей наивная реализация последовательности привела бы к O (n) временной сложности для доступа к элементу и лучшей реализации (как описано Крис Окасаки) имеет O (log n) сложность для последовательности длины n.
Какова временная сложность доступа к произвольному элементу в boost::hana::tuple с operator[]? Если это не так, как это реализовано?
Решение
Сложность выполнения — 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_; }
Другие решения
Других решений пока нет …
detector