JohnDuck JohnDuck - 2 months ago 25
C++ Question

What is the time complexity of element access for boost::hana::tuple?

As far as I can tell, for purely functional sequence types the naive implementation of a sequence would result in O(n) time complexity for element access and a better implementation (as described by Chris Okasaki) enjoys O(log n) complexity, for a sequence of length n.

What is the time complexity of accessing an arbitrary element in a

boost::hana::tuple
with
operator[]
? If it's neither of the above, how is it implemented?

Answer

The runtime complexity is O(1). Basically, it's as fast as accessing a struct member (because that's essentially what it is). The implementation is similar to a std::tuple.

As for the compile-time complexity, it's also O(1), but you do pay O(n) compile-time complexity for creating the tuple at the beginning. Also, here, I measure compile-time complexity in terms of the number of template instantiations, but that's a very naive way of measuring the final compilation time.

Edit: Here's the gist of how tuple access works:

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