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）のコンパイル時の複雑さを支払う必要があります。また、ここでは、テンプレートのインスタンス化の数に関してコンパイル時の複雑さを測定しますが、これは最終的なコンパイル時間を測定する非常に素朴な方法です。

編集：ここでどのようにタプルアクセス作品の要旨です：

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