boost :: hana :: tuple元素訪問的時間複雜度是多少？

Question

據我所知，對於純功能序列類型，序列的天真實現會導致元素訪問的O（n）時間複雜度，並且更好的實現（如Chris Okasaki所述）享有O（log n）複雜度，對於長度爲n的序列。

使用operator[]訪問boost::hana::tuple中的任意元素的時間複雜度是多少？如果它不是上述兩者，它是如何實現的？

Answer 1

運行時複雜度爲O（1）。基本上，它和訪問一個結構成員一樣快（因爲它基本上就是這樣）。該實現類似於std::tuple。至於編譯時的複雜度，它也是O（1），但你在開始時支付O（n）編譯時複雜度來創建元組。另外，在這裏，我用模板實例的數量來衡量編譯時複雜度，但這是測量最終編譯時間的非常幼稚的方法。

編輯：以下是元組訪問工作的要點：如果在文檔提振，因爲說::花是概念上類似於`STD

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