boost :: hana :: tuple에 대한 요소 액세스의 시간 복잡도는 어떻게됩니까?

Question

내가 알 수있는 한 순전히 기능적인 시퀀스 유형의 경우 시퀀스 순진 구현은 요소 액세스에 O (n) 시간 복잡성을 초래하고 O (log n) 복잡성을 누리는 더 나은 구현 (Chris Okasaki) 길이 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_; }